雙向連結清單--可進可退
基本資料結構實作--雙連結清單
*概述
單連結清單節點中隻有一個指向其後記的指針，使得單連結清單隻能從頭節點依次順序地向後周遊。要通路某個節點的前驅節點，隻能從頭
開始周遊，在拿到某節點指針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 }