2.3　线性表的链式存储结构和实现

线性表的顺序存储结构着明显的缺点：插入、删除元素时需要频繁移动元素，运算效率低；必须按事先估计的最大元素个数申请连续的存储空间。存储空间估计大了，则浪费空间；若估计小了，则容易产生溢出，空间难以临时扩大。采用链式存储结构的线性表可以克服线性表的顺序存储结构存在的上述不足。

采用链式存储结构的线性表称为链表。链表有单链表、循环链表和双向链表等多种类型。

2.3.1　单链表的定义和表示

链表中，不仅需要存储每个数据元素，还需存储其直接后继的存储地址，这两部分数据信息组合起来称为结点。结点包括两个域：存储数据元素信息的域称为数据域；存储直接后继存储地址的域称为指针域。每个结点只包含一个指针域的链表，称为单链表。在单链表中，每个元素占用一个结点，结点的结构如图2.4所示，其中，数据域记为element，指针域记为link。在单链表中，数据之间的前驱后继关系是通过指针域中存储的地址来表现的，逻辑上相邻的元素在物理存储空间上是不一定相邻的。

在此约定，在不会引起混淆的场合，将不明确区分结点和元素这两个术语。但必要时，将包括数据元素和地址在内的整个存储块称为结点，而将其中的数据元素称为该结点的元素。

线性表(a0,a1,…,an−1)以单链表形式进行存储时，其结构如图2.5（a）所示。第一个元素a0所在的结点称为头结点。存储头结点地址的指针称为头指针，记为first。若单链表中没有存储数据元素，则单链表为空，此时first指针的值为NULL，在图中用“∧”表示，如图2.5（b）所示。单链表最后一个元素an−1所在的结点称为尾结点，此结点没有后继结点，其指针域的值为NULL，在图中用“∧”表示。

图2.4　单链表的结点结构

图2.5　单链表示例

在单链表中，若first指针中存储的值丢失，即丢失元素a0的地址，将导致无法读取a0的数据域和指针域，此指针域中存放的a1的地址也将丢失。由此类推可知，整个单链表存储的信息都会丢失。在对结点的指针域进行操作时，需注意保存好后继结点的地址，避免丢失后继结点的地址，出现“断链”现象。

单链表的类型定义如下。

在类型Node的定义中，Node表示单链表的结点结构类型，element表示结点的数据域，link为结点的指针域，存放后继结点的地址。在类型SingleList的定义中，SingleList是单链表类型，first表示头指针，n表示单链表中元素的个数。

2.3.2　单链表基本运算的实现

以下讨论单链表中几个主要运算的具体实现。

1．初始化

单链表的初始化运算是构造一个空的单链表。

程序2.8　单链表的初始化

2．查找

单链表的查找运算是读取表中元素ai的值。单链表不具备顺序表的可随机存取元素的特性，必须沿着单链表的头结点开始逐个计数进行查找。

【算法步骤】

（1）判断i是否越界，若越界，返回ERROR。

（2）从头结点开始顺着单链表逐个结点查找。

（3）将ai的值通过x返回。

程序2.9　单链表的查找

3．插入

单链表的插入运算是在ai之后插入新元素x。为了实现此功能，首先需要使用查找算法确定ai的位置，使用指针p指向此结点。

x是一个新元素，在单链表中并不存在，需要先为此元素生成一个新结点，由指针q指向此结点，并将新结点的数据域置为x。

若i=−1，表示将新结点插入单链表的头结点之前，它将成为新的头结点，如图2.6所示，通过以下语句实现。

①q->link=first;

②first=q;

图2.6　结点的插入示例（i=−1）

若i>−1，表示将新结点插入单链表，新结点应成为ai+1的直接前驱、ai的直接后继，如图2.7所示，通过以下语句实现。

①q->link=p->link;　//将p所指结点link域中的地址存储在q所指结点的link域中

②p->link=q;　//将q中存储的新结点地址存放在p所指结点的link域中

上述两条语句的执行顺序不能颠倒，否则将出现“断链”问题。

图2.7　结点的插入示例（i>−1）

【算法步骤】

（1）判断i是否越界，若越界，则返回ERROR。

（2）查找ai，指针p指向此结点。

（3）生成新的结点，将新结点的数据域置为x，指针q指向此结点。

（4）若i=−1，新结点q插在头结点之前，成为新的头结点；若i>−1，将q所指向的结点插入在p所指向的结点之后。

（5）单链表元素个数加1，返回OK。

程序2.10　单链表的插入

4．删除

单链表删除运算的功能是删除元素ai。

若i=0，表示删除头结点，需将first指针指向a1所在结点，使其成为新的头结点，如图2.8所示。实现语句如下。

first=first->link;

若i>0，则使ai的直接前驱ai−1的指针域存储ai的直接后继ai+1的地址，如图2.9所示。实现语句如下。

