線性表的鏈?zhǔn)酱鎯?chǔ)表示和實(shí)現(xiàn)

1、第二章 線性表第三節(jié) 線性表的鏈?zhǔn)酱鎯?chǔ)表示和實(shí)現(xiàn)2.3.1 單鏈表和指針前面已經(jīng)提到，由于在順序表中插入或刪除一個(gè)數(shù)據(jù)元素，平均約需移動(dòng)表中一半元素。因此，對(duì)于需要經(jīng)常進(jìn)行插入和刪除操作、表中元素相對(duì)不穩(wěn)定的線性表，不應(yīng)該采用順序存儲(chǔ)表示，而應(yīng)該采用鏈?zhǔn)酱鎯?chǔ)表示。 何謂"鏈?zhǔn)酱鎯?chǔ)表示"?鏈?zhǔn)酱鎯?chǔ)表示指的是以"附加信息(指針)" 表示數(shù)據(jù)元素之間的邏輯關(guān)系。線性表的鏈?zhǔn)酱鎯?chǔ)表示的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素（這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的）。因此，為了表示每個(gè)數(shù)據(jù)元素與其直接后繼數(shù)據(jù)元素之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素來說，除了存儲(chǔ)

2、其本身的信息之外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息（即直接后繼的存儲(chǔ)位置）。由這兩部分信息組成一個(gè)"結(jié)點(diǎn)"（如下圖所示），表示線性表中一個(gè)數(shù)據(jù)元素。數(shù)據(jù)域 m_Data指針域 m_pNext其中存儲(chǔ)數(shù)據(jù)元素信息的域稱作數(shù)據(jù)域（設(shè)域名為m_pData），存儲(chǔ)直接后繼存儲(chǔ)位置的域稱為指針域（設(shè)域名為m_pNext）。指針域中存儲(chǔ)的信息又稱做指針或鏈。 由分別表示, 的N 個(gè)結(jié)點(diǎn)依次相鏈構(gòu)成的鏈表，稱為線性表的鏈?zhǔn)酱鎯?chǔ)表示，由于此類鏈表的每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，故又稱單鏈表或線性鏈表，如下圖所示。由于鏈?zhǔn)酱鎯?chǔ)不要求線性表的元素依次"緊挨"存放，因此在進(jìn)行插

3、入和刪除操作改變元素之間的關(guān)系時(shí)就不需要移動(dòng)元素，因此它沒有順序存儲(chǔ)結(jié)構(gòu)所具有的弱點(diǎn)，但同時(shí)也失去了順序表可隨機(jī)存取的優(yōu)點(diǎn)。和順序表類似，在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中仍以第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址作為線性表的基地址，通常稱它為頭指針，線性表中所有數(shù)據(jù)元素都可以從頭指針出發(fā)找到。因?yàn)榫€性表的最后一個(gè)數(shù)據(jù)元素沒有后繼，因此最后一個(gè)結(jié)點(diǎn)中的"指針"是一個(gè)特殊的值 "NULL" （在圖上用表示），通常稱它為"空指針"。頭指針的值為第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置，第一個(gè)結(jié)點(diǎn)中的"指針"指向第二個(gè)結(jié)點(diǎn)，即它的值為第二個(gè)結(jié)點(diǎn)的存儲(chǔ)位置，第二個(gè)結(jié)點(diǎn)中的&

4、quot;指針"指向第三個(gè)結(jié)點(diǎn)，依次類推，直至最后一個(gè)結(jié)點(diǎn)。 為了便于處理一些特殊情況，在第一個(gè)結(jié)點(diǎn)之前附加一個(gè)"頭結(jié)點(diǎn)"，令該結(jié)點(diǎn)中指針域的指針指向第一個(gè)元素結(jié)點(diǎn)，并令頭指針指向頭結(jié)點(diǎn)，如下圖所示。頭結(jié)點(diǎn)的結(jié)構(gòu)和鏈表中其它結(jié)點(diǎn)相同，只是它的數(shù)據(jù)域中不存放任何信息，但它的指針域存放的是第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址，即線性表的基地址。此時(shí)稱指向頭結(jié)點(diǎn)的指針為頭指針。通常稱這類單鏈表為"帶頭結(jié)點(diǎn)的單鏈表"。 值得注意的是，若線性表為空，在不帶頭結(jié)點(diǎn)的情況下，頭指針為空(NULL)，但在帶頭結(jié)點(diǎn)的情況下，鏈表的頭指針不為空，而是其頭結(jié)點(diǎn)中指針域的指針為空

