循环单链表（C语言版）

2023-08-28 07:16| 来源: 网络整理| 查看: 265

前言

小可爱们，本次一起来看看循环单链表吧，嘻嘻！

一、循环单链表的定义

循环单链表是单链表的另一种形式，其结构特点链表中最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环。和单链表相同，循环链表也有带头结点结构和不带头结点结构两种，带头结点的循环单链表实现插入和删除操作较为方便。

二、循环单链表的结构

1、结构图在这里插入图片描述

2、代码表示

#define ElemType int typedef struct Node { ElemType data; //数据域 struct Node *next; //指针域 }Node, *PNode; //循环链表管理结点 typedef struct List { PNode first; //指向头结点 PNode last; //指向尾结点 int size; }List; 三、循环单链表的常用操作

1、初始化

//初始化循环单链表 void InitSCList(List *list) { //申请头结点 Node *s = (Node *)malloc(sizeof(Node)); assert(s != NULL); //将链表管理结点中的头指针和尾指针分别指向这个结点 list->first = list->last = s; //将尾结点的下一个结点指向头结点形成循环 list->last->next = list->first; //此时存有数据的结点个数为0 list->size = 0; }

2、获取结点

//获取结点 x为存入结点内的数据 Node* _buynode(ElemType x) { //申请结点 Node *s = (Node *)malloc(sizeof(Node)); assert(s != NULL); //存放数据 s->data = x; s->next = NULL; return s; }

3、尾插

//尾插 void push_back(List *list, ElemType x) { Node *s = _buynode(x);//获取一个结点 list->last->next = s;//将该结点插入 list->last = s;//更改管理结点中尾结点的指向 list->last->next = list->first;//重新形成环状 list->size++;//将有效结点数加一 }

4、头插

//头插 void push_front(List *list, ElemType x) { Node *s = _buynode(x);//获取结点 //将结点插入 s->next = list->first->next; list->first->next = s; //如果这是一个有效结点，那么需要更改管理结点中尾指针的指向 if(list->first == list->last) { list->last = s; } list->size++;//有效结点数加一 }

5、数据显示

//查看链表内的所有数据 void show_list(List *list) { Node *p = list->first->next;//指向有效结点部分 while(p != list->first)//将有效结点内的数据输出 { printf("%d-->",p->data); p = p->next;//下移 } printf("Nul.\n"); }

6、尾删

//尾删 void pop_back(List *list) { //如果没有可删除的有效结点则退出 if(list->size == 0) return; //查找要删除结点的上一结点 Node *p = list->first; while(p->next != list->last) { p = p->next; } //删除尾结点 free(list->last); //将之前查找到的结点(倒数第二个结点)设置为新的尾结点 list->last = p; list->last->next = list->first;//重新形成环 list->size--;//有效结点数减一 }

7、头删

//头删 void pop_front(List *list) { //如果没有有效结点可删除则退出 if(list->size == 0) return; //删除有效头结点 Node *p = list->first->next; list->first->next = p->next; free(p); //如果此时链表内只有一个有效结点，那么需要改变尾指针的指向 if(list->size == 1) { list->last = list->first; } list->size--;//将有效结点数减一 }

8、按值插入(按照升序插入)

//按值插入(按照升序插入) void insert_val(List *list, ElemType x) { //寻找结点的插入位置 Node *p = list->first; while(p->next!=list->last && p->next->data push_back(list,x);//尾插 } else { //中间插入 Node *s = _buynode(x); s->next = p->next; p->next = s; list->size++; } }

9、按值查找

//查找 Node* find(List *list, ElemType key) { //如果没有有效数据结点则无需查找 if(list->size == 0) return NULL; //从有效结点的首位置进行查找 Node *p = list->first->next; while(p != list->first && p->data!=key) p = p->next; //如果没有找到，返回空 if(p == list->first) return NULL; //如果找到，返回结点地址 return p; }

10、求有效结点个数

//求链表有效结点个数 int length(List *list) { return list->size; }