q->link=p->link;

图2.8　单链表中删除ai（i=0）

图2.9　单链表中删除ai（i>0）

删除元素ai时，不可跳过上述操作而直接释放ai的存储空间，否则将导致直接后继ai+1地址丢失，出现“断链”问题。

【算法步骤】

（1）若i越界或单链表为空，返回ERROR。

（2）查找元素ai的直接前驱ai−1，并令指针q指向它。

（3）若i=0，则从单链表中删除头结点；若i>0，则使p指向ai所在结点，并从单链表中删除ai。

（4）释放p所指结点的存储空间。

（5）单链表元素个数减1，返回OK。

程序2.11　单链表的删除

5．输出

单链表的输出运算是从first所指示的第一个结点开始逐个遍历单链表的每个结点，将元素依次输出。

【算法步骤】

（1）判断单链表是否为空，若为空，返回ERROR。

（2）将元素（a0,…,an−1）依次输出。

程序2.12　顺序表的输出

6．撤销

撤销运算的主要功能是释放单链表中动态分配的数据元素存储空间，以防止内存泄漏。

程序2.13　顺序表的撤销

7．主函数main

程序2.14中的主函数main是为了测试单链表的主要运算而设计的。

程序2.14　主函数main

2.3.3　带表头结点的单链表

在上述单链表中头结点之前没有直接前驱，进行插入和删除运算时，需要把头结点的插入和删除作为特殊情况特别处理。为解决上述问题，简化算法，可在单链表的头结点之前增加一个表头结点，由此构成的单链表称为带表头结点的单链表，如图2.10所示。

图2.10　带表头结点的单链表结构

在此需注意表头结点与头结点的区别。图2.10（a）中，元素a0所在结点为头结点，头结点之前的结点为表头结点。表头结点的数据域中并不存放线性表中的数据元素。当表为空时也需有一个表头结点，如图2.10（b）所示。

带表头结点的单链表的类型定义如下。

HeaderList与SingleList类型定义相似，此处的Node类型同SingleList类型定义中的Node类型。

带表头结点的单链表的运算与单链表的运算类似，以下仅给出带表头结点的单链表的初始化、插入、删除运算的具体实现。读者可自行完成其他运算的实现。

1．初始化

初始化运算是构造一个仅带有一个表头结点的空的单链表。

程序2.15　带表头结点的单链表的初始化

2．插入

带表头结点的单链表中每个结点之前都有前驱结点，在插入元素时不需要再单独处理插入在头结点之前的情况，从而简化了插入运算。

程序2.16　带表头结点的单链表的插入运算

3．删除

带表头结点的单链表中每个结点之前都有前驱结点，在删除元素时不需要再单独处理删除头结点的情况，从而简化了删除运算。

程序2.17　带表头结点的单链表的删除运算

2.3.4　单循环链表

单循环链表是另一种线性表链式存储方式。将单链表中最后一个结点的指针域存储头结点的地址，使得整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，如图2.11（a）所示。空的单循环链表如图2.11（b）所示。

图2.11　单循环链表结构

也可为单循环链表增加表头结点，则构成带表头结点的单循环链表，如图2.12（a）所示。空的带表头结点的单循环链表如图2.12（b）所示。

图2.12　带表头结点的单循环链表结构

2.3.5　双向链表

以上介绍的线性表链式存储结构中，每个结点只有一个指针域，从某个结点出发只能顺着指针域向后查找后继结点。若要再向前查找前驱结点，则需从头结点开始再次查找。为了克服单链表存在的上述问题，可使用双向链表，如图2.13所示。

双向链表的结点有三个域，结点的结构如图2.14所示。其中，存储数据元素的域称为数据域，记为element；左指针域是存储直接前驱结点地址的域，记为llink；右指针域是存储直接后继结点地址的域，记为rlink。

图2.13　双向链表

图2.14　双向链表的结点结构

双向链表的存储结构定义如下。

1．双向链表的插入

为了实现在双向链表的元素ai之前插入x，首先需查找到元素ai所在结点并使指针p指向它，这个过程与单链表中查找运算类似。生成新的结点，将新结点的数据域置为x，指针q指向此结点。在p所指向的结点之前插入q所指向的结点，如图2.15所示。

图2.15　双向链表的插入

双向链表的插入运算的核心代码如下。

2．双向链表的删除

为了在双向链表中删除元素ai，首先需要查找元素ai，并令指针p指向其所在结点，这个过程与单链表中查找运算类似；然后使元素ai的前驱结点ai−1的右指针域存储ai的后继结点ai+1的地址；使元素ai的后继结点ai+1的左指针域存储ai的前驱结点ai−1的地址；最后释放元素ai所在结点的存储空间，如图2.16所示。

图2.16　双向链表的删除

双向链表的删除运算的核心代码如下。