5、，如下圖所示。 如果不特別聲明的話，那么以后各節(jié)中討論的單鏈表都指的是這種帶頭結(jié)點(diǎn)的鏈表?？梢杂?C 語言中的"結(jié)構(gòu)指針"來描述鏈表結(jié)構(gòu)。struct ListNode ElemType m_Data;ListNode * m_pNext;從C語言的類型定義可見，在鏈表中，"結(jié)點(diǎn)" 和 "指針" 是相互緊密關(guān)聯(lián)的兩個(gè)概念，不同的結(jié)點(diǎn)結(jié)構(gòu)對(duì)應(yīng)有不同的指針類型。若設(shè)ListNode *p,*q; 則 p和q 均為以上定義的指針型變量。若 p 的值非空，則表明 p 指向某個(gè)結(jié)點(diǎn)，p->m_Data 表示 p 所指結(jié)點(diǎn)中的數(shù)據(jù)域，p-&

6、gt;m_pNext 表示 p 所指結(jié)點(diǎn)中的指針域，若非空，則指向其"后繼"結(jié)點(diǎn)。對(duì)變量 p 和 q 定義之后，它們的值是什么？和其它變量相同，在沒有對(duì)它們進(jìn)行賦值之前，它們是"沒有值"的。 p->m_Data 即為(*p).m_Data，類似地，p->m_pNext 即為(*p).m_pNext。注意：只有在 p "有值" 且"值不為空"的情況下，p->m_Data 和 p->m_pNext 才有意義。指針型變量只能作同類型的指針賦值與比較操作。并且，指針型變量的"值"

7、除了由同類型的指針變量賦值得到外，都必須用 C 語言中的動(dòng)態(tài)分配函數(shù)得到。例如，p = new ListNode; 表示在運(yùn)行時(shí)刻系統(tǒng)動(dòng)態(tài)生成了一個(gè)ListNode 類型的結(jié)點(diǎn)，并令指針 p "指向"該結(jié)點(diǎn)。反之，當(dāng)指針 p 所指結(jié)點(diǎn)不再使用，可用 delete p; 釋放此結(jié)點(diǎn)空間。 注意：一旦執(zhí)行了delete p; 的語句，(*p)不再存在，自然 p->m_Data 和 p->m_pNext 也就沒有意義了。2.3.2 單鏈表中基本操作的實(shí)現(xiàn)以下重點(diǎn)討論線性表的五個(gè)基本操作在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的實(shí)現(xiàn)。一、初始化操作根據(jù)上一節(jié)的約定，初始化建一個(gè)空的鏈表即為建立

