算法系列15天速成第八天线性表【下】

2024-12-08 20:15:21

一：线性表的简单回顾

上一篇跟大家聊过“线性表"顺序存储，通过实验，大家也知道，如果我每次向顺序表的头部插入元素，都会引起痉挛，效率比较低下，第二点我们用顺序存储时，容易受到长度的限制，反之就会造成空间资源的浪费。

二：链表

对于顺序表存在的若干问题，链表都给出了相应的解决方案。

1. 概念：其实链表的“每个节点”都包含一个”数据域“和”指针域“。

”数据域“中包含当前的数据。

”指针域“中包含下一个节点的指针。

”头指针”也就是head，指向头结点数据。

“末节点“作为单向链表，因为是最后一个节点，通常设置指针域为null。

代码段如下：

代码如下:

#region 链表节点的数据结构
/// <summary>
/// 链表节点的数据结构
/// </summary>
    public class Node<T>
    {
7/// <summary>
/// 节点的数据域
/// </summary>
        public T data;

/// <summary>
/// 节点的指针域
/// </summary>
        public Node<T> next;
    }
    #endregion

2.常用操作：

链表的常用操作一般有：

①添加节点到链接尾，②添加节点到链表头，③插入节点。

④删除节点，⑤按关键字查找节点，⑥取链表长度。

<1> 添加节点到链接尾：

前面已经说过，链表是采用指针来指向下一个元素，所以说要想找到链表最后一个节点，必须从头指针开始一步一步向后找,少不了一个for循环，所以时间复杂度为O(N)。

代码段如下：

代码如下:

#region 将节点添加到链表的末尾
        /// <summary>
/// 将节点添加到链表的末尾
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="head"></param>
/// <param name="data"></param>
/// <returns></returns>
        public Node<T> ChainListAddEnd<T>(Node<T> head, T data)
        {
            Node<T> node = new Node<T>();

node.data = data;
node.next = null;

///说明是一个空链表
            if (head == null)
            {
                head = node;
                return head;
            }

//获取当前链表的最后一个节点
ChainListGetLast(head).next = node;

return head;
        }
#endregion
#region 得到当前链表的最后一个节点
        /// <summary>
/// 得到当前链表的最后一个节点
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="head"></param>
/// <returns></returns>
        public Node<T> ChainListGetLast<T>(Node<T> head)
        {
            if (head.next == null)
                return head;
            return ChainListGetLast(head.next);
        }
        #endregion

<2> 添加节点到链表头:

大家现在都知道，链表是采用指针指向的，要想将元素插入链表头，其实还是很简单的，

思想就是：① 将head的next指针给新增节点的next。②将整个新增节点给head的next。

所以可以看出，此种添加的时间复杂度为O(1)。

效果图：

代码段如下：

代码如下:

1#region 将节点添加到链表的开头
/// <summary>
/// 将节点添加到链表的开头
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="chainList"></param>
/// <param name="data"></param>
/// <returns></returns>
        public Node<T> ChainListAddFirst<T>(Node<T> head, T data)
        {
            Node<T> node = new Node<T>();

node.data = data;
node.next = head;

head = node;

return head;

}
#endregion

<3> 插入节点:

其实这个思想跟插入到”首节点“是一个模式，不过多了一步就是要找到当前节点的操作。然后找到

