2.3 线性表的链式表示与实现

在顺序表中，由于逻辑上相邻的元素其物理位置也相邻，因此可以随机存取顺序表中的任何一个元素。但是，顺序表也存在着这样的缺点：

● 插入和删除运算需要移动大量的元素。

● 顺序表中的存储空间必须事先分配好，而事先分配的存储单元的大小可能不适合问题的需要。

采用链式存储的线性表称为链表，链表可以分为单链表、双向链表、循环链表。

2.3.1 单链表的存储结构

所谓线性表的链式存储，是指采用一组任意的存储单元存放线性表中的元素。这组存储单元可以是连续的，也可以是不连续的。为了表示这些元素之间的逻辑关系，除了需要存储元素本身的信息外，还需要存储指示其后继元素的地址信息。这两部分组成的存储结构，称为结点。结点包括两个域：数据域和指针域。其中，数据域存放数据元素的信息，指针域存放元素的直接后继的存储地址。如图2.8所示。

通过指针域把n个结点根据线性表中元素的逻辑顺序链接在一起，就构成了链表。由于链表中的每个结点的指针域只有一个，这样的链表称为线性链表或者单链表。

例如，一个采用链式存储结构的线性表（Yang,Zheng, Feng,Xu,Wu,Wang,Geng）的存储结构如图2.9所示。

存取链表中的元素时，必须从头指针head出发，头指针head指向链表的第一个结点，从头指针head可以找到链表中的每一个元素。

单链表的每个结点的地址存放在其直接前驱结点的指针域中，而第一个结点没有直接前驱结点，因此需要一个头指针指向第一个结点。同时，由于表中的最后一个元素没有直接后继，需要将单链表的最后一个结点的指针域置为“空”（NULL）。

一般情况下，我们只关心链表的逻辑顺序，而不关心链表的实际存储位置。通常用箭头代替指针来连接结点序列。因此，图2.9所示的线性表可以形象化为如图2.10所示的序列。

有时为了操作上的方便，在单链表的第一个结点之前增加一个结点，称为头结点。头结点的数据域可以存放线性表的附加信息，如线性表的长度；头结点的指针域存放第一个结点的地址信息，即指向第一个结点。头指针指向头结点，不再指向链表的第一个结点。带头结点的单链表如图2.11所示。

若带头结点的链表为空链表，则头结点的指针域为“空”，如图2.12所示。

单链表的存储结构用C语言描述如下：

其中，ListNode为链表的结点类型，LinkList为指向链表结点的指针类型。如果有定义：

则定义了一个链表，L指向该链表的第一个结点。它和下面的定义含义相同：

对于不带头结点的链表，如果链表为空，则有L=NULL；对于带头结点的链表，如果链表为空，则L->next=NULL。

2.3.2 单链表上的基本运算

单链表上的基本运算包括链表的建立、单链表的插入、单链表的删除、单链表的长度等。带头结点的单链表的运算具体实现如下（以下算法实现文件保存在“LinkList.h”中）。

（1）单链表的初始化操作。

（2）判断单链表是否为空。

（3）按序号查找操作。链表是一种随机存取结构，只能从头指针开始存取元素。因此，要查找单链表中的第i个元素，需要从单链表的头指针h出发，利用结点的next域依次访问链表的结点，并进行比较操作。利用计数器从0开始计数，当计数器为i时，就找到了第i个结点。

（4）按内容查找操作。

（5）定位操作。定位操作是指按内容查找并返回结点的序号的操作。从单链表的头指针出发，依次访问每个结点，并将结点的值与e比较，如果相等，返回该序号表示成功；如果没有值与e相等的元素，返回0表示失败。

（6）插入操作。插入操作就是将元素e插入到链表中指定的位置i，插入成功返回1，否则返回0。

在单链表的第i个位置插入一个新元素e可分为3步进行：

①在链表中找到其直接前驱结点，即第i-1个结点，并由指针pre指向该结点，如图2.13所示。

②动态申请一个新的结点，并由p指向该结点，将值e赋值给p指向结点的数据域，如图2.14所示。

③修改pre和p指向结点的指针域，如图2.15所示。这样就完成了在第i个位置插入结点的操作。

在单链表中插入新结点分为两个步骤：①将新结点的指针域指向第i个结点，即p->next=pre->next；②将直接前驱结点的指针域指向新结点，即pre->next=p。

注意： 插入结点的操作步骤不能反过来，即先执行pre->next=p操作，后执行p->next=pre->next操作是错误的。

（7）删除操作。删除操作就是将单链表中的第i个结点删除，其他结点仍然构成一个单链表。删除成功返回1，否则返回0。

删除单链表中的第i个结点分为以下3个步骤：

