雙向鏈表（C++實現），實現
![]()
//////////////////////////////////////////////////////////////////////////////////////
/////// 這裡建立兩個類，一個節點類和一個List類，與單鏈表不同的是雙向鏈表的節點要多一
////// 個前驅指針,相應的，雙向鏈表函數實現要與單鏈表實現有所差異
typedef int DataType;
//struct LinkNode //節點類（復合形態）
//{
// friend class SList;
//將SList設為友元，便於SList類可以訪問節點類的私有成員
//public:
// LinkNode(const DataType x);
//private:
// DataType _data; //節點的數據
// LinkNode* _next; //指向該節點的下一個節點
// LinkNode* _prev; //指向該節點的前一個節點
//};
//直接用struct定義LinkNode類，因為struct的成員默認為公有數據成員，所以可直接訪問
struct LinkNode //節點類(建議寫法)
{
LinkNode(const DataType x);
DataType _data; //節點的數據
LinkNode* _next; //後繼指針
LinkNode* _prev; //前驅指針
};
class List //鏈表類
{
public:
List(); //構造函數
List(const List& s); //拷貝構造
List &operator=(List& s); //賦值運算符的重載
~List();
public:
void Reverse();
void Swap(List& s);
void PrintSList(); //打印鏈表
void PushBack(const DataType& x); //在尾部插入一個節點
void Clear(); //鏈表置空
void PopBack();
void PushFront(DataType x); //頭插
void PopFront(); //刪除首節點
void Insert(LinkNode* pos, DataType x);//固定位置插入一個節點
void Erase(LinkNode* pos); //刪除某一節點
LinkNode* Find(DataType x); //查找節點並返回這個節點的地址
int Amount(); //計算鏈表節點的數目
void Remove(DataType x); //查找某節點並刪除
private:
LinkNode* _head; //指向頭結點
LinkNode* _tail; //指向尾節點
};
List.h
![]()
1 #include<iostream>
2 using namespace std;
3 #include<assert.h>
4 #include"List.h"
5
6 //節點類構造函數*
7 LinkNode::LinkNode(const DataType x)
8 :_data(x)
9 , _next(NULL)
10 , _prev(NULL)
11 {}
12
13 //鏈表類*
14 List::List() //構造函數
15 : _head(NULL)
16 , _tail(NULL)
17 {}
18
19 List::List(const List& s) //拷貝構造
20 : _head(NULL)
21 , _tail(NULL)
22 {
23 if (s._head == NULL)
24 {
25 return;
26 }
27 LinkNode* tmp = s._head;
28 while (tmp)
29 {
30 PushBack(tmp->_data);
31 tmp = tmp->_next;
32 }
33
34 }
35
36 //賦值運算符的重載（傳統方法）
37 //SList & SList::operator=(const SList& s)
38 //{
39 // if (this != &s)
40 // {
41 // _head = NULL;
42 // _tail = NULL;
43 // LinkNode* tmp = s._head;
44 // do{
45 // PushBack(tmp->_data);
46 // tmp = tmp->_next;
47 // } while (tmp != s._head);
48 // }
49 // return *this;
50 //}
51
52 //賦值運算符的重載（高效寫法）*
53 /*void SList::Swap(SList& s)
54 {
55 swap(_head, s._head);
56 swap(_tail, s._tail);
57
58 }
59 SList& SList::operator=(SList &s)
60 {
61 if (this != &s)
62 {
63 SList tmp(s);
64 Swap(tmp);
65 }
66 return *this;
67 }*/
68
69 List& List::operator=(List &s) //賦值運算符的重載再優化(推薦寫法)
70 {
71 if (this != &s)
72 {
73 swap(_head, s._head);
74 swap(_tail, s._tail);
75 }
76 return *this;
77 }
78 List::~List() //析構
79 {
80 Clear();
81 }
82
83 void List::Reverse() //鏈表逆置（利用頭插新節點的方法）
84 {
85 if (_head == NULL || _head== _tail)
86 {
87 return;
88 }
89 int ret = Amount();
90
91 /* // 方法一（相當於用頭插的方式重新建立鏈表）
92 _tail = new LinkNode(_head->_data);
93 LinkNode* begin = NULL;
94 LinkNode* tmp = _tail;
95 while (--ret)
96 {
97 LinkNode* del = _head;
98 _head = _head->_next;
99 delete del;
100 begin = new LinkNode(_head->_data);
101 begin->_next = tmp;
102 tmp->_prev = begin;
103 tmp = begin;
104 }
105 _head = begin;*/
106
107 ////// 方法二（只是交換對稱位置節點的數據）**（高效）
108 LinkNode* begin = _head;
109 LinkNode* end = _tail;
110 while (ret)
111 {
112 if (end->_next == begin)
113 break;
114 ret /= 2;
115 swap(begin->_data, end->_data);
116 begin = begin->_next;
117 end = end->_prev;
118 }
119
120 /*// 方法三 交換前驅和後繼指針
121 swap(_head, _tail);
122 LinkNode* cur = _head;
123 while (cur)
124 {
125 swap(cur->_prev,cur->_next);
126 cur = cur->_next;
127 }
128 */
129
130 }
131
132 //打印鏈表*
133 void List::PrintSList()
134 {
135 //頭結點為空時，無需打印鏈表
136 if (_head == NULL)
137 {
138 cout << "This SList is Empty !" << endl;
139 return;
140 }
141 else
142 {
143 LinkNode* tmp = _head;
144 while (tmp)
145 {
146 cout << tmp->_data << "-->";
147 tmp = tmp->_next;
148 }
149 cout <<"NULL"<< endl;
150 }
151 }
152
153 void List::PushBack(const DataType& x) //在尾部插入一個節點*
154 {
155 //如果鏈表為空，插入節點後只有一個節點，此時_head=_tail
156 if (_head == NULL)
157 {
158 _head = new LinkNode(x);
159 _tail = _head;
160 }
161 else
162 {
163 _tail->_next = new LinkNode(x);
164 _tail->_next->_prev=_tail;
165 _tail = _tail->_next;
166 }
167 }
168
169 void List::Clear() //鏈表置空*
170 {
171 LinkNode* begin = _head;
172 while (begin != _tail)
173 {
174 _head = _head->_next;
175 delete begin;
176 begin = _head;
177 }
178 _head = NULL;
179 _tail = NULL;
180 }
181
182 void List::PopBack() //尾刪
183 {
184 if (_head == NULL)
185 {
186 cout << "This SList is empty !" << endl;
187 }
188 else if (_head == _tail)
189 {
190 delete _head;
191 _head = NULL;
192 _tail = NULL;
193 }
194 else
195 {
196 LinkNode* cur = _head;
197 while (cur->_next != _tail)
198 {
199 cur = cur->_next;
200 }
201 delete _tail;
202 _tail = cur;
203 _tail->_prev = cur->_prev;
204 _tail->_next = NULL;
205 }
206 }
207
208 void List::PushFront(DataType x) //頭插*
209 {
210 if (_head == NULL)
211 {
212 PushBack(x);
213 }
214 else
215 {
216 LinkNode* tmp = _head;
217 _head = new LinkNode(x);
218 _head->_next = tmp;
219 tmp->_prev = _head;
220 }
221 }
222
223 void List::PopFront() //刪除首節點
224 {
225 if (_head == NULL)
226 {
227 cout << "This SList is empty !" << endl;
228 return;
229 }
230 LinkNode* tmp = _head;
231 _head = _head->_next;
232 _head->_prev = NULL;
233 delete tmp;
234 }
235
236 //固定位置插入一個節點（這個函數需和Find函數搭配使用）
237 //先用Find函數找到新節點需要插入的位置
238 //（將Find函數的返回值傳給Insert函數的參數pos），再在pos節點後面插入新節點x
239 void List::Insert(LinkNode* pos, DataType x) //*
240 {
241 assert(pos);
242 if (pos == _tail)
243 {
244 PushBack(x);
245 }
246 else
247 {
248 LinkNode* tmp = new LinkNode(x);
249 tmp->_next = pos->_next;
250 pos->_next = tmp;
251 tmp->_next->_prev = tmp;
252 tmp->_prev = pos;
253 }
254 }
255
256 //刪除某一節點，同樣，要先找到該節點並傳參給Erase函數
257 void List::Erase(LinkNode* pos)
258 {
259 assert(pos);
260 if (pos == _tail)
261 {
262 PopBack();
263 }
264 else if (pos == _head)
265 {
266 PopFront();
267 }
268 else
269 {
270 pos->_prev->_next = pos->_next;
271 pos->_next->_prev = pos->_prev;
272 delete pos;
273 }
274 }
275
276 //查找節點並返回這個節點的地址
277 LinkNode* List::Find(DataType x)
278 {
279 if (_head == NULL)
280 {
281 cout << "This SList is empty !" << endl;
282 return NULL;
283 }
284 else
285 {
286 LinkNode* tmp = _head;
287 while (tmp != NULL)
288 {
289 if (tmp->_data == x)
290 {
291 return tmp;
292 }
293 tmp = tmp->_next;
294 }
295 return NULL;
296 }
297 }
298
299 int List::Amount() //計算鏈表節點的數目
300 {
301 if (_head == NULL)
302 {
303 return 0;
304 }
305 else
306 {
307 int count = 0;
308 LinkNode* cur = _head;
309 while (cur != _tail)
310 {
311 count++;
312 cur = cur->_next;
313 }
314 return ++count;
315 }
316 }
317
318 void List::Remove(DataType x) //查找某節點並刪除
319 {
320 if (_head == NULL)
321 {
322 cout << "This SList is empty !" << endl;
323 }
324 else
325 {
326 LinkNode* tmp = Find(x);
327 if (tmp != NULL)
328 {
329 Erase(tmp);
330 }
331 }
332 }
List.cpp
![]()
1 #include"List.h"
2 #include<stdlib.h>
3 #include<iostream>
4 using namespace std;
5
6 void Test1()
7 {
8 List list1;
9 list1.PushBack(1);
10 list1.PushBack(2);
11 list1.PushBack(3);
12 list1.PushBack(4);
13 list1.PushBack(5);
14 list1.PushBack(6);
15 list1.PrintSList();
16
17 /* List list2(list1);
18 list2.PrintSList();*/
19
20 List list2=list1;
21 list2.PrintSList();
22 //list2.PopBack();
23 //list2.Clear();
24 //list2.PushFront(0);
25 //list2.PopFront();
26
27 //////檢驗Find函數
28 ////LinkNode* ret=list2.Find(4);
29 ////if (ret != NULL)
30 ////{
31 //// cout << "ret:" << ret << " " << ret->_data << endl;
32 ////}
33 ////else
34 ////{
35 //// cout << "Not exit !" << endl;
36 ////}
37
38 /* int ret=list2.Amount();
39 cout << ret << endl;*/
40
41 //list2.Erase(list2.Find(5));
42 //list2.Insert(list2.Find(2), 0);
43 //list2.Remove(3);
44 list2.Reverse();
45 list2.PrintSList();
46 }
47
48 int main()
49 {
50 Test1();
51 system("pause");
52 }
Test.cpp
