2.4 雙鏈表和循環(huán)雙鏈表

本節(jié)介紹另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)即雙鏈表，包括雙鏈表和循環(huán)雙鏈表。

2.4.1 雙鏈表的定義

2.3節(jié)討論的單鏈表是用一個(gè)后繼指針表示結(jié)點(diǎn)間的邏輯關(guān)系。本節(jié)介紹的雙鏈表是用兩個(gè)指針表示結(jié)點(diǎn)間的邏輯關(guān)系（因?yàn)榫€性表中每個(gè)元素的前驅(qū)元素和后繼元素是唯一的），因此稱為雙鏈表。

在單鏈表中，每個(gè)結(jié)點(diǎn)的指針指向其后繼結(jié)點(diǎn)，故從任一結(jié)點(diǎn)找其后繼結(jié)點(diǎn)很方便，但要找前驅(qū)結(jié)點(diǎn)比較困難。在雙鏈表中，增加了一個(gè)指向其前驅(qū)結(jié)點(diǎn)的指針域prior，這樣形成的鏈表就有兩條不同方向的鏈，使得從給定結(jié)點(diǎn)出發(fā)查找其前驅(qū)結(jié)點(diǎn)和查找其后繼結(jié)點(diǎn)一樣方便。

仍假設(shè)數(shù)據(jù)元素的類型為ElemType，雙鏈表中結(jié)點(diǎn)的類型聲明如下。

與單鏈表一樣，雙鏈表也分為非循環(huán)雙鏈表（簡(jiǎn)稱為雙鏈表）和循環(huán)雙鏈表兩種。除特別指出外，本章討論的雙鏈表均指帶頭結(jié)點(diǎn)的雙鏈表。

2.4.2 線性表基本運(yùn)算在雙鏈表上的實(shí)現(xiàn)

在帶頭結(jié)點(diǎn)的雙鏈表中，通常頭結(jié)點(diǎn)的數(shù)據(jù)域不存儲(chǔ)任何特定的信息，尾結(jié)點(diǎn)的next域置為NULL。如圖2.33所示是一個(gè)帶頭結(jié)點(diǎn)的雙鏈表，通過頭結(jié)點(diǎn)指針L（頭指針）標(biāo)識(shí)該雙鏈表，其中含一個(gè)頭結(jié)點(diǎn)和n個(gè)數(shù)據(jù)結(jié)點(diǎn)。

下面討論雙鏈表中線性表基本運(yùn)算算法的實(shí)現(xiàn)過程。

1．雙鏈表基本運(yùn)算算法

在雙鏈表中實(shí)現(xiàn)線性表基本運(yùn)算算法如下。

1）初始化線性表運(yùn)算算法

創(chuàng)建一個(gè)空的雙鏈表，它只有一個(gè)頭結(jié)點(diǎn)，由L指向它，該結(jié)點(diǎn)的next域和prior域均為空，data域未設(shè)定任何值，如圖2.34所示。對(duì)應(yīng)的算法如下。

本算法的時(shí)間復(fù)雜度為O（1）。

2）銷毀線性表運(yùn)算算法

銷毀一個(gè)雙鏈表中的所有結(jié)點(diǎn)的算法思路與單鏈表的銷毀算法相同，對(duì)應(yīng)的算法如下。

本算法的時(shí)間復(fù)雜度為O（n），其中，n為雙鏈表L中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。

3）求線性表長度運(yùn)算算法

其設(shè)計(jì)思路與單鏈表的求表長算法完全相同，對(duì)應(yīng)的算法如下。

本算法的時(shí)間復(fù)雜度為O（n），其中，n為雙鏈表L中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。

4）求線性表中第i個(gè)元素運(yùn)算算法

其設(shè)計(jì)思路與單鏈表的求線性表中第i個(gè)元素運(yùn)算算法完全相同，對(duì)應(yīng)的算法如下。

本算法的時(shí)間復(fù)雜度為O（n），其中，n為雙鏈表L中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。

5）按值查找運(yùn)算算法

