初识循环链表
在学习过单链表以及进阶的双链表之后就需要进一步学习循环链表了，顾名思义，这种链表头尾相接，形成一个环（即尾节点的后继指针指向第一个节点），其他的单链表的差别不大，但循环链表从表中任意一个节点出发，都可以访问其他的所有节点，无论前后，这也是单链表不具备的优势，循环链表也有很多种，单循环链表 ，双循环链表和多种循环链表，这里我们只研究单循环链表。下图就是单循环链的一种。
图中可以看出循环链表没有NULL指针，所以终止条件也随之改变，下面我们进入正文：
循环链表头结点和数据节点的定义
这里我们还是选择定义头结构体和数据节点结构体制作链表，循环链表的定义还是和单链表一样，这里就不多说了，直接奉上代码：
typedef struct header//头结点结构体 { int length;//保存循环链表的信息 struct node* next;//指向第一个数据节点 }head; typedef struct node//数据节点结构体 { int val;//数据域 struct node* next;//指针域 }node;
这样头结点和数据节点的结构体就定义好啦，我们需要用的时候直接引用就可以啦，接下来就让我们创建一个单循环链表
循环链表的创建
头结点加数据节点形式的链表创建大同小异都是创建一个头结点并分配空间，后面要用数据节点的时候再分配内存给数据节点就可以了，所以链表的创建也相对简单，代码如下：
head* listcreat() { head* p;//定义头结点 p=(head*)malloc(sizeof(head)); p->next=NULL;//此时没有数据节点，所以头结点指向NULL p->length=0;//初始化头结点 return p;//返回创建好的头节点地址 }
一个初始的头节点就创建好了，用一个图展示链表现在的情况就是下面这样啦
循环链表数据节点的插入
循环链表的数据节点插入其实并不复杂，主要是头插和尾插相对于单链表难一点，建议学的时候可以那一个本子画个草图（巨好用），其他位置的插入和单链表的操作一样，直接附上代码：
void listinsert(head* p,int pos,int x)//头结点，要插入的位置，要插入的元素 { if(p==NULL||pos<0||pos>p->length)//健壮性判断 { printf("listinsert():error\n"); return; } node* temp=(node*)malloc(sizeof(node));为要插入的数据temp分配空间 temp->val=x;//填充数据域 node* pcur=p->next;//定义一个指向第一个数据节点的指针 node* plast=p->next;//指向第一个节点方便遍历 while(pcur!=NULL&&plast->next!=pcur)//使plast指向最后一个节点 { plast=plast->next; } if(p->length==0)//判断循环链表为空的情况 { p->next=temp; temp->next=temp; } else if(pos==0)//头插 { plast->next=temp; temp->next=pcur; p->next=temp; } else if(pos==p->length)//尾插 { plast->next=temp; temp->next=pcur; } else { node* pval=p->next;//pval用来指向要插入位置的数据节点 for(int i=1;i<pos;i++) { pval=pval->next; } temp->next=pval->next; pval->next=temp; } p->length++;//记录循环链表的变化 return; }
数据节点的插入函数就封装成功啦，最后就是循环链表中数据节点的删除了。
循环链表数据节点的删除
在搞清楚循环链表的特点以及同单链表的差别之后，数据节点的删除问题也游刃而解了，但注意循环链表中的数据节点删除和双链表一样都需要把头插，尾插单独拎出来分析，而且表中只有一个数据节点时也需要另外分析，具体代码如下：
void listdelete(head* p,int x)//头结点，要删除的元素 { node* temp;//temp待会指向要删除的节点 temp=p->next; for(int i=0;i<p->length;i++)//遍历链表寻找要删除的数据节点 { if(temp->val==x) { break; } temp=temp->next; } if(temp->val!=x)//没找到对应的数据节点 { printf("listdelete():error\n"); return; } node* pcur=p->next;//pcur指向第一个节点 node* plast=p->next;//plast用来指向最后一个节点 while(plast->next!=pcur)//使plast移向最后一个节点 { plast=plast->next; } if(p->length==1)//循环链表中只有一个数据节点时 { p->next=NULL; } else if(temp==pcur)//删除的是第一个节点时 { p->next=pcur->next; plast->next=pcur->next; } else if(temp==plast)//删除的是最后一个节点时 { node* pre=p->next;//定义一个指针，待会指向倒数第二个节点 while(pre->next!=plast) { pre=pre->next; } pre->next=pcur; } else { node* pre=p->next; while(pre->next!=temp)//使pre指向temp的前一个元素（注意，这里的pre不是上面的pre） { pre=pre->next; } pre->next=temp->next; } p->length--;//记录循环链表的变化 }
循环链表的遍历打印
为了方便实际操作，也可以将循环链表的打印输出封装成一个函数，如下：
void listprint(head* p)//头结点 { if(p==NULL||p->length==0)//健壮性判断 { printf("listprint():error"); return; } node* temp=p->next; for(int i=0;i<p->length;i++)//注意此时遍历的结束条件 { printf("%d ",temp->val); temp=temp->next; } printf("\n"); return; }
在单循环链表打印输出时值得注意的是遍历时的结束条件，因为循环链表不再有NULL指针，所以结束条件也发生了变化，这时候头结点中记录的链表大小就起到了作用。
完整代码
循环链表的操作远不止这些，这里就不一一写出来了，但我认为将这几个操作弄明白之后其他的操作都会变得更加简单，将这几个函数综合使用的完整代码如下，可以根据需要取舍：
#include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct header { int length; struct node* next; }head; typedef struct node { int val; struct node* next; }node; head* listcreat() { head* p; p=(head*)malloc(sizeof(head)); p->next=NULL; p->length=0; return p; } void listinsert(head* p,int pos,int x) { if(p==NULL||pos<0||pos>p->length) { printf("listinsert():error\n"); return; } node* temp=(node*)malloc(sizeof(node)); temp->val=x; node* pcur=p->next;//指向第一个数据节点 node* plast=p->next;//指向最后一个数据节点 while(pcur!=NULL&&plast->next!=pcur)//使plast指向最后一个节点 { plast=plast->next; } if(p->length==0)//判断循环链表为空的情况 { p->next=temp; temp->next=temp; } else if(pos==0)//头插 { plast->next=temp; temp->next=pcur; p->next=temp; } else if(pos==p->length)//尾插 { plast->next=temp; temp->next=pcur; } else { node* pval=p->next;//pval用来指向要插入位置的数据节点 for(int i=1;i<pos;i++) { pval=pval->next; } temp->next=pval->next; pval->next=temp; } p->length++; return; } void listdelete(head* p,int x) { node* temp;//temp指向要删除的节点 temp=p->next; for(int i=0;i<p->length;i++) { if(temp->val==x) { break; } temp=temp->next; } if(temp->val!=x) { printf("listdelete():error\n"); return; } node* pcur=p->next;//pcur指向第一个节点 node* plast=p->next;//plast用来指向最后一个节点 while(plast->next!=pcur) { plast=plast->next; } if(p->length==1)//只有一个元素时 { p->next=NULL; } else if(temp==pcur)//删除的是第一个节点 { p->next=pcur->next; plast->next=pcur->next; } else if(temp==plast)//删除的是最后一个节点 { node* pre=p->next;//指向倒数第二个节点 while(pre->next!=plast) { pre=pre->next; } pre->next=pcur; } else { node* pre=p->next; while(pre->next!=temp)//使pre指向temp的前一个元素 { pre=pre->next; } pre->next=temp->next; } p->length--; } void listprint(head* p) { if(p==NULL||p->length==0) { printf("listprint():error"); return; } node* temp=p->next; for(int i=0;i<p->length;i++) { printf("%d ",temp->val); temp=temp->next; } printf("\n"); return; } int main() { head* p; p=listcreat(); int number; printf("请输入循环链表的初始数据节点个数\n"); scanf("%d",&number); int a[number]; printf("请依次填充数据节点\n"); for(int i=0;i<number;i++) { scanf("%d",&a[i]); } for(int i=number-1;i>=0;i--) { listinsert(p,0,a[i]); } printf("输出初始链表\n"); listprint(p); printf("请输入插入的位置和元素\n"); int m,n; scanf("%d%d",&m,&n); listinsert(p,m,n); printf("输出插入后的链表\n"); listprint(p); printf("请输入要删除的元素\n"); int del; scanf("%d",&del); listdelete(p,del); printf("输出删除后的链表\n"); listprint(p); }
随便写点数据运行一下就是下面这个效果啦，刚学习c语言半年，有不完善的地方还请见谅，感谢阅读。
请输入循环链表的初始数据节点个数
6
请依次填充数据节点
1 2 3 4 5 6
输出初始链表
1 2 3 4 5 6
请输入插入的位置和元素
6 7
输出插入后的链表
1 2 3 4 5 6 7
请输入要删除的元素
5
输出删除后的链表
1 2 3 4 6 7
