算法与数据结构【30天】集训营——线性表之链式表的表示与实现及顺表与链表比较（04）

算法与数据结构【30天】集训营——线性表之链式表的表示与实现及顺表与链表比较（04）

目录

​​单链表的定义和表示​​

​​单链表的基本操作及实现​​

​​初始化​​​​按序号查找结点值​​​​按值查找表结点​​​​插入操作​​​​删除节点操作​​​​删除结点 *P（拓展）​​

​​循环链表​​​​双向链表​​

​​双链表的插入操作​​​​双链表的删徐操作​​

​​静态链表​​​​顺序表和链表的比较​​

​​空间性能比较​​

​​(1)存储空间的分配​​​​(2)存储密度的大小​​

​​时间性能的比较​​

​​(1) 存取元素的效率​​​​(2)插入和删除操作的效率​​

​​经典知识​​​​线性表的应用​​

​​线性表的合并​​​​有序表的合并​​​​链式有序表的合并(了解)​​​​稀疏多项式的运算（回顾）​​​​表格总结对比​​

​​易错例题汇总​​

​​详细知识回顾​​

​​尾指针的作用​​​​头结点好处​​​​总结​​

​​每文一语​​

前面我们学习的顺序表，在插入和输出的时候会造成大量的元素移动，这样的效率是极其的低，所以有没有一种存储方式可以不移动所有的元素就可以实现插入和删除呢？下面我们将学习链表——线性表的链式存储结构。

单链表的定义和表示

线性表的链式存储又称单链表， 它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息外， 还需要存放一个指向其后继的指针。