8、一個(gè)只有頭結(jié)點(diǎn)的鏈表。 算法2.13void InitList(ListNode &L )/ 創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的空鏈表,L 為指向頭結(jié)點(diǎn)的指針L.m_pNext = 0; = NULL; / InitList算法的時(shí)間復(fù)雜度為O (1)。"空"鏈表的頭指針是否為NULL? 若鏈表不帶頭結(jié)點(diǎn)，則以頭指針L=NULL表示空表，在帶頭結(jié)點(diǎn)的情況下，則需建立一個(gè)其指針域的指針為NULL的頭結(jié)點(diǎn)，并令頭指針指向該結(jié)點(diǎn)。 鏈表是一個(gè)進(jìn)行動(dòng)態(tài)存儲(chǔ)管理的結(jié)構(gòu)，因此在初始化時(shí)不需要按照線性表實(shí)際所需最大容量進(jìn)行預(yù)分配。 二、銷毀結(jié)構(gòu)操作 算法2.14void DestroyList(

9、ListNode &L)/ 銷毀以L為頭指針的單鏈表，釋放鏈表中所有結(jié)點(diǎn)空間while(L.m_pNext)ListNode *p = L.m_pNext;L.m_pNext = p->m_pNext;delete p; / while / DestroyList算法的時(shí)間復(fù)雜度為O (Listlength(L)。 "銷毀結(jié)構(gòu)"的操作是在該鏈表的使命已經(jīng)完成之后進(jìn)行的，則應(yīng)將它占有的空間"釋放"。但在C+語言中，析構(gòu)函數(shù)是在類對(duì)象生命期結(jié)束的時(shí)候由系統(tǒng)自動(dòng)調(diào)用。三、存取元素操作單鏈表是一種"順序存取"的結(jié)構(gòu)，即：為取第

10、i 元素，首先必須先找到第 i-1 個(gè)元素。因此不論 i 值為多少，都必須從頭結(jié)點(diǎn)開始起"點(diǎn)數(shù)"，直數(shù)到第 i 個(gè)為止。頭結(jié)點(diǎn)可看成是第0個(gè)結(jié)點(diǎn)?？梢娝惴ㄖ袘?yīng)設(shè)一個(gè)指針變量p和一個(gè)整數(shù)變量 j，并使 p 和 j 同步變化，始終保持指針 p 指向第j的結(jié)點(diǎn)的狀態(tài)。算法2.15int GetElem(const ListNode& L, int pos, ElemType &e )/ 若1posLengthList(L)，則用 e 帶回指針L指向頭結(jié)點(diǎn)的單鏈表/ 中第 pos 個(gè)元素的值且返回函數(shù)值為TRUE,否則返回函數(shù)值為FALSE ListNode *p

11、= L.m_pNext; / 變量初始化，p 指向第一個(gè)結(jié)點(diǎn)int j =1; while ( p && j< pos ) / 順結(jié)點(diǎn)的指針向后查找，直至 p 指到第pos個(gè)結(jié)點(diǎn)或 p 為空止 p = p->m_pNext; +j; if ( !p | j>pos )return 0; / 鏈表中不存在第 pos 個(gè)結(jié)點(diǎn) e = p->m_Data; / 取到第 pos 個(gè)元素 return 1;算法的時(shí)間復(fù)雜度為O (ListLength(L)。由于鏈表的長度是個(gè)隱含值，因此無法預(yù)先判別參數(shù)pos是否超過表長，只能在"數(shù)結(jié)點(diǎn)" 過程

12、中，j還沒有達(dá)到 pos 時(shí)而指針變?yōu)榭諘r(shí)才能判斷出參數(shù)不合法。什么情況下會(huì)出現(xiàn) j>pos 的情況？ j>pos 的情況即為 pos<1 的情況，注意：因算法中j的初值為"1"，若 pos=1，則 while 循環(huán)一次也不執(zhí)行。 能否將變量初始化改為"p=L; j=0;"? 對(duì) pos 為正常值的情況沒有影響，只是使 while 循環(huán)多執(zhí)行一次吧了。但此時(shí)無法用 j>pos 判別出 pos<1 的錯(cuò)誤，當(dāng)然也可以在函數(shù)一開始就加上 pos 是否大于0的判別？ 算法時(shí)間復(fù)雜度的分析：控制結(jié)構(gòu)只有 while 一個(gè)單循環(huán)，基本

13、操作為"移動(dòng)指針"，最壞情況是 pos>=表長的情況，指針需從頭移到尾。四、插入元素操作前面已經(jīng)分析過，在線性表中"插入"一個(gè)元素時(shí)，使元素之間的關(guān)系<,>改變?yōu)?lt;,e>和<e,>。當(dāng)用指針指示后繼元素時(shí)，實(shí)現(xiàn)這種關(guān)系的改變就很容易了，只要修改相應(yīng)指針即可。因?yàn)樾碌脑夭迦朐诰€性表的第i個(gè)元素之前，使得不再是 的后繼，而是新的元素e的后繼，因此需要修改元素e和元素所在結(jié)點(diǎn)的指針。由此，算法的基本思想就是，首先找到第i-1個(gè)結(jié)點(diǎn)，然后修改相應(yīng)指針。 算法2.16int ListInsert (ListNode &a

14、mp;L, int pos, ElemType e)/ 若1posLengthList(L)+1，則在指針L指向頭結(jié)點(diǎn)的單鏈表/ 的第 pos 個(gè)元素之前插入新的元素 e，且返回函數(shù)值為 TRUE,/ 否則不進(jìn)行插入且返回函數(shù)值為 FALSE ListNode *p = L.m_pNext;int j=0; while(p && j<pos-1) / 查找第pos-1個(gè)結(jié)點(diǎn)，并令指針p指向該結(jié)點(diǎn) p = p->m_pNext;+j; if(!p | j>pos-1) return 0; / 參數(shù)不合法，pos 小于1或者大于表長+1 ListNode *s =