这个节点的花费是O(N）。上图上代码，大家一看就明白。

效果图：

代码段：

代码如下:

#region 将节点插入到指定位置
/// <summary>
/// 将节点插入到指定位置
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="head"></param>
/// <param name="currentNode"></param>
/// <param name="data"></param>
/// <returns></returns>
        public Node<T> ChainListInsert<T, W>(Node<T> head, string key, Func<T, W> where, T data) where W : IComparable
        {
            if (head == null)
                return null;

if (where(head.data).CompareTo(key) == 0)
{
Node<T> node = new Node<T>();

node.data = data;

node.next = head.next;

head.next = node;
}

ChainListInsert(head.next, key, where, data);

return head;
}
#endregion

<4> 删除节点:

这个也比较简单，不解释，图跟代码更具有说服力，口头表达反而让人一头雾水。
当然时间复杂度就为O(N)，N是来自于查找到要删除的节点。

效果图：

代码段：

代码如下:

#region 将指定关键字的节点删除
        /// <summary>
/// 将指定关键字的节点删除
/// </summary>
/// <typeparam name="T"></typeparam>
/// <typeparam name="W"></typeparam>
/// <param name="head"></param>
/// <param name="key"></param>
/// <param name="where"></param>
/// <param name="data"></param>
/// <returns></returns>
        public Node<T> ChainListDelete<T, W>(Node<T> head, string key, Func<T, W> where) where W : IComparable
        {
            if (head == null)
                return null;

//这是针对只有一个节点的解决方案
            if (where(head.data).CompareTo(key) == 0)
            {
                if (head.next != null)
                    head = head.next;
                else
                    return head = null;
            }
            else
            {
                //判断一下此节点是否是要删除的节点的前一节点
                while (head.next != null && where(head.next.data).CompareTo(key) == 0)
                {
                    //将删除节点的next域指向前一节点
                    head.next = head.next.next;
                }
            }

ChainListDelete(head.next, key, where);

return head;
}
#endregion

<5> 按关键字查找节点：

这个思想已经包含到“插入节点”和“删除节点”的具体运用中的，其时间复杂度为O(N)。

代码段：

代码如下:

#region 通过关键字查找指定的节点
        /// <summary>
/// 通过关键字查找指定的节点
/// </summary>
/// <typeparam name="T"></typeparam>
/// <typeparam name="W"></typeparam>
/// <param name="head"></param>
/// <param name="key"></param>
/// <param name="where"></param>
/// <returns></returns>
        public Node<T> ChainListFindByKey<T, W>(Node<T> head, string key, Func<T, W> where) where W : IComparable
        {
            if (head == null)
                return null;

if (where(head.data).CompareTo(key) == 0)
return head;

return ChainListFindByKey<T, W>(head.next, key, where);
}
#endregion

<6> 取链表长度:

在单链表的操作中，取链表长度还是比较纠结的，因为他不像顺序表那样是在内存中连续存储的，

因此我们就纠结的遍历一下链表的总长度。时间复杂度为O(N)。

代码段：

代码如下:

#region 获取链表的长度
        /// <summary>
///// 获取链表的长度
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="head"></param>
/// <returns></returns>
        public int ChanListLength<T>(Node<T> head)
        {
            int count = 0;

while (head != null)
            {
                ++count;
                head = head.next;
            }

return count;
}
#endregion

好了，最后上一下总的运行代码：

代码如下:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ChainList
{
    class Program
    {
        static void Main(string[] args)
        {
            ChainList chainList = new ChainList();

Node<Student> node = null;

Console.WriteLine("将三条数据添加到链表的尾部:\n");

//将数据添加到链表的尾部
            node = chainList.ChainListAddEnd(node, new Student() { ID = 2, Name = "hxc520", Age = 23 });
            node = chainList.ChainListAddEnd(node, new Student() { ID = 3, Name = "博客园", Age = 33 });
            node = chainList.ChainListAddEnd(node, new Student() { ID = 5, Name = "一线码农", Age = 23 });

Dispaly(node);

Console.WriteLine("将ID=1的数据插入到链表开头:\n");

//将ID=1的数据插入到链表开头
node = chainList.ChainListAddFirst(node, new Student() { ID = 1, Name = "i can fly", Age = 23 });

Dispaly(node);

Console.WriteLine("查找Name=“一线码农”的节点\n");

//查找Name=“一线码农”的节点
var result = chainList.ChainListFindByKey(node, "一线码农", i => i.Name);

DisplaySingle(node);

Console.WriteLine("将”ID=4“的实体插入到“博客园”这个节点的之后\n");

//将”ID=4“的实体插入到"博客园"这个节点的之后
node = chainList.ChainListInsert(node, "博客园", i => i.Name, new Student() { ID = 4, Name = "51cto", Age = 30 });

Dispaly(node);

Console.WriteLine("删除Name=‘51cto‘的节点数据\n");

//删除Name=‘51cto‘的节点数据
node = chainList.ChainListDelete(node, "51cto", i => i.Name);

Dispaly(node);

Console.WriteLine("获取链表的个数:" + chainList.ChanListLength(node));
}

//输出数据
        public static void Dispaly(Node<Student> head)
        {
            Console.WriteLine("******************* 链表数据如下 *******************");
            var tempNode = head;

while (tempNode != null)
            {
                Console.WriteLine("ID:" + tempNode.data.ID + ", Name:" + tempNode.data.Name + ",Age:" + tempNode.data.Age);
                tempNode = tempNode.next;
            }

Console.WriteLine("******************* 链表数据展示完毕 *******************\n");
}

//展示当前节点数据
        public static void DisplaySingle(Node<Student> head)
        {
            if (head != null)
                Console.WriteLine("ID:" + head.data.ID + ", Name:" + head.data.Name + ",Age:" + head.data.Age);
            else
                Console.WriteLine("未查找到数据！");
        }
    }

#region 学生数据实体
    /// <summary>
/// 学生数据实体
/// </summary>
    public class Student
    {
        public int ID { get; set; }

public string Name { get; set; }

public int Age { get; set; }
}
#endregion

#region 链表节点的数据结构
    /// <summary>
/// 链表节点的数据结构
/// </summary>
    public class Node<T>
    {
        /// <summary>
/// 节点的数据域
/// </summary>
        public T data;

/// <summary>
/// 节点的指针域
/// </summary>
        public Node<T> next;
    }
    #endregion

#region 链表的相关操作
    /// <summary>
/// 链表的相关操作
/// </summary>
    public class ChainList
    {
        #region 将节点添加到链表的末尾
        /// <summary>
/// 将节点添加到链表的末尾
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="head"></param>
/// <param name="data"></param>
/// <returns></returns>
        public Node<T> ChainListAddEnd<T>(Node<T> head, T data)
        {
            Node<T> node = new Node<T>();

node.data = data;
node.next = null;

///说明是一个空链表
            if (head == null)
            {
                head = node;
                return head;
            }

//获取当前链表的最后一个节点
ChainListGetLast(head).next = node;

return head;
}
#endregion

#region 将节点添加到链表的开头
        /// <summary>
/// 将节点添加到链表的开头
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="chainList"></param>
/// <param name="data"></param>
/// <returns></returns>
        public Node<T> ChainListAddFirst<T>(Node<T> head, T data)
        {
            Node<T> node = new Node<T>();

node.data = data;
node.next = head;

head = node;

return head;

}
#endregion

#region 将节点插入到指定位置
        /// <summary>
/// 将节点插入到指定位置
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="head"></param>
/// <param name="currentNode"></param>
/// <param name="data"></param>
/// <returns></returns>
        public Node<T> ChainListInsert<T, W>(Node<T> head, string key, Func<T, W> where, T data) where W : IComparable
        {
            if (head == null)
                return null;

if (where(head.data).CompareTo(key) == 0)
{
Node<T> node = new Node<T>();

node.data = data;

node.next = head.next;

head.next = node;
}

ChainListInsert(head.next, key, where, data);

return head;
}
#endregion

//这是针对只有一个节点的解决方案
            if (where(head.data).CompareTo(key) == 0)
            {
                if (head.next != null)
                    head = head.next;
                else
                    return head = null;
            }
            else
            {
                //判断一下此节点是否是要删除的节点的前一节点
                if (head.next != null && where(head.next.data).CompareTo(key) == 0)
                {
                    //将删除节点的next域指向前一节点
                    head.next = head.next.next;
                }
            }

ChainListDelete(head.next, key, where);

return head;
}
#endregion

if (where(head.data).CompareTo(key) == 0)
return head;

return ChainListFindByKey<T, W>(head.next, key, where);
}
#endregion

while (head != null)
            {
                ++count;
                head = head.next;
            }

return count;
}
#endregion