11、按值删除

//按值删除 void delete_val(List *list, ElemType key) { //如果不存在有效结点，那么无需进行删除 if(list->size == 0) return; //查找要删除结点的位置 Node *p = find(list,key); //如果没有查找到则无需删除 if(p == NULL) { printf("要删除的数据不存.\n"); return; } //如果要删除结点是尾结点，那么可进行尾删 if(p == list->last) { pop_back(list); } else //如果在中间位置，那么把要删除结点的下一结点拷贝到当前要删除结点，然后删除下一结点 { Node *q = p->next; //把要删除结点的下一结点拷贝到当前要删除结点 p->data = q->data; p->next = q->next; //删除下一结点 free(q); list->size--;//有效结点数减一 } }

12、按升序排序

//升序排列 void sort(List *list) { //判断是否要进行排序（有效结点数小于等于1个不进行排序） if(list->size==0 || list->size==1) return; Node *s = list->first->next;//指向第一个有效结点 Node *q = s->next;//指向第二个有效结点 //将原来的循环链表断开，形成一个只含一个有效结点的循环链表和一个单链表 list->last->next = NULL;//单链表的尾结点指向空 list->last = s; list->last->next = list->first; while(q != NULL) //将单链表内的有效结点逐一按照值插入方式（升序的值插入）插入到循环链表中 { //从单链表中拿下一个有效结点 s = q; q = q->next; //查找插入的位置 Node *p = list->first; while(p->next!=list->last && p->next->data data) { p = p->next; } //如果插入位置在尾部，那么进行尾插，否则在中间插入 if(p->next == list->last && p->next->data data) { s->next = list->last->next; list->last->next = s; list->last = s; } else { //中间插入 s->next = p->next; p->next = s; } } }

13、逆置

//逆置 void resver(List *list) { //判断是否要进行逆置（有效结点数小于等于1个不进行逆置） if(list->size==0 || list->size==1) return; Node *p = list->first->next;//指向第一个有效结点 Node *q = p->next;//指向第二个有效结点 //将原来的循环链表断开，形成一个只含一个有效结点的循环链表和一个单链表 list->last->next = NULL;//单链表的尾结点指向空 list->last = p; list->last->next = list->first; while(q != NULL)//将单链表内的有效结点逐一头插到循环链表中 { //从单链表中拿下一个有效结点 p = q; q = q->next; //头插 p->next = list->first->next; list->first->next = p; } }

14、清空循环单链表

//清除有效结点 void clear(List *list) { Node *p = list->first->next;//指向第一个有效结点 while(p != list->first)//将所有有效结点释放清除 { list->first->next = p->next; free(p); p = list->first->next; } //设置管理结点中的尾结点指向和头结点的指针域指向 list->last = list->first; list->last->next = list->first; list->size = 0;//有效结点数为0 }

15、销毁循环单链表

//销毁循环链表 void destroy(List *list) { clear(list);//先清除所有有效结点 free(list->first);//清除头结点 list->first = list->last = NULL; } 总结

循环单链表是一种链式存储结构，它是由单链表改进而来的。把单链表改为循环单链表的过程是将它的尾结点next指针域由原来为空改为指向头结点，整个单链表形成一个环。由此，从表中任一个结点出发均可以找到链表中的其他结点。

附录

以下提供源码测试

Main.cpp

