-
数据结构-单链表
大家好：
衷心希望各位点赞。
您的问题请留在评论区，我会及时回答。
单链表的定义
// 链表的定义 typedef struct _LinkNode { ElemType data; // 数据域 struct _LinkNode* next; // 指针域 }* LinkList, LinkNode; // LinkList：头指针、LinkNode：链表节点- 1
- 2
- 3
- 4
- 5
- 6
单链表的初始化
bool initList(LinkList& L) { L = new LinkNode; // 生成新节点作为头节点，用头指针L指向头节点 if (L == NULL) return false; // 生成节点失败 L->next = NULL; // 头节点指针域置为空 L->data = 0; // 头节点数据映射链表长度 return true; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
代码示范：
#include#include using namespace std; typedef int ElemType; // 链表的定义 typedef struct _LinkNode { ElemType data; // 数据域 struct _LinkNode* next; // 指针域 }* LinkList, LinkNode; // LinkList：头指针、LinkNode：链表节点 // 构造一个空的单链表 // 生成头节点 bool initList(LinkList& L) { L = new LinkNode; // 生成新节点作为头节点，用头指针L指向头节点 if (L == NULL) return false; // 生成节点失败 L->next = NULL; // 头节点指针域置为空 L->data = 0; // 头节点数据映射链表长度 return true; } int main(void) { LinkList L; initList(L); // 初始化链表 system("pause"); 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
单链表的打印
// 打印链表 void listPrint(const LinkList& L) { LinkList p = L->next; if (p == NULL) return ; // 链表为空 cout << "链表长度：" << L->data << " 链表元素："; while (p != NULL) { cout << p->data << " "; p = p->next; } cout << endl; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
单链表的插入——头插法
// 插入节点 // 头插法 bool listInsert_front(LinkList& L, LinkNode* node) { if (L == NULL || node == NULL ) return false; node->next = L->next; // 新节点的指针域指向头结点的后继节点 L->next = node; // 头结点的指针域指向新节点 L->data++; // 链表的节点数加一 return true; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
代码示范：
#include#include using namespace std; typedef int ElemType; // 链表的定义 typedef struct _LinkNode { ElemType data; // 数据域 struct _LinkNode* next; // 指针域 }* LinkList, LinkNode; // 构造一个空的单链表 // 生成头节点 bool initList(LinkList& L); // 插入节点 // 头插法 bool listInsert_front(LinkList& L, LinkNode* node); // 打印链表 void listPrint(const LinkList& L); int main(void) { LinkList L; initList(L); // 初始化链表 for (int i = 0; i < 10; i++) { LinkNode* node = new LinkNode; // 创建节点 node->data = i + 1; // 给新节点的数据域赋值 listInsert_front(L, node); // 头插法给单链表插入新节点 } listPrint(L); system("pause"); return 0; } bool initList(LinkList& L) { L = new LinkNode; // 生成新节点作为头节点，用头指针L指向头节点 if (L == NULL) return false; // 生成节点失败 L->next = NULL; // 头节点指针域置为空 L->data = 0; // 头节点数据映射链表长度 return true; } bool listInsert_front(LinkList& L, LinkNode* node) { if (L == NULL || node == NULL ) return false; node->next = L->next; // 新节点的指针域指向头结点的后继节点 L->next = node; // 头结点的指针域指向新节点 L->data++; // 链表的节点数加一 return true; } void listPrint(const LinkList& L) { LinkList p = L->next; if (p == NULL) return ; // 链表为空 cout << "链表长度：" << L->data << " 链表元素："; while (p != NULL) { cout << p->data << " "; p = p->next; } cout << 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
- 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
运行截图：
单链表的插入——尾插法
// 插入节点 // 尾插法 bool listInsert_back(LinkList& L, LinkNode* node) { if (L == NULL || node == NULL) return false; LinkList p = L; // 指针p移动到表尾元素 while (p->next != NULL) { p = p->next; } node->next = p->next; p->next = node; L->data++; // 链表元素个数加一 return true; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
代码示范：
#include#include using namespace std; typedef int ElemType; // 链表的定义 typedef struct _LinkNode { ElemType data; // 数据域 struct _LinkNode* next; // 指针域 }* LinkList, LinkNode; // 构造一个空的单链表 // 生成头节点 bool initList(LinkList& L); // 插入节点 // 头插法 bool listInsert_front(LinkList& L, LinkNode* node); // 插入节点 // 尾插法 bool listInsert_back(LinkList& L, LinkNode* node); // 打印链表 void listPrint(const LinkList& L); int main(void) { LinkList L; initList(L); // 初始化链表 for (int i = 0; i < 10; i++) { LinkNode* node = new LinkNode; // 创建节点 node->data = i + 1; // 给新节点的数据域赋值 listInsert_back(L, node); // 尾插法给单链表插入新节点 } listPrint(L); system("pause"); return 0; } bool initList(LinkList& L) { L = new LinkNode; // 生成新节点作为头节点，用头指针L指向头节点 if (L == NULL) return false; // 生成节点失败 L->next = NULL; // 头节点指针域置为空 L->data = 0; // 头节点数据映射链表长度 return true; } bool listInsert_front(LinkList& L, LinkNode* node) { if (L == NULL || node == NULL ) return false; node->next = L->next; // 新节点的指针域指向头结点的后继节点 L->next = node; // 头结点的指针域指向新节点 L->data++; // 链表的节点数加一 return true; } bool listInsert_back(LinkList& L, LinkNode* node) { if (L == NULL || node == NULL) return false; LinkList p = L; // 指针p移动到表尾元素 while (p->next != NULL) { p = p->next; } node->next = p->next; p->next = node; L->data++; // 链表元素个数加一 return true; } void listPrint(const LinkList& L) { LinkList p = L->next; if (p == NULL) return ; // 链表为空 cout << "链表长度：" << L->data << " 链表元素："; while (p != NULL) { cout << p->data << " "; p = p->next; } cout << 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
- 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
运行截图：
单链表的插入——在指定位置插入元素
// 插入节点 bool ListInsert(LinkList& L, int pos, ElemType elem) { int i = 0; LinkList p, s; p = L; i = 1; while (p != NULL && i < pos) { // 寻找第i个节点 p = p->next; i++; } if (p == NULL || i > pos)return false; s = new LinkNode; s->data = elem; s->next = p->next; p->next = s; L->data++; 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
代码示范：
#include#include using namespace std; typedef int ElemType; // 链表的定义 typedef struct _LinkNode { ElemType data; // 数据域 struct _LinkNode* next; // 指针域 }* LinkList, LinkNode; // 构造一个空的单链表 // 生成头节点 bool initList(LinkList& L); // 插入节点 // 头插法 bool listInsert_front(LinkList& L, LinkNode* node); // 插入节点 // 尾插法 bool listInsert_back(LinkList& L, LinkNode* node); // 插入节点 bool ListInsert(LinkList& L, int pos, ElemType elem); // 打印链表 void listPrint(const LinkList& L); int main(void) { LinkList L; initList(L); // 初始化链表 for (int i = 0; i < 5; i++) { LinkNode* node = new LinkNode; // 创建节点 node->data = i + 1; // 给新节点的数据域赋值 listInsert_back(L, node); // 尾插法给单链表插入新节点 } listPrint(L); cout << endl; cout << "在第3个位置插入值为10的元素：" << endl;; ListInsert(L, 3, 10); listPrint(L); system("pause"); return 0; } bool initList(LinkList& L) { L = new LinkNode; // 生成新节点作为头节点，用头指针L指向头节点 if (L == NULL) return false; // 生成节点失败 L->next = NULL; // 头节点指针域置为空 L->data = 0; // 头节点数据映射链表长度 return true; } bool listInsert_front(LinkList& L, LinkNode* node) { if (L == NULL || node == NULL ) return false; node->next = L->next; // 新节点的指针域指向头结点的后继节点 L->next = node; // 头结点的指针域指向新节点 L->data++; // 链表的节点数加一 return true; } bool listInsert_back(LinkList& L, LinkNode* node) { if (L == NULL || node == NULL) return false; LinkList p = L; // 指针p移动到表尾元素 while (p->next != NULL) { p = p->next; } node->next = p->next; p->next = node; L->data++; // 链表元素个数加一 return true; } bool ListInsert(LinkList& L, int pos, ElemType elem) { int i = 0; LinkList p, s; p = L; i = 1; while (p != NULL && i < pos) { // 寻找第i个节点 p = p->next; i++; } if (p == NULL || i > pos)return false; s = new LinkNode; s->data = elem; s->next = p->next; p->next = s; L->data++; return true; } void listPrint(const LinkList& L) { LinkList p = L->next; if (p == NULL) return ; // 链表为空 cout << "链表长度：" << L->data << " 链表元素："; while (p != NULL) { cout << p->data << " "; p = p->next; } cout << 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
- 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
运行截图：
单链表的删除
// 单链表的删除 // 删除L的第pos个元素，并用elem返回其值，L的长度减1 bool ListDelete(LinkList& L, int pos, ElemType* elem) { int i; LinkList p, q; p = L; i = 1; while (p->next != NULL && i < pos) { p = p->next; i++; } if (p->next == NULL || i > pos) { return false; } q = p->next; p->next = q->next; *elem = q->data; delete q; L->data--; 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
代码示范：
#include#include using namespace std; typedef int ElemType; // 链表的定义 typedef struct _LinkNode { ElemType data; // 数据域 struct _LinkNode* next; // 指针域 }* LinkList, LinkNode; // 构造一个空的单链表 // 生成头节点 bool initList(LinkList& L); // 插入节点 // 头插法 bool listInsert_front(LinkList& L, LinkNode* node); // 插入节点 // 尾插法 bool listInsert_back(LinkList& L, LinkNode* node); // 插入节点 bool ListInsert(LinkList& L, int pos, ElemType elem); // 单链表的删除 // 删除L的第pos个元素，并用elem返回其值，L的长度减1 bool ListDelete(LinkList& L, int pos, ElemType* elem); // 打印链表 void listPrint(const LinkList& L); int main(void) { LinkList L; initList(L); // 初始化链表 for (int i = 0; i < 5; i++) { LinkNode* node = new LinkNode; // 创建节点 node->data = i + 1; // 给新节点的数据域赋值 listInsert_back(L, node); // 尾插法给单链表插入新节点 } listPrint(L); cout << endl; cout << "删除在第3个位置的元素：" << endl;; ElemType e; ListDelete(L, 3, &e); cout << "删除的元素为：" << e << endl; listPrint(L); system("pause"); return 0; } bool initList(LinkList& L) { L = new LinkNode; // 生成新节点作为头节点，用头指针L指向头节点 if (L == NULL) return false; // 生成节点失败 L->next = NULL; // 头节点指针域置为空 L->data = 0; // 头节点数据映射链表长度 return true; } bool listInsert_front(LinkList& L, LinkNode* node) { if (L == NULL || node == NULL ) return false; node->next = L->next; // 新节点的指针域指向头结点的后继节点 L->next = node; // 头结点的指针域指向新节点 L->data++; // 链表的节点数加一 return true; } bool listInsert_back(LinkList& L, LinkNode* node) { if (L == NULL || node == NULL) return false; LinkList p = L; // 指针p移动到表尾元素 while (p->next != NULL) { p = p->next; } node->next = p->next; p->next = node; L->data++; // 链表元素个数加一 return true; } bool ListInsert(LinkList& L, int pos, ElemType elem) { int i = 0; LinkList p, s; p = L; i = 1; while (p != NULL && i < pos) { // 寻找第i个节点 p = p->next; i++; } if (p == NULL || i > pos)return false; s = new LinkNode; s->data = elem; s->next = p->next; p->next = s; L->data++; return true; } bool ListDelete(LinkList& L, int pos, ElemType* elem) { int i; LinkList p, q; p = L; i = 1; while (p->next != NULL && i < pos) { p = p->next; i++; } if (p->next == NULL || i > pos) { return false; } q = p->next; p->next = q->next; *elem = q->data; delete q; L->data--; return true; } void listPrint(const LinkList& L) { LinkList p = L->next; if (p == NULL) return ; // 链表为空 cout << "链表长度：" << L->data << " 链表元素："; while (p != NULL) { cout << p->data << " "; p = p->next; } cout << 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
- 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
运行截图：
-
相关阅读:
ROS系列（二）：rosbag 中提取视频数据
java建材公司管理系统计算机毕业设计MyBatis+系统+LW文档+源码+调试部署
git使用详解
视频转换器 AnyMP4 Video Converter Ultimate v8.5.52 x64
YOLOv9理性解读 | 网络结构&损失函数&耗时评估
【C++ 学习 ⑳】- 详解二叉搜索树
并发编程带来的安全性挑战之同步锁
C#餐饮收银系统
pytest集成allure报告（allure安装及配置以及如何实现集成）
分享如何筛选延误三天以上物流件
- 原文地址：https://blog.csdn.net/weixin_45146479/article/details/137254550
