考點(diǎn)13 線性鏈表的基本運(yùn)算
線性鏈表的運(yùn)算主要有以下幾個(gè)：
(l)在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素；
(2)在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)；
(3)將兩個(gè)線性鏈表按要求合并成一個(gè)線性表；
(4)將一個(gè)線性鏈表按要求進(jìn)行分解；
(5)逆轉(zhuǎn)線性鏈表；
(6)復(fù)制線性鏈表；
(7)線性鏈表的排序；
(8)線性鏈表的查找。
1在線性鑊表中查找指定元素
在對(duì)線性鏈表進(jìn)行插入或刪除的運(yùn)算中，總是首先需要找到插入或刪除的位置，這就需要對(duì)線性鏈表進(jìn)行掃描查找，在線性鏈表中尋找包含指定元素的前一個(gè)結(jié)點(diǎn)。
在線性鏈表中，即使知道被訪問(wèn)結(jié)點(diǎn)的序號(hào)a，也不能像順序表中那樣直接按序號(hào)i訪問(wèn)結(jié)點(diǎn)，而只能從鏈表的頭指針出發(fā)，順鏈域Next逐個(gè)結(jié)點(diǎn)往下搜索，直到搜索到第i個(gè)結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。
在鏈表中，查找是否有結(jié)點(diǎn)值等于給定值x的結(jié)點(diǎn)，若有的話，則返回首次找到的其值為x的結(jié)點(diǎn)的存儲(chǔ)位置；否則返回NULL。查找過(guò)程從開(kāi)始結(jié)點(diǎn)出發(fā)，順著鏈表逐個(gè)將結(jié)點(diǎn)的值和給定值x作比較。
2線性鏈表的插入
線性鏈表的插入是指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性鏈表中插入一個(gè)新元素。
插入運(yùn)算是將值為X的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到ai-1，與ai之間。因此，我們必須首先找到ai-1的存儲(chǔ)位置p，然后生成一個(gè)數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)*p，并令結(jié)點(diǎn)，p的指針域指向新結(jié)點(diǎn)，新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)ai
由線性鏈表的插入過(guò)程可以看出，由于插入的新結(jié)點(diǎn)取自于可利用棧，因此，只要可利用棧不空，在線性鏈表插入時(shí)總能取到存儲(chǔ)插入元素的新結(jié)點(diǎn)，不會(huì)發(fā)生“上溢”的情況。而且，由于可利用棧是公用的，多個(gè)線性鏈表可以共享它，從而很方便地實(shí)現(xiàn)了存儲(chǔ)空間的動(dòng)態(tài)分配。另外，線性鏈表在插入過(guò)程中不發(fā)生數(shù)據(jù)元素移動(dòng)的現(xiàn)象，只要改變有關(guān)結(jié)點(diǎn)的指針即可，從而提高了插入的效率。
3多線性鏈表的刪除
線性鏈表的刪除是指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性鏈表中刪除包含指定元素的結(jié)點(diǎn)。
刪除運(yùn)算是將表的第i個(gè)結(jié)點(diǎn)刪去。因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)a的存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn)ai-1，的指針域Next中，所以我們必須首先找到ai-1的存儲(chǔ)位置p。然后令p->Next指向ai的直接后件結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)a的空間。
從線性鏈表的刪除過(guò)程可以看出，從線性鏈表中刪除一個(gè)元素后，不需要移動(dòng)表中的數(shù)據(jù)元素，只要改變被刪除元素所在結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的指針域即可。另外，由于可利用棧是用于收集計(jì)算機(jī)中所有的空閑結(jié)點(diǎn)，因此，當(dāng)從線性鏈表中刪除一個(gè)元素后，該元素的存儲(chǔ)結(jié)點(diǎn)就變?yōu)榭臻e，應(yīng)將空閑結(jié)點(diǎn)送回到可利用棧。
考點(diǎn)14 線性雙向鏈表的結(jié)構(gòu)及其基本運(yùn)算
1什么是雙向鏈表
在單鏈表中，從某個(gè)結(jié)點(diǎn)出發(fā)可以直接找到它的直接后件，時(shí)間復(fù)雜度為O(1)，但無(wú)法直接找到它的互接前件；在單循環(huán)鏈表中，從某個(gè)結(jié)點(diǎn)出發(fā)可以直接找到它的直接后件，時(shí)間復(fù)雜度仍為O(1)，直接找到它的直接前件，時(shí)間復(fù)雜度為O(n)。有時(shí)，希望能快速找到一個(gè)結(jié)點(diǎn)的直接前件，這時(shí)，可以在單鏈表中的結(jié)點(diǎn)中增加一個(gè)指針域指向它的直接前件，這樣的鏈表，就稱為雙向鏈表(一個(gè)結(jié)點(diǎn)中含有兩個(gè)指針)。如果每條鏈構(gòu)成一個(gè)循環(huán)鏈表，則會(huì)得到雙向循環(huán)鏈表
2雙向鏈表的基本運(yùn)算
(l)插入：在HEAD為頭指針的雙向鏈表中，在值為Y的結(jié)點(diǎn)之后插入值為X的結(jié)點(diǎn)，插入結(jié)點(diǎn)的指針變化。如圖1-20所示(若改為在值為Y的結(jié)點(diǎn)之前插入值為X的結(jié)點(diǎn)，可以做類似分析)。
(2)刪除：在以HEAD為頭指針的雙向鏈表中刪除值為X的結(jié)點(diǎn)，刪除算法的指針變化，如圖1-21所示。
考點(diǎn)15 循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算
單鏈表上的訪問(wèn)是一種順序訪問(wèn)，從其中的某一個(gè)結(jié)點(diǎn)出發(fā)，可以找到它的直接后件，但無(wú)法找到它的直接前件。
在前面所討論的線性鏈表中，其插入與刪除的運(yùn)算雖然比較方便，但還存在一個(gè)問(wèn)題，在運(yùn)算過(guò)程中對(duì)于空表和對(duì)第一個(gè)結(jié)點(diǎn)的處理必須單獨(dú)考慮，使空表與非空表的運(yùn)算不統(tǒng)一。
因此，我們可以考慮建立這樣的鏈表，具有單鏈表的特征，但又不需要增加額外的存貯空間，僅對(duì)表的鏈接方式稍做改變，使得對(duì)表的處理更加方便靈活。從單鏈表可知，最后一個(gè)結(jié)點(diǎn)的指針域?yàn)镹ULL，表示單鏈表已經(jīng)結(jié)束。如果將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域改為存放鏈表中頭結(jié)點(diǎn)(或第一個(gè)結(jié)點(diǎn))的地址，就使得整個(gè)鏈表構(gòu)成一個(gè)環(huán)，又沒(méi)有增加額外的存儲(chǔ)空間
線性鏈表的運(yùn)算主要有以下幾個(gè)：
(l)在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素；
(2)在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)；
(3)將兩個(gè)線性鏈表按要求合并成一個(gè)線性表；
(4)將一個(gè)線性鏈表按要求進(jìn)行分解；
(5)逆轉(zhuǎn)線性鏈表；
(6)復(fù)制線性鏈表；
(7)線性鏈表的排序；
(8)線性鏈表的查找。
1在線性鑊表中查找指定元素
在對(duì)線性鏈表進(jìn)行插入或刪除的運(yùn)算中，總是首先需要找到插入或刪除的位置，這就需要對(duì)線性鏈表進(jìn)行掃描查找，在線性鏈表中尋找包含指定元素的前一個(gè)結(jié)點(diǎn)。
在線性鏈表中，即使知道被訪問(wèn)結(jié)點(diǎn)的序號(hào)a，也不能像順序表中那樣直接按序號(hào)i訪問(wèn)結(jié)點(diǎn)，而只能從鏈表的頭指針出發(fā)，順鏈域Next逐個(gè)結(jié)點(diǎn)往下搜索，直到搜索到第i個(gè)結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。
在鏈表中，查找是否有結(jié)點(diǎn)值等于給定值x的結(jié)點(diǎn)，若有的話，則返回首次找到的其值為x的結(jié)點(diǎn)的存儲(chǔ)位置；否則返回NULL。查找過(guò)程從開(kāi)始結(jié)點(diǎn)出發(fā)，順著鏈表逐個(gè)將結(jié)點(diǎn)的值和給定值x作比較。
2線性鏈表的插入
線性鏈表的插入是指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性鏈表中插入一個(gè)新元素。
插入運(yùn)算是將值為X的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到ai-1，與ai之間。因此，我們必須首先找到ai-1的存儲(chǔ)位置p，然后生成一個(gè)數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)*p，并令結(jié)點(diǎn)，p的指針域指向新結(jié)點(diǎn)，新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)ai
由線性鏈表的插入過(guò)程可以看出，由于插入的新結(jié)點(diǎn)取自于可利用棧，因此，只要可利用棧不空，在線性鏈表插入時(shí)總能取到存儲(chǔ)插入元素的新結(jié)點(diǎn)，不會(huì)發(fā)生“上溢”的情況。而且，由于可利用棧是公用的，多個(gè)線性鏈表可以共享它，從而很方便地實(shí)現(xiàn)了存儲(chǔ)空間的動(dòng)態(tài)分配。另外，線性鏈表在插入過(guò)程中不發(fā)生數(shù)據(jù)元素移動(dòng)的現(xiàn)象，只要改變有關(guān)結(jié)點(diǎn)的指針即可，從而提高了插入的效率。
3多線性鏈表的刪除
線性鏈表的刪除是指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性鏈表中刪除包含指定元素的結(jié)點(diǎn)。
刪除運(yùn)算是將表的第i個(gè)結(jié)點(diǎn)刪去。因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)a的存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn)ai-1，的指針域Next中，所以我們必須首先找到ai-1的存儲(chǔ)位置p。然后令p->Next指向ai的直接后件結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)a的空間。
從線性鏈表的刪除過(guò)程可以看出，從線性鏈表中刪除一個(gè)元素后，不需要移動(dòng)表中的數(shù)據(jù)元素，只要改變被刪除元素所在結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的指針域即可。另外，由于可利用棧是用于收集計(jì)算機(jī)中所有的空閑結(jié)點(diǎn)，因此，當(dāng)從線性鏈表中刪除一個(gè)元素后，該元素的存儲(chǔ)結(jié)點(diǎn)就變?yōu)榭臻e，應(yīng)將空閑結(jié)點(diǎn)送回到可利用棧。
考點(diǎn)14 線性雙向鏈表的結(jié)構(gòu)及其基本運(yùn)算
1什么是雙向鏈表
在單鏈表中，從某個(gè)結(jié)點(diǎn)出發(fā)可以直接找到它的直接后件，時(shí)間復(fù)雜度為O(1)，但無(wú)法直接找到它的互接前件；在單循環(huán)鏈表中，從某個(gè)結(jié)點(diǎn)出發(fā)可以直接找到它的直接后件，時(shí)間復(fù)雜度仍為O(1)，直接找到它的直接前件，時(shí)間復(fù)雜度為O(n)。有時(shí)，希望能快速找到一個(gè)結(jié)點(diǎn)的直接前件，這時(shí)，可以在單鏈表中的結(jié)點(diǎn)中增加一個(gè)指針域指向它的直接前件，這樣的鏈表，就稱為雙向鏈表(一個(gè)結(jié)點(diǎn)中含有兩個(gè)指針)。如果每條鏈構(gòu)成一個(gè)循環(huán)鏈表，則會(huì)得到雙向循環(huán)鏈表
2雙向鏈表的基本運(yùn)算
(l)插入：在HEAD為頭指針的雙向鏈表中，在值為Y的結(jié)點(diǎn)之后插入值為X的結(jié)點(diǎn)，插入結(jié)點(diǎn)的指針變化。如圖1-20所示(若改為在值為Y的結(jié)點(diǎn)之前插入值為X的結(jié)點(diǎn)，可以做類似分析)。
(2)刪除：在以HEAD為頭指針的雙向鏈表中刪除值為X的結(jié)點(diǎn)，刪除算法的指針變化，如圖1-21所示。
考點(diǎn)15 循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算
單鏈表上的訪問(wèn)是一種順序訪問(wèn)，從其中的某一個(gè)結(jié)點(diǎn)出發(fā)，可以找到它的直接后件，但無(wú)法找到它的直接前件。
在前面所討論的線性鏈表中，其插入與刪除的運(yùn)算雖然比較方便，但還存在一個(gè)問(wèn)題，在運(yùn)算過(guò)程中對(duì)于空表和對(duì)第一個(gè)結(jié)點(diǎn)的處理必須單獨(dú)考慮，使空表與非空表的運(yùn)算不統(tǒng)一。
因此，我們可以考慮建立這樣的鏈表，具有單鏈表的特征，但又不需要增加額外的存貯空間，僅對(duì)表的鏈接方式稍做改變，使得對(duì)表的處理更加方便靈活。從單鏈表可知，最后一個(gè)結(jié)點(diǎn)的指針域?yàn)镹ULL，表示單鏈表已經(jīng)結(jié)束。如果將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域改為存放鏈表中頭結(jié)點(diǎn)(或第一個(gè)結(jié)點(diǎn))的地址，就使得整個(gè)鏈表構(gòu)成一個(gè)環(huán)，又沒(méi)有增加額外的存儲(chǔ)空間