#region 得到当前链表的最后一个节点
        /// <summary>
/// 得到当前链表的最后一个节点
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="head"></param>
/// <returns></returns>
        public Node<T> ChainListGetLast<T>(Node<T> head)
        {
            if (head.next == null)
                return head;
            return ChainListGetLast(head.next);
        }
        #endregion

}
#endregion
}

运行结果：

当然，单链表操作中有很多是O(N)的操作，这给我们带来了尴尬的局面，所以就有了很多的优化方案，比如：双向链表，循环链表。静态链表等等，这些希望大家在懂得单链表的情况下待深一步的研究。

算法系列15天速成第七天线性表【上】

哈哈,我们的数据也一样,存在这三种基本关系,用术语来说就是: <1> 线性关系.<2> 树形关系.<3> 网状关系. 一: 线性表 1 概念: 线性表也就是关系户中最简单的一种关系,一对一. 如:学生学号的集合就是一个线性表. 2 特征: ① 有且只有一个"首元素". ② 有且只有一个"末元素".
C语言安全编码之数组索引位的合法范围

C语言中的数组索引必须保证位于合法的范围内! 示例代码如下: enum {TABLESIZE = 100}; int *table = NULL; int insert_in_table(int pos, int value) { if(!table) { table = (int *)malloc(sizeof(int) *TABLESIZE); } if(pos >= TABLESIZE) { return -1; } table[pos] = value; return 0; } 其中:p
C语言安全之数组长度与指针实例解析