#include"SCList.h" void main() { List mylist; InitSCList(&mylist); ElemType Item; Node *p = NULL; int select = 1; while(select) { printf("**************************************\n"); printf("* [1] push_back [2] push_front *\n"); printf("* [3] show_list [4] pop_back *\n"); printf("* [5] pop_front [6] insert_val *\n"); printf("* [7] find [8] length *\n"); printf("* [9] delete_val [10] sort *\n"); printf("* [11] resver [12] clear *\n"); printf("* [13*] destroy [0] quit_system*\n"); printf("**************************************\n"); printf("请选择:>"); scanf("%d",&select); if(select == 0) break; switch(select) { case 1: printf("请输入要插入的数据(-1结束):>"); while(scanf("%d",&Item),Item != -1) { push_back(&mylist,Item); } break; case 2: printf("请输入要插入的数据(-1结束):>"); while(scanf("%d",&Item),Item != -1) { push_front(&mylist,Item); } break; case 3: show_list(&mylist); break; case 4: pop_back(&mylist); break; case 5: pop_front(&mylist); break; case 6: printf("请输入要插入的数据:>"); scanf("%d",&Item); insert_val(&mylist,Item); break; case 7: printf("请输入要查找的数据:>"); scanf("%d",&Item); p = find(&mylist,Item); if(p == NULL) { printf("要查找的数据在链表中不存在.\n"); } break; case 8: printf("单链表的长度为:> %d \n",length(&mylist)); break; case 9: printf("请输入要删除的值:>"); scanf("%d",&Item); delete_val(&mylist,Item); break; case 10: sort(&mylist); break; case 11: resver(&mylist); break; case 12: clear(&mylist); break; //case 13: // destroy(&mylist); // break; default: printf("输入的命令错误,请重新输入.\n"); break; } } destroy(&mylist); }

SCList.h

#ifndef __SCLIST_H__ #define __SCLIST_H__ #include #include #include #define ElemType int typedef struct Node { ElemType data; //数据域 struct Node *next; //指针域 }Node, *PNode; //循环链表管理结点 typedef struct List { PNode first; //指向头结点 PNode last; //指向尾结点 int size; }List; Node* _buynode(ElemType x); void InitSCList(List *list); void push_back(List *list, ElemType x); void push_front(List *list, ElemType x); void show_list(List *list); void pop_back(List *list); void pop_front(List *list); void insert_val(List *list, ElemType x); Node* find(List *list, ElemType key); int length(List *list); void delete_val(List *list, ElemType key); void sort(List *list); void resver(List *list); void clear(List *list); void destroy(List *list); #endif //__SCLIST_H__

SCList.cpp

