2.3　線性表的鏈式存儲結構和實現

線性表的順序存儲結構著明顯的缺點：插入、刪除元素時需要頻繁移動元素，運算效率低；必須按事先估計的最大元素個數申請連續的存儲空間。存儲空間估計大了，則浪費空間；若估計小了，則容易產生溢出，空間難以臨時擴大。采用鏈式存儲結構的線性表可以克服線性表的順序存儲結構存在的上述不足。

采用鏈式存儲結構的線性表稱為鏈表。鏈表有單鏈表、循環鏈表和雙向鏈表等多種類型。

2.3.1　單鏈表的定義和表示

鏈表中，不僅需要存儲每個數據元素，還需存儲其直接后繼的存儲地址，這兩部分數據信息組合起來稱為結點。結點包括兩個域：存儲數據元素信息的域稱為數據域；存儲直接后繼存儲地址的域稱為指針域。每個結點只包含一個指針域的鏈表，稱為單鏈表。在單鏈表中，每個元素占用一個結點，結點的結構如圖2.4所示，其中，數據域記為element，指針域記為link。在單鏈表中，數據之間的前驅后繼關系是通過指針域中存儲的地址來表現的，邏輯上相鄰的元素在物理存儲空間上是不一定相鄰的。

在此約定，在不會引起混淆的場合，將不明確區分結點和元素這兩個術語。但必要時，將包括數據元素和地址在內的整個存儲塊稱為結點，而將其中的數據元素稱為該結點的元素。

線性表(a0,a1,…,an?1)以單鏈表形式進行存儲時，其結構如圖2.5（a）所示。第一個元素a0所在的結點稱為頭結點。存儲頭結點地址的指針稱為頭指針，記為first。若單鏈表中沒有存儲數據元素，則單鏈表為空，此時first指針的值為NULL，在圖中用“∧”表示，如圖2.5（b）所示。單鏈表最后一個元素an?1所在的結點稱為尾結點，此結點沒有后繼結點，其指針域的值為NULL，在圖中用“∧”表示。

圖2.4　單鏈表的結點結構

圖2.5　單鏈表示例

在單鏈表中，若first指針中存儲的值丟失，即丟失元素a0的地址，將導致無法讀取a0的數據域和指針域，此指針域中存放的a1的地址也將丟失。由此類推可知，整個單鏈表存儲的信息都會丟失。在對結點的指針域進行操作時，需注意保存好后繼結點的地址，避免丟失后繼結點的地址，出現“斷鏈”現象。

單鏈表的類型定義如下。

在類型Node的定義中，Node表示單鏈表的結點結構類型，element表示結點的數據域，link為結點的指針域，存放后繼結點的地址。在類型SingleList的定義中，SingleList是單鏈表類型，first表示頭指針，n表示單鏈表中元素的個數。

2.3.2　單鏈表基本運算的實現

以下討論單鏈表中幾個主要運算的具體實現。

1．初始化

單鏈表的初始化運算是構造一個空的單鏈表。

程序2.8　單鏈表的初始化

2．查找

單鏈表的查找運算是讀取表中元素ai的值。單鏈表不具備順序表的可隨機存取元素的特性，必須沿著單鏈表的頭結點開始逐個計數進行查找。

【算法步驟】

（1）判斷i是否越界，若越界，返回ERROR。

（2）從頭結點開始順著單鏈表逐個結點查找。

（3）將ai的值通過x返回。

程序2.9　單鏈表的查找

3．插入

單鏈表的插入運算是在ai之后插入新元素x。為了實現此功能，首先需要使用查找算法確定ai的位置，使用指針p指向此結點。

x是一個新元素，在單鏈表中并不存在，需要先為此元素生成一個新結點，由指針q指向此結點，并將新結點的數據域置為x。

若i=?1，表示將新結點插入單鏈表的頭結點之前，它將成為新的頭結點，如圖2.6所示，通過以下語句實現。

①q->link=first;

②first=q;

圖2.6　結點的插入示例（i=?1）

若i>?1，表示將新結點插入單鏈表，新結點應成為ai+1的直接前驅、ai的直接后繼，如圖2.7所示，通過以下語句實現。

①q->link=p->link;　//將p所指結點link域中的地址存儲在q所指結點的link域中

②p->link=q;　//將q中存儲的新結點地址存放在p所指結點的link域中

上述兩條語句的執行順序不能顛倒，否則將出現“斷鏈”問題。

圖2.7　結點的插入示例（i>?1）

【算法步驟】

（1）判斷i是否越界，若越界，則返回ERROR。

（2）查找ai，指針p指向此結點。

（3）生成新的結點，將新結點的數據域置為x，指針q指向此結點。

（4）若i=?1，新結點q插在頭結點之前，成為新的頭結點；若i>?1，將q所指向的結點插入在p所指向的結點之后。

（5）單鏈表元素個數加1，返回OK。

程序2.10　單鏈表的插入

4．刪除

單鏈表刪除運算的功能是刪除元素ai。

若i=0，表示刪除頭結點，需將first指針指向a1所在結點，使其成為新的頭結點，如圖2.8所示。實現語句如下。

first=first->link;

若i>0，則使ai的直接前驅ai?1的指針域存儲ai的直接后繼ai+1的地址，如圖2.9所示。實現語句如下。

q->link=p->link;

圖2.8　單鏈表中刪除ai（i=0）

圖2.9　單鏈表中刪除ai（i>0）

