数据结构的练习day2(未完待续)

凌魁

数据结构线性结构之单向循环链表的基本操作

1. /********************************************************************************************************
2. *
3. *
4. * 设计单向循环链表的接口
5. *
6. *
7. *
8. * Copyright (c)  2023-2024   17820413718@163.com   All right Reserved
9. * ******************************************************************************************************/
10. #include <stdio.h>
11. #include <stdlib.h>
12. #include <stdbool.h>
14. // 指的是单向循环链表中的结点有效数据类型，用户可以根据需要进行修改
15. typedef int DataType_t;
17. // 构造单向循环链表的结点,链表中所有结点的数据类型应该是相同的
18. typedef struct CircularLinkedList
19. {
20.         DataType_t data;                                                                 // 结点的数据域
21.         struct CircularLinkedList *next; // 结点的指针域
23. } CircLList_t;
25. // 遍历链表
26. bool CircLList_Print(CircLList_t *Head)
27. {
28.         // 对单向循环链表的头结点的地址进行备份
29.         CircLList_t *Phead = Head;
31.         // 判断当前链表是否为空，为空则直接退出
32.         if (Head->next == Head)
33.         {
34.                 printf("current linkeflist is empty!\n");
35.                 return false;
36.         }
38.         // 从首结点开始遍历
39.         while (Phead->next)
40.         {
41.                 // 把头结点的直接后继作为新的头结点
42.                 Phead = Phead->next;
43.                 // 输出头结点的直接后继的数据域
44.                 printf("data = %d\n", Phead->data);
46.                 // 判断是否到达尾结点，尾结点的next指针是指向首结点的地址
47.                 if (Phead->next == Head->next)
48.                 {
49.                         break;
50.                 }
51.         }
53.         return true;
54. }
55. // 创建一个空单向循环链表，空链表应该有一个头结点，对链表进行初始化
56. CircLList_t *CircLList_Create(void)
57. {
58.         // 1.创建一个头结点并对头结点申请内存
59.         CircLList_t *Head = (CircLList_t *)calloc(1, sizeof(CircLList_t));
60.         if (NULL == Head)
61.         {
62.                 perror("Calloc memory for Head is Failed");
63.                 exit(-1);
64.         }
66.         // 2.对头结点进行初始化，头结点是不存储数据域，指针域指向自身，体现“循环”思想
67.         Head->next = Head;
69.         // 3.把头结点的地址返回即可
70.         return Head;
71. }
73. // 创建新的结点，并对新结点进行初始化（数据域 + 指针域）
74. CircLList_t *CircLList_NewNode(DataType_t data)
75. {
76.         // 1.创建一个新结点并对新结点申请内存
77.         CircLList_t *New = (CircLList_t *)calloc(1, sizeof(CircLList_t));
78.         if (NULL == New)
79.         {
80.                 perror("Calloc memory for NewNode is Failed");
81.                 return NULL;
82.         }
84.         // 2.对新结点的数据域和指针域进行初始化
85.         New->data = data;
86.         New->next = NULL;
88.         return New;
89. }
91. // 头插
92. bool CircLList_HeadInsert(CircLList_t *Head, DataType_t data)
93. {
94.         if (Head == NULL)
95.         {
96.                 printf("链表为空!\n");
97.                 return false;
98.         }
99.         // 创建一个指针代替Head
100.         CircLList_t *phead = Head;
101.         // 新建一个结点
102.         CircLList_t *newNode = CircLList_NewNode(data);
103.         // 让新建的结点指向原来的首结点
104.         newNode->next = phead->next;
105.         // 让头结点指向新建的结点
106.         phead->next = newNode;
107.         return true;
108. }
110. // 尾插
111. bool CircLList_TailInsert(CircLList_t *Head, DataType_t data)
112. {
113.         if (Head == NULL)
114.         {
115.                 printf("链表为空!\n");
116.                 return false;
117.         }
118.         // 创建一个指针代替Head
119.         CircLList_t *phead = Head->next;
120.         // 新建一个结点
121.         CircLList_t *newNode = CircLList_NewNode(data);
123.         while (phead->next != Head)
124.         {
125.                 phead = phead->next;
126.                 if (phead->next == Head->next)
127.                 {
128.                         break;
129.                 }
130.         }
131.         //  尾结点指向新结点
132.         phead->next = newNode;
133.         // 新结点指向首结点
134.         newNode->next = Head->next;
135.         return true;
136. }
138. // 指定位置插入(后插)
139. bool CircLList_DestInsert(CircLList_t *Head, DataType_t destval, DataType_t data)
140. {
141.         if (Head == NULL)
142.         {
143.                 printf("链表为空!\n");
144.                 return false;
145.         }
146.         // 创建一个指针代替Head
147.         CircLList_t *phead = Head;
148.         // 新建一个结点
149.         CircLList_t *newNode = CircLList_NewNode(data);
150.         while (phead)
151.         {
152.                 // 找到目标结点的上前结点
153.                 if (phead->next->data == destval)
154.                 {
155.                         break;
156.                 }
157.                 phead = phead->next;
158.         }
159.         newNode->next = phead->next;
160.         phead->next = newNode;
161. }
163. // 头删
164. bool CircLList_HeadDel(CircLList_t *Head)
165. {
166.         // 对单向循环链表的首结点的地址进行备份
167.         CircLList_t *Phead = Head->next;
168.         while (Phead->next != Head)
169.         {
170.                 if (Phead->next == Head->next)
171.                 {
172.                         break;
173.                 }
174.                 Phead = Phead->next;
175.         }
176.         Phead->next = Head->next->next;
177.         Phead = Head->next;
178.         Head->next = Head->next->next;
179.         Phead->next = NULL;
180.         free(Phead);
181.         return true;
182. }
184. // 尾删
185. bool CircLList_TailDel(CircLList_t *Head)
186. {
187.         // 对单向循环链表的首结点的地址进行备份
188.         CircLList_t *phead = Head->next;
189.         // 找到尾结点的前一个结点
190.         while (phead->next->next != Head)
191.         {
192.                 if (phead->next->next == Head->next)
193.                 {
194.                         break;
195.                 }
196.                 phead = phead->next;
197.         }
198.         phead->next->next = NULL;
199.         free(phead->next);
200.         phead->next = Head->next;
202.         return true;
203. }
205. // 指定数据的结点删除(后删)
206. bool CircLList_DestDes(CircLList_t *Head, DataType_t destval)
207. {
208.         // 对单向循环链表的首结点的地址进行备份
209.         CircLList_t *phead = Head->next;
210.         // 前结点
211.         CircLList_t *preNode = Head;
212.         // 要删除的结点
213.         CircLList_t *delNode = Head->next;
214.         while (phead->next != Head)
215.         {
216.                 if (delNode->data == destval)
217.                 {
218.                         break;
219.                 }
220.                 preNode = delNode;
221.                 delNode = delNode->next;
222.         }
223.         preNode->next = delNode->next;
224.         delNode->next = NULL;
225.         free(delNode);
226.         return true;
227. }
228. int main(int argc, char const *argv[])
229. {
230.         CircLList_t *Head = CircLList_Create();
232.         CircLList_HeadInsert(Head, 40);
233.         CircLList_HeadInsert(Head, 30);
234.         CircLList_HeadInsert(Head, 20);
235.         CircLList_HeadInsert(Head, 10);
237.         CircLList_TailInsert(Head, 50);
238.         CircLList_DestInsert(Head, 30, 15);
239.         CircLList_HeadDel(Head);
240.         CircLList_Print(Head);
241.         CircLList_TailDel(Head);
242.         CircLList_DestDes(Head, 20);
243.         CircLList_Print(Head);
244.         return 0;
245. }

复制代码

来源:https://www.cnblogs.com/DengJian111222/p/18153810
免责声明：由于采集信息均来自互联网，如果侵犯了您的权益，请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容，谢谢合作！