#include"SCList.h" //获取结点 x为存入结点内的数据 Node* _buynode(ElemType x) { //申请结点 Node *s = (Node *)malloc(sizeof(Node)); assert(s != NULL); //存放数据 s->data = x; s->next = NULL; return s; } //初始化循环单链表 void InitSCList(List *list) { //申请头结点 Node *s = (Node *)malloc(sizeof(Node)); assert(s != NULL); //将链表管理结点中的头指针和尾指针分别指向这个结点 list->first = list->last = s; //将尾结点的下一个结点指向头结点形成循环 list->last->next = list->first; //此时存有数据的结点个数为0 list->size = 0; } //尾插 void push_back(List *list, ElemType x) { Node *s = _buynode(x);//获取一个结点 list->last->next = s;//将该结点插入 list->last = s;//更改管理结点中尾结点的指向 list->last->next = list->first;//重新形成环状 list->size++;//将有效结点数加一 } //头插 void push_front(List *list, ElemType x) { Node *s = _buynode(x);//获取结点 //将结点插入 s->next = list->first->next; list->first->next = s; //如果这是一个有效结点，那么需要更改管理结点中尾指针的指向 if(list->first == list->last) { list->last = s; } list->size++;//有效结点数加一 } //查看链表内的所有数据 void show_list(List *list) { Node *p = list->first->next;//指向有效结点部分 while(p != list->first)//将有效结点内的数据输出 { printf("%d-->",p->data); p = p->next;//下移 } printf("Nul.\n"); } //尾删 void pop_back(List *list) { //如果没有可删除的有效结点则退出 if(list->size == 0) return; //查找要删除结点的上一结点 Node *p = list->first; while(p->next != list->last) { p = p->next; } //删除尾结点 free(list->last); //将之前查找到的结点(倒数第二个结点)设置为新的尾结点 list->last = p; list->last->next = list->first;//重新形成环 list->size--;//有效结点数减一 } //头删 void pop_front(List *list) { //如果没有有效结点可删除则退出 if(list->size == 0) return; //删除有效头结点 Node *p = list->first->next; list->first->next = p->next; free(p); //如果此时链表内只有一个有效结点，那么需要改变尾指针的指向 if(list->size == 1) { list->last = list->first; } list->size--;//将有效结点数减一 } //按值插入(按照升序插入) void insert_val(List *list, ElemType x) { //寻找结点的插入位置 Node *p = list->first; while(p->next!=list->last && p->next->data push_back(list,x);//尾插 } else { //中间插入 Node *s = _buynode(x); s->next = p->next; p->next = s; list->size++; } } //查找 Node* find(List *list, ElemType key) { //如果没有有效数据结点则无需查找 if(list->size == 0) return NULL; //从有效结点的首位置进行查找 Node *p = list->first->next; while(p != list->first && p->data!=key) p = p->next; //如果没有找到，返回空 if(p == list->first) return NULL; //如果找到，返回结点地址 return p; } //求链表有效结点个数 int length(List *list) { return list->size; } //按值删除 void delete_val(List *list, ElemType key) { //如果不存在有效结点，那么无需进行删除 if(list->size == 0) return; //查找要删除结点的位置 Node *p = find(list,key); //如果没有查找到则无需删除 if(p == NULL) { printf("要删除的数据不存.\n"); return; } //如果要删除结点是尾结点，那么可进行尾删 if(p == list->last) { pop_back(list); } else //如果在中间位置，那么把要删除结点的下一结点拷贝到当前要删除结点，然后删除下一结点 { Node *q = p->next; //把要删除结点的下一结点拷贝到当前要删除结点 p->data = q->data; p->next = q->next; //删除下一结点 free(q); list->size--;//有效结点数减一 } } //升序排列 void sort(List *list) { //判断是否要进行排序（有效结点数小于等于1个不进行排序） if(list->size==0 || list->size==1) return; Node *s = list->first->next;//指向第一个有效结点 Node *q = s->next;//指向第二个有效结点 //将原来的循环链表断开，形成一个只含一个有效结点的循环链表和一个单链表 list->last->next = NULL;//单链表的尾结点指向空 list->last = s; list->last->next = list->first; while(q != NULL) //将单链表内的有效结点逐一按照值插入方式（升序的值插入）插入到循环链表中 { //从单链表中拿下一个有效结点 s = q; q = q->next; //查找插入的位置 Node *p = list->first; while(p->next!=list->last && p->next->data data) { p = p->next; } //如果插入位置在尾部，那么进行尾插，否则在中间插入 if(p->next == list->last && p->next->data data) { s->next = list->last->next; list->last->next = s; list->last = s; } else { //中间插入 s->next = p->next; p->next = s; } } } //逆置 void resver(List *list) { //判断是否要进行逆置（有效结点数小于等于1个不进行逆置） if(list->size==0 || list->size==1) return; Node *p = list->first->next;//指向第一个有效结点 Node *q = p->next;//指向第二个有效结点 //将原来的循环链表断开，形成一个只含一个有效结点的循环链表和一个单链表 list->last->next = NULL;//单链表的尾结点指向空 list->last = p; list->last->next = list->first; while(q != NULL)//将单链表内的有效结点逐一头插到循环链表中 { //从单链表中拿下一个有效结点 p = q; q = q->next; //头插 p->next = list->first->next; list->first->next = p; } } //清除有效结点 void clear(List *list) { Node *p = list->first->next;//指向第一个有效结点 while(p != list->first)//将所有有效结点释放清除 { list->first->next = p->next; free(p); p = list->first->next; } //设置管理结点中的尾结点指向和头结点的指针域指向 list->last = list->first; list->last->next = list->first; list->size = 0;//有效结点数为0 } //销毁循环链表 void destroy(List *list) { clear(list);//先清除所有有效结点 free(list->first);//清除头结点 list->first = list->last = NULL; }

【本文地址】

公司简介

联系我们