2.4 双链表和循环双链表_数据结构简明教程（第2版）微课版-QQ阅读中文都市网

上QQ阅读APP看书，第一时间看更新

2.4 双链表和循环双链表

本节介绍另一种链式存储结构即双链表，包括双链表和循环双链表。

2.4.1 双链表的定义

2.3节讨论的单链表是用一个后继指针表示结点间的逻辑关系。本节介绍的双链表是用两个指针表示结点间的逻辑关系（因为线性表中每个元素的前驱元素和后继元素是唯一的），因此称为双链表。

在单链表中，每个结点的指针指向其后继结点，故从任一结点找其后继结点很方便，但要找前驱结点比较困难。在双链表中，增加了一个指向其前驱结点的指针域prior，这样形成的链表就有两条不同方向的链，使得从给定结点出发查找其前驱结点和查找其后继结点一样方便。

仍假设数据元素的类型为ElemType，双链表中结点的类型声明如下。

与单链表一样，双链表也分为非循环双链表（简称为双链表）和循环双链表两种。除特别指出外，本章讨论的双链表均指带头结点的双链表。

2.4.2 线性表基本运算在双链表上的实现

在带头结点的双链表中，通常头结点的数据域不存储任何特定的信息，尾结点的next域置为NULL。如图2.33所示是一个带头结点的双链表，通过头结点指针L（头指针）标识该双链表，其中含一个头结点和n个数据结点。

图2.33 带头结点的双链表

下面讨论双链表中线性表基本运算算法的实现过程。

1．双链表基本运算算法

在双链表中实现线性表基本运算算法如下。

1）初始化线性表运算算法

创建一个空的双链表，它只有一个头结点，由L指向它，该结点的next域和prior域均为空，data域未设定任何值，如图2.34所示。对应的算法如下。

图2.34 一个空的双链表

本算法的时间复杂度为O（1）。

2）销毁线性表运算算法

销毁一个双链表中的所有结点的算法思路与单链表的销毁算法相同，对应的算法如下。

本算法的时间复杂度为O（n），其中，n为双链表L中数据结点的个数。

3）求线性表长度运算算法

其设计思路与单链表的求表长算法完全相同，对应的算法如下。

本算法的时间复杂度为O（n），其中，n为双链表L中数据结点的个数。

4）求线性表中第i个元素运算算法

其设计思路与单链表的求线性表中第i个元素运算算法完全相同，对应的算法如下。

本算法的时间复杂度为O（n），其中，n为双链表L中数据结点的个数。

5）按值查找运算算法

其设计思路与单链表的按值查找运算算法完全相同，对应的算法如下。

本算法的时间复杂度为O（n），其中，n为双链表L中数据结点的个数。

6）插入元素运算算法

先在双链表中查找到第i—1个结点，若成功找到这样的结点p，创建一个以x为值的新结点s，在p结点之后插入s结点。在双链表中p结点之后插入s结点的操作如图2.35所示，其步骤如下。

图2.35 在双链表的p结点之后插入新结点s

（1）将结点s的next域指向结点p的下一个结点（s—>next=p—>next）。

（2）若结点p不是尾结点（若结点p是尾结点，只插入结点s作为新尾结点），则将结点p的后继结点的prior域指向结点s（p—>next—>prior=s）。

（3）结点s的prior域指向p结点（s—>prior=p）。

（4）将结点p的next域指向结点s（p—>next=s）。

注意：上述插入步骤中，通常将p—>next域的修改放在最后执行，否则可能出现由于找不到其后继结点而导致的插入错误。

对应的算法如下。

本算法的时间复杂度为O（n），其中，n为双链表L中数据结点的个数。

说明：在双链表中可以通过一个结点找到其前驱结点，所以插入算法也可以改为：在双链表中找到第i个结点p，然后在p结点之前插入新结点。

7）删除结点运算算法

先在双链表中查找到第i个结点，若成功找到这样的结点p，通过前驱结点和后继结点的指针域改变来删除p结点。在双链表中删除p结点（其前驱结点为结点pre）的操作如图2.36所示，其步骤如下。

（1）若结点p不是尾结点，则将其后继结点的prior域指向pre结点（p—>next—>prior= pre）。

（2）将结点pre结点的next域改为指向p结点的后继结点（pre—>next=p—>next）。

图2.36 在双链表中删除p结点

对应的算法如下。

本算法的时间复杂度为O（n），其中，n为双链表L中数据结点的个数。

8）输出线性表运算算法

其设计思路与单链表的输出元素值运算算法完全相同，对应的算法如下。

