C++實現單鏈表和子類棧(Stack)及單向隊列(Queue)

　　剛剛開始學習c++。之前c的內容掌握的也不多，基本只是一本概論課的程度，以前使用c的struct寫過的鏈表、用python寫過簡單的數據結構，就試著把兩者用c++寫出來，也是對c++的class，以及繼承中的public/protected/private的性質進行初步瞭解。第一次寫頭文件.h和源文件.cpp分開的c++代碼。過程中參考了ProLyn和kgvito的代碼，基本就是百度“單鏈表 c++”的前幾個搜索結果。

 　　節點listNode還是用struct來寫了，因為我想節點除了構造沒有什麼方法需要實現，變數和構造也總是需要處於public的狀態方便其他類函數調用。

　　棧是保持先進後出(First In Last Out, 或者FILO)的數據結構，在這裡只是定義了最基本的五種方法，實現從尾部添加、從尾部彈出；隊列是保持先進先出(First In First Out, FIFO)的數據結構，同樣定義了最基本的方法實現從尾部添加從頭部彈出。二者我都使用了private繼承，因為除了重新封裝list的幾種方法外，多數list的方法都不需要出現在這兩種數據結構中，我認為禁止public訪問這些方法比較好。

 1 // linked_list.h
 2 // Base class linked list "linkList", derived "linkStack" & "linkQueue" 
 3 typedef int DataType;
 4 
 5 // constructing struct "listNode"
 6 struct listNode
 7 {
 8     DataType nodeVal;
 9     listNode* nextNode;
10     listNode(const DataType x);            // listNode construct func
11 };
12 
13 // constructing base class "linklist"
14 class linkList
15 {
16 private:                                // private variables headNode & tailNode
17     listNode* headNode;
18     listNode* tailNode;
19 // construction functions, and operator overload
20 public:
21     linkList();
22     linkList(const linkList& lista);
23     linkList& operator=(linkList& lista);
24     DataType operator[](int index);
25 // other functions, public
26 public:
27     bool isEmpty();
28     void PrintList();
29     void PushBack(const DataType& x);
30     void PushFront(const DataType& x);
31     void PopBack();
32     void PopFront();
33     DataType PeekBack();
34     DataType PeekFront();
35     void InsertNext(listNode* pos, DataType x);
36     void DeleteNext(listNode* pos);
37     void Delete(listNode* pos);
38     void Clear();
39     void Remove(DataType x);
40     void RemoveAll(DataType x);
41     void Sort();
42     int GetLength();
43     listNode* Find(DataType x);
44 };
45 
46 // derived class linkStack
47 class linkStack : private linkList
48 {
49 public:
50     linkStack();
51     linkStack(const linkStack& stack1);
52     linkStack& operator=(linkStack& stack1);
53 // the least functions needed
54 public:
55     bool isEmpty();
56     int getSize();
57     void PushBack(const DataType& x);
58     void PopBack();
59     DataType PeekBack();
60 };
61 
62 // derived class linkQueue
63 class linkQueue : private linkList
64 {
65 public:
66     linkQueue();
67     linkQueue(const linkQueue& queue1);
68     linkQueue& operator=(linkQueue& queue1);
69 
70 public:
71     bool isEmpty();
72     int getSize();
73     void PushBack(const DataType& x);
74     void PopFront();
75     DataType PeekFront();
76 }

