-
数据结构上机练习——单链表的基本操作、头文件、类定义、main函数、多种链表算法的实现，含注释
单链表的基本操作实现
1.头文件
头文件和源文件分开有很多好处：可以提高编译速度、提高代码的可维护性、提高代码的可重用性和可扩展性，同时也可以使代码结构更清晰，方便代码的管理和维护。
LinkList.h
#pragma once #include//定义单链表节点 typedef struct LNode { int data; LNode* next; }LNode; - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
test.cpp
#includeusing namespace std; #include"LinkList.h" - 1
- 2
- 3
- 4
2.类定义和多种算法的实现
（下面所有函数都默认在类中实现）
我们以带头单向非循环链表为例:
带头单向非循环链表是一种链表数据结构，其中每个节点包含一个数据域和一个指向下一个节点的指针域。在这种链表中，有一个特殊的节点称为头节点，它指向链表的第一个节点。头节点不是链表的一部分，仅用于方便操作。
2.1创建空表
我们定义了一个名为LinkList的类，代表一个单链表。这个类有两个私有成员：一个指向LNode类型的指针_head，代表链表的头节点，以及一个整型变量_size，代表链表的大小。
//定义单链表类 class LinkList { public: //默认构造函数 LinkList() { _head = new LNode(0);//创建头结点(哨兵位节点) _size = 0; } private: LNode* _head; int _size; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
2.2头插法创建n个元素的线性链表
先以头插单个元素为例：
我们可以先创建一个新的节点来存储该元素。然后，检查链表是否为空，如果为空，则新节点就是链表的第一个节点； 否则，新节点将插入到当前头节点的后面。插入完成后，_size（代表链表元素个数的变量）加1。
void push_front(const int& val) { //创建一个插入的新节点，将要插入的值val赋值给它 LNode* newnode = new LNode(val); LNode* cur = _head->next;//保存原来第一个结点 //进行头插操作 _head->next = newnode; _head->next->next = cur;//连接原来的第一个节点 _size++; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
加上n循环即可实现头插法创建n个元素的线性链表
//头插法创建n个元素 void push_front_n() { cout << "请输入要插入的元素个数:"; int n; cin >> n; cout << endl; cout << "输入要插入的元素:"; while (n) { int tmp; cin >> tmp; push_front(tmp); n--; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
2.3一个带头节点的链表存放一组整数，设计一个算法删除值等于x的所有节点。
无返回值版本
我们先检查链表是否为空，如果为空，则输出一条错误消息并返回。如果链表非空，它开始遍历链表，检查每个节点的下一个节点是否为要删除的节点。如果是，则删除该节点并释放其内存；如果不是，则移动到下一个节点。 在遍历过程中，保持对当前节点的引用，以防止删除连续的要删除的节点时出现问题。
//删除所有x的节点 void erase_all_x(int x) { LNode* cur = _head; if (cur->next == nullptr)//判断是否为空链表 { cout << "该链表为空不可删除\n"; return; } else { while (cur && cur->next)//删除的数据有可能连续，所以最好保持当前节点 { if (cur->next->data == x)//如果下一个节点为要删除节点 { LNode* tmp = cur->next;//用临时指针保存要删除的节点 cur->next = cur->next->next;//链表指向删除节点的下一个节点 delete tmp;//删除节点中的元素 tmp = nullptr; } else//如果下个节点不是删除节点，那直接指向下个节点 { cur = cur->next; } } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
有返回值版本
//删除所有x的节点，有删除节点返回true，无删除节点返回false bool erase_all_x(int x) { LNode* cur = _head; if (cur->next == nullptr) { cout << "该链表为空不可删除\n"; return false; } else { int count = 0;//设计一个计数器，统计是否有删除的节点 while (cur && cur->next)//删除的数据有可能连续，所以最好保持当前节点 { if (cur->next->data == x) { count++;//有删除的节点，count++ LNode* tmp = cur->next; cur->next = cur->next->next;//删除x节点 delete tmp; tmp = nullptr; } else//如果下个节点不是删除节点，那直接指向下个节点 { cur = cur->next; } } if (count == 0)//count==0，则没有可以删除的节点 { cout << "链表中没有可以删除的元素" << endl; return false; } return true; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
2.4计算线性表中值为偶数的节点个数
我们定义函数用于遍历链表并计算其中偶数节点的数量。首先，它检查链表是否为空，如果为空，则输出一条错误消息。如果链表非空，它开始遍历链表，检查每个节点的数据是否为偶数。如果是偶数，则计数器加1。 遍历完成后，输出链表中偶数节点的数量。
//打印链表中值为偶数的节点个数 void print_even_number() { LNode* cur = _head->next; int count = 0; if (cur == nullptr) { cout << "该链表为空，没有节点\n"; } else//核心就在不断通过指针遍历寻找即可 { while (cur)//遍历链表中的每一个节点 { if (cur->data % 2 == 0) { count++;//如果cur为偶数，计数++; } cur = cur->next; } cout << "该链表中偶数节点的个数为:" << count << endl; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
2.5一个带头节点的单链表heada存放一组整数，设计分裂heada算法，偶数放在heada中，奇数放在headb中
我们定义该函数用于将链表中的偶数节点和奇数节点分开，使得偶数节点在heada链表中，奇数节点在headb链表中。
函数使用两个指针cur1和cur2分别遍历heada和headb链表。在遍历过程中，如果当前节点的下一个节点是偶数节点，则保持原链表不变，移动cur1指针；
如果当前节点的下一个节点是奇数节点，则将其从原链表中删除，并添加到headb链表的末尾，同时移动cur1和cur2指针。 最后，函数返回修改后的heada和headb链表。
//分裂链表，偶数在heada中，奇数在headb中 void divide_LinkList(LNode* heada, LNode* headb) { LNode* cur1 = heada; LNode* cur2 = headb; while (cur1 && cur1->next)//退出循环的条件要cur1和cur1下个节点不为空 { if (cur1->next->data % 2 == 0)//为偶数原链表不变 { cur1 = cur1->next;//cur1直接向后移动 } else//若链表为奇数，需要移动放入headb中 { //交换链表节点操作 LNode* tmp = cur1->next; cur1->next = cur1->next->next; //调整cur2，使其获得cur1的节点，断开cur1节点的后面节点的连接 cur2->next = tmp; cur2->next->next = nullptr; //cur1和cur2各向后移动 cur2 = cur2->next; } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
3.main函数和源码实现
3.1测试实现：
test_LinkList1();
test_LinkList2();
test_LinkList3();
3.2LinkList.h
#pragma once #include//定义单链表节点 typedef struct LNode { int data; LNode* next; LNode(const int& val) :data(val) , next(nullptr) {} }LNode; //定义单链表类 class LinkList { public: //默认构造函数 LinkList() { _head = new LNode(0);//创建头结点(哨兵位节点) _size = 0; } //拷贝构造函数 lt1(lt) LinkList(const LinkList& lt) { LNode* oldcur = lt._head->next; //这个this指针是新建的链表lt1的 this->_head = new LNode(0); this->_size = 0; LNode* newcur = _head; while (oldcur)//深拷贝以完成链表的赋值操作 { //将旧链表中的值赋值到新链表中 LNode* tmp = new LNode(oldcur->data); //向后移动新旧链表节点 newcur->next = tmp; newcur = newcur->next; oldcur = oldcur->next; _size++; } } //析构函数 ~LinkList() { LNode* cur = _head->next; while (cur) { LNode* tmp = cur; cur = cur->next; delete tmp; tmp = nullptr; } } //单链表打印 void print() { LNode* cur = _head->next; if (cur == nullptr) { cout << "该单链表为空\n"; } else { cout << "该单链表中的元素为:"; while (cur) { printf("%d->", cur->data); cur = cur->next; } cout << "NULL\n"; } } //单链表尾插 void push_back(const int& val) { LNode* newnode = new LNode(val); LNode* cur = _head; while (cur && cur->next)//找到尾结点 { cur = cur->next; } cur->next = newnode;//尾插 _size++; } //单链表头插 void push_front(const int& val) { LNode* newnode = new LNode(val); LNode* cur = _head->next; _head->next = newnode; _head->next->next = cur; _size++; } //单链表尾删 void pop_back() { LNode* cur = _head->next; LNode* prev = _head; if (cur == nullptr) { cout << "单链表为空不可删除\n"; } else { while (cur && cur->next)//找到尾结点和前一个节点 { cur = cur->next; prev = prev->next; } prev->next = nullptr; delete cur; cur = nullptr; _size--; } } //单链表头删 void pop_front() { LNode* cur = _head->next; if (cur == nullptr) { cout << "单链表为空不可删除\n"; } else { _head->next = cur->next; delete cur; cur = nullptr; _size--; } } //头插法创建n个元素 void push_front_n() { cout << "请输入要插入的元素个数:"; int n; cin >> n; cout << endl; cout << "输入要插入的元素:"; while (n) { int tmp; cin >> tmp; push_front(tmp); //LNode* newnode = new LNode(tmp); //LNode* cur = _head->next; //if (cur == nullptr) //{ // _head->next = newnode; //} //else //{ // newnode->next = cur; // _head->next = newnode; //} n--; //_size++; } } //删除第n个元素 void erase(int n) { assert(n > 0 && n <= _size); LNode* cur = _head; if (cur->next == nullptr) { cout << "该链表为空不可删除\n"; return; } else { LNode* tmp = cur; while (n)//找到删除节点的前一个位置 { tmp = cur; cur = cur->next; n--; } tmp->next = tmp->next->next; delete cur; cur = nullptr; } } //单链表节点个数 void print_size() { cout << "单链表节点个数为:" << _size << endl; } //删除所有x的节点，有删除节点返回true，无删除节点返回false bool erase_all_x(int x) { LNode* cur = _head; if (cur->next == nullptr) { cout << "该链表为空不可删除\n"; return false; } else { int count = 0;//设计一个计数器，统计是否有删除的节点 while (cur && cur->next)//删除的数据有可能连续，所以最好保持当前节点 { if (cur->next->data == x) { count++;//有删除的节点，count++ LNode* tmp = cur->next; cur->next = cur->next->next;//删除x节点 delete tmp; tmp = nullptr; } else//如果下个节点不是删除节点，那直接指向下个节点 { cur = cur->next; } } if (count == 0)//count==0，则没有可以删除的节点 { cout << "链表中没有可以删除的元素" << endl; return false; } return true; } } //打印链表中值为偶数的节点个数 void print_even_number() { LNode* cur = _head->next; int count = 0; if (cur == nullptr) { cout << "该链表为空，没有节点\n"; } else { while (cur)//遍历链表中的每一个节点 { if (cur->data % 2 == 0) { count++;//如果cur为偶数，计数++; } cur = cur->next; } cout << "该链表中偶数节点的个数为:" << count << endl; } } //返回当前链表的头结点 LNode* get_head() { return _head; } //分裂链表，偶数在heada中，奇数在headb中 void divide_LinkList(LNode* heada, LNode* headb) { LNode* cur1 = heada; LNode* cur2 = headb; while (cur1 && cur1->next) { if (cur1->next->data % 2 == 0)//为偶数原链表不变 { cur1 = cur1->next; } else//若链表为奇数，需要移动放入headb中 { //交换链表节点操作 LNode* tmp = cur1->next; cur1->next = cur1->next->next; cur2->next = tmp; cur2->next->next = nullptr; //cur1和cur2各向后移动 cur2 = cur2->next; } } } private: LNode* _head; int _size; }; - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
- 276
- 277
- 278
- 279
- 280
- 281
- 282
- 283
- 284
- 285
- 286
- 287
- 288
- 289
- 290
- 291
- 292
- 293
- 294
- 295
- 296
- 297
- 298
- 299
- 300
- 301
- 302
- 303
- 304
- 305
- 306
- 307
- 308
- 309
- 310
- 311
- 312
- 313
- 314
- 315
- 316
- 317
- 318
- 319
- 320
- 321
- 322
- 323
- 324
- 325
- 326
- 327
- 328
3.3test.cpp
#define _CRT_SECURE_NO_WARNINGS 1 #includeusing namespace std; #include"LinkList.h" void test_LinkList1() { LinkList lt; //链表打印 lt.print(); //测试空链表删除 lt.pop_front(); //尾插 lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.print(); //头插 lt.push_front(5); lt.push_front(6); lt.push_front(7); lt.push_front(8); lt.print(); //打印链表节点 lt.print_size(); //尾删 lt.pop_back(); lt.pop_back(); lt.print(); //头删 lt.pop_front(); lt.pop_front(); lt.print(); lt.print_size(); } void test_LinkList2() { //头插法创建n个元素的链表 LinkList lt; lt.push_front_n(); lt.print(); lt.print_size(); } void test_LinkList3() { LinkList lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); lt.push_back(6); lt.push_back(7); lt.push_back(8); lt.push_back(9); lt.push_back(10); lt.print(); lt.print_size(); lt.push_back(6); lt.push_back(6); lt.push_back(6); //删除第11节点的元素 lt.erase(11); lt.print(); //删除所有元素为6的节点 cout << "是否删除成功:" << lt.erase_all_x(6) << endl; lt.print(); cout << "是否删除成功:" << lt.erase_all_x(6) << endl; lt.print(); //打印所有节点为偶数的个数 lt.print_even_number(); //拷贝构造函数 LinkList lt1(lt); lt1.print(); lt1.print_size(); //编译器生成了默认的赋值运算符重载 LinkList lt2 = lt1; lt2.print(); //创建空链表 LinkList lt3; lt3.print(); lt1.push_back(11); lt1.push_back(14); lt1.push_back(12); lt1.push_back(13); lt1.print(); //分离链表lt1，使lt1只含有偶数，lt3只含有奇数 lt1.divide_LinkList(lt1.get_head(), lt3.get_head()); lt1.print(); lt3.print(); } int main() { //不想输入数据就调用test_LinkList1()或test_LinkList3(); //test_LinkList1(); //test_LinkList2(); test_LinkList3(); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
-
相关阅读:
BiConsumer的使用
集成websocket实现实时通信(ruoyi 使用笔记)
多元共进｜2023 Google 开发者大会主旨演讲亮点回顾
二战字节跳动成功上岸，准备了小半年，拿27k也算不上很高吧~
ConnectTimeout 和 ConnectionError 的差异
java并发编程 守护线程 用户线程 main
【开源】EValidator Java简单校验工具二
多线程学习（C/C++）
调用内部或私有方法的N种方法
面试题解：基于 ZooKeeper 的分布式锁实现原理是什么？和Reids做分布式锁的区别？
- 原文地址：https://blog.csdn.net/Crocodile1006/article/details/132992886
