考點(diǎn)5 線性鏈表

1.線性鏈表的基本概念

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為線性鏈表。

為了存儲(chǔ)線性表中的每一個(gè)元素，一方面要存儲(chǔ)數(shù)據(jù)元素的值；另一方面要存儲(chǔ)各數(shù)據(jù)元素之間的前后件關(guān)系。為此，在鏈?zhǔn)酱鎯?chǔ)方式中，每個(gè)節(jié)點(diǎn)由兩部分組成：一部分稱(chēng)為數(shù)據(jù)域，用于存放數(shù)據(jù)元素值；另一部分稱(chēng)為指針域，用于存放下一個(gè)數(shù)據(jù)元素的存儲(chǔ)序號(hào)，即指向后件節(jié)點(diǎn)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)既可以表示線性結(jié)構(gòu)，也可以表示非線性結(jié)構(gòu)。

線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組不連續(xù)的存儲(chǔ)單元存儲(chǔ)線性表中的各個(gè)元素。因?yàn)榇鎯?chǔ)單元不連續(xù)，所以數(shù)據(jù)元素之間的邏輯關(guān)系就不能依靠數(shù)據(jù)元素的存儲(chǔ)單元之間的物理關(guān)系來(lái)表示。

2.線性鏈表的基本運(yùn)算

線性鏈表主要包括以下8種運(yùn)算：

●在線性鏈表中包含指定元素的節(jié)點(diǎn)之前插入一個(gè)新元素；

●在線性鏈表中刪除包含指定元素的節(jié)點(diǎn)；

●將兩個(gè)線性鏈表按要求合并成一個(gè)線性鏈表；

●將一個(gè)線性鏈表按要求進(jìn)行分解；

●逆轉(zhuǎn)線性鏈表；

●復(fù)制線性鏈表；

●線性鏈表的排序；

●線性鏈表的查找。

真考鏈接

考核概率為35%?？忌煊浽摽键c(diǎn)內(nèi)容，尤其是線性鏈表的概念和特點(diǎn)、順序表和鏈表的優(yōu)、缺點(diǎn)等。

3.循環(huán)鏈表及其基本運(yùn)算

（1）循環(huán)鏈表的定義。

在單鏈表的第一個(gè)節(jié)點(diǎn)前增加一個(gè)表頭節(jié)點(diǎn)，隊(duì)頭指針指向表頭節(jié)點(diǎn)，在最后一個(gè)節(jié)點(diǎn)的指針域的值由NULL改為指向表頭節(jié)點(diǎn)，這樣的鏈表稱(chēng)為循環(huán)鏈表。循環(huán)鏈表中，所有節(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈。

（2）循環(huán)鏈表與單鏈表的比較。

對(duì)單鏈表的訪問(wèn)是一種順序訪問(wèn)，從其中某一個(gè)節(jié)點(diǎn)出發(fā)，只能找到它的直接后繼，但無(wú)法找到它的直接前驅(qū)。而且對(duì)于空表和第一個(gè)節(jié)點(diǎn)的處理必須單獨(dú)考慮，空表與非空表的操作不統(tǒng)一。

在循環(huán)鏈表中，只要指出表中任何一個(gè)節(jié)點(diǎn)的位置，就可以從它出發(fā)訪問(wèn)到表中其他所有的節(jié)點(diǎn)。由于表頭節(jié)點(diǎn)是循環(huán)鏈表所固有的節(jié)點(diǎn)，因此，即使在表中沒(méi)有數(shù)據(jù)元素的情況下，表中也至少有一個(gè)節(jié)點(diǎn)存在，從而使空表和非空表的運(yùn)算統(tǒng)一。

真題精選

下列敘述中正確的是______。

A）線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

B）棧與隊(duì)列是非線性結(jié)構(gòu)

C）雙向鏈表是非線性結(jié)構(gòu)

D）只有根節(jié)點(diǎn)的二叉樹(shù)是線性結(jié)構(gòu)

【答案】A

【解析】根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后關(guān)系的復(fù)雜程序，可將數(shù)據(jù)結(jié)構(gòu)分為兩大類(lèi)型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿(mǎn)足下列兩個(gè)條件：①有且只有一個(gè)根節(jié)點(diǎn)；②每個(gè)節(jié)點(diǎn)最多有一個(gè)前驅(qū)，也最多有一個(gè)后繼，則稱(chēng)該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)，也叫做線性表。若不滿(mǎn)足上述條件，則稱(chēng)之為非線性結(jié)構(gòu)。線性表、棧與隊(duì)列、線性鏈表都是線性結(jié)構(gòu)，而二叉樹(shù)是非線性結(jié)構(gòu)。