任务描述
用数组处理数据存在两方面的问题：其一，如果数据个数不确定，则数组长度必须是可能的最大长度，这显然会浪费内存；其二，当需要向数组增加或删除一个数据时，可能需要移动大量的数组元素，这会造成时间上的浪费。为解决上述问题，本任务将介绍一种新的数据结构——链表。
链表是一种动态地进行存储分配的数据结构，它既不需要事先确定最大长度，在插入或者删除一个元素时也不会引起数据的大量移动。
知识学习
（1）链表的结构
链表有一个“头”，一个“尾”。中间有若干元素，每个元素称为一个结点。每个结点包括两部分：一部分是用户关心的实际数据，称为数据域；另一部分是下一个结点的地址，称为指针域。具体如图8.2所示。其中，head 称为头指针，它指向链表的第一个结点；最后一个结点称为“表尾”，该结点的指针域值为0，指向内存中编号为零的地址（常用符号常量NULL 表示，称为空地址），表尾不再有后继结点，链表到此结束。
图8.2 链表结构示意图
说明：
①链表中各元素在内存中可以不连续存放。
②查找链表中某个结点，必须从头指针开始顺序查找各结点，直至找到或到达表尾为止。
③头指针至关重要，没有头指针则整个链表无法访问。
（2）链表的定义
链表各结点中，数据域中的数据与指针域中的数据通常具有不同的类型，数据域本身还可以包含类型不同的多个成员，因此，一般用结构体变量表示链表的一个结点。该结构体变量不仅要有成员表示数据域的值，还要有一个指针类型的成员表示指针域中的数据。例如，对图8.3所示链表，可定义如下结构体类型：
图8.3 单链表示例
其中，成员num、name 和score 存放结点中用户关心的数据，next 是指针类型的成员，它指向链表中的下一个结点，基类型是结构体类型本身。
创建链表的结点有两种方式：其一，在程序中定义相应数量的结构体变量来充当结点；其二，在程序执行过程中动态开辟结点。第一种方式创建的链表称为静态链表，第二种方式创建的链表称为动态链表。静态链表各结点所占用的存储空间在程序执行完毕后由系统释放；动态链表可在程序执行过程中调用动态存储分配函数释放。
（3）静态链表
链表长度固定且结点个数较少时通常使用“静态链表”，下面举例说明静态链表的建立和输出方法。
例8.11 建立静态链表。
（4）动态链表
1）动态存储分配函数
与静态链表不同，动态链表可以动态地分配存储，即在程序运行过程中根据需要动态地开辟或者释放结点。常用的动态内存分配函数有malloc、calloc 和free，它们包含在头文件“stdlib.h”或“malloc.h”中。
①malloc 函数。
函数原型：void *malloc（unsigned size）
功能：在内存的动态存储区中分配size 字节的连续空间。返回值为所分配存储区的起始地址，分配不成功则返回NULL。
例如：char *p；
p=(char *)malloc(8);
说明：
表示分配8 个字节的连续存储空间并进行强制类型转换，p 代表首地址。
函数返回值为void 指针类型，使用时需强制类型转换为所需类型。以下程序片段利用动态内存分配函数建立一个长度事先不确定的浮点型数组：
int n,i;
float *a;
scanf("%d",&n);
a=(float *)malloc(n*sizeof(float));
for(i=0;i<n;i++)
scanf("%f",a[i]);
②calloc 函数。
函数原型：void *calloc（unsigned n，unsigned size）
功能：在内存的动态存储区中分配n 个长度为size 字节的连续空间。返回值为所分配存储区的起始地址，分配不成功则返回NULL。
例如：char *p；
p=(char *)calloc(2,20);
说明：
表示分配2 块大小为20 个字节的连续存储空间并进行强制类型转换，p 代表首地址。
与malloc 函数相比，calloc 函数可以一次分配n 块区域。
③free 函数。
函数原型：void free（void *p）
功能：释放p 所指向的内存空间。
例如：int n，*p；
scanf("%d",&n);
p=(int *)malloc(n*sizof(int));
free(p);
说明：
调用free 函数时，p 从指向int 型的指针自动转化为void 型指针。
所释放的内存空间必须是由malloc 函数或calloc 函数分配的。
2）动态链表的操作
假设链表的结点类型如下：
①动态链表的建立。
创建动态链表是指在程序执行过程中从无到有地建立一个链表。
算法思想：开辟N 个结点，每开辟一个结点都让p1 指向新结点，p2 指向当前表尾结点，把p1 所指向的结点连接到p2 所指向结点的后面。
下面以含有3 个结点的动态链表为例说明创建步骤：
第1 步：开辟新结点，并令指针head、p1 与p2 都指向该结点，如图8.4所示。
图8.4 开辟首结点
第2 步：再开辟一个新结点，令指针p1 指向该结点；如图8.5（a）所示。然后，令前一个结点指针域的指针指向该结点，如图8.5（b）所示；最后，令指针p2 后移一个位置，以指向新开辟结点，如图8.5（c）所示。(www.xing528.com)
图8.5 开辟第2 个结点并与前一个结点连接
第3 步：开辟第三个结点，令指针p1 指向该结点，如图8.6（a）所示；然后，令前一个结点指针域的指针指向该结点，如图8.6（b）所示。
图8.6 开辟第3 个结点并与前一个结点连接
例8.12 编写函数建立动态链表，结点个数作函数形参，返回链表头指针。
说明：
可将结构体类型的长度定义为符号常量，如#define LEN sizeof（struct student）。
①动态链表的输出。
先让指针变量p 指向第一个结点，输出该结点的值；然后后移一个结点，再输出；如此重复，直到到达表尾结点，如图8.7所示。
图8.7 链表输出示意图（p'代表指针p 后移一个结点后指向的位置，p"代表后移两个结点后的位置）
例8.13 编写函数输出动态链表。
②动态链表结点的删除。
要删除一个结点，只需从第一个结点出发沿链表搜索，找到待删除结点后，修改该结点前驱结点的指针域，使其指向待删除结点的后继结点即可，如图8.8所示。
图8.8 删除结点C 示意图
例8.14 编写函数，删除指定学号的学生结点，以头指针和学号作参数。
注意：
程序中只是将结点从链表中删除，该结点所占用的内存由系统在程序执行完毕后释放。
③动态链表结点的插入。
将结点插入到链表的指定位置，比如将图8.9 中结点b 插入到结点a 与结点c 之间，只需修改结点b 指针域的值，使其指向结点c；然后令结点a 的指针指向结点b。这样原链表中由结点a 到结点c 的连接被断开，结点b 被插入到链表中。
图8.9 插入结点示意图
例8.15 设链表中各结点按学号由小到大排列，编写函数插入一个新结点，使链表仍按原顺序排列。
④动态链表的综合操作。
例8.16 在主函数中调用上述各子函数实现链表的建立、输入、输出、删除及插入。
任务总结
链表是一种零散的线性数据结构，链表建立、插入、删除、查找、遍历等基本操作。链表的插入删除的时间复杂度为O（1）O（1），而查找的时间复杂度为O（n）O（n）。按照组织的方式，链表可以分为单链表、双链表、环形链表。
单链表的节点只包括数据域和一个指针域，其中指针域指向其后继节点，因此只能单向访问，不能够访问前置节点。双向链表则包括了两个指针域，分别指向其前驱和后继节点。循环链表则是双向链表的一种延伸，其最后一个节点的后继不是指向了nullptr 而是指向了第一个节点（nullptr 是C+ +11 标准中的空指针的保留字）。
链表可以带头指针也可以不带头指针，但是带了头指针则会充分利用nullptr 可以直接赋值的特性，使一些操作边界条件处理简化（比如删除节点为第一个节点）。nullptr 的这些技巧在二叉树中也会有使用。
下面以双向带头链表为例来说明链表这一数据结构的基本操作。
首先需要定义链表的节点：
这里自定义了一个默认的构造函数，用来把新建的节点的指针域全部设置为nullptr。这样可以在后续操作时更加简洁。
（1）链表的建立
链表的建立非常简单，只需要构造出一个表即可。这里使用了一个带头链表，只需返回头节点的指针即可，因为初始化在构造函数中完成了，因此可直接返回一个new。
（2）链表的插入
对于链表的插入有两种处理方法：头插法和尾插法。顾名思义，头插法是将新的节点插入在已知链表的第一个节点之前；而尾插法则是要保存一个末尾指针，插入时先将末尾指针所指向的节点的后继设置为新的节点，然后更新末尾指针为新的节点。假设使用new 运算符新建的节点具有构造函数能把所有的指针域设为nullptr，因此没有描述哪些指针需要设置为空。如果使用C语言中的malloc（）函数或者没有显式给出构造函数去初始化指针域，将未使用的指针域设置为空这一点还是需要注意的。下面给出头插法和尾插法的代码：
①头插法：
②尾插法：
更倾向于为链表的接口单独提供一个类（C 不支持类，可以提供一个结构体，用来单独保存尾插法所需的tail 指针），这样使得代码更为简洁明了。
（3）链表的查找
链表本质上是一个顺序表，因此查找链表只能从头或者从尾顺序查找，与数组的顺序查找较为类似，只要一个个地遍历整个表中的元素，判断其元素是否符合要求的元素，找不到则返回空指针即可。
下面给出了双向链表的查找：
当然这里使用了模板的方法，要求模板的实例化后的类T 具有= =运算符。至于单向链表的查找其实一样，但是如果想要利用查找的结果来进行删除操作，则务必返回前一个节点，这样查找的具体代码又会有所不同。
（4）链表节点的删除
删除节点略有麻烦，因为要涉及前后指针域的修改。前面提及为了简化边界条件的处理，使用了带头的链表。这样只需判断该节点的后继是否为空（是不是最后一个节点）即可，如果非空则将其的前驱设置为被删除节点的前驱。如果不使用带头表，也需要判断一下该节点的前驱是否为空（是不是第一个节点）。当然，如果一开始构造了一个带头又带尾的表，两个判断都是不需要的。
代码实现如下：
（5）链表的销毁
在动态数据结构中，为了避免内存泄漏，在使用结束时应进行销毁。链表的销毁很简单，只需遍历整个表，逐个删除节点即可。删除的时候需要注意保存当前节点的后继，以免delete运算符释放当前节点后无法找到其下一个节点。
切记不能使用节点的析构函数实现递归销毁整个表，这样会导致在删除单个节点时把以该节点为头的子表也全部销毁了。
链表的用途：链表作为基本的数据结构，除了其本身插入删除非常快之外，还可以实现其他的复杂数据结构和算法，比如可以用链表实现栈和队列，可以处理哈希表的冲突，还可以用邻接表来表示图，等等。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