本算法的时间复杂度为O（n），其中，n为双链表L中数据结点的个数。

说明：将双链表结点类型声明及其基本运算函数存放到DLinkNode.cpp文件中。

当双链表的基本运算设计好后，给出以下主函数调用这些基本运算函数，读者可以对照程序执行结果进行分析，进一步体会双链表各种操作的实现过程。

上述程序的执行结果如图2.9所示。

2．创建整体双链表的算法

假设通过一个含有n个数据的数组来建立整个双链表。建立整体双链表的常用方法有如下两种。

1）头插法建表

该方法从一个空双链表（仅含一个L指向的头结点）开始，读取数组a（含有n个元素）中的一个元素，生成一个新结点s，将读取的数据元素存放到新结点的数据域中，然后将新结点s插入到当前链表的表头上；再读取数组a的下一个元素，采用相同的操作建立新结点s并插入到双链表L中，直到数组a中所有元素读完为止。

采用头插法建表的算法如下。

本算法的时间复杂度为O（n）。

若数组a包含4个元素1、2、3和4，则调用CreateListF（L，a，4）建立的双链表如图2.37所示，从中看到，双链表L中数据结点的次序与数组a的元素次序正好相反。

图2.37 采用头插法建立的双链表L

2）尾插法建表

该方法从一个空双链表（仅含一个L指向的头结点）开始，读取数组a（含有n个元素）中的一个元素，生成一个新结点s，将读取的数据元素存放到新结点的数据域中，然后将新结点s插入到当前链表的表尾上；再读取数组a的下一个元素，采用相同的操作建立新结点s并插入到双链表L中，直到数组a中所有元素读完为止。

由于尾插法每次将新结点插到当前链表的表尾上，为此增加一个尾指针tc，使其始终指向当前链表的尾结点。

采用尾插法建表的算法如下。

本算法的时间复杂度为O（n）。

若数组a包含4个元素1、2、3和4，则调用CreateListR（L，a，4）建立的双链表如图2.38所示，从中看到，双链表L中数据结点的次序与数组a的元素次序相同。

图2.38 采用尾插法建立的双链表L

2.4.3 双链表的算法设计示例

【例2.22】假设一个整数序列采用双链表L存储，设计一个算法删除其中第一个最大值的结点。

解：用p扫描双链表L，用maxp保存找到的第一个最大值的结点（初值为p）。最后通过其前驱结点pre和后继结点post删除maxp结点并释放其空间，如图2.39所示。对应的算法如下。

从本例算法看出，在双链表中删除一个结点不必像单链表中一样要已知其前驱结点，只需找到这个被删结点即可（实际上在双链表找到被删结点后，就可以通过其prior、next域找到其前驱和后继结点，然后通过修改前驱和后继结点的相关指针域实现删除操作）。

图2.39 删除第一个最大值的结点

【例2.23】设有一个双链表L，设计一个算法查找第一个元素值为x的结点，将其与后继结点进行交换。

解：先找到第一个元素值为x的结点p，post指向其后继结点，如图2.40所示。再删除p结点，将p结点插入到post结点之后。

图2.40 查找值为x的结点

对应的算法如下。

2.4.4 循环双链表

与循环单链表一样，也可以将双链表改造为循环双链表，即将双链表中尾结点的next域由原来为NULL改为指向头结点，将头结点的prior域由原来没有使用改为指向尾结点，这样得到循环双链表。

循环双链表的结点类型与双链表的结点类型相同，也采用前面声明的DLinkNode类型。如图2.41所示是一个带头结点的含n个数据结点的循环双链表。

在循环双链表中有两个环，从任一给定的结点出发可以找到表中其他结点。实际上与双链表相比，循环双链表的最大特点是可以快速找到尾结点，查找时间为O（1）。

循环双链表的整体建表算法也分为头插法建表和尾插法建表，和双链表的相似，这里不再介绍。

图2.41 带头结点的循环双链表

在循环双链表中线性表基本运算算法的实现如下。

图2.42 一个空的循环双链表

1．初始化线性表运算算法

创建一个空的循环双链表，它只有一个头结点，由L指向它，该结点的next域和prior域均指向该头结点，data域未设定任何值，如图2.42所示。对应的算法如下。

      void InitList(DLinkNode ∗ &L)
      {    L=(DLinkNode ∗)malloc(sizeof(DLinkNode));
           L—>prior=L—>next=L;
      }

本算法的时间复杂度为O（1）。

2．销毁线性表运算算法

销毁一个循环双链表中的所有结点的算法思路与循环单链表的销毁算法相同，对应的算法如下。