其設(shè)計(jì)思路與單鏈表的按值查找運(yùn)算算法完全相同，對(duì)應(yīng)的算法如下。

本算法的時(shí)間復(fù)雜度為O（n），其中，n為雙鏈表L中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。

6）插入元素運(yùn)算算法

先在雙鏈表中查找到第i—1個(gè)結(jié)點(diǎn)，若成功找到這樣的結(jié)點(diǎn)p，創(chuàng)建一個(gè)以x為值的新結(jié)點(diǎn)s，在p結(jié)點(diǎn)之后插入s結(jié)點(diǎn)。在雙鏈表中p結(jié)點(diǎn)之后插入s結(jié)點(diǎn)的操作如圖2.35所示，其步驟如下。

（1）將結(jié)點(diǎn)s的next域指向結(jié)點(diǎn)p的下一個(gè)結(jié)點(diǎn)（s—>next=p—>next）。

（2）若結(jié)點(diǎn)p不是尾結(jié)點(diǎn)（若結(jié)點(diǎn)p是尾結(jié)點(diǎn)，只插入結(jié)點(diǎn)s作為新尾結(jié)點(diǎn)），則將結(jié)點(diǎn)p的后繼結(jié)點(diǎn)的prior域指向結(jié)點(diǎn)s（p—>next—>prior=s）。

（3）結(jié)點(diǎn)s的prior域指向p結(jié)點(diǎn)（s—>prior=p）。

（4）將結(jié)點(diǎn)p的next域指向結(jié)點(diǎn)s（p—>next=s）。

注意：上述插入步驟中，通常將p—>next域的修改放在最后執(zhí)行，否則可能出現(xiàn)由于找不到其后繼結(jié)點(diǎn)而導(dǎo)致的插入錯(cuò)誤。

對(duì)應(yīng)的算法如下。

本算法的時(shí)間復(fù)雜度為O（n），其中，n為雙鏈表L中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。

說明：在雙鏈表中可以通過一個(gè)結(jié)點(diǎn)找到其前驅(qū)結(jié)點(diǎn)，所以插入算法也可以改為：在雙鏈表中找到第i個(gè)結(jié)點(diǎn)p，然后在p結(jié)點(diǎn)之前插入新結(jié)點(diǎn)。

7）刪除結(jié)點(diǎn)運(yùn)算算法

先在雙鏈表中查找到第i個(gè)結(jié)點(diǎn)，若成功找到這樣的結(jié)點(diǎn)p，通過前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針域改變來刪除p結(jié)點(diǎn)。在雙鏈表中刪除p結(jié)點(diǎn)（其前驅(qū)結(jié)點(diǎn)為結(jié)點(diǎn)pre）的操作如圖2.36所示，其步驟如下。

（1）若結(jié)點(diǎn)p不是尾結(jié)點(diǎn)，則將其后繼結(jié)點(diǎn)的prior域指向pre結(jié)點(diǎn)（p—>next—>prior= pre）。

（2）將結(jié)點(diǎn)pre結(jié)點(diǎn)的next域改為指向p結(jié)點(diǎn)的后繼結(jié)點(diǎn)（pre—>next=p—>next）。

對(duì)應(yīng)的算法如下。

本算法的時(shí)間復(fù)雜度為O（n），其中，n為雙鏈表L中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。

8）輸出線性表運(yùn)算算法

其設(shè)計(jì)思路與單鏈表的輸出元素值運(yùn)算算法完全相同，對(duì)應(yīng)的算法如下。

本算法的時(shí)間復(fù)雜度為O（n），其中，n為雙鏈表L中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。

說明：將雙鏈表結(jié)點(diǎn)類型聲明及其基本運(yùn)算函數(shù)存放到DLinkNode.cpp文件中。

當(dāng)雙鏈表的基本運(yùn)算設(shè)計(jì)好后，給出以下主函數(shù)調(diào)用這些基本運(yùn)算函數(shù)，讀者可以對(duì)照程序執(zhí)行結(jié)果進(jìn)行分析，進(jìn)一步體會(huì)雙鏈表各種操作的實(shí)現(xiàn)過程。