①找到第i个结点的直接前驱结点，即第i-1个结点，并将指针pre指向该结点，指针p指向第i个结点，如图2.16所示。

②修改pre和p指向结点的指针域，使p指向的结点与原链表断开，即pre->next=p->next。

③动态释放指针p指向的结点。如图2.17所示。

注意： 在寻找第i-1个结点（被删除结点的前驱结点）时，要保证被删除结点存在，即pre->next->next!=NULL。如果没有该判断条件，且要删除的结点在链表中不存在，就会执行循环后出现p指向NULL指针域，从而造成错误。

（8）求表长。

（9）销毁链表。

2.3.3 单链表应用举例

【例2.3】 利用单链表的基本运算，求A-B。即若单链表B中的元素出现在单链表A中，则从A中删除该元素。

【分析】对于单链表A中的每个元素e，在单链表B中进行查找，如果在B中存在与A中相同的元素，则将元素从A中删除。

算法描述如下：

测试程序如下：

程序的运行结果如图2.18所示。

在具体实现算法A-B时，利用p=Get（B,i）依次取出单链表B中的元素，然后通过pos=LocatePos（A,p->data）在链表A中查找与该值相等的元素，并调用函数DeleteList（A,pos,&e）将A中对应的结点删除。

在该算法中，假设单链表A的长度为m，单链表B的长度为n，则时间主要耗费在A和B中对元素的查找上，算法的时间复杂度为O（m×n）。

上面的算法是通过单链表的基本运算实现的，也可以不用单链表的基本运算实现该算法。

上面算法中，在单链表A中，指针p指向单链表A中与单链表B中要比较的结点，pre指向p的前驱结点，在单链表B中，利用指针q指向B中的第一个结点，依次与A中p指向的结点的元素比较。如图2.19所示。

如果当前A中要比较的是元素a _i ，指针p指向a _i 所在结点，在B中，如果q指向元素b _j 所在结点，而b _j =a _i ，则指针q停止向前比较。在A中，利用指针r指向要删除的结点p，令pre指向p的后继结点，从而使p指向的结点与链表断开，即r=p，pre->next=p->next。如图2.20所示。

然后，p指向链表A中下一个要比较的结点，最后释放r指向的结点。如图2.21所示。

算法DelElem2的时间复杂度也是O（m×n）。

说明： 在算法DelElem2的实现过程中，隐藏了查找元素结点与删除元素结点的实现细节，而在算法DelElem2中，将整个查找过程和删除过程展现得淋漓尽致。

【考研真题】假设一个带有表头结点的单链表，结点结构如下。

假设该链表只给出了头指针list，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点数据域的值，并返回1；否则返回0。要求如下。

（1）描述算法的基本设计思想。

（2）描述算法的详细实现步骤。

（3）根据设计思想和实现步骤，采用程序设计语言描述算法。

【分析】这是一道考研试题，主要考察对链表的掌握程度，这个题目比较灵活，利用一般的思维方式不容易实现。

（1）算法的基本思想：定义两个指针p和q，初始时均指向头结点的下一个结点。p指针沿着链表移动，当p指针移动到第k个结点时，q指针与p指针同步移动；当p指针移动到链表表尾结点时，q指针所指向的结点即为倒数第k个结点。

（2）算法的详细步骤如下。

①令count=0，p和q指向链表的第一个结点。

②若p为空，则转向⑤执行。

③若count等于k，则q指向下一个结点；否则令count++。

④令p指向下一个结点，转向②执行。

⑤若count等于k，则查找成功，输出结点的数据域的值，并返回1；否则，查找失败，返回0。

（3）算法实现代码如下。

2.3.4 循环单链表

1.循环单链表的存储

循环单链表 （Circular Linked List）是一种首尾相连的单链表。在线性链表中，每个结点的指针都指向它的下一个结点，最后一个结点的指针域为空，不指向任何结点，仅表示链表结束。若把这种结构改变一下，使最后一个结点的指针域指向链表的第一个结点，就构成了循环链表。

与单链表类似，循环单链表也可分为带头结点的结构和不带头结点的结构。循环单链表不为空时，最后一个结点的指针域指向头结点。如图2.22所示。

循环单链表为空时，头结点的指针域指向头结点本身。如图2.23所示。

注意： 带头结点的循环单键表为空时，有head->next==head。

有时为了操作上的方便，在循环单链表中只设置尾指针rear而不设置头指针，利用rear指向循环单链表的最后一个结点。如图2.24所示。

利用尾指针可以使有些操作变得简单，例如，要将如图2.25所示的两个循环单链表（尾指针分别为LA和LB）合并成一个链表，只需要将一个表的表尾和另一个表的表头连接即可。如图2.26所示。

