首页 > > 程序设计 > C/C++ >

C++实现单链表和子类栈(Stack)及单向队列(Queue)

2018-09-01 05:38:06来源：博客园阅读 ()

　　刚刚开始学习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         {
108             case 0:
109                 return 0;
110             case 2:
111                 cin >> parameter;
112                 stack1.PushBack(parameter);
113                 break;
114             case 4:
115                 stack1.PopBack();
116                 break;
117             case 12:
118                 parameter = stack1.PeekBack();
119                 cout << ">> " << parameter << endl;
120                 break;
121         }
122     }
123     return 0;
124 }
125 
126 int main() {
127     test_stack();
128     return 0;
129 }