上述程序的執(zhí)行結(jié)果如圖2.9所示。

2．創(chuàng)建整體雙鏈表的算法

假設(shè)通過一個(gè)含有n個(gè)數(shù)據(jù)的數(shù)組來建立整個(gè)雙鏈表。建立整體雙鏈表的常用方法有如下兩種。

1）頭插法建表

該方法從一個(gè)空雙鏈表（僅含一個(gè)L指向的頭結(jié)點(diǎn)）開始，讀取數(shù)組a（含有n個(gè)元素）中的一個(gè)元素，生成一個(gè)新結(jié)點(diǎn)s，將讀取的數(shù)據(jù)元素存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)s插入到當(dāng)前鏈表的表頭上；再讀取數(shù)組a的下一個(gè)元素，采用相同的操作建立新結(jié)點(diǎn)s并插入到雙鏈表L中，直到數(shù)組a中所有元素讀完為止。

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

本算法的時(shí)間復(fù)雜度為O（n）。

若數(shù)組a包含4個(gè)元素1、2、3和4，則調(diào)用CreateListF（L，a，4）建立的雙鏈表如圖2.37所示，從中看到，雙鏈表L中數(shù)據(jù)結(jié)點(diǎn)的次序與數(shù)組a的元素次序正好相反。

2）尾插法建表

該方法從一個(gè)空雙鏈表（僅含一個(gè)L指向的頭結(jié)點(diǎn)）開始，讀取數(shù)組a（含有n個(gè)元素）中的一個(gè)元素，生成一個(gè)新結(jié)點(diǎn)s，將讀取的數(shù)據(jù)元素存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)s插入到當(dāng)前鏈表的表尾上；再讀取數(shù)組a的下一個(gè)元素，采用相同的操作建立新結(jié)點(diǎn)s并插入到雙鏈表L中，直到數(shù)組a中所有元素讀完為止。

由于尾插法每次將新結(jié)點(diǎn)插到當(dāng)前鏈表的表尾上，為此增加一個(gè)尾指針tc，使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。

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

本算法的時(shí)間復(fù)雜度為O（n）。

若數(shù)組a包含4個(gè)元素1、2、3和4，則調(diào)用CreateListR（L，a，4）建立的雙鏈表如圖2.38所示，從中看到，雙鏈表L中數(shù)據(jù)結(jié)點(diǎn)的次序與數(shù)組a的元素次序相同。

2.4.3 雙鏈表的算法設(shè)計(jì)示例

【例2.22】假設(shè)一個(gè)整數(shù)序列采用雙鏈表L存儲(chǔ)，設(shè)計(jì)一個(gè)算法刪除其中第一個(gè)最大值的結(jié)點(diǎn)。

解：用p掃描雙鏈表L，用maxp保存找到的第一個(gè)最大值的結(jié)點(diǎn)（初值為p）。最后通過其前驅(qū)結(jié)點(diǎn)pre和后繼結(jié)點(diǎn)post刪除maxp結(jié)點(diǎn)并釋放其空間，如圖2.39所示。對(duì)應(yīng)的算法如下。

從本例算法看出，在雙鏈表中刪除一個(gè)結(jié)點(diǎn)不必像單鏈表中一樣要已知其前驅(qū)結(jié)點(diǎn)，只需找到這個(gè)被刪結(jié)點(diǎn)即可（實(shí)際上在雙鏈表找到被刪結(jié)點(diǎn)后，就可以通過其prior、next域找到其前驅(qū)和后繼結(jié)點(diǎn)，然后通過修改前驅(qū)和后繼結(jié)點(diǎn)的相關(guān)指針域?qū)崿F(xiàn)刪除操作）。

【例2.23】設(shè)有一個(gè)雙鏈表L，設(shè)計(jì)一個(gè)算法查找第一個(gè)元素值為x的結(jié)點(diǎn)，將其與后繼結(jié)點(diǎn)進(jìn)行交換。

