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