-
2.4 循环单链表：理论+C语言详细实现
2.1 链式存储概述 和 2.2 线性表的链式存储–单链表（C语言详细实现）
2.4 循环单链表
1 、循环单链表基本概念
单链表和带头结点的单链表不足之处：
- 从表中的某个结点开始，都只能访问这个结点及其后面的结点，不能访问到它前面的结点，除非再从首指针所指向的结点开始访问。
循环链表优点
- 可以解决单链表和带头结点的单链表不足之处。循环链表可以从表中的任意一个结点开始，都能访问表中的所有其他结点，只需要设置表中最后一个结点的指针域指向表中的第一个结点。
循环链表的实现：
单链表中某个结点p是表中最后一个结点的特征是p->nextNULL,对于一个循环单链表，若首指针为head，表中的某个结点p是最后一个结点的特征应该是p->nexthead.
2、ADT描述
数据集合 K：K={k1,k2,k3…,kn},n≥0，K中的元素是datatype类型；
数据关系R：R={r} ， r = {
操作集合如下：
函数 功能 node *init() 建立一个空的循环链表 void display(node *head, int i) 输出带头结点的单链表中各个结点的值 node *findth(node *head, int i) 按序号查找，在带头结点的单链表中查找第i个结点 node* find(node* head, datatype x) 按值查找，在带头结点的链表中查找值为x的结点 node *insert(node *head , datatype x) 在带头结点的单链表中插入一个值为x的结点 node *dele(node *head, datatype x) 在带头结点的单链表中删除一个值为x的结点 int length(node *head) 查询带头结点的链表的长度 node *rear(node *head) 获得循环单链表的最后一个结点的存储地址 3、重要操作
- 插入（在第i-1(1<= i <=n+1 )）个结点后插入一个值为x的新结点
- 1 先构造一个新结点，用s指向
- 2 在找到链表的第i-1个结点，用p指向
- 3 然后修改指针，插入结点（p之后插入新结点是s）
注意：如果插入的结点成为表中的第一个结点，那么必须修改表中最后一个结点的指针域，使最后一个结点的指针域指向新插入的结点。
- 删除（删除循环链表的第i(1<=i<=n)）个位置上的结点
- 1 先找到链表的第i-1个结点，用p指向
- 2 再用指针s指向要删除的结点（p的下一个结点）
- 3 然后修改指针，删除s所指结点
- 最后释放s所指结点的空间，这样内存空间才不会泄漏
注意：如果删除的结点是表中的第一个结点，那么必须要修改表中最后一个结点的指针域，使最后一个结点的指针域指向表中的第二个结点，而且首指针也指向原来表中第二个结点。
3、编程实战
- main.c
#include"clnklist.h" void main() { struct clnkllist* head; node* p; head = init(); int i = 0, number,position; while (i<5)//首先在空链表中插入0~4 { head = insert(head, i, i); i++; } while (i<10) { printf("input the command that you want: 1:init 2:display 3:findth 4:find 5:insert 6: dele 7:length 8:rear \n"); scanf_s("%d", &i); switch (i) { case 1:free(head); head = init(); break; case 2:display(head); break; case 3: { printf("请输入要查找的结点的序号\n"); scanf_s("%d", &position); p = findth(head, position); printf("info: %5d next:%5d", p->info, p->next); break; } case 4: { printf("请输入要查找的结点的值\n"); scanf_s("%d", &number); position = find(head, number); printf("值为%d的结点位置是：%5d\n", number,position); break; } case 5: { printf("please input the datatype and position that you want：\n"); scanf_s("%d %d", &number, &position); head = insert(head,number, position); break; } case 6: { printf("input delete datatype ：\n"); scanf_s("%d", &number); head=dele(head,number); break; } case 7:printf("The Linklist length is :%5d\n", length(head)); break; default:printf("input is error,input again\n"); break; } } }- 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
- 头文件：clnklist.h
#pragma once #ifndef __CLNKLIST_H #define __CLNKLIST_H #include#include typedef int datatype; typedef struct clnkllist { datatype info; struct clnklist* next; }node; //初始化一个空的循环链表 node* init(); //获得循环单链表的最后一个结点的存储地址 node* rear(node* head); //打印输出循环链表中各个结点的值 void display(node* head); //按序号查找，返回指向结点i的指针 node* findth(node* head, int i); //按值查找，返回x结点的位置 int find(node* head, datatype x); //插入一个新结点，返回头指针 node* insert(node* head, datatype x, int i); //在循环链表中删除一个值为x的结点 node* dele(node* head, datatype x); //查询链表的长度 int length(node* head); #endif - 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
- 函数定义：clnklist.c
#include"clnklist.h" /* *建立一个空的循环链表 */ node* init() { return NULL; //创建成功返回null } /* * 获得循环单链表的最后一个结点的存储地址 */ node* rear(node *head) { node* p; if (!head) { p = NULL; } else { p = head; while (p->next!=head) { p = p->next; } } return p; //返回指向尾结点的指针 } /* * 输出带头结点的单链表中各个结点的值 */ void display(node* head) { node* p; p = head; if (!p) { printf("circular single linked list is null\n"); } else { printf("从头到尾，循环链表中各个值为\n"); while (p!=rear(head)) //循环输出p的下一个结点是头结点 { printf("%5d",p->info); p = p->next; } printf("%5d", p->info); printf("\n"); } } //按序号查找，在带头结点的单链表中查找第i个结点 node* findth(node* head, int i) { node* p; p = head; int sum = 0; if (!p||i<0) { printf("circular single linked list is null or input is <0\n"); exit(1); } else { while (p->next != head&&sum<i) //循环输出p的下一个结点是头结点 { printf("%5d", p->info); p = p->next; sum++; } printf("查找到了%d个结点\n",i); } return p; } //按值查找，返回x所对应结点的位置 int find(node* head,datatype x) { node* p = head; //p指向头结点 int sum = 0; if (!p ) { printf("circular single linked list is null \n"); return NULL; } else { while (p->next != head && p->info!= x) //没有找到并且没有查找完整个表 { p = p->next; sum++; } if (p->info==x) { printf("查找到了值为%d个结点\n", x); return sum; //如果找到返回位置对应的序号 } return 0; //如果没有找到返回0 } } /* 功能：指定链表位置pos插入一个值为x的结点 返回：链表头结点的指针 */ node* insert(node* head, datatype x, int i) { node* p, * q, * myrear; p = (node*)malloc(sizeof(node)); //为要插入的结点开辟一个结点空间 p->info = x; if (i<0) { printf("插入的位置不能小于0，请重新输入\n"); free(p); return head; } if (i==0&&!head) //如果插入的位置是空链表的第一个结点,则新结点的指针域应指向它自己 { p->next = p; head = p; printf("%5d插入成功\n",x); return head; } if (i==0&&head)//如果在非空的链表最前面插入 { myrear = rear(head); //找到喜欢链表的最后一个结点 p->next = head; myrear->next = p; //head->next = p; printf("%5d插入成功\n", x); return head; } if (i>0&&!head) { printf("无法找到要插入的位置\n"); free(p); return head; } if (i>0&&head) //在非空的循环链表中位置i插入值为x { q = head; int j = 1; while (i!=j&&q->next!=head) { q = q->next; j++; } if (i==j) //找到对应的位置i，进行插入操作 { p->next = q->next; q->next = p; printf("%5d插入成功\n", x); return head; } else { printf("表中不存在第%d个结点，无法进行插入\n"); return head; } } } /* 在循环链表中删除一个值为x的结点 返回指向头结点的指针 */ node* dele(node* head, datatype x) { node* pre = NULL, * q;//q用来指向要删除值为x的结点，pre是要删除结点的前驱。 if (!head) { printf("循环单链表为空，无法进行删除操作\n"); return head; } q = head; while (q->next!=head&&q->info!=x) { pre = q; q = q->next; } if (q->info==x) //找到要删除的结点 { if (q != head) { pre->next = q->next; free(q); } else if (q->next==head) { free(q); head = NULL; } else { //要删除的是第一个结点 pre = head->next; while (pre->next!=q) { pre = pre->next; //找到q的前驱结点的位置 } head = head->next; pre->next = head; free(q); } } return head; } //查询链表的长度 int length(node* head) { node* p; p = head; int num = 0; if (!p) { printf("该链表为空\n"); } while (p->next!=head) { num++; p = p->next; } return num; }- 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
- 运行结果
-
相关阅读:
Gusfield算法学习
C++异常
JVM的运行时数据区
FOC学习笔记-坐标变换以及仿真验证
【无标题】
贝叶斯理论框架综述
【老狗 - Java 输入输出 (赛码网)】
读书笔记：《你拿什么定义自己》
二分查找，查找第一个大于目标元素target所对应的下标-2300. 咒语和药水的成功对数
查询或解析solidity智能合约事件event或logs日志
- 原文地址：https://blog.csdn.net/qq_45986997/article/details/126055337
