1.5　線性鏈表

視頻二維碼（掃碼觀看）

一、線性鏈表的基本概念

【定義】線性表的鏈式存儲結構稱為線性鏈表。線性鏈表的數據結構包括兩部分，一是數據元素的值，二是數據元素之間的前后件關系。

圖1-12　線性鏈表的一個存儲結點

為什么用線性鏈表？

（1）線性表順序存儲結構存在的缺點：

①插入或刪除過程中需要移動大量的數據元素。

②出現線性表的存儲空間已滿，但還需要插入新的元素時，就會發生“上溢”錯誤。

③線性表的順序存儲結構不便于存儲空間的動態分配。

（2）線性表鏈式存儲結構存在的優點：

在鏈式存儲結構中，存儲數據結構的存儲空間可以不連續，各數據結點的存儲順序與數據元素之間的邏輯關系可以不一致，而數據元素之間的邏輯關系是由指針域來確定的。

【說明】

①在線性鏈表中，用一個專門的指針HEAD指向線性鏈表中第一個數據元素的結點（即存放線性表中第一個數據元素的存儲結點的序號）。線性表中最后一個元素沒有后件，因此，線性鏈表中最后一個結點的指針域為空（用NULL或0表示），表示鏈表終止。

圖1-13　線性鏈表的邏輯結構

②在線性表的鏈式存儲結構中，各數據結點的存儲序號是不連續的，并且各結點在存儲空間中的位置關系與邏輯關系也不一致。

③當HEAD＝NULL（或0）時稱為空表。

圖1-14　線性鏈表例

1雙向鏈表

對線性鏈表中的每個結點設置兩個指針，一個稱為左指針（Llink），用以指向其前件結點；另一個稱為右指針（Rlink），用以指向其后件結點。

圖1-15　雙向鏈表示意圖

2帶鏈的棧

棧也是線性表，也可以采用鏈式存儲結構。

圖1-16　帶鏈的棧

在實際應用中，帶鏈的棧可以用來收集計算機存儲空間中所有空閑的存儲結點，這種帶鏈的棧稱為可利用棧。

圖1-17　可利用棧及其運算

3帶鏈的隊列

隊列也是線性表，也可以采用鏈式存儲結構。

圖1-18　帶鏈的隊列及其運算

二、線性鏈表的基本運算

線性鏈表的運算主要有以下幾個：

①插入：在線性鏈表中包含指定元素的結點之前插入一個新元素。

②刪除：在線性鏈表中刪除包含指定元素的結點。

③合并：將兩個線性鏈表按要求合并成一個線性鏈表。

④分解：將一個線性鏈表按要求進行分解。

⑤逆轉

⑥復制

⑦排序

⑧查找

1在線性鏈表中查找指定元素

從頭指針指向的結點開始往后沿指針進行掃描，直到后面已沒有結點或下一個結點的數據域為x為止。

因此，由這種方法找到的結點p有兩種可能：

①當線性鏈表中存在包含元素x的結點時，則找到的p為第一次遇到的包含元素x的前一個結點序號；

②當線性鏈表中不存在包含元素x的結點時，則找到的p為線性鏈表中的最后一個結點號。

2線性鏈表的插入

圖1-19　線性鏈表的插入

3線性鏈表的刪除

圖1-20　線性鏈表的刪除

三、循環鏈表

線性鏈表中，其插入與刪除的運算雖然比較方便，但還存在一個問題，在運算過程中對于空表和對第一個結點的處理必須單獨考慮，使空表與非空表的運算不統一。

1循環鏈表的特點

（1）增加了表頭結點，其數據域為任意或者根據需要來設置，指針域指向線性表的第一個元素的結點。循環鏈表的頭指針指向表頭結點。

（2）循環鏈表中最后一個結點的指針域不是空，而是指向表頭結點。即在循環鏈表中，所有結點的指針構成了一個環狀鏈。

圖1-21　循環鏈表的邏輯狀態

2循環鏈表與線性單鏈表相比主要有以下兩個方面的優點：

（1）在循環鏈表中，只要指出表中任何一個結點的位置，就可以從它出發訪問到表中其他所有的結點。線性單鏈表做不到這一點。

（2）由于在循環鏈表中設置了一個表頭結點，因此，在任何情況下循環鏈表中至少有一個結點存在，從而使空表與非空表的運算統一。