線性表的鏈式存儲表示和實現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

14、mp;L, int pos, ElemType e)/ 若1posLengthList(L)+1，則在指針L指向頭結(jié)點的單鏈表/ 的第 pos 個元素之前插入新的元素 e，且返回函數(shù)值為 TRUE,/ 否則不進行插入且返回函數(shù)值為 FALSE ListNode *p = L.m_pNext;int j=0; while(p && j<pos-1) / 查找第pos-1個結(jié)點，并令指針p指向該結(jié)點 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; / 存儲空間分配失敗 s->m_Data=e; / 創(chuàng)建新元素的結(jié)點 s->m_pNext = p->m_pNext; p->m_pNext = s; / 修改指針 return 1;算法時間復雜度為O (ListLength(L)。這里的變量初始化能否改為 "p=L->m_pNext; j=1;"? 不行!因為插入時修改的是前驅(qū)結(jié)點的指針，因此算法中的目標是找第 pos 個結(jié)點的前驅(qū)，如果一開始，p 就指向第一個結(jié)點，那么當pos=1時就找不到它的前驅(qū)了。你想到了嗎? 如果單鏈表

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

17、Node &L, int pos, ElemType &e)/ 若1posLengthList(L)，則刪除指針L指向頭結(jié)點的單鏈表/ 中第 pos 個元素并以 e 帶回其值，返回函數(shù)值為 TRUE，/ 否則不進行刪除操作且返回函數(shù)值為 FALSE ListNode *p = L.m_pNext;int j=0; while(p && j<pos-1) / 尋找第pos個結(jié)點，并令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é)點空間 return 1; 算法時間復雜度為O (ListLength(L)。你是否注意到了，在刪除算法中參數(shù)不合理的判斷條件和插入的情況不同？為什么？因為對插入而言，只要"前驅(qū)"存在即可，而對刪除而言，不僅"前驅(qū)"要存在，被刪結(jié)點也必須存在。你是否也想到了？ 如果單鏈表沒有頭結(jié)點，應(yīng)該如何修改算法2.17? 需對刪除第一個結(jié)點的情況進行單獨處理。你一定也想到了，因為和插

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

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

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

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

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

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

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

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

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

28、>m_pNext = L.m_pNext; L.m_pNext = p; else delete p; / 釋放結(jié)點 *p p = succ; 此算法的時間復雜度為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)。因為算法中的"插入"操作是將元素"倒序"插入新表中的，由于考慮集合中的元素沒有次序關(guān)系，而"倒插"不需要加輔助指針變量。 試比較算法2.21和算法2.12，你將得出什么結(jié)論？ 你

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

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

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