點擊進入：2011計算機等考二級公共基礎知識講義匯總>>

　　1.5 線性鏈表(學吧學吧獨家稿件)

　　1、線性表順序存儲的缺點(學吧學吧獨家稿件)：(1)插入或刪除的運算效率很低。在順序存儲的線性表中，插入或刪除數據元素時需要移動大量的數據元素;(2)線性表的順序存儲結構下，線性表的存儲空間不便于擴充;(3)線性表的順序存儲結構不便于對存儲空間的動態分配。

　　2、線性鏈表：線性表的鏈式存儲結構稱為線性鏈表，是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接來實現的。因此，在鏈式存儲方式中，每個結點由兩部分組成：一部分用于存放數據元素的值，稱為數據域;另一部分用于存放指針，稱為指針域，用于指向該結點的前一個或后一個結點(即前件或后件)，如下圖所示：

　　線性鏈表分為單鏈表、雙向鏈表和循環鏈表三種類型。

　　在單鏈表中，每一個結點只有一個指針域，由這個指針只能找到其后件結點，而不能找到其前件結點。因此，在某些應用中，對于線性鏈表中的每個結點設置兩個指針，一個稱為左指針，指向其前件結點;另一個稱為右指針，指向其后件結點，這種鏈表稱為雙向鏈表，如下圖所示：

　　3、線性鏈表的基本運算

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

　　*：在線性鏈表中插入元素時，不需要移動數據元素，只需要修改相關結點指針即可，也不會出現“上溢[注釋1] ”現象(學吧學吧獨家稿件)。

　　(2)在線性鏈表中刪除包含指定元素的結點。

　　*：在線性鏈表中刪除元素時，也不需要移動數據元素，只需要修改相關結點指針即可。

　　(3)將兩個線性鏈表按要求合并成一個線性鏈表。

　　(4)將一個線性鏈表按要求進行分解。

　　(5)逆轉線性鏈表。

　　(6)復制線性鏈表。

　　(7)線性鏈表的排序。

　　(8)線性鏈表的查找。

　　*：線性鏈表不能隨機存取[注釋2] 。

　　4、循環鏈表及其基本運算

　　在線性鏈表中，其插入與刪除的運算雖然比較方便，但還存在一個問題，在運算過程中對于空表和對第一個結點的處理必須單獨考慮，使空表與非空表的運算不統一。為了克服線性鏈表的這個缺點，可以采用另一種鏈接方式，即循環鏈表。

　　與前面所討論的線性鏈表相比，循環鏈表具有以下兩個特點：1)在鏈表中增加了一個表頭結點，其數據域為任意或者根據需要來設置，指針域指向線性表的第一個元素的結點，而循環鏈表的頭指針指向表頭結點;2)循環鏈表中最后一個結點的指針域不是空，而是指向表頭結點。即在循環鏈表中，所有結點的指針構成了一個環狀鏈。

　　下圖a是一個非空的循環鏈表，圖b是一個空的循環鏈表：

　　循環鏈表的優點主要體現在兩個方面：一是在循環鏈表中，只要指出表中任何一個結點的位置，就可以從它出發訪問到表中其他所有的結點，而線性單鏈表做不到這一點;二是由于在循環鏈表中設置了一個表頭結點，在任何情況下，循環鏈表中至少有一個結點存在，從而使空表與非空表的運算統一。

　　*：循環鏈表是在單鏈表的基礎上增加了一個表頭結點，其插入和刪除運算與單鏈表相同。但它可以從任一結點出發來訪問表中其他所有結點，并實現空表與非空表的運算的統一。

　　注釋1：當為一個線性表分配順序存儲結構后，如果出現線性表的存儲空間已滿，但還需要插入新的元素時，就會發生“上溢”現象。

　　注釋2：在鏈表中，即使知道被訪問結點的序號i，也不能像順序表中那樣直接按序號i訪問結點，而只能從鏈表的頭指針出發，順著鏈域逐個結點往下搜索，直至搜索到第i個結點為止。因此，鏈表不是隨機存儲結構。

　　相關推薦：

　　2011計算機等考二級公共基礎知識要點匯總

　　2010年9月計算機等級考試成績查詢時間匯總

　　2011年上半年計算機等級考試報名時間匯總