2.3 线性表的链式存储及实现
顺序存储虽然是一种很有用的存储结构，但它具有如下局限性：
（1）若要为线性表扩充存储空间，则需重新创建一个地址连续的更大的存储空间，并把原有的数据元素都复制到新的存储空间中。
（2）因为顺序存储要求逻辑上相邻的数据元素在物理存储位置上也是相邻的，这就使得要插入或删除一个数据元素将会引起平均约一半的数据元素的移动。也就是说，顺序存储不便于做插入和删除操作。
所以，顺序表最适合于表示“静态”线性表，即线性表一旦形成以后，就很少进行插入与删除操作。对于需要频繁执行插入和删除操作的“动态”线性表，通常采用链式存储结构。链式存储结构不要求逻辑上相邻的数据元素在物理上也相邻，它是用一组地址任意的存储单元来存放数据元素的值。因此，链式存储结构没有顺序存储结构所具有的某些操作上的局限性，但却失去了可随机存取的特点，在链式存储结构上只能进行顺序存取。
2.3.1 单链表的表示
采用链式存储方式存储的线性表称为链表，链表中每一个结点包含存放数据元素的值的数据域和存放指向逻辑上相邻结点的指针域。若一个结点中只包含一个指针域，则称此链表为单链表（Single Linked List）。如图2-7所示为线性表（a1，a2，a3，…，an）的单链表存储结构。
图2-7 单链表的存储结构
由图2-7可知，单链表是通过指向后继结点的指针把它的一串结点链接成一个链。以线性表中第一个数据元素的存储地址作为线性表的起始地址，称作线性表的头指针。一个单链表由它的头指针来唯一标识它。单链表中的最后一个结点（也称为尾结点）没有后继，所以它的指针域的值为空指针NULL。有时为了操作方便，在第一个结点之前虚加一个“头结点”，它的数据域一般不存放具体的值，指针域存放指向第一个结点（也称为首结点）的指针，此时指向头结点的指针为单链表的头指针。虚加了头结点的单链表也称为带头结点的单链表，如图2-8（a）所示。若线性表为空表，则头结点的指针域为“空”，如图2-8（b）所示。如果以后书中如无特殊说明，都是指带头结点的单链表。
图2-8 带头结点的单链表的存储结构
由图2-8也可知单链表是由若干个结点连接而成的。其中每个结点由两部分构成，一部分是用于存放数据元素值的数据域，另一部分是用于存放线性表中后继结点的地址（后继指针）的指针域，如图2-9所示。
图2-9 单链表中结点的结构
如果数据域用data描述，而后继指针域用next描述，则单链表的存储结构可描述为：
C0 2-3-1
typedef int ElemType；//为后续描述算法方便，特将数据元素类型自定义为整型
typedef struct LNode {
ElemType data； //数据域
struct LNode *next；//指针域
}LNode，*LinkList；
注意：上述描述中将单链表的结点类型命名为LNode，而将指向结点的指针类型命名为LinkList，请读者区分它们的使用。
2.3.2 单链表上基本操作的实现
下面以初始化、查找、插入、删除、输出和创建一个单链表为例，来介绍带头结点的单链表上基本操作的实现。
1．单链表上的初始化操作
从如图2-8（b）可知，带头结点的空单链表就是一个只含头结点的单链表。所以要创建一个空的单链表，则只要分配一个结点大小的空间来作为头结点，并使其指针域置为空指针，头指针指向该结点即可。
【算法2-13】初始化操作算法
Status InitList（LinkList&L）
//创建一个带头结点的空单链表L
{ L=（LinkList）malloc（sizeof（LNode））；//为头结点分配空间，并使L指针指向它
if（!L） //空间分配失败
return ERROR；
L-＞next=NULL； //将头结点的指针域置为空
return OK；
}//算法2-13 结束
2．单链表上的查找操作
单链表上的查找操作根据给定的查找条件不同，其实现方法也不相同。下面介绍两种查找方式：按位序号查找和按值查找。
1）按位序号查找
按位序号查找操作的基本要求是在单链表中查找线性表中位序号为i的数据元素结点，如果查找成功，则返回其数据元素值。其中i的限制条件是：1≤i≤n（n为单链表的当前长度）。
由于单链表的存储空间不连续，所以它不能像顺序表那样直接通过位序号来定位其存储地址，从而实现随机存取。单链表是一种顺序存取的结构，如果要取第i个结点的数据值，只能从头指针所指的结点开始沿着后继指针依次进行查找。在查找过程中，需引进一个指针变量p和一个计数变量j，p用于指示当前查找到的结点，其初值指向链表中的首结点，j用于记录p所指示的结点在单链表中的位序号，其初值为1，所以整个查找过程就变成从首结点开始沿着后继指针一个一个进行结点“点数”的过程，直到点到第i个结点为止。
【算法2-14】按位序号查找操作算法
Status LocateElem_1（LinkList L，int i，ElemType&e）
//查找线性表中第i个数据元素，如果查找成功，则用e返回其数据元素值
{ LinkList p=L-＞next；//p指向链表中的首结点
int j=1； //j记录p结点在表中的位序号
while（p&&j＜i） //沿着后继指针一个一个“点数”
{ p=p-＞next；
j++；
}
if（! p||j＞i） //i值不合法
return ERROR；
e=p-＞data； //用e返回第i个元素的值
return OK；
}//算法2-14 结束
2）按值查找
按值查找操作的基本要求是在单链表上查找数据元素值与给定值e相等的结点，若查找成功，则返回该结点在单链表中的位序号，否则返回0。
按值查找的实现方法与按位序号查找的实现方法基本相同，只不过在查找过程不但要通过变量j“点数”，而且要不断比较p指针所指向结点的数据值与给定值e是否相等。
【算法2-15】按值查找操作算法
int LocateElem（LinkList L，ElemType e）//按值查找
//查找带头结点的单链表L中值为e的数据元素，如果查找成功，
//则函数返回它在线性表中首次出现时的位序号，否则，函数返回 0
{LinkList p=L-＞next； //p指向链表中的首结点
int j=1； //j记录p结点在表中的位序号
while（p&&p-＞data!=e）
{ p=p-＞next；
j++；
}
if（!p）
return 0； //查找不成功，则函数返回 0
return j； //否则函数返回j
}//算法2-15 结束
由于上面两种查找都是从单链表的表头开始沿着链依次进行比较，所以它们的时间复杂度都为O（n）。
3．单链表上的插入操作
单链表上的插入操作ListInsert（&L，i，e）的基本要求是在单链表的第i个结点之前插入一个数据域值为e的新结点，其中i的限制条件是：1≤i≤n+1（n为单链表的当前长度）。当i=1时，在表头插入新结点；当i=n+1时，在表尾插入新结点。
在单链表中要实现有序对＜ai-1，ai＞到＜ai-1，e＞和＜e，ai＞的改变，并不需要像顺序表那样移动一批数据元素，而只要改变相关结点的后继指针值即可，如图2-10所示。
图2-10 单链表上插入操作前后的状态变化
由图2-10可知，相关结点的后继指针值的改变主要涉及了待插入位置的前驱结点和新插入结点的后继指针值的改变，也就是如图2-10（b）中②和①所标识的两个后继指针。要实现这两个指针值的修改，还得先访问第i个结点的前驱结点，即第i-1个结点。假设p指针指向第i-1个结点，s指针指向新结点，则①和②所标识的指针指向可通过语句s-＞next=p-＞next和p-＞next=s来实现。
C0 2-3-2
根据上述分析，在单链表上进行插入操作的主要步骤归纳如下：
（1）查找到待插入位置的前驱结点。
（2）创建数据域值为x的新结点。
（3）修改相关结点的链指针，使新结点插入到单链表中指定的位置上。
【算法2-16】单链表上的插入操作算法
1 Status ListInsert（LinkList&L，int i，ElemType e）
2 //在单链表L的第i个数据元素之前插入新的元素e，i的合法值是 1≤i≤表长+1
3 { LinkList p=L，s； //p指针指示链表中的头结点
4 int j=0； //j指示p指针所指向的结点在表中的位序号
5 while（p&&j＜i-1） //找到第i个元素的前驱结点，并用p指针指示它
6 { p=p-＞next；
7 ++j；
8 }
9 if（! p||j＞i-1） //i不合法（找不到前驱结点）
1 0 return ERROR；
1 1 s=（LinkList）malloc（sizeof（LNode））；//产生新的结点
12 s-＞data=e；
13 s-＞next=p-＞next； //修改链指针，让新结点插入到第i-1个元素结点p的后面
14 p-＞next=s；
15 return OK；
16 }//算法2-16 结束
注意：
（1）算法中对i合法性的判断与顺序表插入操作类似，i的合法值仍为1≤i≤表长+1。但在单链表中表的长度是隐性值，所以不能直接通过条件（i＜1||i＞表长+1）来判断i的值是不合法的，只能通过算法2-16中的第9行语句来进行判断，其中if中的第一个条件若为真，则说明参数i＞表长+1；若if中的第二个条件为真，则说明参数i＜1。
（2）由于链式存储采用的是动态分配存储空间，所以在插入操作之前无须判断存储空间是否为满。
（3）算法中的第13行和第14行的语句执行顺序不能颠倒，为什么？留给读者思考。
（4）此算法尽管可在常数时间内完成创建新结点和修改链指针的操作，但要查找到第i-1个结点，它的时间复杂度是O（n），所以插入算法的时间复杂度为O（n）。
（5）在带头结点的单链表上进行插入操作，无论插入位置是表头、表尾还是在表的中间，其操作语句都是一致的。但在不带头结点的单链表上进行插入操作，在表头插入和在其他位置插入新结点的操作语句是不相同的，如图2-11所示为在不带头结点的单链表的表头位置插入一个新结点前、后的状态变化。
图2-11 在不带头结点的单链表的表头插入新结点前、后的状态变化
从图2-11中可见，新结点要插入到不带头结点的单链表的头部，需对如图2-11（b）中标识的①和②的链指针进行修改，其对应的执行语句为
① s-＞next=L；
② L=s；
若是在不带头结点的单链表的中间位置或在表尾插入一个新结点，其修改链指针的语句与在带头结点的单链表上的插入操作相同，都为
s-＞next=p-＞next；
p-＞next=s；
因此，若在不带头结点的单链表上实现插入操作，需要分两种情况分别处理，它比在带头结点的单链表上实现插入操作要更复杂，这也是为什么要在单链表中虚加一个头结点的原因。算法2-17给出了具体的实现过程。
【算法2-17】在不带头结点的单链表上的插入操作算法
1 Status ListInsert_Nohead（LinkList&L，int i，ElemType e）
2 //在不带头结点的单链表的第i个结点之前插入一个数据域值为e的新结点
3 { LinkList s，p=L；
4 int j=0；
5 while（p&&j ＜ i-1） //请用i=0，1，2 去测试
6 { p=p-＞next；
7 ++j；
8 }
9 if（!p||j ＞ i-1 ）
return ERROR；
1 0 s=（LinkList）malloc（sizeof（LNode））；//产生新的结点
1 1 s-＞data=e；
12 if（i==1） //插入位置为表头
13 { s-＞next=L；
14 L=s；
15 }
16 else //插入位置为表的中间或表尾时
1 7 { s-＞next=p-＞next；
18 p-＞next=s；
19 }
20 return OK；
21 } //算法2-17 结束
它的时间复杂度为O（n）（n为表长）。
4．单链表上的删除操作
单链表上删除操作ListDelete（&L，i，&e）的基本要求是删除单链表上第i个结点，并且用e返回其值，其中i的限制条件是：1≤i≤表长。
在单链表中要实现有序对＜ai-1，ai＞和＜ai，ai+1＞到＜ai-1，ai+1＞的改变，则要改变被删结点的前驱结点的后继指针值，如图2-12所示。
图2-12 单链表上删除操作前、后的状态变化
与插入操作相同，从单链表中删除一个结点也需要先查找到被删除结点的前驱结点，然后通过修改它的前驱结点的后继指针值来实现线性表中逻辑关系的改变。在单链表上进行删除操作的主要步骤归纳如下：
C0 2-3-3
（1）判断单链表是否为空，若为空则以操作失败结束算法，否则转到（2）。
（2）查找到待删除结点的前驱结点（或确定待删除结点的位置）。
（3）修改链指针，使待删除结点从单链表中脱离出来。
（4）释放被删结点空间。
【算法2-18】单链表上的删除操作算法
1 Status ListDelete（LinkList&L，int i，ElemType&e）
2 //删除单链表L中的第i个数据元素，并用e返回其值，i的合法值是 1≤i≤表长
3 { LinkList p=L，q； //p指针指示链表中的头结点
4 int j=0； //j指示p指针所指向的结点在表中的位序号
5 while（p-＞next&&j＜i-1）//找到被删结点的前驱结点
6 { p=p-＞next；
7 ++j；
8 }
9 if（!p-＞next||j＞i-1） //i不合法（找不到前驱结点）
1 0 return ERROR；
1 1 q=p-＞next； //q指向待删结点
12 p-＞next=q-＞next； //修改链指针让待删结点从链中脱离出来
13 e=q-＞data； //用e保存待删结点的数据元素值
14 free（q）； //释放待删结点空间
15 return OK；
16 } //算法2-18 结束
注意：
（1）对于带头结点的单链表，若为空表，则满足条件L-＞next==NULL。但从上述算法中可以看到，在进行删除操作之前，无须特意去判断链表是否为空，因为算法2-18中第5～10行语句的执行包含了空表的情况。
（2）算法2-18中的第5～8条语句与算法2-16、算法2-17中的第5～8条语句比较，大家不难发现它们同样都是完成查找第i-1个元素的功能，为什么算法2-18中的第5条语句与其他两个算法中的第5条语句却不完全相同呢？请读者要注意其差异化的内容，并思考其原因。
（3）每种操作的基本条件是可根据具体问题改变的，只要条件稍作改变，实现方法就可能不同。但无论条件如何变化，其通用性的处理步骤还是一致的。例如：
①若删除操作的基本条件改为在不带头结点的单链表上删除第i个结点，则也要像插入操作一样分成两种情况分别处理：一种情况删除的是第一个结点；另一种情况删除的是其他位置的结点。
②若删除操作的基本条件改为在带头结点的单链表上删除数据域值为e的结点。要完成此操作，首先仍然需要查找到数据域值为e的结点的前驱结点，只不过实现语句就不再是用算法2-18中第5～8行的语句，而应将此部分改为
while（p-＞next!=NULL&&p-＞next-＞data!=e） //沿着链依次查找数据域值为e的结点
p=p-＞next；
此条件下的删除操作还需考虑在单链表中不含数据域值为e的结点的情况。如果含有数据域值为e的结点（即待删结点存在），则后面的处理步骤与算法2-18中从第12条起的实现语句完全相同。
单链表上的删除操作与插入操作相同，它的时间代价也是花费在查找待删除结点的前驱结点上，所以时间复杂度仍为O（n）。
5．单链表的输出操作
由于链式存储是一种顺序存取的结构，所以要输出单链表中各结点的数据元素值，只要从首结点出发，沿着后继指针在对每一个结点进行遍历的过程中将其数据域的值输出即可。
【算法2-19】输出操作算法
void DisplayList（LinkList L）
//输出单链表L中各数据元素值
{ LinkList p=L-＞next； //p指向链表的首结点
while（p）
{ printf（"%4d"，p-＞data）； //输出p指针所指结点的数据值
p=p-＞next； //p指针后移
}
printf（"\n"）；
}//算法2-19 结束
6．单链表的建立操作
单链表是一种动态存储结构，它不需要预先分配存储空间。生成单链表的过程是一个结点“逐个插入”的过程，它的总体思想是从一个空表开始，依次产生新结点，并将新结点插入当前形成的单链表中。根据插入位置的不同，可将创建单链表的方法分成两种：一种叫头插法（逆位序法）；另一种叫尾插法（顺位序法）。
1）头插法创建单链表
头插法创建单链表每次都是将新结点插入到当前形成的单链表的表头，其插入过程如图2-13所示。
图2-13 用头插法创建单链表的过程
从图2-13可见，头插法是从表尾到表头逆向创建单链表的过程，所以读入的数据顺序与创建形成的单链表的结点顺序相反，即若读入的数据顺序为（an，an-1，an-2，…，a1），则创建的单链表的结点顺序为（a1，a2，…，an-1，an），所以也将头插法叫作逆位序法。
【算法2-20】用头插法逆位序创建单链表的算法
Status CreatLinkList（LinkList&L）
//用头插法创建一个带头结点的单链表——方法一
{ ElemType node；
L=（LinkList）malloc（sizeof（LNode））；//先创建一个空链表
L-＞next=NULL；
//请求输入线性表中各个元素，以 0 结束
printf（"\n请逆位序输入数据元素值（以 0 结束）：\n "）；
scanf（"%d"，&node）；
while（node!=0） //将非零元素结点依次插入链表的头部
{ LinkList p=（LinkList）malloc（sizeof（LNode））；
if（! p）
return ERROR；
p-＞data=node；
p-＞next=L-＞next；
L-＞next=p；
scanf（"%d"，&node）；
}
return OK；
}//算法2-20 结束
如果在前面对单链表的初始化操作和插入操作已经实现的前提下，用头插法创建单链表的算法也可描述如下：
【算法2-21】
Status CreatLinkList_1（LinkList&L）
//用头插法创建一个带头结点的单链表——方法二
{ ElemType node；
InitList（L）； // 创建一个空表
printf（"\n请逆位序输入数据元素值（以 0 结束）：\n"）；
scanf（"%d"，&node）；
while（node）
{ ListInsert（L，1，node）； //将node新结点插入表头
scanf（"%d"，&node）；
}
return OK；
}//算法2-2 1 结束
2）尾插法创建单链表
尾插法创建单链表每次都是将创建的新结点插入当前形成的单链表的表尾，其插入过程如图2-14所示。
图2-14 用尾插法创建单链表的过程
尾插法是从表头到表尾的创建过程，所以读入的数据顺序与创建成立的单链表的结点顺序相同。
【算法2-22】用尾插法创建单链表操作算法
Status CreatLinkList_2（LinkList&L）
//用尾插法创建一个带头结点的单链表
{ ElemType node；
L=（LinkList）malloc（sizeof（LNode））； //先创建一个空链表
L-＞next=NULL；
LinkList r=L，p； //其中r始终指向链表当前的尾结点
printf（"\n please input the elem（end with 0）：\n "）；//请求输入线性表中各个元素，以 0 结束
scanf（"%d"，&node）；
while（node!=0） //将非零元素结点依次插入链表尾部
{ p=（LinkList）malloc（sizeof（LNode））； //产生新结点p
if（! p）
return ERROR；
p-＞data=node；
p-＞next=NULL；
r-＞next=p； //将新结点p链接到链表的尾部
r=p； //使r指向新的尾结点
scanf（"%d"，&node）；
}
return OK；
}//算法2-22 结束
这个创建单链表的操作同样可以通过调用单链表的初始化操作和插入操作来完成。请读者思考完成。
2.3.3 单链表应用举例
本节将通过三个实例来进一步分析单链表上其他操作的实现方法。其实对于任何一个求解问题都可以从两种方法去考虑：一种是采用前面已经实现的基本操作来完成规定的操作；另一种就是不利用任何基本操作来完成规定的操作。为节省篇幅，下文在无特殊说明的情况下都只给出采用第二种方法的实现算法。
【例2-6】已知一个单链表L和一个指向单链表中非头结点的指针p，现要求将一个已知的结点s（s为指向结点的指针）插入p结点的前面。试设计算法Insert（&L，p，s），并要求算法的时间复杂度为O（1）。
【分析】本题涉及的主要知识点是单链表上的插入操作。假设，已知的单链表及指针p的指向如图2-15（a）所示，按要求将已知的s结点88插入p结点12的前面后所形成的单链表如图2-15（b）所示。要完成这种操作，根据上节中给出的在单链表上实现插入操作的主要步骤可知，需要先查找到p的前驱结点，而此查找过程的时间复杂度为O（n），显然不满足题目要求。所以本题按这种常规的插入操作方法是行不通的。
图2-15 在单链表上插入s结点的前、后状态
图2-16给出了满足题目要求的一种实现方法，它是先将s结点插入p结点的后面，然后将p结点和s结点的数据域的值置换，这样既满足了逻辑关系，又能使算法的时间复杂度为O（1）。
图2-16 在单链表上插入s结点的前、后状态
【算法2-23】例2-6的设计算法
Status Insert（LinkList&L，LinkList p，LinkList s）
//在单链表L的p结点之前插入一个s结点
{
s-＞next=p-＞next； //先将s结点插入p结点之后
p-＞next=s；
ElemType temp=p-＞data； //再将s结点与p结点的数据域值进行置换
p-＞data=s-＞data；
s-＞data=temp；
return OK；
}//算法2-23 结束
【例2-7】用单链表保存n个整数，且整数的绝对值不大于m。现要求设计一个时间复杂度尽可能高效的算法，删除单链表中“多余”的结点，即将数据域的绝对值相同的结点，仅保留第一次出现的结点。例如：若给定的单链表如图2-17（a）所示，则删除“多余”结点后的单链表如图2-17（b）所示。
图2-17 删除“多余”结点前、后的单链表
【分析】本题涉及的主要知识点是单链表上的删除操作，要删除某个结点，首先就要找到被删除结点的前驱结点。为了找到数据域的绝对值相等的结点的前驱，最容易想到的方法是针对单链表中的每一个结点，再对单链表中该结点之后的所有结点扫描一遍，扫描过程中如遇到与该结点数据域的绝对值相等的结点，则将后面遇到的这个结点从单链表中删除，按这种设计思想则要对单链表近似扫描n-1遍，其算法的时间复杂度为O（n2）。是否还有时间复杂度更高效的设计思想呢？下面给出采用牺牲空间来赢得时间的设计思想。使用一个辅助数组来记录单链表中已出现的数据值，从而只需对单链表扫描一遍。具体实现方法是：先设置辅助数组a，因单链表结点中数据域的绝对值不大于m，则a的容量设置为m+1，并且数组各元素均赋初值0；再依次扫描单链表中各结点，假设当前扫描到的结点的数据绝对值为i，则检查a[i]的值是否为0，如果为0，则保留该结点，并修改a[i]的值为1；否则，就从单链表中删除该结点。
【算法2-24】例2-7的设计算法
Status DeleteSame（LinkList&L，int m）
//删除单链表L中数据域的绝对值相同的结点，其中结点数据域的绝对值不大于m
{ LinkList p=L，q； //p是扫描指针，q用于记载待删结点
int *a=（int *）malloc（（m+1）*sizeof（int））；//申请分配一个容量为m+1的辅助数组空间
if（!a） //分配空间失败
exit（OVERFLOW）；
for（int i=0；i＜m+1；i++） //数组元素置初始值为 0
a[i]=0；
while（p-＞next）
//求结点数据域中的绝对值
{ int i=（p-＞next-＞data）＞=0? p-＞next-＞data：-p-＞next-＞data；
if（a[i]==0） //判断该结点的数据值是否已出现过
{ a[i]=1； //首次出现
p=p-＞next；
}
else //重复出现，则要删除
{ q=p-＞next； //用q指针指向待删结点
p-＞next=q-＞next； //修改链指针，使q从链中脱离
free（q）； //释放被删结点的空间
}
}
free（a）； //释放辅助数组空间
return OK；
}//算法2-24 结束
【例2-8】设计一个算法，将两个按元素值递增有序的单链表合并为一个非递增有序的单链表，并要求空间复杂度为O（1）。
【分析】本题涉及的主要知识点是单链表上的查找、插入操作。假设已知两个递增有序的单链表L1、L2如图2-18（a）所示，则按题目要求合并后形成的非递增的有序单链表L如图2-18（b）所示。因题目中要求空间复杂度为O（1），则在合并后的结果单链表中，所有结点空间必须采用链表L1与L2中的原结点空间，不能产生任何新的结点。本题的算法设计思想与例2-2类似，不同点在于：均从两个链表的首结点开始扫描两个链表时，是将数据元素值较小的结点依次插入合并后的结果单链表L的头部，而不是尾部。因题目要求结果单链表并不是按递增顺序排列，而是按非递增的顺序排列，这是读者需要特别注意的地方。在算法的实现过程中，为了扫描已知的两个链表，需要引进两个工作指针，假设为p和q，p与q的初始值都指向两个有序单链表的首结点。
图2-18 两个有序单链表合并前、后的状态
【算法2-25】例2-8的设计算法
Status MergeLinkList（LinkList L1，LinkList L2，LinkList&L）
//将两个递增有序的单链表L1，L2 合并成一个非递增有序的单链表L
//p，q分别为链表L1，L2的工作指针，初值指向链表的首结点
{ LinkList r，p=L1-＞next，q=L2-＞next；
L=L1； //以L1的头结点作为合并后的结果链表L的头结点
L-＞next=NULL； //此时L为空表
while（p&&q） //当两个链表均不空时
{ if（p-＞data＜=q-＞data）
{ r=p-＞next； //将p的后继结点暂存于r
p-＞next=L-＞next；//将p结点插入结果链表的头部
L-＞next=p；
p=r； //恢复p为当前L1中待比较的结点
}
else
{ r=q-＞next； //将q的后继结点暂存于r
q-＞next=L-＞next；//将q结点插入结果链表的头部
L-＞next=q；
q=r； //恢复q为当前L2中待比较的结点
}
}
while（p） //将链表L1中的剩余结点依次插入结果链表的头部
{ r=p-＞next；
p-＞next=L-＞next；
L-＞next=p；
p=r；
}
while（q） //将链表L2中的剩余结点依次插入结果链表的头部
{ r=q-＞next；
q-＞next=L-＞next；
L-＞next=q；
q=r；
}
return OK；
}//算法2-25 结束
2.3.4 其他链表
在实际应用中，为了使程序代码更简洁、高效，可以对单链表的结构调整或改进，常见的方法有循环链表、双向链表和双向循环链表等。特别需要指出的是：名词“链表”有两种含义，一是指单链表，二是指各种形式的链式存储结构，所以“链表”的确切含义应取决于上下文，必须分清楚。
1．循环链表
循环链表（Circular Linked List）也被称为环形链表。其中循环单链表的结构与单链表相似，只是将单链表的首尾相连，即将单链表的最后一个结点的后继指针指向第一个结点，从而构成一个环状链表，如图2-19所示。
图2-19 带头结点的循环单链表的存储结构
在循环链表中，每一个结点都有后继，所以从循环链表的任一个结点出发都可以访问到链表中的所有结点。在某些情况下，需要利用这一特性而将许多结点连接成循环链表。例如，在操作系统的资源管理中，当n个进程在同一段时间使用同一种资源时，任一进程在使用前必须确定没有其他进程访问该资源，所以这n个进程先都被放在一个循环链表中进行等待。系统则通过一个指针沿着循环链表逐个结点（进程）进行检索并激活其中某进程。
循环链表的操作算法与单链表的操作算法基本一致。其差别，一方面在于判定单链表中访问的是否是最后一个结点的条件不再是它的后继是否为空，而是它的后继是否为头结点。例如，在非循环链表中的操作语句内容若为while（p）或while（p-＞next），则在循环链表中需改为while（p!=L）或while（p-＞next!=L），等。另一方面在于对循环链表判空的条件不再是判断L-＞next是否为空，而是要判断L-＞next是否为L[从图2-19（b）可知]。所以，循环链表上基本操作的实现算法只要在非循环链表的基本操作算法基础上稍加修改即可得到，在此就不具体介绍。
一个已知的循环链表，既可以用头指针来标识它，也可以用尾指针来标识它，还可头、尾指针都用，这需根据实际解决的问题来决定。有些情况下仅用一个尾指针（指向表尾结点的指针）tail来标识循环链表，比仅用一个头指针来标识它更为优越。因为循环链表的第一个结点可通过表尾指针访问，所以用尾指针标识的循环链表不论是访问第一个结点还是访问最后一个结点其时间复杂度都是O（1）；若仅用头指针标识循环链表，则访问第一个结点的时间复杂度为O（1），但访问最后一个结点的时间复杂度为O（n）。所以在实际应用中，往往仅使用尾指针来标识循环链表，这样可简化某些操作。例如：要实现将一个线性表{b1，b2，…，bi，…，bm}合并到另一个线性表{a1，a2，…，ai，…，an}的尾部，从而形成线性表{a1，a2，…，ai，…，an，b1，b2，…，bi，…，bm}的操作，则可考虑采用通过尾指针标识的循环单链表来作为两个线性表的存储结构。这样，合并两个线性表时仅需将一个表的表尾和另一个表的表头相接即可，其时间复杂度和空间复杂度都为O（1）。图2-20为仅用尾指针标识的两个循环链表在合并前、后的状态示意图。
图2-20 两个循环单链表合并前、后的状态
图2-20中用①②③标明了合并过程中所需要修改的链指针，它们实现的语句序列分别是：
① p=tailb-＞next； //记下第2个表的头结点
② tailb-＞next=taila-＞next； //第2个表的表尾与第 1个表的表头相连
③ taila-＞next=p-＞next； //第 1个表的表尾与第2个表的表头相连
最后还需将第2个表的头结点空间释放，合并后的循环链表是通过原来第2个表的尾指针来标识的。
循环单链表在实际问题求解中也有着较广泛的应用，如：猴子选王问题、约瑟夫问题、Josephus问题等的求解，都可借助循环单链表来实现。后面第2.4节给出了Josephus问题的求解方法。
C0 2-3-4
2．双向链表
在单链表的结点中仅仅包含指向其后继结点的指针，所以要查找一个指定结点的后继结点，只要顺着它的后继指针即可一次性找到，其时间复杂度为O（1）。但若要查找一个指定结点的前驱结点，则要从单链表的表头开始沿着后继指针链依次进行查找，其时间复杂度为O（n），这是快速进行链表操作的一大障碍。为克服单链表这一单向性的缺点，可对单链表进行重新定义，使其结点具有两个指针域，一个指针指向前驱结点，另一个指针指向后继结点。这种类型的链表被称为双向链表，如图2-21所示是带头结点的双向链表的存储结构。
图2-21 双向链表的存储结构
双向链表的存储结构描述如下：
typedef struct DuLNode
{ ElemType data； //数据域
struct LNode *prior； //前驱指针域
struct LNode *next； //后继指针域
}DuLNode，*DuLinkList；
双向链表也与单链表一样，只要首尾相连即可构成双向循环链表，如图2-22所示为双向循环链表的存储结构。在双向循环链表中存在两个环，它们分别由前驱指针和后继指针连接而成。
图2-22 双向循环链表的存储结构
在双向链表中，要实现的某种操作若只涉及一个后继方向的指针，则它们的算法描述与单链表相应操作的算法一致，例如：ListLength（L），GetElem（L，i，&e），LocateElem（L，e）和DisplayList（L）等。但对于插入操作和删除操作的算法要比单链表相应操作的算法更复杂一些，因为它要涉及对两个指针域值的修改。下面以循环双向链表为例，分别介绍它的初始化插入操作和删除操作的实现方法。
1）循环双向链表的初始化操作
从图2-22（b）可知，一个空的双向循环链表只含一个头结点，且头结点的前驱指针和后继指针都指向头结点自身，从而使其构成一个空环。
【算法2-26】双向链表上的初始化操作算法
Status InitList（LinkList&L）
//创建一个带头结点的空双向链表L
{ L=（DuLinkList）malloc（sizeof（DuLNode））；//为头结点分配空间，并使L指针指向它
L-＞next=L-＞prior=L； //将头结点的前驱指针域和后继指针域均指向头结点
}//算法2-26 结束
2）循环双向链表上的插入操作
在单向的链表中，为了插入新结点时修改链指针的方便，在插入操作之前需先找到插入位置的前驱结点。但在双向链表中，在插入操作之前无论是先找到插入位置的结点，还是找到插入位置的前驱结点，都能比较方便地对相关链指针进行修改。如图2-23和图2-24所示分别给出了这两种情况下在插入前、后其指针的状态变化情况。而且在图中用①②③④标明了在双向链表中进行插入操作时需要完成4个指针的修改。这也是在描述双向链表上插入操作算法时与单向链表上的插入操作算法描述不相同的地方。请读者特别要注意修改这4个指针的实现语句。图2-23中修改指针对应的语句序列分别为：
图2-23 在双向链表的第i个结点p之前插入一个新结点时的指针状态变化
图2-24 在双向链表的第i-1个结点p之后插入一个新结点时的指针状态变化
① s-＞next=p；
② s-＞prior=p-＞prior；
③ s-＞prior-＞next=s；
④ p-＞prior=s；
注意：其中第④条语句必须放在第②条语句之后执行，否则就不能通过p的前驱指针来访问到第i-1个结点，其他语句的执行顺序可以改变。
图2-24中修改指针对应的语句序列分别为：
① s-＞next=p-＞next；
② s-＞prior=p；
③ p-＞ next=s；
④ s-＞next-＞prior=s；
注意：其中第③条语句必须放在第①条语句之后执行，否则就不能通过p的后驱指针来访问到第i个结点，其他语句的执行顺序可以改变。
下面只给出第一种情况的算法描述，另一种请读者思考完成。它们的时间复杂度都为O（n）（n为表长）。
【算法2-27】双向循环链表上的插入操作算法
Status DuLinkListInsert（DuLinkList&L，int i，ElemType e）
//在双向循环链表L的第i个数据元素之前插入新的元素e，i的合法值是 1≤i≤表长+1
{ DuLinkList p=L-＞next，s； //p指针指示链表中的首结点
int j=1； //j指示p指针所指向的结点在表中的位序号
while（p!=L&&j＜i） //确定插入位置（找到第i个元素结点）
{ p=p-＞next；
++j；
}
if（j !=i） //i不合法
return ERROR；
s=（DuLinkList）malloc（sizeof（DuLNode））；//产生新的结点
s-＞data=e；
s-＞next=p； //①修改链，让新结点插入到第i个元素结点p的前面
s-＞prior=p-＞prior； //②
s-＞prior-＞next=s； //③
p-＞prior=s； //④
return OK；
}//算法2-27 结束
3）循环双向链表上的删除操作
在双向链表上删除一个指定结点之前，也可以先找到待删除的结点，或者先找到待删除结点的前驱，然后再修改相关指针。如图2-25和图2-26所示分别给出了这两种情况下在删除前、后其指针的状态变化情况。并在图中用①②标明了在双向链表中进行删除操作时需要完成2个指针的修改，下面分别给出它们的实现语句。
图2-25 在双向链表中删除第i个结点p时指针状态变化
图2-26 在双向链表中删除第i-1个结点p之后的结点时指针状态变化
C0 2-3-5
图2-25中修改指针对应的语句序列分别为
① p-＞prior-＞next=p-＞next；
② p-＞next-＞prior=p-＞prior；
图2-26中修改指针对应的语句序列分别为
q=p-＞next； //用q记下待删结点
① p-＞next=q-＞next；
② q-＞next-＞prior=p；
下面也只给出第一种情况的算法描述，其算法的时间复杂度为O（n）（n为表长）。
【算法2-28】双向循环链表上的删除操作算法
Status DuLinkListDelete（DuLinkList&L，int i，ElemType&e）
//删除双向循环链表L中的第i个数据元素，并用e返回其值，i的合法值是 1≤i≤表长
{ DuLinkList p=L-＞next； //p指针指示链表中的首结点
int j=1； //j指示p指针所指向的结点在表中的位序号
while（p!=L&&j＜i） //确定插入位置（找到第i个元素结点）
{ p=p-＞next；
++j；
}
if（P=L‖j＞i） //i不合法
return ERROR；
p-＞prior-＞next=p-＞next；//①
p-＞next-＞prior=p-＞prior；//②
e=p-＞data；
free（p）；
return OK；
}//算法2-28 结束