1.C语言编码需要保证变长数组的长度参数位于合法范围之内例如以下代码: void func(size_t s) { int vla[s]; /*...*/ } /*...*/ func(size); /*...*/ 解决方案如下: enum {MAX_ARRAY = 1024}; void func(size_t s) { if(s < MAX_ARRAY && s != 0) { int vla[s]; /*...*/ } else { //错误处理 } } /*...*/ fu
python和C语言混合编程实例

最近为了测试网速情况怎么样,由于部分业务服务器需要关闭icmp,这样的话采用普通的ping就无法适应我的需求,于是自己简单的写了一个基于tcp端口的ping的程序,由于c执行效率比较的不错,但是开发效率低下,而python是开发效率高,但是执行效率不如C,由于需要大规模的使用,于是用C实现核心部分的代码,并把这部分实现成一个python的模块,由python调用c的模块,下面就贴代码吧复制代码代码如下: /* tcpportping.c */#include <Python.h>#incl
C语言线性表的顺序表示与实现实例详解

1.概述通常来说顺序表是在计算机的内存中以数组的形式保存的线性表,是用一组地址连续的存储单元依次存储数据元素的线性数据结构.线性表采用顺序存储的方式存储就称之为顺序表.顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中. 将表中元素一个接一个的存入一组连续的存储单元中,这种存储结构就是顺序结构. 采用顺序存储结构的线性表简称为" 顺序表".顺序表的存储特点是:只要确定了起始位置,表中任一元素的地址都通过下列公式得到:LOC(ai)=LOC(a1)+(i-1)*L 1≤
数据结构简明备忘录线性表

线性表线性表是线性结构的抽象,线性结构的特点是结构中的数据元素之间存在一对一的线性关系. 数据元素之间的位置关系是一个接一个的排列: .除第一个位置的数据元素外,其他数据元素位置的前面都只有一个数据元素. .除最后一个位置的外,其他数据元素位置的后面都只有一个元素. 线性表通常表示为:L=(D,R) D是数据元素的有限集合 R是数据元素之间关系的有限集合线性表的基本操作: 复制代码代码如下: public interface IListDS<T> { int GetLength(); /
java线性表排序示例分享

大家可以先看一下这个静态方法public static <T> void sort(List<T> list, Comparator<? super T> c) 1.先定义一个模型: 复制代码代码如下: package model; /** * User.java * * @author 梁WP 2014年3月3日 */public class User{ private String userName; private int userAge; pub
C语言安全编码数组记法的一致性

对C语言程序来说,在同一文件中时,void func(char *a); 和 void func(char a[]); 完全等价但在函数原型之外,如果一个数组在一个文件中声明为指针,在另一个不同的文件中声明为数组,那么它们是不等价的示例代码如下: //main.c #include<stdlib.h> enum {ARRAYSIZE = 100}; char *a; void insert_a(void); int main(void) { a = (char*)malloc(ARRA
php线性表顺序存储实现代码(增删查改)

复制代码代码如下: <?php /* *文件名:linearList.php * 功能:数据结构线性表的顺序存储实现 * author:黎锦焕 * @copyright:www.drw1314.com */ class linearList { private $arr; private $length; const MAXSIZE=100; /* *构造函数,判断空表还是飞空表,并且进行实例化 * @param array $arr 输入的数组 * @param int $n 输入数组的长度
C语言安全编码之数值中的sizeof操作符

通常来说获取数组的长度时不要对指针应用sizeof操作符. 现来看看下面这段代码: void clear(int array[]) { for(size_t i = 0; i < sizeof(array) / sizeof(array[0]); i++) { array[i] = 0; } } void dowork(void) { int dis[12]; clear(dis); /*...*/ } clear()使用sizeof(array) / sizeof(array[0])这种用法确

算法系列15天速成 第八天 线性表【下】

相关推荐

随机推荐

算法系列15天速成第八天线性表【下】