热门标签
热门文章
- 1elasticsearch搜索引擎
- 2MyBatis-Plus——实现乐观锁_mybatis-plus 乐观锁
- 3部署LCM（Latent Consistency Models）实现快速出图_simianluo/lcm_dreamshaper_v7
- 4富格林：明确暗箱操作保障安全
- 5Angular 图片、条件判断（*ngIf、[ngSwitch]、属性[ngClass]、[ngStyle]）
- 6Redis可视化工具下载及其安装_redisinsight下载
- 7windows 远程桌面优化及常见问题_windows 远程桌面优化设置
- 8自动化测试面试题及答案大全（上）
- 9HiveServer2与Beeline 报错，就此记录_authorizationexception: user 'mpp2' does not have
- 10买车了
当前位置: article > 正文
数据结构和算法（二）单向循环链表的创建插入删除实现_实现递增有序的单循环链表的插入和删除操作;
作者：我家自动化 | 2024-04-18 05:20:22
赞
踩
实现递增有序的单循环链表的插入和删除操作;
上一篇博客“线性表” 详细讲解了顺序表和单链表的基本操作。本篇博客主要讲解对于循环链表的基本操作。
1. 线性表概要
我们先来总的看一下线性表主要有哪些操作，如下图：
红框里面的内容是本篇博客主要讲解的内容，后面的博客会继续讲解双向链表，循环双向链表等。
先回顾一下单链表
链表是一种线性表, 也是一种存储数据的数据结构.如下图：这种的一个节点中包含自身数据以及指向下一个节点的位置,一个嵌套着下一个. 这中结构就称之为链表.
2. 单向循环链表
本篇博客demo点击这里下载：单向循环链表demo
单向循环链表结点的定义跟单链表一样，区别就是尾结点执行头结点，形成一个环。 如下图（1）表示一个单向循环链表，由尾结点指向头结点：
我们再来回顾一下单向链表的结构图：如下图：图2
我们对比看，可以明显的看出，单向循环链表和单向链表的区别，仅仅是多了一个尾结点指针指向头结点的过程，他们的结点定义是一样的。
- 单向循环链表结点定义如下：
typedef int KStatus;
typedef int KElementType;
typedef struct KNode {
KElementType data;//用来存储一个int数据(具体数据类型根据开发实际情况而定,此处使用int)
struct KNode *next;//指向下一个节点的指针
} Node;
typedef struct KNode * LinkList;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
2.1 建表
单向循环链表的建表过程跟单链表非常相似。我们一般都采用尾部插入法，这样比较符合我们的业务逻辑，尾部插入法的得到的数据和我们定义的顺序是一样的，如果采用头部插入法，则得到的是一个逆序的表。
如我们初始化链表时，只是有一个头结点，它的next指针指向它自己，如下图3是一个空链表：
我们采用尾部插入法，分别插入数据9，16，18，20 就得到了下面的链表，如图4：
我们插入建表的过程如下：
分为两种情况：① 第一次开始创建; ②已经创建,往里面新增数据
判断是否第一次创建链表：
YES->创建一个新结点,并使得新结点的next 指向自身; (*L)->next = (*L);
NO-> 找链表尾结点,将尾结点的next = 新结点. 新结点的next = (*L);
我们细分一下过程如下：
- 我们先初始化得到一个空链表如下：
- 插入1个结点后如下：
3. 插入2个结点后如下：
代码实现如下：
- 方式1：
//1. 创建循环链表 //2种情况:① 第一次开始创建; ②已经创建,往里面新增数据 /* 1. 判断是否第一次创建链表 YES->创建一个新结点,并使得新结点的next 指向自身; (*L)->next = (*L); NO-> 找链表尾结点,将尾结点的next = 新结点. 新结点的next = (*L); */ KStatus createCircleList(LinkList *L) { int item; LinkList temp = NULL; LinkList target = NULL; printf("输入节点的值，输入0结束\n"); while (1) { scanf("%d",&item); if(item == 0) break; //判断，如果输入的链表是空，则创建一个新结点，并且使其next指针指向自己 (*head)->next=*head; if(NULL == *L) { *L = (LinkList)malloc(sizeof(Node)); if(!L) return ERROR; (*L)->data = item; (*L)->next = *L; } else { //如果输入的链表不为空，则寻找链表的尾结点，是尾结点的next=新节点。新节点的next指向头节点 for (target = *L; target->next != *L; target = target->next); temp = (LinkList)malloc(sizeof(Node)); if(!temp) return ERROR; //结点赋值，并插入尾部 temp->data = item; //1.新节点指向头节点 temp->next = *L; //2.尾节点指向新节点 target->next = temp; } } return OK; }
- 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
上面的代码我们通过一个for循环来查找到链表的尾部结点，实际上我们初始化链表的时候，可以用一个指针r专门指向尾结点，这样我们就没有必要循环遍历去查找尾结点了，修改后的代码如下：
- 方式2：
KStatus createCircleList2(LinkList *L) { int item; LinkList temp = NULL; //LinkList target = NULL; //增加一个赋值指针，指向尾结点 LinkList r = *L; printf("输入节点的值，输入0结束\n"); while (1) { scanf("%d",&item); if(item == 0) break; //判断，如果输入的链表是空，则创建一个新结点，并且使其next指针指向自己 (*head)->next=*head; if(NULL == *L) { *L = (LinkList)malloc(sizeof(Node)); if(!L) return ERROR; (*L)->data = item; (*L)->next = *L; //记录尾结点 r = *L; } else { //如果输入的链表不为空，则寻找链表的尾结点，是尾结点的next=新节点。新节点的next指向头节点 //for (target = *L; target->next != *L; target = target->next); //这里已经用r指向了尾结点，不需要查找了。 temp = (LinkList)malloc(sizeof(Node)); if(!temp) return ERROR; //结点赋值，并插入尾部 temp->data = item; //1.新节点指向头节点 temp->next = *L; //2.尾节点指向新节点 r->next = temp; //移动r指针，保存r指针一直指向尾结点 r = temp; } } return OK; }
- 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
2.2 遍历
循环链表的遍历很简单，一个do while 语句就做完了，如下遍历代码:
// 2.遍历循环链表 void traverseCircleList(LinkList L) { //判断链表是否为空 if(!L) { printf("链表为空！\n"); return; } LinkList temp; temp = L; do { printf("%6d", temp->data); temp = temp->next; }while (temp != L) ; printf("\n"); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
2.3 插入
单向循环链表的插入也跟单向链表插入相似，只是多了尾部结点指针特殊处理。
单向循环链表的插入又分为两种情况：
- 第一种情况：插入位置在首结点，需要单独特殊处理
- 第二种情况: 其他位置（非首结点）可以统一处理
为了更好的理解，下面我们通过图来区分两种情况的插入。
第一种情况：插入位置在首结点，如下图（图2.3.1）：
根据上图，我们来分析一下第一种情况的插入过程大致如下：
首先我们创建一个新结点，赋值为2，
然后，我们用下面三步完成结点2的插入
1、将新创建的结点 next 指向原来的首元结点。（上图对应标号2，我们用结点X的next指针指向结点A）
2、将尾结点 next 指向新创建的结点。（上图对应标号3，将尾结点C的next指针指向新的头结点X）
3、将L指针指向新创建的结点。（上图对应标号4 ，将L指向新的首结点X）
完成插入后得到：
注意：这里步骤1，2的顺序不能更换，假设我们先指向步骤2，再执行步骤1，那么我们原来的首节点1，就会丢失，找不到了。我们链表插入的最重要的原则就是，保证链表不要丢失结点。断开结点前必须有指针指向即将要断开的结点，这样才能保证不丢失结点。
第二种情况: 其他位置（非首结点），如下图：
如上图表示的第二种情况，在非首节点插入新创建的结点X
如上图所示，我们同样先新建一个结点X，假设我们要插入在B和C之间，那么我们首先需要找到C结点的前一个结点B，然后再用同样的3步完成插入操作。
插入过程：
1、找到插入结点前一个结点(B结点)，（我们用target指针指向B.）
2、将新创建结点X的next 指向插入位置后面的结点(X->next = C)
3、然后再把插入位置前面的结点next 指向新创建的结点（B->next= X）
完成插入后我们得到如下：
插入结点的实现代码如下：
// 3. 循环链表插入元素 // L : 链表指针 // place: 要插入的位置 // data : 要插入的数据 KStatus insertElement(LinkList *L, int place, int data) { LinkList temp, target; int i; //先判断位置是否为首结点，在首结点需要单独处理 if (place == 1) { //1. 创建一个新结点 temp = (LinkList)malloc(sizeof(Node)); //判断内存是否分配成功 if (! temp) return ERROR; //赋值 temp->data = data; //2. 找到链表的最后一个结点，尾结点 for(target = *L; target->next != *L ; target = target->next); //3.找到尾结点，插入到尾结点后面 //3.1 让新结点的next,指向新的头结点 temp->next = *L; //3.2 让尾结点的next指向新的结点，这样新的结点成了新的尾结点。 target->next = temp; //3.3 让头指针指向新的尾结点 *L = temp; } else { //其他位置 //1. 创建一个新结点 temp = (LinkList)malloc(sizeof(Node)); //判断内存是否分配成功 if (! temp) return ERROR; //赋值 temp->data = data; //2. 找到链表的第place - 1 的位置 for(i = 1, target = *L; target->next != *L && i != place - 1 ; target = target->next, i++); //3. 指向插入操作，将新结点插入到place位置 //3.1 新结点的next 指向target原来的next位置 ; temp->next = target->next; //3.2 插入结点的前驱指向新结点 target->next = temp; } return OK; }
- 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
2.4 删除
删除跟插入一样，也是分为两种情况：
- 第一种情况：删除首结点，需要特殊处理。
- 第二种情况：删除其他结点，非首结点，可以统一处理。
对于第一种情况（删除首结点）：
我们来分析一下过程：
如上图，我们要删除首结点A，我们先要找到尾结点C。
然后，将尾结点C的next,指向新的首结点B。（C->next = B）
然后，将L指向新的首结点B。(*L = B)
最后释放A结点的内存。
第二种情况删除非首结点：
我们删除非首结点的话就可以统一处理，如上图，假设我们删除结点X,
那我们先要找到X的上一个结点B。
然后，将X的上一个结点也就是B的next执行 X的下一个结点也就是C。 （B->next = C 或者 B->next = B->next->next）
最后我们释放X结点的内存。
实现代码如下：
// 4. 循环链表删除元素 // 删除第place位置的元素 // L : 链表指针 // place: 要删除的位置 KStatus deleteElement(LinkList *L, int place) { LinkList temp, target; int i; //temp 指向链表首元结点 temp = *L; //如果为空链表，则结束 if (!temp) return ERROR; //判断是否是首节点，如果是首结点需要单独特殊处理 if (place == 1) { //①.如果删除到只剩下首元结点了,则直接将*L置空; if((*L)->next == (*L)) { *L = NULL; return OK; } //②.链表还有很多数据,但是删除的是首结点; // 2.1 先要找到尾结点， for (target = *L; target->next != *L; target = target->next) ; // 2.2 使得尾结点next 指向头结点的下一个结点 target->next = (*L)->next; temp = *L; *L = (*L)->next; // 2.3 新结点做为头结点,则释放原来的头结点 target->next = *L; //释放资源 free(temp); } else { //其他位置，统一处理 //遍历找到第place-1个位置 for (i = 1, target = *L; target->next != *L && i != place - 1; target = target->next, i++) { //找到删除结点前一个结点target //用temp指向要删除的元素，第place位置 temp = target->next; //使得target->next 指向下一个结点 target->next = temp->next; //释放内存 free(temp); } } return OK; }
- 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
2.5 查询
查询非常结点，一个while循环就弄完了，实现代码如下：
//5. 循环列表查询 // 返回位置的索引值 int queryValue(LinkList L , int value) { int i = 1; LinkList p = L; //寻找链表中的结点 data == value while (p->data != value) { i++; p = p->next; } //当尾结点指向头结点就会直接跳出循环,所以要额外增加一次判断尾结点的data == value; if (p->next == L && p->data != value) return -1; //没有找到 //找到了元素，返回下标 return i; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
2.6 单元测试
// 6. 单元测试 void test() { LinkList head; int place,num; int iStatus; iStatus = createCircleList(&head); //iStatus = createCircleList2(&head); printf("原始的链表：\n"); traverseCircleList(head); // printf("输入要插入的位置和数据用空格隔开："); // scanf("%d %d",&place,&num); // iStatus = insertElement(&head,place,num); // traverseCircleList(head); printf("输入要删除的位置："); scanf("%d",&place); deleteElement(&head,place); traverseCircleList(head); printf("输入你想查找的值:"); scanf("%d",&num); place = queryValue(head,num); if(place!=-1) printf("找到的值的位置是place = %d\n",place); else printf("没找到值\n"); }
- 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
2.7 完整代码实现
// // main.c // 004_CircularLinedList // // Created by 孔雨露 on 2020/4/5. // Copyright © 2020 Apple. All rights reserved. // #include <stdio.h> #include "string.h" #include "ctype.h" #include "stdlib.h" #include "math.h" #include "time.h" #define ERROR 0 #define TRUE 1 #define FALSE 0 #define OK 1 #define MAXSIZE 20 /* 存储空间初始分配量 */ typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */ typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */ //定义结点 typedef struct Node{ ElemType data; struct Node *next; }Node; typedef struct Node * LinkList; /* 4.1 循环链表创建! 2种情况:① 第一次开始创建; ②已经创建,往里面新增数据 1. 判断是否第一次创建链表 YES->创建一个新结点,并使得新结点的next 指向自身; (*L)->next = (*L); NO-> 找链表尾结点,将尾结点的next = 新结点. 新结点的next = (*L); */ Status CreateList(LinkList *L){ int item; LinkList temp = NULL; LinkList target = NULL; printf("输入节点的值，输入0结束\n"); while(1) { scanf("%d",&item); if(item==0) break; //如果输入的链表是空。则创建一个新的节点，使其next指针指向自己 (*head)->next=*head; if(*L==NULL) { *L = (LinkList)malloc(sizeof(Node)); if(!L)exit(0); (*L)->data=item; (*L)->next=*L; } else { //输入的链表不是空的，寻找链表的尾节点，使尾节点的next=新节点。新节点的next指向头节点 for (target = *L; target->next != *L; target = target->next); temp=(LinkList)malloc(sizeof(Node)); if(!temp) return ERROR; temp->data=item; temp->next=*L; //新节点指向头节点 target->next=temp;//尾节点指向新节点 } } return OK; } Status CreateList2(LinkList *L){ int item; LinkList temp = NULL; LinkList target = NULL; LinkList r = NULL; printf("请输入新的结点, 当输入0时结束!\n"); while (1) { scanf("%d",&item); if (item == 0) { break; } //第一次创建 if(*L == NULL){ *L = (LinkList)malloc(sizeof(Node)); if(!*L) return ERROR; (*L)->data = item; (*L)->next = *L; r = *L; }else{ temp = (LinkList)malloc(sizeof(Node)); if(!temp) return ERROR; temp->data = item; temp->next = *L; r->next = temp; r = temp; } } return OK; } //4.2 遍历循环链表，循环链表的遍历最好用do while语句，因为头节点就有值 void show(LinkList p) { //如果链表是空 if(p == NULL){ printf("打印的链表为空!\n"); return; }else{ LinkList temp; temp = p; do{ printf("%5d",temp->data); temp = temp->next; }while (temp != p); printf("\n"); } } //4.3 循环链表插入数据 Status ListInsert(LinkList *L, int place, int num){ LinkList temp ,target; int i; if (place == 1) { //如果插入的位置为1,则属于插入首元结点,所以需要特殊处理 //1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR; //2. 找到链表最后的结点_尾结点, //3. 让新结点的next 执行头结点. //4. 尾结点的next 指向新的头结点; //5. 让头指针指向temp(临时的新结点) temp = (LinkList)malloc(sizeof(Node)); if (temp == NULL) { return ERROR; } temp->data = num; for (target = *L; target->next != *L; target = target->next); temp->next = *L; target->next = temp; *L = temp; }else { //如果插入的位置在其他位置; //1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR; //2. 先找到插入的位置,如果超过链表长度,则自动插入队尾; //3. 通过target找到要插入位置的前一个结点, 让target->next = temp; //4. 插入结点的前驱指向新结点,新结点的next 指向target原来的next位置 ; temp = (LinkList)malloc(sizeof(Node)); if (temp == NULL) { return ERROR; } temp->data = num; for ( i = 1,target = *L; target->next != *L && i != place - 1; target = target->next,i++) ; temp->next = target->next; target->next = temp; } return OK; } //4.4 循环链表删除元素 Status LinkListDelete(LinkList *L,int place){ LinkList temp,target; int i; //temp 指向链表首元结点 temp = *L; if(temp == NULL) return ERROR; if (place == 1) { //①.如果删除到只剩下首元结点了,则直接将*L置空; if((*L)->next == (*L)){ (*L) = NULL; return OK; } //②.链表还有很多数据,但是删除的是首结点; //1. 找到尾结点, 使得尾结点next 指向头结点的下一个结点 target->next = (*L)->next; //2. 新结点做为头结点,则释放原来的头结点 for (target = *L; target->next != *L; target = target->next); temp = *L; *L = (*L)->next; target->next = *L; free(temp); }else { //如果删除其他结点--其他结点 //1. 找到删除结点前一个结点target //2. 使得target->next 指向下一个结点 //3. 释放需要删除的结点temp for(i=1,target = *L;target->next != *L && i != place -1;target = target->next,i++) ; temp = target->next; target->next = temp->next; free(temp); } return OK; } //4.5 循环链表查询值 int findValue(LinkList L,int value){ int i = 1; LinkList p; p = L; //寻找链表中的结点 data == value while (p->data != value && p->next != L) { i++; p = p->next; } //当尾结点指向头结点就会直接跳出循环,所以要额外增加一次判断尾结点的data == value; if (p->next == L && p->data != value) { return -1; } return i; } int main(int argc, const char * argv[]) { // insert code here... printf("Hello, World!\n"); LinkList head; int place,num; int iStatus; //iStatus = CreateList(&head); iStatus = CreateList2(&head); printf("原始的链表：\n"); show(head); // printf("输入要插入的位置和数据用空格隔开："); // scanf("%d %d",&place,&num); // iStatus = ListInsert(&head,place,num); // show(head); printf("输入要删除的位置："); scanf("%d",&place); LinkListDelete(&head,place); show(head); printf("输入你想查找的值:"); scanf("%d",&num); place=findValue(head,num); if(place!=-1) printf("找到的值的位置是place = %d\n",place); else printf("没找到值\n"); 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
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
- 276
- 277
- 278
- 279
- 280
- 281
- 282
- 283
- 284
- 285
- 286
- 287
- 288
- 289
- 290
- 291
- 292
输出结果：
Hello, kongyulu! 请输入新的结点, 当输入0时结束! 1 2 3 4 5 6 0 原始的链表： 1 2 3 4 5 6 输入要删除的位置：1 2 3 4 5 6 输入你想查找的值:4 找到的值的位置是place = 3 Program ended with exit code: 0
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/444210
推荐阅读
相关标签