解：先找到第一個(gè)元素值為x的結(jié)點(diǎn)p，post指向其后繼結(jié)點(diǎn)，如圖2.40所示。再刪除p結(jié)點(diǎn)，將p結(jié)點(diǎn)插入到post結(jié)點(diǎn)之后。

對(duì)應(yīng)的算法如下。

2.4.4 循環(huán)雙鏈表

與循環(huán)單鏈表一樣，也可以將雙鏈表改造為循環(huán)雙鏈表，即將雙鏈表中尾結(jié)點(diǎn)的next域由原來為NULL改為指向頭結(jié)點(diǎn)，將頭結(jié)點(diǎn)的prior域由原來沒有使用改為指向尾結(jié)點(diǎn)，這樣得到循環(huán)雙鏈表。

循環(huán)雙鏈表的結(jié)點(diǎn)類型與雙鏈表的結(jié)點(diǎn)類型相同，也采用前面聲明的DLinkNode類型。如圖2.41所示是一個(gè)帶頭結(jié)點(diǎn)的含n個(gè)數(shù)據(jù)結(jié)點(diǎn)的循環(huán)雙鏈表。

在循環(huán)雙鏈表中有兩個(gè)環(huán)，從任一給定的結(jié)點(diǎn)出發(fā)可以找到表中其他結(jié)點(diǎn)。實(shí)際上與雙鏈表相比，循環(huán)雙鏈表的最大特點(diǎn)是可以快速找到尾結(jié)點(diǎn)，查找時(shí)間為O（1）。

循環(huán)雙鏈表的整體建表算法也分為頭插法建表和尾插法建表，和雙鏈表的相似，這里不再介紹。

在循環(huán)雙鏈表中線性表基本運(yùn)算算法的實(shí)現(xiàn)如下。

1．初始化線性表運(yùn)算算法

創(chuàng)建一個(gè)空的循環(huán)雙鏈表，它只有一個(gè)頭結(jié)點(diǎn)，由L指向它，該結(jié)點(diǎn)的next域和prior域均指向該頭結(jié)點(diǎn)，data域未設(shè)定任何值，如圖2.42所示。對(duì)應(yīng)的算法如下。

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

本算法的時(shí)間復(fù)雜度為O（1）。

2．銷毀線性表運(yùn)算算法

銷毀一個(gè)循環(huán)雙鏈表中的所有結(jié)點(diǎn)的算法思路與循環(huán)單鏈表的銷毀算法相同，對(duì)應(yīng)的算法如下。

本算法的時(shí)間復(fù)雜度為O（n），其中，n為循環(huán)雙鏈表L中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。

3．求線性表長度運(yùn)算算法

其設(shè)計(jì)思路與循環(huán)單鏈表的求表長算法完全相同，對(duì)應(yīng)的算法如下。

本算法的時(shí)間復(fù)雜度為O（n），其中，n為循環(huán)雙鏈表L中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。

4．求線性表中第i個(gè)元素運(yùn)算算法

其設(shè)計(jì)思路與循環(huán)單鏈表中求線性表中第i個(gè)元素運(yùn)算算法完全相同，對(duì)應(yīng)的算法如下。

本算法的時(shí)間復(fù)雜度為O（n），其中，n為循環(huán)雙鏈表L中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。

5．按值查找運(yùn)算算法

其設(shè)計(jì)思路與循環(huán)單鏈表中按值查找運(yùn)算算法完全相同，對(duì)應(yīng)的算法如下。

本算法的時(shí)間復(fù)雜度為O（n），其中，n為循環(huán)雙鏈表L中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。

6．插入元素運(yùn)算算法

其設(shè)計(jì)思想是：先在循環(huán)雙鏈表L中查找第i個(gè)結(jié)點(diǎn)p，用j記錄p結(jié)點(diǎn)的序號(hào)，當(dāng)p==L且i＞j+1時(shí)表示i參數(shù)錯(cuò)誤（如循環(huán)雙鏈表中只有三個(gè)結(jié)點(diǎn)，當(dāng)i＞4時(shí)出現(xiàn)這種錯(cuò)誤），當(dāng)成功找到第i個(gè)結(jié)點(diǎn)p時(shí)，創(chuàng)建data域?yàn)?span id="jt696dh" class="italic">x的結(jié)點(diǎn)s，讓pre指向p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，在pre結(jié)點(diǎn)之后插入s結(jié)點(diǎn)。對(duì)應(yīng)的算法如下。