typedef struct LNode { //定义单链表结点类型 ElemType data; //数据域 struct LNode *next; /指针域 }LNode ,*LinkList;

增加头结点的单链表

引入头结点的好处：

① 由于第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。

② 无论链表是否为空，其头指针都指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就得到了统一。

单链表的基本操作及实现

初始化

按序号查找结点值

在单链表中从第一个结点出发， 顺指针next域逐个往下搜索， 直到找到第i个结点为止,否则返回最后一个结点指针域null，具体算法如下：

按序号查找操作的时间复杂度为O(n)

按值查找表结点

从单链表的第一个结点开始， 由前往后依次比较表中各结点数据域的值， 若某结点数据域的值等于给定值e,则返回该结点的指针； 若整个单链表中没有这样的结点， 则返回NULL。

按值查找操作的时间复杂度为O(n)

插入操作

假设要在单链表的两个数据元素a和b之间插入一个数据元素X, 已知p为其单链表存储结构中指向结点a的指针。

为插入数据元素 x, 首先要生成一个数据域为 x 的结点， 然后插入到单链表中。 根据插人操作的逻辑定义， 还需要修改结点a 中的指针域， 令其指向结点 x, 而结点 x 中的指针域应指向结点b, 从而实现 3 个元素a、 b和x之间逻辑关系的变化。

用代码实现如下：

s->next=p->next//s指向的要等于最开始p指向的P->next=s

注意是先断开，在修改，然后链接

当你理解到算法本质的精髓后，这些代码实现都是比较简单的一种逻辑实现。

单链表的插入的时间复杂度为O(n)

删除节点操作

实现代码：

删除结点 *P（拓展）

实质就是将其后继结点的值赋予其自身， 然后删除后继结点， 也能使得时间复杂度为0（1）。

循环链表

循环链表是另一种形式的链式存储结构。其特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点

循环单链表的操作和单链表基本一致，差别仅在于：当链表遍历时，判别当前指针p是否指向表尾结点的终止条件不同。在单链表中，判别条件为p!=NULL或p->next!=NULL,而循环单链表的判别条件为p!=L或p->next!=L。

双向链表

单链表结点中只有一个指向其后继的指针， 使得单链表只能从头结点依次顺序地向后遍历。

要访问某个结点的前驱结点（插入、 删除操作时），只能从头开始遍历， 访问后继结点的时间复杂度为0（1）,访问前驱结点的时间复杂度为0（n）。

为了克服单链表的上述缺点， 引入了双链表， 双链表结点中有两个指针prior和next,分别指向其前驱结点和后继结点。

多了一个指针指向前驱节点

双链表在单链表的结点中增加了一个指向其前驱的prior指针， 因此双链表中的按值查找和按位查找的操作与单链表的相同。 但双链表在插入和删除操作的实现上， 与单链表有着较大的不同。

双链表可以很方便地找到其前驱结点， 因此， 插入、 删除操作的时间复杂度仅为0(1)

双链表的插入操作

在双链表中P所指的结点之后插入结点*s,其指针的变化过程如图：

上述操作虽然不是唯一的，但是①②操作必须要在④之前

解读上面的逻辑关系：s指向的next等于p指向的next，也就是将s与c连接起来了，然后p指向next的c的prior=s，也就是将c与s连接起来了，然后s的prior等于p，连接s与p ,最后p的next等于s，完成其插入！

双链表的删徐操作

静态链表

静态链表借助数组来描述线性表的链式存储结构， 结点也有数据域data和指针域next,与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址（数组下标），又称游标。

顺序表和链表的比较

空间性能比较

(1)存储空间的分配

顺序表的存储空间必须预先分配，元素个数扩充受一定限制，易造成存储空间浪费或空间溢出现象；而链表不需要为其预先分配空间，只要内存空间允许，链表中的元素个数就没有限制。基于此，当线性表的长度变化较大，难以预估存储规模时，宜采用链表作为存储结构。

(2)存储密度的大小

链表的每个结点除了设置数据域用来存储数据元素外，还要额外设置指针域，用来存储指示元素之间逻辑关系的指针，从存储密度上来讲，这是不经济的。 所谓存储密度是指数据元素本身所占用的存储量和整个结点结构所占用的存储量之比，即

存储密度越大，存储空间的利用率就越高。 显然，顺序表的存储密度为1,而链表的存储密度小于1。

基于此，当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。

时间性能的比较

(1) 存取元素的效率

基于此，若线性表的主要操作是和元素位置紧密相关的这类取值操作，很少做插入或删除时，宜采用顺序表作为存储结构。

(2)插入和删除操作的效率

对于频繁进行插入或删除操作的线性表，宜采用链表作为存储结构。

经典知识

①线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

错，线性表是逻辑结构概念，可以顺序存储或链式储，与元素数据类型无关。链表就是线性表的一种 前后矛盾

②若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( )存储方式最节省运算时间。

单链表仅有头指针的单循环链表双链表仅有尾指针的单循环链表

要插入结点，只要改变一下指针即可，要删除头结点，只要删除指针.next的元素即可。故是仅有尾指针的单循环链表

注意：线性表是具有n个数据元素的有限序列，而不是数据项

线性表的应用

线性表的合并

有序表的合并

算法的时间复杂度为O(m+n)

链式有序表的合并(了解)

时间复杂度和有序表一样

稀疏多项式的运算（回顾）

表格总结对比

易错例题汇总

详细知识回顾

尾指针的作用

补充：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和 rear, 查找时间都是O(1)。 若用头指针来表示该链表，则查找终端结点的时间为O(n)。

头结点好处

头结点即在链表的首元结点（即存储实际数据的第一个节点）之前附设的一个结点，该结点的数据域可以为空，也可存放表长度等附加信息，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。

p->next的意思是指针p所指向的内容中的next部分，也就说P所指向的节点就是P的指针域

如何理解P->next ：P结点的next指向下一个元素的指针域，这个时候P->next=P+1个元素，但是此时的指向的是P+1的指针域，只是在变化为实体的数据域时，我们习惯于用整体代替。

对于这个，首先我们看P的next指向下一个元素，下一个元素的prev指向本身，此时真正的指向是指向本身的指针域，所以要等于P的前驱结点指针域。

双向查找的链表，指针域有两个指针变量，一个存放上一个节点的地址，另一个存放下一个节点的地址。有个例子，单链表进行删除操作的时候需要知道上一个节点的地址p，然后进行p=p->next->next，达到删除某个节点的操作，但是得到上一个节点的地址，通常都需要重新查找一下。对于双向链表来说，p->prev是上一个节点元素的地址，p->next是下一个节点元素的地址，所以进行p->prev = p->next，就可直接达到删除节点p的操作。

根据这道题，首先我们要明确的是双向链表的存储，一个元素的左右两边分别是存储的是一个元素的地址和下一个元素的地址，所以P指向的下一个元素的地址的上一个地址要等于原来的P的上一个地址才可以，P指向上一个元素的地址的下一个元素要等于原来P下一个元素的地址。

要充分理解这些链表的表示和运算，只有自己不断的理解和尝试才能够明白！

总结

在链表和顺表这一知识，我们最容易做错的不是那些基本概念，时间复杂度以及它们的优劣对比，而是在于链表的算法实现，我们应该区分单链表（有头结点），双链表，循环链表，带头结点单循环链表，带尾指针的单循环链表这些链表的特点以及图像。

以及尾指针的作用，这里非常的重要，尾指针可以使得循环链表可以通过首尾互相直达对方，时间复杂度为O(1)

每文一语

加油！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。