　　對struct listNode，class linkList, linkStack, linkQueue的方法的具體實現，後兩者基本只是對於linkList的重新封裝，為了能在private繼承的子類中實現，也不得不在linkList中添加了一些沒什麼用處的函數。其中構造函數和賦值下標運算重載的寫法都是現學的…如果現學的不到位請不吝賜教！

  1 #include <iostream>
  2 #include "linked_list.h"
  3 using namespace std;
  4 // construction func for listNode
  5 listNode::listNode(const DataType x)
  6     :nodeVal(x), nextNode(nullptr)
  7 {}
  8 // construction funcs for linkList
  9 linkList::linkList()                        // without argument
 10     : headNode(nullptr), tailNode(nullptr)
 11 {}
 12 
 13 linkList::linkList(const linkList& lista)    // with argument
 14     : headNode(nullptr), tailNode(nullptr)
 15 {
 16     if (lista.headNode) {
 17         listNode* tmp = lista.headNode;
 18         while (tmp->nextNode) {
 19             PushBack(tmp->nodeVal);
 20             tmp = tmp->nextNode;
 21         }
 22         PushBack(tmp->nodeVal);
 23     }
 24 }
 25 // operator reload =
 26 linkList& linkList::operator=(linkList &lista) {
 27     if (this != &lista) {
 28         swap(headNode, lista.headNode);
 29         swap(tailNode, lista.tailNode);
 30     }
 31     return *this;
 32 }
 33 // operator reload [](index)
 34 DataType linkList::operator[](int index) {
 35     if (index < 0 || headNode == nullptr) {
 36         cout << "Invalid index!" << endl;
 37         return -1;
 38     }
 39     else {
 40         listNode* tmp = headNode;
 41         int i;
 42         while (tmp != nullptr && i < index) {
 43             tmp = tmp->nextNode;
 44             i++;
 45         }
 46         if (tmp == nullptr) {
 47             cout << "Invalid index!" << endl;
 48             return -1;
 49         }
 50         else {
 51             return tmp->nodeVal;
 52         }
 53     }
 54 }
 55 
 56 bool linkList::isEmpty() {
 57     if (headNode) {
 58         return true;
 59     }
 60     else {
 61         return false;
 62     }
 63 }
 64 
 65 int linkList::GetLength() {
 66     int count = 0;
 67     listNode* tmp = headNode;
 68     while (tmp) {
 69         count++;
 70         tmp = tmp->nextNode;
 71     }
 72     return count;
 73 }
 74 
 75 void linkList::PrintList() {
 76     listNode* tmp = headNode;
 77     if (tmp) {
 78         cout << tmp->nodeVal;
 79         tmp = tmp->nextNode;
 80         while (tmp) {
 81             cout << "->" << tmp->nodeVal;
 82             tmp = tmp->nextNode;
 83         }
 84         cout << endl;
 85     }
 86     else {
 87         cout << "Empty linked list!" << endl;
 88     }
 89 }
 90 
 91 void linkList::PushBack(const DataType& x) {
 92     if (headNode) {
 93         tailNode->nextNode = new listNode(x);
 94         tailNode = tailNode->nextNode;
 95     }
 96     else {
 97         headNode = new listNode(x);
 98         tailNode = headNode;
 99     }
100 }
101 
102 void linkList::PushFront(const DataType& x) {
103     if (headNode) {
104         listNode* tmp = new listNode(x);
105         tmp->nextNode = headNode;
106         headNode = tmp;
107     }
108     else {
109         headNode = new listNode(x);
110         tailNode = headNode;
111     }
112 }
113 
114 void linkList::PopBack() {
115     if (headNode) {
116         if (headNode->nextNode) {
117             listNode* tmp = headNode;
118             while (tmp->nextNode != tailNode) {
119                 tmp = tmp->nextNode;
120             }
121             delete tailNode;
122             tmp->nextNode = nullptr;
123             tailNode = tmp;
124         }
125         else {
126             delete headNode;
127             headNode = nullptr;
128             tailNode = nullptr;
129         }
130     }
131     else {
132         cout << "Empty linked list!" << endl;
133     }
134 }
135 
136 void linkList::PopFront() {
137     if (headNode) {
138         if (headNode->nextNode) {
139             listNode* tmp = headNode->nextNode;
140             delete headNode;
141             headNode = tmp;
142         }
143         else {
144             delete headNode;
145             headNode = nullptr;
146             tailNode = nullptr;
147         }
148     }
149     else {
150         cout << "Empty linked list!" << endl;
151     }
152 }
153 
154 DataType linkList::PeekBack() {
155     if (tailNode) {
156         return tailNode->nodeVal;
157     }
158     else {
159         cout << "Empty linked list!" << endl;
160         return -1;
161     }
162 }
163 
164 DataType linkList::PeekFront() {
165     if (headNode) {
166         return headNode->nodeVal;
167     }
168     else {
169         cout << "Empty linked list!" << endl;
170         return -1;
171     }
172 }
173 
174 listNode* linkList::Find(DataType x) {
175     listNode* targetNode = headNode;
176     while (targetNode) {
177         if (targetNode->nodeVal == x) {break;}
178     }
179     return targetNode;
180 }
181 
182 void linkList::InsertNext(listNode* pos, DataType x) {
183     if (pos) {
184         if (pos == tailNode) {
185             listNode* tmp = new listNode(x);
186             pos->nextNode = tmp;
187             tailNode = tmp;
188         }
189         else {
190             listNode* tmp = new listNode(x);
191             tmp->nextNode = pos->nextNode;
192             pos->nextNode = tmp;
193         }
194     }
195     else {
196         cout << "Invalid position!" << endl;
197     }
198 }
199 
200 void linkList::DeleteNext(listNode* pos) {
201     if (pos) {
202         if (pos == tailNode) {
203             cout << "Invalid node!" << endl;
204         }
205         else {
206             listNode* tmp = (pos->nextNode)->nextNode;
207             delete pos->nextNode;
208             pos->nextNode = tmp;
209         }
210     }
211     else {
212         cout << "Invalid node!" << endl;
213     }
214 }
215 
216 void linkList::Remove(DataType x) {
217     if (headNode) {
218         if (headNode->nextNode) {
219             listNode* tmp = headNode;
220             while (tmp->nextNode) {
221                 if ((tmp->nextNode)->nodeVal == x) {
222                     DeleteNext(tmp);
223                     break;
224                 }
225                 tmp = tmp->nextNode;
226             }
227         }
228         else {
229             if (headNode->nodeVal == x) {PopFront();}
230         }
231     }
232 }
233 
234 void linkList::RemoveAll(DataType x) {
235     if (headNode) {
236         listNode* tmp = headNode;
237         while (tmp->nextNode) {
238             if ((tmp->nextNode)->nodeVal == x) {
239                 if (tmp->nextNode == tailNode){
240                     PopBack();
241                     break;
242                 }
243                 else {DeleteNext(tmp);}
244             }
245             tmp = tmp->nextNode;
246         }
247         if (tmp->nodeVal == x) {
248             PopBack();
249         }
250     }
251 }
252 
253 void linkList::Clear() {
254     if (headNode) {
255         listNode* prev = headNode;
256         listNode* tmp;
257         while (prev->nextNode) {
258             tmp = prev->nextNode;
259             delete prev;
260             prev = tmp;
261         }
262         headNode = nullptr;
263         tailNode = nullptr;
264     }
265 }
266 // construction funcs for linkStack
267 linkStack::linkStack()                            // without arguments
268     :linkList()
269 {}
270 
271 linkStack::linkStack(const linkStack& stack1)    // with an argument
272     :linkList(stack1)
273 {}
274 // other public funcs for linkStack
275 bool linkStack::isEmpty() {
276     return linkList::isEmpty();
277 }
278 
279 int linkStack::getSize() {
280     return linkList::GetLength();
281 }
282 
283 void linkStack::PushBack(const DataType& x) {
284     linkList::PushBack(x);
285 }
286 
287 void linkStack::PopBack() {
288     linkList::PopBack();
289 }
290 
291 DataType linkStack::PeekBack() {
292     return linkList::PeekBack();
293 }
294 // construction funcs for linkQueue
295 linkQueue::linkQueue()
296     :linkList()
297 {}
298 
299 linkQueue::linkQueue(const linkQueue& queue1)
300     :linkList(queue1)
301 {}
302 // other public funcs for linkQueue
303 bool linkQueue::isEmpty() {
304     return linkList::isEmpty();
305 }
306 
307 int linkQueue::getSize() {
308     return linkList::GetLength();
309 }
310 
311 void linkQueue::PushBack(const DataType& x) {
312     linkList::PushBack(x);
313 }
314 
315 void linkQueue::PopFront() {
316     linkList::PopFront();
317 }
318 
319 DataType linkQueue::PeekFront() {
320     return linkList::PeekFront();
321 }

