基本資料結構--單連結清單的實作。并嘗試實作一種重要操作：将給定連結清單反序。
基本資料結構實作--單連結清單
連結清單是線性表的另一種實作方式。與順序表不同，連結清單中邏輯上相鄰的資料元素在實體上未必相鄰，而是通過一個指針指明下一個元素的
實體位址。單連結清單中節點類型的描述如下：
1 struct LNode {
2 ElemType data; //節點資料域
3 LNode* next; //指向下一個節點的指針
4 };
5 typedef LNode* LinkList; 單連結清單的優點：與順序表相比，單連結清單的優點在于插入和删除操作：雖然單連結清單的插入和删除操作與順序表一樣時間複雜度都是O(n),但是對于單連結清單來說，
插入和删除時的基本操作主要是“比較”（對于按位插入删除，比較是否到了第i位；對于按值操作，比較值是否相等），而順序表插入和删除時
的基本操作主要是“移動”。從硬體的角度講，做一次比較運算的時間是遠小于指派運算的。是以，連結清單的插入和删除操作要高效得多。
單連結清單的缺點：由于單連結清單中邏輯上相鄰的元素在實體上未必相鄰，故不能根據第一個元素的位址立即計算出第i個元素的位址。于是單連結清單不支援随機通路。
（所謂随機通路是指：根據起始位址加上元素序号就可以立即找到任意一個元素。）要在單連結清單中通路第i個元素，必須一個一個通路連結清單中每一個元素直到
第i個。
以下代碼實作一個帶頭節點的單連結清單，并嘗試實作一種重要操作：将連結清單反序
1 /* 帶頭節點的單連結清單
2
3 實作操作：
4 *1 判空
5 *2 求表長
6 *3 按位序查找
7 *4 按值查找
8 *5 前插操作
9 *6 後插操作
10 *7 按位插入
11 *8 删除指定節點
12 *9 按位删除
13 *10 單連結清單的建立-頭插和尾插
14 */
15 #include <iostream>
16 #include <cstdio>
17 using namespace std;
18
19 typedef int ElemType;
20 typedef struct LNode {
21 ElemType data; //節點資料域
22 LNode* next; //指向下一個節點的指針
23 } * LinkList;
24
25 bool Empty(LinkList& L)
26 {
27 if( L->next == NULL )
28 return true;
29 return false;
30 }
31
32 //求表的長度
33 int Length(LinkList L)
34 {
35 int len = 0;
36 LNode* p = L;
37 //始終讓p指向第j個節點，當p沒有下一個節點時，j就是表的長度
38 while( p->next != NULL ) {
39 len++;
40 p = p->next;
41 }
42 return len;
43 }
44
45 //按位序查找，傳回指向第i個節點的指針
46 //查找失敗時傳回的是NULL
47 LNode* GetElem(LinkList L,int i)
48 {
49 if( i < 0 )
50 return NULL;
51 int j = 0;
52 LNode* p = L;
53 while( j < i && p != NULL ) {
54 j++;
55 p = p->next;
56 }
57 return p; //i=0時傳回的是頭節點,i值大于表長是傳回的是空指針
58 }
59
60 //按值查找，找到資料域為e的節點,傳回其指針
61 LNode* LocateElem(LinkList L,ElemType e)
62 {
63 LNode* p = L->next; //注意不是LNode* p = L :因為指向頭節點，資料域是未知的
64 while( p != NULL && p->data != e ) {
65 p = p->next;
66 }
67 return p; //若e不存在，傳回空指針
68 }
69
70 //前插操作：在p節點之前插入元素e
71 bool InsertPriorNode(LNode* p,ElemType e)
72 {
73 if( p == NULL )
74 return false;
75
76 //偷天換日
77 LNode* s = new LNode;
78 s->next = p->next;
79 p->next = s;
80 s->data = p->data;
81 p->data = e;
82 return true;
83 }
84
85 //後插操作：在p節點之後插入元素e
86 bool InsertNextNode(LNode* p,ElemType e)
87 {
88 if( p == NULL )
89 return false;
90 LNode* s = new LNode;
91 s->data = e;
92 s->next = p->next;
93 p->next = s;
94 return true;
95 }
96
97 //按位插入：在單連結清單L的第i個位置插入元素e
98 bool ListInsert(LinkList& L,int i,ElemType e)
99 {
100 if( i < 1 )
101 return false; //位序最小是1
102
103 //先拿到指向第i-1個節點的指針，然後在他後面插入元素e
104 LNode* p = GetElem(L,i-1);
105 return InsertNextNode(p,e);
106 }
107
108 //删除指定節點p
109 bool DeleteNode(LNode* p)
110 {
111 if( p == NULL )
112 return false;
113 //偷天換日
114 LNode* s = p->next;
115 //有bug：當p是最後一個節點時，無法删除(無法從p->next擷取data)
116 //非要删除最後一個節點的話，可以傳L頭節點指針進來
117 p->data = s->data;
118 p->next = s->next;
119 delete s;
120
121 return true;
122 }
123
124 //按位删除：删除單連結清單L的位序為i的元素，并用e傳回
125 bool ListDelete(LinkList& L, int i,int& e)
126 {
127 if( i < 1 )
128 return false;
129 LNode* p = GetElem(L,i-1);
130
131 if( p == NULL ) //沒有第i-1個節點，更沒有第i個節點
132 return false;
133 if( p->next == NULL ) //找到了第i-1個節點，但是沒有第i個節點
134 return false;
135 LNode* t = p->next;
136 e = t->data;
137 p->next = t->next;
138 delete t;
139 return true;
140 }
141
142 //頭插法建立單連結清單(假設所給資料從鍵盤輸入)
143 LinkList List_HeadInsert(LinkList& L)
144 {
145 //假設元素為int型
146 int x;
147 L = new LNode;
148 L->next = NULL;
149 while( cin >> x ) {
150 InsertNextNode(L,x);
151 }
152 return L;
153 }
154
155 //尾插法建立單連結清單(假設所給資料從鍵盤輸入)
156 LinkList List_TailInsert(LinkList& L)
157 {
158 //假設元素為int型
159 int x;
160 L = new LNode;
161 L->next = NULL;
162 LNode* r = L;
163 while( cin >> x ) {
164 LNode* s = new LNode;
165 s->data = x;
166 r->next = s;
167 r = s; //建立過程中不必将尾節點的next置空，因為後面還會有節點
168 }
169 r->next = NULL; //連結清單建立結束，最後一個節點的下一個節點置空
170 return L;
171 }
172
173 //按順序輸出單連結清單中所有元素
174 void Print(LinkList L)
175 {
176 if( L == NULL )
177 return ;
178 LNode* iterater = L->next;
179 while( iterater != NULL ) {
180 cout << iterater->data << endl;
181 iterater = iterater->next;
182 }
183 }
184
185 void test1()
186 {
187 //*測試使用a[i]=2*i的100個元素建立連結清單
188 int a[100];
189 for( int i=0; i<100; i++ ) {
190 a[i] = 2*i;
191 }
192 LinkList L = new LNode;
193 L->next = NULL;
194 //使用尾插法将以上數組插傳入連結表L
195 LNode* r = L;
196 for( int i=0; i<100; i++ ) {
197
198 LNode* s = new LNode;
199 s->data = a[i];
200 r->next = s;
201 r = s;
202 }
203 r->next = NULL;
204
205 //*測試在值為20的元素後插入元素985211
206 LNode* t = LocateElem(L,20); //按值查找
207 InsertNextNode(t,985211);
208
209 //*測試删除位序為15的元素(值應該是26)
210 LNode* tt = GetElem(L,15); //按位序查找
211 if( tt != NULL ) {
212 DeleteNode(tt);
213 }
214
215 //*測試按位序删除位序為100的元素
216 int ttt = 0;
217 if( ListDelete(L,100,ttt) )
218 cout << "按位序删除成功，删除的元素是：" << ttt << endl;
219 Print(L);
220 cout << "-------------------------------" << endl;
221
222
223 //下面嘗試将L反序 *****重要*****
224 //抓住連結清單中的第一個資料元素,一個一個往後進行頭插,表頭結點指針還是L
225 LNode* it = L->next;
226 L->next = NULL; //*****第一個資料已經抓住了;不加這句會導緻表尾自己指向自己(而非指向NULL)
227
228 //從連結清單的第一個節點開始，一個一個地在将表中所有節點重新插在表頭
229 while( it != NULL ) {
230 LNode* nxt = it->next;
231 it->next = L->next;
232 L->next = it; //頭插法重構連結清單，即可将連結清單反序
233 it = nxt;
234 }
235 Print(L);
236
237 //*測試查找不存在的元素傳回空指針
238 if( LocateElem(L,999) == NULL ) {
239 cout << endl << "999不存在" << endl;
240 }
241
242 }
243
244 //測試頭插法
245 void test2()
246 {
247 LinkList L;
248 List_HeadInsert(L);
249 Print(L);
250 }
251
252 int main()
253 {
254 // test1();
255 // test2();
256 return 0;
257 }