C中单向链表之增删改查

C中单向链表之增删改查

1. // 链表（Linked List）是一种基础但至关重要的数据结构。它通过动态内存分配实现数据的非连续存储，解决了数组的固定长度和插入/删除低效的问题。无论是算法面试还是实际开发，链表都是高频考点和核心技能之一。
2. #include <iostream>
3. #include <stdlib.h>
4. #include <stdio.h>
5. #include <cstring>
6. using namespace std;
8. // 单向链表（Singly Linked List）
9. typedef struct Node
10. {
12.     int num;
13.     char data[20];
14.     struct Node *next;
15.     Node(int x) : num(num), next(nullptr) {}
16.     Node() {}
17. } STU, Node, *PNode;
18. // 链表创建(头插法)
20. PNode linked_create_head1()
21. {
23.     int num, i = 0;
24.     cout << "请输入节点数量：" << endl;
25.     cin >> num;
26.     PNode head = NULL;
27.     PNode current = NULL;
29.     while (i < num)
30.     {
31.         PNode temp;
32.         PNode node = (PNode)malloc(sizeof(Node));
33.         if (node == NULL)
34.         {
35.             printf("内存分配失败！\n");
36.             exit(1);
37.         }
39.         memset(node, 0, sizeof(Node));
40.         cout << "请输入第" << i << "节点data：" << endl;
41.         cin >> node->data;
43.         // 如果当前头节点为空，则将新节点作为头节点
44.         if (head == NULL)
45.         {
47.             head = node;
48.         }
49.         else
50.         {
52.             node->next = head; // 将新节点的指针域指向head（老节点）
54.             head = node; // 将新节点作为头节点
55.         }
56.         i++;
57.     }
58.     // 给节点编号
59.     current = head;
60.     for (int i = 0; i < num; i++)
61.     {
62.         current->num = i;
63.         current = current->next;
64.     }
66.     return head;
67. }
69. // 链表创建(尾插法)
70. PNode linked_create_tail()
71. {
72.     int num;
73.     cout << "请输入节点数量：" << endl;
74.     cin >> num;
76.     PNode head = nullptr;
77.     PNode tail = nullptr; // 记录尾节点
79.     for (int i = 0; i < num; i++)
80.     {
81.         // 创建新节点
82.         PNode node = (PNode)malloc(sizeof(Node));
83.         if (node == NULL)
84.         {
85.             printf("内存分配失败！\n");
86.             exit(1);
87.         }
88.         memset(node, 0, sizeof(Node));
90.         cout << "请输入第" << i + 1 << "个节点data：" << endl;
91.         cin >> node->data;
92.         node->num = i; // 直接设置节点编号
94.         // 如果是第一个节点
95.         if (head == nullptr)
96.         {
97.             head = node;
98.             tail = node;
99.             node->next = nullptr;
100.         }
101.         else
102.         {
103.             // 将新节点连接到链表尾部
104.             tail->next = node;
105.             tail = node; // 更新尾节点
106.             node->next = nullptr;
107.         }
108.     }
110.     return head;
111. }
113. // 释放链表
114. void free_list(PNode head)
115. {
116.     // 内存释放函数
117.     // 当前节点指针
118.     if (head == NULL)
119.     {
120.         cout << "链表为空" << endl;
121.         return;
122.     }
123.     while (head != NULL)
124.     {                      // 遍历链表
125.         PNode temp = head; // 临时保存当前节点
126.         head = head->next; // 移动到下一个节点
127.         free(temp);        // 释放原节点内存
128.     }
129. }
131. void print_list(PNode *head)
132. {
134.     // 检查链表是否为空
135.     if (*head == NULL)
136.     {
137.         printf("链表为空\n");
138.         return;
139.     }
140.     PNode current = *head; // 使用临时变量避免修改传入的 head 指针
141.     // 遍历整个链表，包括最后一个节点
142.     while (current) // 修改为 head 而不是 head->next
143.     {
144.         printf("当前节点为:%d,节点数据为%s\n", current->num, current->data);
145.         current = current->next;
146.     }
147. }
149. /*
150. task     : 1.从指定位置插入节点
151.            2.创建一个有序链表，根据value值排序
152. */
153. void update_data(PNode head, int value)
154. {
155.     PNode temp = head;
156.     while (temp)
157.     {
158.         if (value == temp->num)
159.         {
160.             // 找到指定节点
161.             // 先清空原始数据
162.             memset(temp->data, 0, sizeof(temp->data));
163.             cout << "请输入要更改的节点数据：" << endl;
164.             cin >> temp->data;
165.             cout << "节点数据更新成功" << endl;
166.             printf("更改后的数据为%s\n", temp->data);
167.             return;
168.         }
170.         temp = temp->next;
171.     }
172. }
173. void insert_node(PNode head)
174. {
175.     PNode temp = head;
177.     PNode new_node = (PNode)malloc(sizeof(Node));
178.     if (new_node == NULL)
179.     {
180.         printf("内存分配失败！\n");
181.         exit(1);
182.     }
183.     memset(new_node, 0, sizeof(Node));
184.     cout << "请输入插入节点的序号" << endl;
185.     cin >> new_node->num;
186.     cout << "请输入插入节点的数据" << endl;
187.     cin >> new_node->data;
188.     while (temp)
189.     {
191.         if (temp->num >= new_node->num)
192.         {
193.             if (temp->num == new_node->num)
194.             {
195.                 new_node->next = temp; // 调整后续链表
196.             }
197.             temp->num = temp->num + 1; // 节点序号递增
198.         }
200.         temp = temp->next;
201.     }
202.     //设置前一位node的next为new_node
203.     temp = head;
204.     while (temp)
205.     {
206.         if ((temp->num) + 1 == new_node->num)
207.         {
208.             temp->next = new_node;
209.             break; // 遍历链表找到插入的位置
210.         }
211.     }
212. }
214. int main()
215. {
216.     PNode head;
217.     head = linked_create_head1();
218.     print_list(&head);
219.     insert_node(head);
220.     print_list(&head);
221.     update_data(head, 1);
222.     print_list(&head);
223.     free_list(head);
224.     return 0;
225. }

复制代码

关于insert节点理解：

我们这里要想插入一个节点就得先找到它的序号前一位和后一位，所以我们将前一位node的next指向new_node，将new_node的next指向后一位node，将后几位node的序号各加一

本篇用于记录学习，如有问题欢迎指出

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！