热门标签
热门文章
- 1Numpy数组中数据的排序【sort()，argsort()与 lexsort()】 （Numpy篇-13）_numpy中数组的方法sort,argsort,lexsort
- 2GPU与CPU的性能比较及影响因素_gpu比cpu快多少
- 3【视频文稿】车载Android应用开发与分析 - 走进车载操作系统_adstudy车载测试视频csdn
- 4Llama 3 五一超级课堂 笔记 ==＞ 第五节、Llama 3 Agent 能力体验与微调_llama3 支持agent吗
- 5如何制作自己的数字人
- 6【MySQL】 锁机制：InnoDB引擎中锁分类以及表锁、行锁、页锁详解
- 7[立创泰山派]RK3566 buildroot添加qt5运行环境_rk3566 qt
- 8【FAQ】解决org.json.JSONException: JSONArray[0] is not a JSONArray._jsonarray[0] is not a jsonobject
- 9一款非常好看好用的Linux操作系统中国发行版_linux好看的版本
- 10【小5聊】Sql Server基础使用之SHOWPLAN permission denied in database_showplan permission denied in database 'cam'.
当前位置: article > 正文
C语言/C++实现链表的详细教程_c++ 链表
作者：我家小花儿 | 2024-05-30 07:51:45
赞
踩
c++ 链表
C语言/C++实现链表的详细教程
1. 什么是链表
链表是一种常用的数据结构，它由一系列节点组成，每个节点包含两部分内容：数据和指向下一个节点的指针,最后一个节点指向空。链表的节点可以动态添加和删除，因此可以方便地进行插入、删除等操作。链表有多种类型，包括单向链表、双向链表和循环链表等。
1.1 单向链表（Singly Linked List）
单向链表是最简单的链表类型，它的每个节点只包含一个指向下一个节点的指针。单向链表的优点是插入和删除节点的速度较快，但查找节点的速度较慢。单向链表的数据结构如下所示：
cstruct ListNode {
int val; // 节点的值
struct ListNode *next; // 指向下一个节点的指针
};
- 1
- 2
- 3
- 4
1.2 双向链表（Doubly Linked List）
双向链表是在单向链表的基础上增加了一个指向前一个节点的指针。这样一来，双向链表可以从前往后遍历，也可以从后往前遍历，但相应地，插入和删除节点的操作会稍微复杂一些。双向链表的数据结构如下所示：
cstruct ListNode {
int val; // 节点的值
struct ListNode *prev; // 指向前一个节点的指针
struct ListNode *next; // 指向下一个节点的指针
};
- 1
- 2
- 3
- 4
- 5
1.3 循环链表（Circular Linked List）
循环链表是一种特殊的链表类型，它的最后一个节点指向第一个节点（或者说，第一个节点指向最后一个节点）。这样一来，循环链表可以无限循环下去，因此常用于循环队列等数据结构中。循环链表的数据结构和单向链表或双向链表类似，只是最后一个节点的指针指向第一个节点。
本教程主要演示的是单向链表的使用。
2. 节点的定义
首先，我们需要定义链表的节点结构。每个节点包含一个数据元素和一个指向下一个节点的指针。在C语言中，我们可以使用结构体来定义节点。
typedef struct Node {
int data; // 数据元素
struct Node* next; // 指向下一个节点的指针
} Node;
- 1
- 2
- 3
- 4
3. 创建和初始化链表
下面是一个函数，用于创建并初始化一个空链表。
Node* createLinkedList() {
return NULL; // 返回空链表
}
- 1
- 2
- 3
4. 插入节点
接下来，我们需要实现在链表中插入新节点的功能。我们可以根据需要在链表的开头、末尾或中间插入新节点。
// 插入节点到链表开头 Node *insertAtBeginning(Node *head, int data) { // 创建新节点 Node *newNode = (Node*)malloc(sizeof(Node)); // 设置节点数据 newNode->data = data; // 将新节点指向原来的头节点 newNode->next = head; // 返回新的链表头节点 return newNode; } // 插入节点到链表末尾 Node *insertAtEnd(Node *head, int data) { // 创建新节点 Node *newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; // 将新节点的下一个节点指针设置为NULL newNode->next = NULL; // 如果链表为空，将新节点作为链表的唯一节点 if (head == NULL) { return newNode; } Node* current = head; // 遍历链表直到达到最后一个节点 while (current->next != NULL) { current = current->next; } // 将新节点插入到已有链表的末尾 current->next = newNode; // 返回原来的头节点 return head; } // 在指定位置插入节点 Node* insertAtPosition(Node* head, int data, int position) { // 创建新节点 Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; // 如果插入位置为0，则将新节点作为新的头节点 if (position == 0) { newNode->next = head; return newNode; } Node* current = head; // 找到插入位置的前一个节点 for (int i = 0; i < position - 1; i++) { if (current == NULL) { printf("位置超出链表存储范围。\n"); return head; } current = current->next; } // 将新节点的next指针指向当前位置的节点 newNode->next = current->next; // 将当前位置的节点指向新节点 current->next = newNode; // 返回原来的头节点 return head; }
- 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
5. 删除节点
我们也可以从链表中删除节点。下面是一些用于删除节点的函数示例。
// 从链表开头删除节点 Node* deleteAtBeginning(Node* head) { if (head == NULL) { printf("链表为空"); return NULL; } Node* temp = head; // 更新头节点 head = head->next; // 释放删除节点的内存 free(temp); // 返回新的头节点 return head; } // 从链表末尾删除节点 Node* deleteAtEnd(Node* head) { if (head == NULL) { printf("链表为空！！！\n"); return NULL; } // 如果只有一个节点，直接删除 if (head->next == NULL) { free(head); return NULL; } Node *current = head, *prev; // 找到倒数第二个节点 while (current->next != NULL) { prev = current; current = current->next; } //将倒数第二个节点的next指针设置为NULL，删除最后一个节点 prev->next = NULL; // 释放删除节点的内存 free(current); // 返回原来的头节点 return head; } // 根据数据值删除节点 Node* deleteByValue(Node* head, int data) { if (head == NULL) { printf("链表为空！！！\n"); return NULL; } Node *current = head, *prev; // 遍历链表找到要删除的节点 while (current != NULL && current->data != data) { prev = current; current = current->next; } if (current == NULL) { printf("数据不存在！！！\n"); return head; } if (current == head) { //如果删除节点是头节点，则更新头节点 head = head->next; } else { //将前一个节点的next指针跳过删除节点 prev->next = current->next; } free(current);// 释放删除节点的内存 return head; }
- 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
6. 打印链表
为了验证链表的操作，我们可以编写一个函数来打印链表的所有节点。
//打印链表数据
void printList(Node* head) {
Node* current = head;
printf("链表所存数据: ");
//表头为空，结束循环
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
7. 测试代码
我们可以编写一段测试代码来验证我们的链表代码：
//主函数 int main() { //创建链表 Node* head = createLinkedList(); printf("链表已经创建完成，可以正常使用！！！\n"); while(true){ printf("1、添加新的数据到链表头。\n"); printf("2、添加新的数据到链表尾。\n"); printf("3、添加新的数据到固定位置。\n"); printf("4、删除链表头的数据。\n"); printf("5、删除链表尾的数据。\n"); printf("6、删除指定数据。\n"); printf("7、退出程序。\n"); printf("请输入你的选择："); int ch; bool flag=false; scanf("%d",&ch); system("cls"); switch(ch){ case 1: int insertN; printf("请输入需要插入的数据："); scanf("%d",&insertN); head = insertAtBeginning(head, insertN); break; case 2: int insertEndN; printf("请输入需要插入的数据："); scanf("%d",&insertEndN); head = insertAtEnd(head, insertEndN); break; case 3: int insertPosN,pos; printf("请输入需要插入的数据和位置："); scanf("%d %d",&insertPosN,&pos); head = insertAtPosition(head, insertPosN, pos-1); break; case 4: head = deleteAtBeginning(head); break; case 5: head = deleteAtEnd(head); break; case 6: int delN; printf("请输入需要删除的数据："); scanf("%d",&delN); head = deleteByValue(head, delN); break; case 7:printf("程序结束，欢迎使用。\n");exit(0); default: printf("您的输入有误，请检查后重新输入！\n"); flag=true; break; } if(!flag){ printf("****-----------------------------****\n"); printList(head); printf("****-----------------------------****\n\n"); } getchar(); } 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
8. 总结
恭喜你！你已经完成了C语言实现链表的教程。链表是一种非常有用的数据结构，可以在运行时动态管理数据。通过学习链表的实现，您可以对如何操作和管理数据有更深入的了解。希望本教程对你有所帮助，谢谢！
9. 完整代码
#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; // 数据元素 struct Node *next; // 指向下一个节点的指针 } Node; //创建并初始化链表 Node *createLinkedList() { return NULL; // 返回空链表 } // 插入节点到链表开头 Node *insertAtBeginning(Node *head, int data) { // 创建新节点 Node *newNode = (Node*)malloc(sizeof(Node)); // 设置节点数据 newNode->data = data; // 将新节点指向原来的头节点 newNode->next = head; // 返回新的链表头节点 return newNode; } // 插入节点到链表末尾 Node *insertAtEnd(Node *head, int data) { // 创建新节点 Node *newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; // 将新节点的下一个节点指针设置为NULL newNode->next = NULL; // 如果链表为空，将新节点作为链表的唯一节点 if (head == NULL) { return newNode; } Node* current = head; // 遍历链表直到达到最后一个节点 while (current->next != NULL) { current = current->next; } // 将新节点插入到已有链表的末尾 current->next = newNode; // 返回原来的头节点 return head; } // 在指定位置插入节点 Node* insertAtPosition(Node* head, int data, int position) { // 创建新节点 Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; // 如果插入位置为0，则将新节点作为新的头节点 if (position == 0) { newNode->next = head; return newNode; } Node* current = head; // 找到插入位置的前一个节点 for (int i = 0; i < position - 1; i++) { if (current == NULL) { printf("位置超出链表存储范围。\n"); return head; } current = current->next; } // 将新节点的next指针指向当前位置的节点 newNode->next = current->next; // 将当前位置的节点指向新节点 current->next = newNode; // 返回原来的头节点 return head; } // 从链表开头删除节点 Node* deleteAtBeginning(Node* head) { if (head == NULL) { printf("链表为空"); return NULL; } Node* temp = head; // 更新头节点 head = head->next; // 释放删除节点的内存 free(temp); // 返回新的头节点 return head; } // 从链表末尾删除节点 Node* deleteAtEnd(Node* head) { if (head == NULL) { printf("链表为空！！！\n"); return NULL; } // 如果只有一个节点，直接删除 if (head->next == NULL) { free(head); return NULL; } Node *current = head, *prev; // 找到倒数第二个节点 while (current->next != NULL) { prev = current; current = current->next; } //将倒数第二个节点的next指针设置为NULL，删除最后一个节点 prev->next = NULL; // 释放删除节点的内存 free(current); // 返回原来的头节点 return head; } // 根据数据值删除节点 Node* deleteByValue(Node* head, int data) { if (head == NULL) { printf("链表为空！！！\n"); return NULL; } Node *current = head, *prev; // 遍历链表找到要删除的节点 while (current != NULL && current->data != data) { prev = current; current = current->next; } if (current == NULL) { printf("数据不存在！！！\n"); return head; } if (current == head) { //如果删除节点是头节点，则更新头节点 head = head->next; } else { //将前一个节点的next指针跳过删除节点 prev->next = current->next; } free(current);// 释放删除节点的内存 return head; } //打印链表数据 void printList(Node* head) { Node* current = head; printf("链表所存数据: "); //表头为空，结束循环 while (current != NULL) { printf("%d ", current->data); current = current->next; } printf("\n"); } //主函数 int main() { //创建链表 Node* head = createLinkedList(); printf("链表已经创建完成，可以正常使用！！！\n"); while(true){ printf("1、添加新的数据到链表头。\n"); printf("2、添加新的数据到链表尾。\n"); printf("3、添加新的数据到固定位置。\n"); printf("4、删除链表头的数据。\n"); printf("5、删除链表尾的数据。\n"); printf("6、删除指定数据。\n"); printf("7、退出程序。\n"); printf("请输入你的选择："); int ch; bool flag=false; scanf("%d",&ch); system("cls"); switch(ch){ case 1: int insertN; printf("请输入需要插入的数据："); scanf("%d",&insertN); head = insertAtBeginning(head, insertN); break; case 2: int insertEndN; printf("请输入需要插入的数据："); scanf("%d",&insertEndN); head = insertAtEnd(head, insertEndN); break; case 3: int insertPosN,pos; printf("请输入需要插入的数据和位置："); scanf("%d %d",&insertPosN,&pos); head = insertAtPosition(head, insertPosN, pos-1); break; case 4: head = deleteAtBeginning(head); break; case 5: head = deleteAtEnd(head); break; case 6: int delN; printf("请输入需要删除的数据："); scanf("%d",&delN); head = deleteByValue(head, delN); break; case 7:printf("程序结束，欢迎使用。\n");exit(0); default: printf("您的输入有误，请检查后重新输入！\n"); flag=true; break; } if(!flag){ printf("****-----------------------------****\n"); printList(head); printf("****-----------------------------****\n\n"); } getchar(); } 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
- 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
以上就是C语言实现链表的详细教程。希望对您有所帮助！如果您还有其他问题，请随时提问。
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/645951
推荐阅读
相关标签
