實現基於單向鏈表的list類。
struct node {
int x;
int y;
node(int xx, int yy) {
x = xx;
y = yy;
}
}
1.構造函數時先設置一個head結點，其指向空。如下：
2.插入結點：
當position為0時，本來應該是這樣的：
但是，這個函數在這裡插入結點時，如果count=0，則將圖中position位置看成NULL，那麼下面的插入方法仍然成立不受影響。所以這就是設置頭結點的優點是所在了，在position=0時插入結點就不需要通過條件判斷了（這種判斷很容易忘記漏寫，導致苦逼的debug），在這裡只要通過current找到插入的位置position前的結點，然後將新的結點插在current後面，新結點的next為current->next即可完成insert的工作。
3.remove結點：
如圖所示的方法刪除position位置的結點，同樣是利用head來減少判斷步驟。
附代碼及注釋：
1 #include <iostream>
2 using namespace std;
3 enum Error_code {
4 success,
5 underflow,
6 overflow
7 };
8 template <class List_entry>
9 struct Node {
10 List_entry entry;
11 Node<List_entry> *next;
12 };
13 template <class List_entry>
14 class MyList {
15 public:
16 MyList() {
17 head = new Node<List_entry>;//設置一個頭結點
18 head->entry = 0;
19 head->next = NULL;
20 count = 0;//當前鏈表為空（頭部之後的結點才是我們存進去的，count指的是我們存進去的結點數）
21 curPosition = -1;//頭部的位置為-1
22 current = head;//當前位置指向鏈表的頭部
23 }
24 /*設置頭部的作用主要體現在insert（int position, const List_entry &entry）,remove(...), retrieve(...),
25 replay(...)這些函數裡面，詳見相關函數*/
26 ~MyList() {
27 current = NULL;
28 curPosition = -1;
29 Node<List_entry> *temp = head, *a;
30 while (head != NULL) {
31 head = temp->next;
32 a = temp;
33 delete a;
34 temp = head;
35 }
36 count = 0;
37 }
38 // 拷貝構造函數和賦值運算符重載，注意深拷貝與淺拷貝的差異
39 MyList(const MyList<List_entry> ©) {
40 head = new Node<List_entry>;//this start...
41 head->entry = 0;
42 head->next = NULL;
43 count = 0;
44 curPosition = -1;
45 current = head;//this end...拷貝構造函數，相當於構造一個MyList()之後將copy這個鏈表的內容復制進去
46 if (copy.count != 0) {//拷貝鏈表內容
47 count = copy.count;
48 Node<List_entry> *a, *b;
49 a = copy.head->next;
50 b = head;
51 for (int i = 0; i < copy.count; i++) {
52 b->next = new Node<List_entry>;
53 b = b->next;
54 b->entry = a->entry;
55 b->next = NULL;
56 a = a->next;
57 }
58 }
59 }
60 //跟拷貝構造函數不一樣，這個函數實現的前提是已經MyList()例如MyList a，然後將copy復制到a
61 void operator =(const MyList<List_entry> ©) {
62 if (!empty()) clear();//清空
63 if (copy.count != 0) {//同上拷貝鏈表內容
64 count = copy.count;
65 Node<List_entry> *a, *b;
66 a = copy.head->next;
67 b = head;
68 for (int i = 0; i < copy.count; i++) {
69 b->next = new Node<List_entry>;
70 b = b->next;
71 b->entry = a->entry;
72 b->next = NULL;
73 a = a->next;
74 }
75 }
76 }
77 // 清空list，清空時候保留頭結點，數據恢復到原始狀態
78 void clear() {
79 if (!empty()) {
80 Node<List_entry> *temp = head->next, *a;
81 while (temp != NULL) {
82 head->next = temp->next;
83 a = temp;
84 temp = head->next;
85 delete a;
86 count--;
87 }
88 current = head;
89 curPosition = -1;
90 }
91 }
92 // 判斷list是否為空
93 bool empty() const {
94 if (count != 0) return false;
95 return true;
96 }
97 // 判斷list是否已滿
98 bool full() const {
99 return false;
100 }
101 // 獲取list的元素數量
102 int size() const {
103 return count;
104 }
105 // 在第position個位置插入值為entry的元素，如果position為0則插入在head（head的position為-1）後面，依次類推
106 // 若position < 0 或者 position > count，則返回underflow
107 Error_code insert(int position, const List_entry &entry) {
108 if (position < 0 || position > count) return underflow;
109 Node<List_entry> *new_node, *pre, *follow;
110 //new一個新的結點
111 new_node = new Node<List_entry>;
112 new_node->entry = entry;
113 //setPosition的作用是設置當前的位置current指向position-1這個位置，在position-1後面插入new_node
114 //當position==0時，應該插在頭部後面的位置，pre指向頭部。若沒有head，則需要討論當position == 0時候的情況，容易漏判斷
115 setPosition(position - 1);
116 pre = current;
117 follow = current->next;
118 //新結點指向follow，pre前一個結點指向新結點new_node
119 new_node->next = follow;
120 pre->next = new_node;
121 count++;
122 return success;
123 }
124 // 刪除第position個位置的元素，並將該元素的值保存在entry中
125 // 若position < 0 或者 position >= count，則返回underflow
126 Error_code remove(int position, List_entry &entry) {
127 if (position < 0 || position >= count) return underflow;
128 Node<List_entry> *pre, *now, *follow;
129 //去掉position位置的結點，應該讓pre指向該位置的前一個，所以應該先找出position-1位置的結點
130 setPosition(position - 1);
131 pre = current;
132 now = current->next;
133 entry = now->entry;
134 follow = now->next;
135 pre->next = follow;
136 delete now;//刪掉position的結點
137 count--;
138 return success;
139 }
140 // 獲取第position個位置的元素，保存在entry中
141 // 若position < 0 或者 position >= count，則返回underflow
142 Error_code retrieve(int position, List_entry &entry) const {
143 if (position < 0 || position >= count) return underflow;
144 setPosition(position);
145 entry = current->entry;
146 return success;
147 }
148 // 將第position個位置的元素替換為entry
149 // 若position < 0 或者 position >= count，則返回underflow
150 Error_code replace(int position, const List_entry &entry) {
151 if (position < 0 || position >= count) return underflow;
152 setPosition(position);
153 current->entry = entry;
154 return success;
155 }
156 // 用visit函數遍歷list內所有的元素
157 void traverse(void (*visit)(List_entry &)) {
158 Node<List_entry> *a = head->next;
159 for (int i = 0; i < count; i++) {
160 (*visit)(a->entry);
161 a = a->next;
162 }
163 }
164 protected:
165 int count; // 記錄list內元素數量
166 Node<List_entry> *head; // 鏈表頭指針
167 mutable int curPosition; // current指針的位置編號
168 mutable Node<List_entry> *current; // current指針
169 // 設置current指針的位置，指向第position個位置
170 void setPosition(int position) const {
171 if (position < curPosition) {
172 curPosition = -1;
173 current = head;
174 }
175 for (; curPosition < position; curPosition++) {
176 current = current->next;
177 }
178 }
179 };
