基本數據結構實現–雙鏈表【含測試程式碼】
- 2021 年 6 月 29 日
- 筆記
- 基本數據結構實現(包括測試程式碼)
基本數據結構實現–雙鏈表
*概述
單鏈表節點中只有一個指向其後記的指針，使得單鏈表只能從頭節點依次順序地向後遍歷。要訪問某個節點的前驅節點，只能從頭
開始遍歷，在拿到某節點指針p後，訪問p的後繼節點的時間複雜度為O(1)，訪問前驅節點的時間複雜度依舊是O(N)。
為了解決這個問題，引入了雙鏈表。在原本的單鏈表每個節點中加入了一個指向其前驅的節點prior。因此，在我們拿到某節點指針p
的前提下，想要對這個節點的前驅進行操作就可以在O(1)的時間內完成。請注意：一般情況下我們並沒有鏈表中所有節點的指針資訊，
而是僅僅保存類似頭節點、尾節點的標誌性節點。
對於單鏈表，拿到某節點指針p後，其後所有節點都可以找到，而想要訪問前面的節點只能從頭節點開始一一查找。而對於雙鏈表來說，
拿到某節點指針後既可以向後查找，也可以向前查找。
*雙鏈表結構類型的定義
一個雙鏈表的類型可以定義如下：
1 typedef struct DNode { 2 ElemType data; //節點數據域 3 DNode* next,* prior; //後繼指針、前驅指針 4 } * DLinkList;
此處，DNode 定義了一個雙鏈表的節點類型，DLinkList便定義了一個雙鏈表。DLinkList即是頭結點指針。請注意：要標記一個鏈表，只需
要保存鏈表的頭節點指針就可以了(當然根據需求不同也可以保存尾指針，甚至第i個節點的指針)。因此這裡DLinkList既是雙鏈表的頭指針，又
代表了「雙鏈表」這一數據類型。
*雙鏈表基本操作及其實現
(1) 初始化一個雙鏈表
1 void InitDLinkList(DLinkList& L) 2 { 3 L = new DNode; //C語言版:L = (DNode*)malloc(sizeof(DNode)); 4 L->data = 0; 5 L->next = NULL; 6 L->prior = NULL; 7 }
由於L指向的是鏈表的頭節點，這個數據域是不屬於鏈表的有效元素的，如果沒有他用，可以隨意賦值（這裡賦值0）.
(2) 後插操作,在p指向的節點之後插入s指向的節點。插入成功返回true，失敗(如p不合法等)返回false。
1 bool InsertNextDNode( DNode* p,DNode* s ) 2 { 3 if( p == NULL || s == NULL ) 4 return false; 5 s->next = p->next; 6 //如果p是最後一個節點，p沒有下一個節點，自然不需要修改下一個結點的前驅指針 7 if( p->next != NULL ) 8 p->next->prior = s; 9 s->prior = p; 10 p->next = s; 11 return true; 12 }
注意這裡與單鏈表的不同。雙鏈表在插入、刪除操作時不僅要修改next指針，還要修改節點的prior指針。在後插時，
如果p是最後一個節點，則不需要修改p->next->prior：因為p沒有next。其他情況時需要修改p->next->prior為s。
(3) 刪除操作：刪除p的後繼節點。成功刪除返回true，失敗（如p不合法，或p沒有後繼節點等）返回false。
1 bool DeleteNextDNode( DNode* p ) 2 { 3 if( p == NULL ) 4 return false; 5 if( p->next == NULL ) 6 return false; 7 DNode* q = p->next; //q是p的後繼節點 8 //需要修改兩個指針：p的next以及q的後繼的prior 9 if( q->next != NULL ) 10 q->next->prior = p; 11 p->next = q->next; 12 delete q; //C語言版: free(q); 13 return true; 14 }
要注意：p是否是最後一個節點？p的下一個節點是否是最後一個節點?
(4) 按值查找
1 DNode* LocateElem( DLinkList DL,ElemType e ) 2 { 3 DNode* p = DL->next; 4 while( p != NULL && p->data != e ) { 5 p = p->next; 6 } 7 return p; 8 }
(5) 按位序查找
1 DNode* GetElem( DLinkList L, int i ) 2 { 3 if( i < 0 ) //認為頭節點是第0個節點，如果輸入i為0則返回頭結點的指針 4 return NULL; 5 int j = 0; 6 DNode* p = L; 7 while( j != i && p != NULL ) { 8 j++; 9 p = p->next; 10 } 11 return p; 12 }
按值查找與按位序查找在僅有頭指針的前提下和單鏈表中的實現沒有任何區別。
(6) 銷毀整個鏈表
在實現了刪除後繼節點的操作後，我們就可以使用這個操作，逐一刪除頭節點的後繼節點，從而達成銷毀整個
鏈表的目的。請注意：把頭結點看成第0個節點的話，每執行一次，相當於刪除了鏈表中的第一個節點，而刪
除前的第二個節點成為了新的第一個節點。實現程式碼如下：
1 void DestroyList( DLinkList& DL ) 2 { 3 while( DL->next != NULL ) 4 DeleteNextDNode(DL); 5 delete DL; 6 DL = NULL; 7 }
* 程式碼測試
以下測試先將0,2,4,6,8,10,12,14,16,18這10個數以後插的方式建立鏈表，然後嘗試找到值為18的節點並
將其刪除；接下來測試查找不存在的，值為200的節點。然後嘗試用後插操作實現一個前插操作。（思想：
在p前插入s，先通過prior指針拿到p的前驅節點pp，這樣，就相當於對pp執行後插操作）。
1 /* 帶頭節點的雙鏈表 2 3 實現操作： 4 *1 刪除p的後繼節點 5 *2 後插操作：在p後插入s 6 *3 前插操作：在p前插入s 7 *4 按值查找 8 *5 按位序查找 9 *6 銷毀整個鏈表 10 */ 11 #include <iostream> 12 #include <cstdio> 13 using namespace std; 14 15 typedef int ElemType; 16 17 typedef struct DNode { 18 ElemType data; //節點數據域 19 DNode* next,* prior; //後繼指針、前驅指針 20 } * DLinkList; 21 22 //初始化一個雙鏈表 23 void InitDLinkList(DLinkList& L) 24 { 25 L = new DNode; //C語言版:L = (DNode*)malloc(sizeof(DNode)); 26 L->data = 0; 27 L->next = NULL; 28 L->prior = NULL; 29 } 30 31 //後插操作,在p指向的節點之後插入s指向的節點 32 bool InsertNextDNode( DNode* p,DNode* s ) 33 { 34 if( p == NULL || s == NULL ) 35 return false; 36 s->next = p->next; 37 //如果p是最後一個節點，p沒有下一個節點，自然不需要修改下一個結點的前驅指針 38 if( p->next != NULL ) 39 p->next->prior = s; 40 s->prior = p; 41 p->next = s; 42 return true; 43 } 44 45 //刪除操作：刪除p節點的後繼節點 46 //由於鏈表是帶頭結點的，因此使用這個函數也可以刪除表的第一個數據節點 47 bool DeleteNextDNode( DNode* p ) 48 { 49 if( p == NULL ) 50 return false; 51 if( p->next == NULL ) 52 return false; 53 DNode* q = p->next; //q是p的後繼節點 54 //需要修改兩個指針：p的next以及q的後繼的prior 55 if( q->next != NULL ) 56 q->next->prior = p; 57 p->next = q->next; 58 delete q; //C語言版: free(q); 59 return true; 60 } 61 62 //銷毀整個鏈表 63 void DestroyList( DLinkList& DL ) 64 { 65 while( DL->next != NULL ) 66 DeleteNextDNode(DL); 67 delete DL; 68 DL = NULL; 69 } 70 71 //列印整個鏈表 72 void Print( DLinkList DL ) 73 { 74 if( DL == NULL ) 75 return ; 76 DNode* p = DL->next; 77 while( p != NULL ) { 78 cout << p->data << endl; 79 p = p->next; 80 } 81 82 } 83 84 //按值查找：找到表中第一個值等於e的元素，返回其指針，如果 85 //不存在值等於e的，返回NULL 86 DNode* LocateElem( DLinkList DL,ElemType e ) 87 { 88 DNode* p = DL->next; 89 while( p != NULL && p->data != e ) { 90 p = p->next; 91 } 92 return p; 93 } 94 95 //按位序查找,找到表中第i個元素，返回其指針 96 DNode* GetElem( DLinkList L, int i ) 97 { 98 if( i < 0 ) //認為頭節點是第0個節點，如果輸入i為0則返回頭結點的指針 99 return NULL; 100 int j = 0; 101 DNode* p = L; 102 while( j != i && p != NULL ) { 103 j++; 104 p = p->next; 105 } 106 return p; 107 } 108 109 //嘗試使用後插操作實現一個前插操作：要在p指向的節點前插入s指向的節點， 110 //先拿到p的前驅節點的指針pp，在pp後插入s 111 bool InsertPriorNode( DNode* p,DNode* s ) 112 { 113 if( p == NULL || s == NULL ) 114 return false ; 115 //如果p的前驅為空，說明p是頭節點，顯然不能在頭節點前插入數據 116 if( p->prior == NULL ) 117 return false; 118 DNode* pp = p->prior; 119 InsertNextDNode(pp,s); 120 return true; 121 } 122 123 124 void test1() 125 { 126 //初始化 127 DLinkList DL; 128 InitDLinkList(DL); 129 //測試後插 130 for( int i=0; i<10; i++ ) { 131 DNode* temp = new DNode; 132 temp->data = 2*i; 133 temp->next = temp->prior = NULL; 134 InsertNextDNode(DL,temp); 135 } 136 Print(DL); 137 cout << "-------------------------" << endl; 138 //測試按值查找和刪除 139 { 140 //嘗試找到值為18的節點並將其刪除 141 DNode* temp = LocateElem(DL,18); 142 if( temp != NULL ) 143 DeleteNextDNode(temp); 144 145 //嘗試查找不存在的節點 146 temp = LocateElem(DL,200); 147 if( temp == NULL ) { 148 cout << "200不存在" << endl; 149 } 150 } 151 Print(DL); 152 cout << "--------------------------" << endl; 153 //測試前插操作 154 { 155 //嘗試在第一個元素及最後一個元素前插入值為985的元素 156 DNode* temp1 = GetElem(DL,1); 157 DNode* temp2 = GetElem(DL,9); //表中現在只有9個元素 158 cout << temp2->data << endl; 159 DNode* _9851 = new DNode; 160 _9851->data = 985; 161 _9851->next = _9851->prior = NULL; 162 DNode* _9852 = new DNode; 163 _9852->data = 985; 164 _9852->next = _9852->prior = NULL; 165 if( InsertPriorNode(temp1,_9851) && InsertPriorNode(temp2,_9852) ) 166 Print(DL); 167 } 168 //測試銷毀 169 { 170 DestroyList(DL); 171 cout << "123456" << endl; 172 Print(DL); 173 cout << "123456" << endl; 174 } 175 } 176 177 int main() 178 { 179 test1(); 180 return 0; 181 }
