3.4 线性链表及其运算

线性表顺序表示方法因为逻辑上相邻的元素其存储的物理位置也是相邻的，所以无须为表示结点间的逻辑关系而增加额外的存储空间，并且具有可以方便地随机存取表中的任一元素的优点。但该方法也有其明显的缺点，主要体现在以下两个方面：

1）插入或删除运算不方便，除表尾的位置外，在表的其他位置上进行插入或删除操作都必须移动大量的结点，其效率较低。

2）由于顺序表要求占用连续的存储空间，存储分配只能预先进行静态分配。因此当表的长度变化较大时，难以确定合适的存储规模。若按照可能达到的最大长度预先分配表空间，则可能造成一部分空间长期闲置而得不到充分利用；若事先对表的长度估计不足，则插入操作可能使表长超过预先分配的空间而造成溢出。

为了克服顺序表的缺点，可以采用链接方式存储线性表。通常将采用链式存储结构的线性表称为链表。

3.4.1 链表的基本概念和结构特征

在顺序表中，是用一组地址连续的存储单元来依次存放线性表的结点，因此结点的逻辑次序和物理次序是一致的。而链表则不然，链表是用一组任意的存储单元来存放线性表的结点，这组存储单元可以是连续的，也可以是非连续的，甚至是离散分布在内存的任何位置上。因此，链表中结点的逻辑次序和物理次序不一定相同。为了正确地表示结点间的逻辑关系，必须在存储线性表的每个数据元素值的同时，存储指示其后继结点的地址或位置信息，这两部分信息组成的存储映像叫做结点（Node）。它包括两个域：数据域用来存储结点的值；指针域用来存储数据元素的直接后继的地址或位置，如图3-11所示。

3.4.2 单链表

1.单链表的概念与存储结构

链表正是通过每个结点的指针域将线性表的n个结点按其逻辑顺序链接在一起。由于链表的每个结点只有一个指针域，故将这种链表又称为单链表。

由于单链表中每个结点的存储地址是存放在其前趋结点的指针域中，而第一个结点无前趋，所以应设一个头指针head指向第一个结点。同时，由于表中最后一个结点没有直接后继，则指定线性表中最后一个结点的指针域为“空”（NULL）。这样对于整个链表的存取必须从头指针开始。一般情况下，使用链表只关心链表中结点间的逻辑顺序，并不关心每个结点的实际存储位置，因此通常是用箭头来表示链域中的指针，于是链表就可以更直观地表示成用箭头链接起来的结点序列，如图3-12所示。

有时为了操作的方便，还可以在单链表的第一个结点之前附设一个头结点，头结点的数据域可以存储一些关于线性表的长度的附加信息，也可以什么都不存；而头结点的指针域存储指向第一个结点的指针（即第一个结点的存储位置）。此时带头结点的单链表头指针就不再指向表中第一个结点而是指向头结点。如果线性表为空表，则头结点的指针域为“空”，如图3-13所示。

由上述可见，单链表可以由头指针唯一确定。单链表的存储结构描述如下：

2.单链表上的基本运算

下面通过实例讨论用单链表作存储结构时，如何实现线性表的几种基本运算。

（1）建立一个带头结点的单链表

输入一系列整数，以0标志结束，将这些整数作为data域建立一个单链表的函数。

如果输入的整数序列是：5138790，则建立的单链表如图3-14所示。

（2）建立一个循环单链表

循环单链表的结构与普通单链表一样，只是普通单链表的最后一个结点的next域取值为NULL，而循环单链表的最后一个结点的next域指向第一个结点。

根据上例，以0标志循环结束，建立一个不带头结点的循环单链表的函数如下：

如果输入的整数序列是：5138790，则建立的单链表如图3-15所示。

（3）链表的查找算法

在已建立的循环单链表（不带头结点）中查找元素值为x的函数：

（4）链表的长度算法

1）计算一个已建立的单链表（带头结点）的结点个数的函数：

2）计算一个已建立的循环单链表（不带头结点）的结点个数的函数：

（5）链表的插入算法

1）在单链表（带头结点）的第i个结点之后插入一个元素为x的结点的函数（i≥0，i＝0表示插入的结点作为第一个结点）。

2）在单链表（带头结点）的已知数据元素a之后插入数据元素b。未找到a时，插入表尾。

（6）链表删除算法

从单链表（带头结点）中删除一个其值为x的结点的函数：

3.双向链表的存储结构

双向链表是另一种形式的链式存储结构。在双向链表的结点中有两个指针域：一个指向直接后继，另一个指向直接前趋。

（1）线性表的双向链表存储结构

对指向双向链表任一结点的指针d，有下面的关系：

即当前结点后继的前趋是自身，当前结点前趋的后继也是自身，如图3-16所示。

循环双链表的结构与普通双链表一样，只是普通双链表的第一个结点的prior域置为NULL，最后一个结点的next域置为NULL，而循环双链表的最后一个结点的next域指向第一个结点，第一个结点的prior域指向最后一个结点，如图3-16中虚线所示。

（2）双向链表的删除操作（见图3-17）

（3）双向链表的插入操作（见图3-18）

3.4.3 线性链表算法编程实例

使用单链表实现一个电话簿管理程序，电话簿中的每条记录包括姓名和电话两项。程序实现了菜单，初始化，添加、删除和显示等功能。

C语言程序代码如下：