刪除元素ai時，不可跳過上述操作而直接釋放ai的存儲空間，否則將導致直接后繼ai+1地址丟失，出現“斷鏈”問題。

【算法步驟】

（1）若i越界或單鏈表為空，返回ERROR。

（2）查找元素ai的直接前驅ai?1，并令指針q指向它。

（3）若i=0，則從單鏈表中刪除頭結點；若i>0，則使p指向ai所在結點，并從單鏈表中刪除ai。

（4）釋放p所指結點的存儲空間。

（5）單鏈表元素個數減1，返回OK。

程序2.11　單鏈表的刪除

5．輸出

單鏈表的輸出運算是從first所指示的第一個結點開始逐個遍歷單鏈表的每個結點，將元素依次輸出。

【算法步驟】

（1）判斷單鏈表是否為空，若為空，返回ERROR。

（2）將元素（a0,…,an?1）依次輸出。

程序2.12　順序表的輸出

6．撤銷

撤銷運算的主要功能是釋放單鏈表中動態分配的數據元素存儲空間，以防止內存泄漏。

程序2.13　順序表的撤銷

7．主函數main

程序2.14中的主函數main是為了測試單鏈表的主要運算而設計的。

程序2.14　主函數main

2.3.3　帶表頭結點的單鏈表

在上述單鏈表中頭結點之前沒有直接前驅，進行插入和刪除運算時，需要把頭結點的插入和刪除作為特殊情況特別處理。為解決上述問題，簡化算法，可在單鏈表的頭結點之前增加一個表頭結點，由此構成的單鏈表稱為帶表頭結點的單鏈表，如圖2.10所示。

圖2.10　帶表頭結點的單鏈表結構

在此需注意表頭結點與頭結點的區別。圖2.10（a）中，元素a0所在結點為頭結點，頭結點之前的結點為表頭結點。表頭結點的數據域中并不存放線性表中的數據元素。當表為空時也需有一個表頭結點，如圖2.10（b）所示。

帶表頭結點的單鏈表的類型定義如下。

HeaderList與SingleList類型定義相似，此處的Node類型同SingleList類型定義中的Node類型。

帶表頭結點的單鏈表的運算與單鏈表的運算類似，以下僅給出帶表頭結點的單鏈表的初始化、插入、刪除運算的具體實現。讀者可自行完成其他運算的實現。

1．初始化

初始化運算是構造一個僅帶有一個表頭結點的空的單鏈表。

程序2.15　帶表頭結點的單鏈表的初始化

2．插入

帶表頭結點的單鏈表中每個結點之前都有前驅結點，在插入元素時不需要再單獨處理插入在頭結點之前的情況，從而簡化了插入運算。

程序2.16　帶表頭結點的單鏈表的插入運算

3．刪除

帶表頭結點的單鏈表中每個結點之前都有前驅結點，在刪除元素時不需要再單獨處理刪除頭結點的情況，從而簡化了刪除運算。

程序2.17　帶表頭結點的單鏈表的刪除運算

2.3.4　單循環鏈表

單循環鏈表是另一種線性表鏈式存儲方式。將單鏈表中最后一個結點的指針域存儲頭結點的地址，使得整個單鏈表形成一個環，這種頭尾相接的單鏈表稱為單循環鏈表，如圖2.11（a）所示。空的單循環鏈表如圖2.11（b）所示。

圖2.11　單循環鏈表結構

也可為單循環鏈表增加表頭結點，則構成帶表頭結點的單循環鏈表，如圖2.12（a）所示。空的帶表頭結點的單循環鏈表如圖2.12（b）所示。

圖2.12　帶表頭結點的單循環鏈表結構

2.3.5　雙向鏈表

以上介紹的線性表鏈式存儲結構中，每個結點只有一個指針域，從某個結點出發只能順著指針域向后查找后繼結點。若要再向前查找前驅結點，則需從頭結點開始再次查找。為了克服單鏈表存在的上述問題，可使用雙向鏈表，如圖2.13所示。

雙向鏈表的結點有三個域，結點的結構如圖2.14所示。其中，存儲數據元素的域稱為數據域，記為element；左指針域是存儲直接前驅結點地址的域，記為llink；右指針域是存儲直接后繼結點地址的域，記為rlink。

圖2.13　雙向鏈表

圖2.14　雙向鏈表的結點結構

雙向鏈表的存儲結構定義如下。

1．雙向鏈表的插入

為了實現在雙向鏈表的元素ai之前插入x，首先需查找到元素ai所在結點并使指針p指向它，這個過程與單鏈表中查找運算類似。生成新的結點，將新結點的數據域置為x，指針q指向此結點。在p所指向的結點之前插入q所指向的結點，如圖2.15所示。

圖2.15　雙向鏈表的插入

雙向鏈表的插入運算的核心代碼如下。

2．雙向鏈表的刪除

為了在雙向鏈表中刪除元素ai，首先需要查找元素ai，并令指針p指向其所在結點，這個過程與單鏈表中查找運算類似；然后使元素ai的前驅結點ai?1的右指針域存儲ai的后繼結點ai+1的地址；使元素ai的后繼結點ai+1的左指針域存儲ai的前驅結點ai?1的地址；最后釋放元素ai所在結點的存儲空間，如圖2.16所示。

圖2.16　雙向鏈表的刪除

雙向鏈表的刪除運算的核心代碼如下。