15、 new ListNode; if (!s)return 0; / 存儲(chǔ)空間分配失敗 s->m_Data=e; / 創(chuàng)建新元素的結(jié)點(diǎn) s->m_pNext = p->m_pNext; p->m_pNext = s; / 修改指針 return 1;算法時(shí)間復(fù)雜度為O (ListLength(L)。這里的變量初始化能否改為 "p=L->m_pNext; j=1;"? 不行!因?yàn)椴迦霑r(shí)修改的是前驅(qū)結(jié)點(diǎn)的指針，因此算法中的目標(biāo)是找第 pos 個(gè)結(jié)點(diǎn)的前驅(qū)，如果一開始，p 就指向第一個(gè)結(jié)點(diǎn)，那么當(dāng)pos=1時(shí)就找不到它的前驅(qū)了。你想到了嗎? 如果單鏈表

16、沒有頭結(jié)點(diǎn)，應(yīng)該如何修改算法2.16? 需對(duì)在第一個(gè)結(jié)點(diǎn)之前進(jìn)行插入的情況單獨(dú)進(jìn)行處理。是不是很麻煩呀？ 算法時(shí)間復(fù)雜度的分析：在插入算法中，修改指針的時(shí)間復(fù)雜度僅為O(1)，但為了修改前驅(qū)結(jié)點(diǎn)的指針首先要找到這個(gè)結(jié)點(diǎn)，因此插入算法的時(shí)間主要消耗在查詢結(jié)點(diǎn)上，因此，其時(shí)間復(fù)雜度和"存取元素"的操作相同。五、刪除元素操作和插入類似，由于刪除元素改變了元素之間的關(guān)系，使不再是的后繼，而是的后繼，因此需要修改元素所在結(jié)點(diǎn)的指針。因此在單鏈表中刪除元素操作的算法基本思想和插入相同，也是：首先找到第 i-1 個(gè)結(jié)點(diǎn)，然后修改相應(yīng)指針。算法2.17int ListDelete(List

17、Node &L, int pos, ElemType &e)/ 若1posLengthList(L)，則刪除指針L指向頭結(jié)點(diǎn)的單鏈表/ 中第 pos 個(gè)元素并以 e 帶回其值，返回函數(shù)值為 TRUE，/ 否則不進(jìn)行刪除操作且返回函數(shù)值為 FALSE ListNode *p = L.m_pNext;int j=0; while(p && j<pos-1) / 尋找第pos個(gè)結(jié)點(diǎn)，并令p指向其前驅(qū) p = p->m_pNext;+j; if(!p->m_pNext | j > pos-1) return 0; / 刪除位置不合理 ListNo

18、de *q = p->m_pNext; / 修改指針p->m_pNext = q->m_pNext; e = q->m_Data;delete(q); / 釋放結(jié)點(diǎn)空間 return 1; 算法時(shí)間復(fù)雜度為O (ListLength(L)。你是否注意到了，在刪除算法中參數(shù)不合理的判斷條件和插入的情況不同？為什么？因?yàn)閷?duì)插入而言，只要"前驅(qū)"存在即可，而對(duì)刪除而言，不僅"前驅(qū)"要存在，被刪結(jié)點(diǎn)也必須存在。你是否也想到了？ 如果單鏈表沒有頭結(jié)點(diǎn)，應(yīng)該如何修改算法2.17? 需對(duì)刪除第一個(gè)結(jié)點(diǎn)的情況進(jìn)行單獨(dú)處理。你一定也想到了，因?yàn)楹筒?/p>