本算法的時(shí)間復(fù)雜度為O（n），其中，n為循環(huán)雙鏈表L中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。

7．刪除元素運(yùn)算算法

其設(shè)計(jì)思想是：先在循環(huán)雙鏈表L中查找第i個(gè)結(jié)點(diǎn)p，若成功找到后通過其前驅(qū)結(jié)點(diǎn)pre將p結(jié)點(diǎn)刪除。對(duì)應(yīng)的算法如下。

本算法的時(shí)間復(fù)雜度為O（n），其中，n為循環(huán)雙鏈表L中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。

8．輸出線性表運(yùn)算算法

其設(shè)計(jì)思路與循環(huán)單鏈表的輸出元素值運(yùn)算算法完全相同，對(duì)應(yīng)的算法如下。

本算法的時(shí)間復(fù)雜度為O（n），其中，n為循環(huán)雙鏈表L中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。

說明：將循環(huán)雙鏈表結(jié)點(diǎn)類型聲明及其基本運(yùn)算函數(shù)存放在CDLinkNode.cpp文件中。

當(dāng)循環(huán)雙鏈表的基本運(yùn)算設(shè)計(jì)好后，給出以下主函數(shù)調(diào)用這些基本運(yùn)算函數(shù)，讀者可以對(duì)照程序執(zhí)行結(jié)果進(jìn)行分析，進(jìn)一步體會(huì)循環(huán)雙鏈表各種操作的實(shí)現(xiàn)過程。

上述程序的執(zhí)行結(jié)果如圖2.9所示。

2.4.5 循環(huán)雙鏈表的算法設(shè)計(jì)示例

【例2.24】設(shè)計(jì)一個(gè)算法將帶頭結(jié)點(diǎn)的循環(huán)雙鏈表L的所有結(jié)點(diǎn)逆置。

解：先建立一個(gè)空的循環(huán)雙鏈表L（結(jié)果循環(huán)雙鏈表），用p掃描余下的數(shù)據(jù)結(jié)點(diǎn)，依次將p結(jié)點(diǎn)采用頭插法插入到L中。對(duì)應(yīng)的算法如下。

【例2.25】有一個(gè)帶頭結(jié)點(diǎn)的循環(huán)雙鏈表L，其結(jié)點(diǎn)data域值為整數(shù)，設(shè)計(jì)一個(gè)算法，判斷其所有元素是否對(duì)稱。如果從前向后讀和從后向前讀得到的數(shù)據(jù)序列相同，表示是對(duì)稱的；否則不是對(duì)稱的。

解：先讓p指向首結(jié)點(diǎn)，q指向尾結(jié)點(diǎn)，當(dāng)兩者所指結(jié)點(diǎn)值不相等時(shí)返回0，否則p后移一個(gè)結(jié)點(diǎn)，q前移一個(gè)結(jié)點(diǎn)，依次比較下去，直到p—>next==q或p==q，如圖2.43所示。循環(huán)結(jié)束后返回1。

對(duì)應(yīng)的算法如下。

線性表除了采用前面介紹的順序表和各種鏈表存儲(chǔ)外，還有一種稱為靜態(tài)鏈表的存儲(chǔ)結(jié)構(gòu)，它采用一個(gè)一維數(shù)組表示線性表，每個(gè)數(shù)組元素存儲(chǔ)一個(gè)線性表元素，同時(shí)使用游標(biāo)（數(shù)組元素下標(biāo)）代替指針以指示元素在數(shù)組中的位置，元素的插入和刪除操作類似于單鏈表，不需要移動(dòng)大量元素，但同時(shí)也失去了數(shù)組的隨機(jī)存取特性。靜態(tài)鏈表的相關(guān)算法這里不再討論。