　　最後還有測試代碼，和主題沒什麼關係，但是從以前用python學習數據結構開始我就喜好把測試代碼寫成假互動式，所以索性貼在這裡方便取用。

  1 #include <iostream>
  2 #include "linked_list.h"
  3 #include <stdlib.h>
  4 #include <map>
  5 
  6 using namespace std;
  7 
  8 static map<string, int>stringVal {
  9     {"Exit", 0},
 10     {"Printlist", 1},
 11     {"Pushback", 2},
 12     {"Pushfront", 3},
 13     {"Popback", 4},
 14     {"Popfront", 5},
 15     {"Clear", 6},
 16     {"Remove", 7},
 17     {"Removeall", 8},
 18     {"Sort", 9},
 19     {"Getlength", 10},
 20     {"Index", 11},
 21     {"Peekback", 12},
 22     {"Peekfront", 13}
 23 };
 24 
 25 int test_list() {
 26     linkList list1;
 27     cout << ">> Linked list tesing.\n"
 28         ">> Enter a direction, namely Printlist, Pushback, Pushfront, Popback, Peekback, "
 29         "Popfront, Peekfront, Clear, Remove, Removeall, Sort, Getlength or Index," 
 30         "enter Exit to exit." << endl;
 31     string direction;
 32     DataType parameter;
 33     int param;
 34     while (1) {
 35         cout << ">> ";
 36         cout.flush();
 37         cin >> direction;
 38         switch(stringVal[direction])
 39         {
 40             case 0:
 41                 return 0;
 42             case 1:
 43                 list1.PrintList();
 44                 break;
 45             case 2:
 46                 cin >> parameter;
 47                 list1.PushBack(parameter);
 48                 break;
 49             case 3:
 50                 cin >> parameter;
 51                 list1.PushFront(parameter);
 52                 break;
 53             case 4:
 54                 list1.PopBack();
 55                 break;
 56             case 5:
 57                 list1.PopFront();
 58                 break;
 59             case 6:
 60                 list1.Clear();
 61                 break;
 62             case 7:
 63                 cin >> parameter;
 64                 list1.Remove(parameter);
 65                 break;
 66             case 8:
 67                 cin >> parameter;
 68                 list1.RemoveAll(parameter);
 69                 break;
 70 /*            case 9:
 71                 list1.Sort();
 72                 break;*/
 73             case 10:
 74                 param = list1.GetLength();
 75                 cout << ">> " << param << endl;
 76                 break;
 77             case 11:
 78                 cin >> param;
 79                 parameter = list1[param];
 80                 cout << ">> " << parameter << endl;
 81                 break;
 82             case 12:
 83                 parameter = list1.PeekBack();
 84                 cout << ">> " << parameter << endl;
 85                 break;
 86             case 13:
 87                 parameter = list1.PeekFront();
 88                 cout << ">> " << parameter << endl;
 89         }
 90     }
 91     return 0;
 92 }
 93 
 94 int test_stack() {
 95     linkStack stack1;
 96     cout << ">> Linked list stack tesing.\n"
 97         ">> Enter a direction, namely Pushback, Popback or Peekback, "
 98         "enter Exit to exit." << endl;
 99     string direction;
100     DataType parameter;
101     int param;
102     while (1) {
103         cout << ">> ";
104         cout.flush();
105         cin >> direction;
106         switch(stringVal[direction])
107