19、入是一樣的問題，對(duì)吧？ 算法時(shí)間復(fù)雜度的分析：顯然，和插入一樣，其時(shí)間消耗在查詢前驅(qū)結(jié)點(diǎn)上。2.3.3 單鏈表其它算法舉例例2-7 逆序創(chuàng)建鏈表假設(shè)線性表(,，)的數(shù)據(jù)元素存儲(chǔ)在一維數(shù)組 An中，則從數(shù)組的最后一個(gè)分量起，依次生成結(jié)點(diǎn)，并逐個(gè)插入到一個(gè)初始為"空"的鏈表中。解題分析：由于鏈表是一種動(dòng)態(tài)存儲(chǔ)管理的結(jié)構(gòu)，鏈表中每個(gè)結(jié)點(diǎn)占用的存儲(chǔ)空間不需預(yù)先分配劃定，而是在運(yùn)行時(shí)刻由系統(tǒng)應(yīng)需求即時(shí)生成，因此，建立鏈表的過程是一個(gè)動(dòng)態(tài)生成的過程。即從 "空表"起，依次建立結(jié)點(diǎn)，并逐個(gè)插入鏈表。所謂"逆序"創(chuàng)建鏈表指的是，依和線性表的邏輯順序相

20、"逆"的次序輸入元素。例如線性表 (a,b,c,d,e) 的逆序創(chuàng)建的過程。由于鏈表的生成是從最后一個(gè)結(jié)點(diǎn)起逐個(gè)插入，因此每個(gè)新生成的結(jié)點(diǎn)都是插入在鏈表的"第一個(gè)"結(jié)點(diǎn)之前，即頭結(jié)點(diǎn)之后，使新插入的結(jié)點(diǎn)成為插入之后的鏈表中的第一個(gè)結(jié)點(diǎn)。 算法2.19int InsertToList_Head(ListNode& L, ElemType data)ListNode *p = new ListNode;if(!p)return 0; / 存儲(chǔ)空間分配失敗p->m_Data = data; / 賦元素值p->m_pNext = L.m_pN

21、ext; L.m_pNext = p; / 插入在頭結(jié)點(diǎn)之后return 1;int CreateList_L(ListNode &L, int n, ElemType a) / 已知數(shù)組 A 中存有線性表的 n 個(gè)數(shù)據(jù)元素，/ 逆序建立帶頭結(jié)點(diǎn)的單鏈表。for(int i=0; i<n; i+)if(!InsertToList_Head(L, ai)return 0;return 1;容易看出，算法的時(shí)間復(fù)雜度為O (ListLength(L)?？刂平Y(jié)構(gòu)只有一個(gè)單循環(huán)，循環(huán)次數(shù)和表長相同。 如果是"順序"創(chuàng)建單鏈表，那么算法該如何寫呢？ 因?yàn)槊總€(gè)新生成的結(jié)點(diǎn)

22、的插入位置在表尾，則算法中必須維持一個(gè)始終指向已建立的鏈表表尾的指針。其實(shí)也很簡單，對(duì)嗎？ 例2-8 以鏈表作存儲(chǔ)結(jié)構(gòu)解例2-5的問題，即將線性表(,)改變成(, , , )。在以順序表作存儲(chǔ)結(jié)構(gòu)時(shí)，我們曾分析過它的一個(gè)簡單算法就是，將從起到的數(shù)據(jù)元素從原地刪除后再插入到之前，而在以順序表作存儲(chǔ)結(jié)構(gòu)時(shí)因?yàn)樾枰罅恳苿?dòng)元素而不能采用。那么在以鏈表作存儲(chǔ)結(jié)構(gòu)時(shí)能否采用這個(gè)算法呢？ 解題分析：因?yàn)閷?duì)鏈表來說，"插入"和"刪除"僅需修改指針即可完成，并且由于前 m 個(gè)元素之間和后 n 個(gè)元素之間的鏈接關(guān)系分別都不需要改變，則算法的實(shí)際操作為：(1) 從鏈表中刪除

23、(, )；(2) 將(, )鏈接到頭結(jié)點(diǎn)之后；(3) 將(, )鏈接到之后。算法2.20void Exchange_L(ListNode &L, int m)/ 本算法實(shí)現(xiàn)單鏈表中前 m 個(gè)結(jié)點(diǎn)和后 n 個(gè)結(jié)點(diǎn)的互換 if ( m && L.m_pNext) / 鏈表不空且 m!=0 ListNode *p = L.m_pNext;int k = 1; while(k<m && p ) / 查找 am 所在結(jié)點(diǎn) p = p->m_pNext;+k; if(p && p->m_pNext) / n!=0 時(shí)才需要修改指針

