2.3 线性表的链式表示与实现
视频二维码（扫码观看）
一、线性表的链式存储结构
链式存储：用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。
存储链表中结点的一组存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。
链表中结点的逻辑顺序和物理顺序不一定相同。
为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后继结点的地址（或位置），称为指针（pointer）或链（link），这两部分组成了链表中的结点结构，如图2-2所示。
图2-2 链表结点结构
链表是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一起的。每一个结点只包含一个指针域的链表，称为单链表。为操作方便，总是在链表的第一个结点之前附设一个头结点（头指针）head指向第一个结点。头结点的数据域可以不存储任何信息（或存储链表长度等信息）。
单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。
【例1】线性表L＝（bat，cat，eat，fat，hat），其带头结点的单链表的逻辑状态和物理存储方式，如图2-3所示。
图2-3 带头结点的单链表的逻辑状态、物理存储方式
1结点的描述与实现
C语言中用带指针的结构体类型来描述
2结点的实现
结点是通过动态分配和释放来实现的，即在需要时分配内存，不需要时释放内存。实现时分别使用C语言提供的标准函数：malloc（），realloc（），sizeof（），free（）。
动态分配：p＝（LNode*）malloc（sizeof（LNode））；
函数malloc申请了一大小为LNode的内存空间作为结点空间，并将其首地址放入指针变量p中。
动态释放：free（p）；
系统回收由指针变量p所指向的内存区。p必须是最近一次调用malloc函数时的返回值。
3最常用的基本操作及其示意图
（1）结点的赋值
（2）常见的指针操作
①q＝p；
②q＝p->next；
③p＝p->next；
④q->next＝p；
⑤q->next＝p->next；
二、单线性链式的基本操作
1建立单链表
假设线性表中结点的数据类型是整型，以32767作为结束标志。动态地建立单链表的常用方法有如下两种：头插入法，尾插入法。
（1）头插入法建表
从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。即每次插入的结点都作为链表的第一个结点。
算法描述
（2）尾插入法建表
头插入法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾，使其成为当前链表的尾结点。
算法描述
无论是哪种插入方法，如果要插入建立的单线性链表的结点是n个，算法的时间复杂度均为O（n）。
对于单链表，无论是哪种操作，只要涉及到钩链（或重新钩链），如果没有明确给出直接后继，钩链（或重新钩链）的次序必须是“先右后左”。
2单链表的查找
（1）按序号查找
取单链表中的第i个元素。对于单链表，不能像顺序表中那样直接按序号i访问结点，而只能从链表的头结点出发，沿链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。
设单链表的长度为n，要查找表中第i个结点，仅当1≤i≤n时，i的值是合法的。
算法描述
移动指针p的频度：
当i＜1时，0次；
当1≤i≤n时，i－1次；
当i＞n时，n次。
因此时间复杂度：O（n）。
（2）按值查找
按值查找是在链表中，查找是否有结点值等于给定值key的结点？若有，则返回首次找到的值为key的结点的存储位置；否则返回NULL。查找时从开始结点出发，沿链表逐个将结点的值和给定值key作比较。
算法描述
算法的执行与形参key有关，平均时间复杂度为O（n）。
3单链表的插入
插入运算是将值为e的新结点插入到表的第i个结点的位置上，即插入到ai－1与ai之间。因此，必须首先找到ai－1所在的结点p，然后生成一个数据域为e的新结点q，q结点作为p的直接后继结点。
算法描述
设链表的长度为n，合法的插入位置是1≤i≤n。算法的时间主要耗费移动指针p上，故时间复杂度亦为O（n）。
4单链表的删除
（1）按序号删除
删除单链表中的第i个结点。
为了删除第i个结点ai，必须找到结点的存储地址。该存储地址是在其直接前驱结点ai－1的next域中，因此，必须首先找到ai－1的存储位置p，然后令p->next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间，将其归还给“存储池”。
设单链表长度为n，则删去第i个结点仅当1≤i≤n时是合法的。则当i＝n＋1时，虽然被删结点不存在，但其前驱结点却存在，是终端结点。故判断条件之一是p->next!＝NULL。显然此算法的时间复杂度也是O（n）。
算法描述
视频二维码（扫码观看）
（2）按值删除
删除单链表中值为key的第一个结点。
与按值查找相类似，首先要查找值为key的结点是否存在？若存在，则删除；否则返回NULL。
算法描述
算法的执行与形参key有关，平均时间复杂度为O（n）。
从上面的讨论可以看出，链表上实现插入和删除运算，无需移动结点，仅需修改指针。解决了顺序表的插入或删除操作需要移动大量元素的问题。
变形之一：
删除单链表中值为key的所有结点。
与按值查找相类似，但比前面的算法更简单。
基本思想：从单链表的第一个结点开始，对每个结点进行检查，若结点的值为key，则删除之，然后检查下一个结点，直到所有的结点都检查。
算法描述
变形之二：
删除单链表中所有值重复的结点，使得所有结点的值都不相同。
与按值查找相类似，但比前面的算法更复杂。
基本思想：从单链表的第一个结点开始，对每个结点进行检查：检查链表中该结点的所有后继结点，只要有值和该结点的值相同，则删除之；然后检查下一个结点，直到所有的结点都检查。
算法描述
5单链表的合并
设有两个有序的单链表，它们的头指针分别是La、Lb，将它们合并为以Lc为头指针的有序链表。合并前的示意图如图2-4所示。
图2-4 两个有序的单链表La、Lb的初始状态
合并了值为－7，－2的结点后示意图如图2-5所示。
图2-5 合并了值为－7，－2的结点后的状态
算法说明
算法中pa，pb分别是待考察的两个链表的当前结点，pc是合并过程中合并的链表的最后一个结点。
算法描述
算法分析：
若La，Lb两个链表的长度分别是m，n，则链表合并的时间复杂度为O（m＋n）。
三、循环链表
1循环链表（Circular Linked List）
循环链表是一种头尾相接的链表。其特点是最后一个结点的指针域指向链表的头结点，整个链表的指针域链接成一个环。从循环链表的任意一个结点出发都可以找到链表中的其他结点，使得表处理更加方便灵活。如图2-6所示。
图2-6 带头结点的单循环链表示意图
2循环链表的操作
对于单循环链表，除链表的合并外，其他的操作和单线性链表基本上一致，仅仅需要在单线性链表操作算法基础上作以下简单修改：
（1）判断是否是空链表：head->next＝＝head；
（2）判断是否是表尾结点：p->next＝＝head。
四、双向链表
视频二维码（扫码观看）
双向链表（Double Linked List）：指的是构成链表的每个结点中设立两个指针域：一个指向其直接前驱的指针域prior，一个指向其直接后继的指针域next。这样形成的链表中有两个方向不同的链，故称为双向链表。
和单链表类似，双向链表一般增加头指针也能使双链表上的某些运算变得方便。
将头结点和尾结点链接起来也能构成循环链表，并称之为双向循环链表。
双向链表是为了克服单链表的单向性的缺陷而引入的。
1双向链表的结点及其类型定义
双向链表的结点的类型定义如下。如图2-7所示。
图2-7 双向链表结构
双向链表结构具有对称性，设p指向双向链表中的某一结点，则其对称性可用下式描述：
(p->prior)->next=p=(p->next)->prior;
结点p的存储位置存放在其直接前驱结点p->prior的直接后继指针域中，同时也存放在其直接后继结点p->next的直接前驱指针域中。
2双向链表的基本操作
（1）双向链表的插入：将值为e的结点插入双向链表中。插入前后链表的变化如图2-8所示。
图2-8 双向链表的插入
①插入时仅仅指出直接前驱结点，钩链时必须注意先后次序是：“先右后左”。部分语句组如下：
S=(DulNode *)malloc(sizeof(DulNode));
S->data=e;
S->next=p->next;p->next->prior=S;
p->next=S;S->prior=p;/*钩链次序非常重要*/
②插入时同时指出直接前驱结点p和直接后继结点q，钩链时无须注意先后次序。部分语句组如下：
S=(DulNode *)malloc(sizeof(DulNode));
S->data=e;
p->next=S;
S->next=q;
S->prior=p;
q->prior=S;
（2）双向链表的结点删除
设要删除的结点为p，删除时可以不引入新的辅助指针变量，可以直接先断链，再释放结点。部分语句组如下：
p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
注意：
与单链表的插入和删除操作不同的是，在双向链表中插入和删除必须同时修改两个方向上的指针域。