（五）線性鏈表
1．基本概念
前面的線性表均是采用順序存儲(chǔ)結(jié)構(gòu)及在順序存儲(chǔ)結(jié)構(gòu)下的運(yùn)算。
1）順序存儲(chǔ)的優(yōu)點(diǎn)：
結(jié)構(gòu)簡(jiǎn)單
運(yùn)算方便
2）順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)：
要在順序存儲(chǔ)的線性表中插入一個(gè)新元素或刪除一個(gè)元素時(shí)，為了保證插入或刪除后的線性表仍然為順序存儲(chǔ)。在插入或刪除元素時(shí)，需要移動(dòng)大量的數(shù)據(jù)元素，因此運(yùn)算效率較低。
如果一個(gè)線性表分配順序存儲(chǔ)空間后，如果出現(xiàn)線性表的存儲(chǔ)空間已滿，但還需要插入元素時(shí)，會(huì)發(fā)生“上溢”錯(cuò)誤。
在實(shí)際應(yīng)用時(shí)，可能有多個(gè)線性表同時(shí)使用存儲(chǔ)空間，這樣給存儲(chǔ)空間的分配帶來問題，有可能使有的隊(duì)列空間不夠或過多造成浪費(fèi)。
基于上述情況，對(duì)于大的線性表或元素變動(dòng)頻繁的大線性表不宜采用順序存儲(chǔ)結(jié)構(gòu)，而應(yīng)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
3）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
假設(shè)每一個(gè)數(shù)據(jù)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)存儲(chǔ)單元，該存儲(chǔ)單元稱為存儲(chǔ)結(jié)點(diǎn)，簡(jiǎn)稱結(jié)點(diǎn)。
在鏈?zhǔn)酱鎯?chǔ)方式中，要求每一個(gè)結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素，你為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域。該指針用于指向該結(jié)點(diǎn)的前一個(gè)或后一個(gè)結(jié)點(diǎn)。
在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)既可以用于線性結(jié)構(gòu)，也可用于非線性結(jié)構(gòu)。
4）線性鏈表
線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。
將存儲(chǔ)空間劃分成若干的小塊，每塊占用若干個(gè)字節(jié)，這些小塊稱為存儲(chǔ)結(jié)點(diǎn)。
將存儲(chǔ)結(jié)點(diǎn)分為兩個(gè)部分，一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存儲(chǔ)元素之間的前后件關(guān)系，即存放下一個(gè)元素在存儲(chǔ)序號(hào)（即存儲(chǔ)地址），即指向后件結(jié)點(diǎn)，稱為指針域。
在線性鏈表中用一個(gè)專門的指針HEAD指向線性鏈表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)（即存放第一個(gè)元素的地址）。線性表中最后一個(gè)元素沒有后件，因此，線性鏈表中的最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭眨ㄓ肗ull或0表示），表示鏈終結(jié)。
在線性鏈表中，各元素的存儲(chǔ)序號(hào)是不連續(xù)的，元素間的前后件關(guān)系與位置關(guān)系也是不一致的。在線性鏈表中，前后件的關(guān)系依靠各結(jié)點(diǎn)的指針來指示，指向表的第一個(gè)元素的指針HEAD稱為頭指針，當(dāng)HEAD=NULL時(shí)，表示該鏈表為空。
對(duì)于線性鏈表，可以從頭指針開始，沿著各結(jié)點(diǎn)的指針掃描到鏈表中的所有結(jié)點(diǎn)。
這種線性鏈表稱為線性單鏈表，即可以從表頭開始向后掃描鏈表中的所有結(jié)點(diǎn)，而不能從中間或表尾結(jié)點(diǎn)向前掃描位于該結(jié)點(diǎn)之前的元素。
這種鏈表結(jié)構(gòu)的缺點(diǎn)是不能任意地對(duì)鏈表中的元素按下同的方向進(jìn)行掃描。在某些應(yīng)用時(shí)，如果對(duì)鏈表中的元素設(shè)置兩個(gè)指針域，一個(gè)為指向前件的指針域，稱為左指針（LLink），一個(gè)為指向后件的指針域，稱為右指針（RLink）。則這種鏈表是雙向鏈表。
5）帶鏈的棧
帶鏈的棧即是用來收集計(jì)算機(jī)存儲(chǔ)空間中的所有空閑的存儲(chǔ)結(jié)點(diǎn)，這種帶鏈的棧稱為可利用棧。
當(dāng)需要存儲(chǔ)結(jié)點(diǎn)時(shí)，即從可利用的棧的頂部取出棧頂結(jié)點(diǎn)；當(dāng)系統(tǒng)要釋放一個(gè)存儲(chǔ)結(jié)點(diǎn)時(shí)，將該結(jié)點(diǎn)空間放回到可利用棧的棧頂。
即在計(jì)算機(jī)中所有空閑的空間，均可以以結(jié)點(diǎn)的方式鏈接到可利用棧中，隨著其他線性鏈表中結(jié)點(diǎn)的插入與刪除，可利用棧處于動(dòng)態(tài)變化之中，即可利用棧經(jīng)常要進(jìn)行退棧和入棧操作。
6）帶鏈的隊(duì)列
隊(duì)列也是線性表，也可利用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來進(jìn)行保存。
2．線性鏈表的基本運(yùn)算
線性鏈表包括的基本運(yùn)算：
在鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素
在鏈表中刪除包含指定元素的結(jié)點(diǎn)
將兩個(gè)線性鏈表按要求合并成一個(gè)線性鏈表
將一個(gè)線性鏈表按要求進(jìn)行分解
逆轉(zhuǎn)線性鏈表
復(fù)制線性鏈表
線性鏈表的排序
線性鏈表的查找
1）線性鏈表中查找指定的元素
在線性鏈表中查找元素X：從頭指針指向的結(jié)點(diǎn)開始往后沿指針進(jìn)行掃描，直到后面已沒有結(jié)點(diǎn)或下一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閄為止。
元素的查找，經(jīng)常是為了進(jìn)行插入或刪除操作而進(jìn)行的，因此，在查找時(shí)，往往是需要記錄下該結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)。
2）線性鏈表的插入
線性鏈表的插入即在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表中插入一個(gè)新元素。
在線性鏈表中包含元素x的結(jié)點(diǎn)之前插入新元素b，插入過程：
（1）從可利用棧中取得一個(gè)結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)號(hào)為p，即取得的結(jié)點(diǎn)的存儲(chǔ)序號(hào)存放在變量p中。并置結(jié)點(diǎn)p的數(shù)據(jù)域?yàn)椴迦氲脑刂礲。
（2）在線性鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的存儲(chǔ)序號(hào)為q。
（3）將結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后。具體的操作：首先，使結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后（即結(jié)點(diǎn)q的后件結(jié)點(diǎn)），然后，使結(jié)點(diǎn)q的指針域 內(nèi)容改為指向結(jié)點(diǎn)p。
線性鏈表的插入操作，新結(jié)點(diǎn)是為來自于可利用棧，因此不會(huì)造成線性表的溢出。同樣，由于可利用?？杀欢鄠€(gè)線性表利用，因此，不會(huì)造成存儲(chǔ)空間的浪費(fèi)，大家動(dòng)態(tài)地共同使用存儲(chǔ)空間。
3）線性鏈表的刪除
線性鏈表的刪除，即是在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表中刪除指定元素的結(jié)點(diǎn)。
操作方式：
（1）在線性表中找到包含指定元素x的前一個(gè)結(jié)點(diǎn)p
（2）將該結(jié)點(diǎn)p后的包含元素x的結(jié)點(diǎn)從線性鏈表中刪除，然后將被刪除結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn)q的地址提供給結(jié)點(diǎn)p的指針域，即將結(jié)點(diǎn)p指向結(jié)點(diǎn)q。
（3）將刪除的結(jié)點(diǎn)送回可利用棧。
從以上的刪除操作可見，刪除一個(gè)指定的元素，不需要移動(dòng)其他的元素即可實(shí)現(xiàn)，這是順序存儲(chǔ)的線性表所不能實(shí)現(xiàn)的。同時(shí)，此操作還可更有效地利用計(jì)算機(jī)的存儲(chǔ)空間。
3．循環(huán)鏈表及其基本操作
在線性鏈表中，雖然對(duì)數(shù)據(jù)元素的插入和刪除操作比較簡(jiǎn)單，但由于它對(duì)第一個(gè)結(jié)點(diǎn)和空表需要單獨(dú)處理，使得空表與非空表的處理不一致。
循環(huán)鏈表，即是采用另一種鏈接方式，它的特點(diǎn)如下：
（1）在循環(huán)鏈表中增加一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蚋鶕?jù)需要來設(shè)置，指針域指向線性表的第一個(gè)元素的結(jié)點(diǎn)。循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。
（2）循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不是空的，而是指向表頭結(jié)點(diǎn)。在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成一個(gè)環(huán)狀鏈。
在循環(huán)鏈表中，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置，均可以從它開始掃描到所有的結(jié)點(diǎn)，而線性鏈表做不到，線性鏈表是一種單向的鏈表，只能按照指針的方向進(jìn)行掃描。
循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn)，因此，在任何時(shí)候都至少有一個(gè)結(jié)點(diǎn)，因此空表與非空表的運(yùn)算相統(tǒng)一。