2011計算機等考二級公共基礎(chǔ)知識講義：第1章(5)

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

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

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

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

　　線性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類型。

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

　　3、線性鏈表的基本運算

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

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

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

　　*：在線性鏈表中刪除元素時，也不需要移動數(shù)據(jù)元素，只需要修改相關(guān)結(jié)點指針即可。

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

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

　　(5)逆轉(zhuǎn)線性鏈表。

　　(6)復制線性鏈表。

　　(7)線性鏈表的排序。

　　(8)線性鏈表的查找。

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

　　4、循環(huán)鏈表及其基本運算

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

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

　　下圖a是一個非空的循環(huán)鏈表，圖b是一個空的循環(huán)鏈表：

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

　　*：循環(huán)鏈表是在單鏈表的基礎(chǔ)上增加了一個表頭結(jié)點，其插入和刪除運算與單鏈表相同。但它可以從任一結(jié)點出發(fā)來訪問表中其他所有結(jié)點，并實現(xiàn)空表與非空表的運算的統(tǒng)一。

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

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

　　相關(guān)推薦：

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

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

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