24、ListNode *ha = L.m_pNext; / 以指針 ha 記 a1 結(jié)點(diǎn)的位置 L.m_pNext = p->m_pNext; / 將 b1 結(jié)點(diǎn)鏈接在頭結(jié)點(diǎn)之后 p->m_pNext = 0; / 設(shè) am 的后繼為空 ListNode *q = L.m_pNext; / 令q 指向 b1 結(jié)點(diǎn) while (q->m_pNext) / 查找 bn 結(jié)點(diǎn)q = q->m_pNext; q->m_pNext = ha; / 將 a1 結(jié)點(diǎn)鏈接到 bn 結(jié)點(diǎn)之后 算法的時(shí)間復(fù)雜度為O (ListLength(L)。循環(huán)的條件中為什么要有p!=NULL的判

25、斷？ 因?yàn)閱捂湵淼拈L度是個(gè)隱含值，在此無法如順序表那樣事先判別參數(shù) m 是否合法，如果參數(shù)不合適，則在沒有找到第 m 個(gè)結(jié)點(diǎn)時(shí)，p=NULL，while 循環(huán)中的語句就會(huì)出問題。 由于參數(shù)中沒有給出 n 的值，只有在找到 am 之后加以判別。如果這里不加 p-> m_pNext是否為空的判別條件，下面哪一個(gè)語句會(huì)出問題？ 算法執(zhí)行到 q-> m_pNext 時(shí)會(huì)出問題，因?yàn)楫?dāng)p-> m_pNext =NULL 時(shí)，q=NULL，q-> m_pNext 也就不成立了。這種情況對(duì)初學(xué)鏈表的人是最容易出問題的地方，但千萬要注意避免。 整個(gè)算法就是對(duì)鏈表從頭巡視到尾，兩個(gè)單循環(huán)

26、次數(shù)之和恰為表長。因此算法的時(shí)間復(fù)雜度為O(ListLength(L)。此例充分顯示了用"指針"指示"后繼"的靈活性。例2-9 編寫算法刪除單鏈表中"多余"的數(shù)據(jù)元素，即使操作之后的單鏈表中所有元素的值都不相同。解題分析：可以和順序表采用同樣算法，即設(shè)想新建一個(gè)鏈表，然后順序考察原鏈表中每一個(gè)結(jié)點(diǎn)的數(shù)據(jù)元素，在"新表"中進(jìn)行查找，如果有相同的則舍棄之，否則就插入到新表中。算法2.21void Purge_L(ListNode &L )/ 刪除單鏈表L中的冗余元素，即使操作之后的單鏈表中只保留/ 操作之前表中

27、所有值都不相同的元素 ListNode *p = L.m_pNext; L.m_pNext = NULL; / 設(shè)新表為空表 while (p) / 順序考察原表中每個(gè)元素 ListNode *succ = p->m_pNext; / 記下結(jié)點(diǎn) *p 的后繼 ListNode *q = L.m_pNext; / q 指向新表的第一個(gè)結(jié)點(diǎn) while( q && p->m_Data != q->m_Data) / 在新表中查詢是否存在和p->m_Data 相同的元素q = q->m_pNext; if (!q) / 將結(jié)點(diǎn) *p 插入到新的表中 p-

28、>m_pNext = L.m_pNext; L.m_pNext = p; else delete p; / 釋放結(jié)點(diǎn) *p p = succ; 此算法的時(shí)間復(fù)雜度為O (ListLength2(L)。假設(shè)已知鏈表中的數(shù)據(jù)元素為(5,2,5,3,3,4,2,5,7,5,4,3),則經(jīng)算法2.21操作之后的鏈表表示的線性表是什么？ 是(7,4,3,2,5)。因?yàn)樗惴ㄖ械?quot;插入"操作是將元素"倒序"插入新表中的，由于考慮集合中的元素沒有次序關(guān)系，而"倒插"不需要加輔助指針變量。 試比較算法2.21和算法2.12，你將得出什么結(jié)論？ 你

29、一定發(fā)現(xiàn)這兩個(gè)算法極為相似，因?yàn)樗鼈兲幚淼氖抢?-2提出的同一個(gè)問題。由此可見，順序表和鏈表只是存儲(chǔ)結(jié)構(gòu)的不同，不影響問題求解的算法。 由于對(duì)原表中每個(gè)元素都需要在新的鏈表中進(jìn)行查詢，因此最壞情況下的時(shí)間復(fù)雜度仍為平方級(jí)的，和順序表相同，正好說明這個(gè)時(shí)間復(fù)雜度是由算法決定的。從以上對(duì)鏈表的各種操作的討論可知，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)勢在于：(1) 能有效利用存儲(chǔ)空間；因?yàn)樗莿?dòng)態(tài)存儲(chǔ)分配的結(jié)構(gòu)，不需要預(yù)先為線性表分配足夠大的空間，而是向系統(tǒng)"隨用隨取"，并且在刪除元素時(shí)可同時(shí)釋放空間。(2) 用"指針"指示數(shù)據(jù)元素之間的后繼關(guān)系，便于進(jìn)行"插入&quo