合并两个设置尾指针的循环单链表需要三步操作：

①把LA的表尾与LB的第一个结点相连接，即LA->next=LB->next->next。

②释放LB的头结点，即free（LB->next）。

③把LB的表尾与LA的表头相连接，即LB->next=LA->next。

2.循环单链表的应用

【例2.4】 约瑟夫问题。有n个人，编号为1，2，…，n，围成一个圆圈，按照顺时针方向让编号为k的人从1开始报数，报数为m的人出列，从出列的下一个人重新开始报数，报数为m的人出列，一直这样重复下去，直到所有的人都出列。要求编写一个算法，输入n、k和m，依次输出每次出列人的编号。

【分析】解决约瑟夫问题可以分为三个步骤：

（1）建立一个具有n个结点的不带头结点的循环单链表，编号从1到n，代表n个人。

（2）找到第k个结点，即第一个开始报数的人。

（3）编号为k的人从1开始报数，并开始计数，报数为m的人出列即删除该结点。从下一个结点开始继续报数，重复执行步骤（2）和（3），直到最后一个结点被删除。

约瑟夫问题算法描述如下：

测试程序如下：

程序运行结果如图2.27所示。

2.3.5 双向链表

在前面讨论过的单链表和循环链表中，每个结点的指针域只有一个，用来存放后继结点的指针，而没有关于前驱结点的信息。因此，从某个结点出发，只能顺着指针往后查找其他结点。若要查找结点的前驱，这需要从表头结点开始，顺着指针寻找，显然，使用单链表处理不够方便。同样，从单链表中删除一个结点也会遇到类似的问题。为了克服单链表的这种缺点，可以使用双向链表。

1.双向链表的存储结构

双向链表中，每个结点有两个指针域：一个指向直接前驱结点，另一个指向直接后继结点。双向链表的结点结构如图2.28所示。

在双向链表中，每个结点包括3个域：data域、prior域和next域。其中，data域为数据域，存放数据元素；prior域为前驱结点指针域，指向直接前驱结点；next域为后继结点指针域，指向直接后继结点。

双向链表也可分为带头结点和不带头结点两种，带头结点使某些操作更加方便。另外，双向链表也有循环结构，称为双向循环链表。带头结点的双向循环链表如图2.29所示。

双向循环链表为空的情况如图2.30所示，判断带头结点的双循环链表为空的条件是head->prior==head或head->next==head。

在双向链表中，每个结点既有前驱结点的指针域又有后继结点的指针域，因此查找结点非常方便。如果p是指向链表中某个结点的指针，则有p=p->prior->next=p->next->prior。

双向链表的结点类型描述如下：

2.双向链表的插入操作和删除操作

对于双向链表的有些操作，如求链表的长度、查找链表的第i个结点等，与单链表中的算法实现基本没什么差异。但是，对于双向循环链表的插入操作和删除操作，因为涉及的是前驱结点指针和后继结点指针，所以需要修改两个方向的指针。

（1）插入操作

插入操作就是要在双向循环链表的第i个位置插入一个元素值为e的结点。插入成功返回1，否则返回0。

【算法思想】首先找到第i个结点，用p指向该结点。再申请一个新结点，由s指向该结点，将e放入到数据域。然后开始修改p和s指向的结点的指针域：修改s的prior域，使其指向p的直接前驱结点，即s->prior=p->prior；将p的直接前驱结点的next域，使其指向s指向的结点，即p->prior->next=s；修改s的next域，使其指向p指向的结点，即s->next=p；修改p的prior域，使其指向s指向的结点，即p->prior=s。插入操作指针修改情况如图2.31所示。

插入操作算法实现如下。

（2）删除操作

删除操作就是将带头结点的双向循环链表中的第i个结点删除。删除成功返回1，否则返回0。

【算法思想】首先找到第i个结点，用p指向该结点。然后开始修改p指向的结点的直接前驱结点和直接后继结点的指针域，从而将p与链表断开。将p指向的结点与链表断开需要两步：

①修改p的直接前驱结点的next域，使其指向p的直接后继结点，即p->prior->next=p->next。

②修改p的直接后继结点的prior域，使其指向p的直接前驱结点，即p->next->prior=p->prior。

删除操作指针修改情况如图2.32所示。

删除操作算法实现如下。

插入操作和删除操作的时间耗费主要在查找结点上，两者的时间复杂度都为O（n）。

注意： 双向链表的插入操作和删除操作需要修改结点的prior域和next域，因此要注意修改结点指针域的顺序。 tEbkLIQmM3p88H7XW+m0h0IksMxOpA5ScpFhAic0LuqBXsm19jwwe/XEMF4mJBbS