C++实现单链表和子类栈(Stack)及单向队列(Queue)
程序员文章站
2022-05-18 23:03:53
刚刚开始学习c++。之前c的内容掌握的也不多，基本只是一本概论课的程度，以前使用c的struct写过的链表、用python写过简单的数据结构，就试着把两者用c++写出来，也是对c++的class，以及继承中的public/protected/private的性质进行初步了解。第一次写头文件.h和源文 ......
刚刚开始学习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 }
下一篇： 自媒体如何打造抖音ip达人，爆粉玩法分享