30、t;、"刪除"等操作；插入或刪除時(shí)只需要修改指針，而不需要進(jìn)行大量元素的移動(dòng)。而其劣勢則是不能隨機(jī)存取數(shù)據(jù)元素。同時(shí)，它還丟失了一些順序表有的長處，如線性表的"表長"和數(shù)據(jù)元素在線性表中的"位序"，在上述的單鏈表中都看不見了。又如，不便于在表尾插入元素，需遍歷整個(gè)表才能找到插入的位置。表長和位序是線性表中兩個(gè)重要屬性，在本節(jié)設(shè)置的單鏈表中表長是一個(gè)隱含值，必須從前到后遍歷整個(gè)表才能得到。為了更突出鏈表的優(yōu)勢，需改進(jìn)單鏈表結(jié)構(gòu)的定義。除了保留指向頭結(jié)點(diǎn)的指針外，還應(yīng)增設(shè)"尾指針"和"表長"兩個(gè)屬性

31、，同時(shí)，我們從上面討論的鏈表基本操作的實(shí)現(xiàn)算法中可以看出，在對(duì)鏈表進(jìn)行操作時(shí)，經(jīng)常需要一個(gè)指針在鏈表中巡游，由此可以設(shè)想，如果將這個(gè)在操作中進(jìn)行巡游的"指針"以及它所指結(jié)點(diǎn)的數(shù)據(jù)元素在線性表中的"位序"納入鏈表結(jié)構(gòu)中，作為鏈表定義中的兩個(gè)成員，必然會(huì)對(duì)鏈表的操作帶來很多方便。如算法2.1和2.2中都需要進(jìn)行"在最后一個(gè)結(jié)點(diǎn)之后插入元素"的操作。本來順序表因插入元素要移動(dòng)元素是個(gè)缺點(diǎn)，但當(dāng)插入位置在表尾時(shí)不需要移動(dòng)元素，所需時(shí)間是個(gè)常量，反過來，由于鏈表進(jìn)行插入操作只需要修改指針本是個(gè)優(yōu)點(diǎn)，然而為了查找插入位置卻要遍歷整個(gè)表，所需時(shí)間反而多。由此，在實(shí)際使用鏈表時(shí)需重新考慮鏈表結(jié)構(gòu)的定義并重新設(shè)計(jì)操作界面。詳細(xì)情況將留在2.5節(jié)進(jìn)行討論。2.3.4 循環(huán)鏈表循環(huán)鏈表(Circular Linked List)是線性表的另一種形式的鏈?zhǔn)酱鎯?chǔ)表示。它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表成為一個(gè)由鏈指針相鏈接的環(huán)，并且將頭指針設(shè)成指向最后一個(gè)結(jié)點(diǎn)。空的循環(huán)鏈表由只含一個(gè)自成循環(huán)的頭結(jié)點(diǎn)表示。頭指針指向表尾的好處是既能立即找到鏈表的尾結(jié)點(diǎn)，也容易找到鏈表中的第一個(gè)結(jié)點(diǎn)。循環(huán)鏈表的操作和單鏈表基本一致，差別僅在于，判別鏈表中最后一個(gè)結(jié)點(diǎn)