目录
1.循环单链表
特点：表中最后一个节点的指针域指向头结点，整个链表形成一个环。
2.循环单链表相关操作
（1）单链表的定义
#include<stdlib.h>
#include<stdio.h>
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode*next;
}LNode,*LinkList;
//清单列表
void MenuLinkList(){
printf("-------------1.插入操作-------------\n");
printf("-------------2.定位插入操作---------\n");
printf("-------------3.按序查找操作---------\n");
printf("-------------4.按值查找操作---------\n");
printf("-------------5.定位删除操作---------\n");
printf("-------------6.按值删除元素---------\n");
printf("-------------7.删除整个表-----------\n");
printf("-------------8.表的长度-------------\n");
printf("-------------9.打印操作-------------\n");
printf("-------------10.结束操作-------------\n");
}（2）初始化和销毁操作
//初始化不带头节点
void InitList(LinkList&L){
L=(LNode*)malloc(sizeof(LNode));
if(L==NULL){
printf("内存分配失败!\n");
return ;
}
//注意这个地方，不再是指向NULL，而是头结点本身
L->next=L;
printf("空间申请成功!\n");
}
//销毁操作
void DestryList(LinkList&L){
LNode*p=L->next;
while(p->next!=L){
LNode*s=p->next;
p->next=s->next;
free(s);
}
//最后一个节点特殊处理
LNode*s=p->next;
p->next=L->next;
L=p;
free(s);
} 销毁的主要思路是：首选释放前n-1个节点的空间，随后再将最后一个节点做单独的处理：如图
（3）判空，判满和表的长度
//判断链表是否为空
bool Empty(LinkList L){
if(L->next==L){
return true;
}else{
return false;
}
}
//判断节点p是否为尾节点
bool isTail(LinkList L,LNode*p){
if(p->next==L){
return true;
}else{
return false;
}
}
//表的长度
int LinkListLength(LinkList L){
int len=0;
LNode*p=L->next;
while(p->next!=L){
p=p->next;
len++;
}
return len;
} （4）插入操作
//循环链表的插入操作
//这里从后插，并且让L指向尾部，便于插入和删除
void InsertLNode(LinkList&L,ElemType e){
LNode*s=(LNode*)malloc(sizeof(LNode));
s->data=e;
s->next=L->next;
L->next=s;
L=s;
printf("插入节点成功!\n");
}（5）按序插入到第i个位置
//查找第i个节点
LNode*FindILNode(LinkList L,int i){
if(i>LinkListLength(L)){
printf("没有相关的位置可插入!\n");
return NULL;
}
int j=1;
LNode*p=L->next;
//这里使用j<i-1，主要是为了便于后面的插入操作，直接在p节点后面插入节点即可
while(p!=L&&j<i){
p=p->next;
j++;
}
if(p==L){
printf("插入的位置不合法!\n");
return NULL;
}
return p;
}
//在第i个位置插入节点
void InsertILNode(LinkList&L,int i,ElemType e){
LNode*p=FindILNode(L,i);
LNode*s=(LNode*)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
printf("插入节点成功!\n");
}（6）按值查找节点
//按值查找操作
bool FindElem(LinkList L,ElemType&e){
LNode*p=L->next;
while(p->next!=NULL){
if(p->next->data==e){
return true;
}
p=p->next;
}
return false;
}（7）按值删除和按序删除第i个节点
//定位删除节点
void DeleteILNode(LinkList&L,int i,ElemType&e){
LNode*p=FindILNode(L,i);
LNode*s=p->next;
e=s->data;
p->next=s->next;
free(s);
}
//按值删除节点（删除所有值相同的节点
void DeleteElemLNode(LinkList&L,ElemType e){
LNode*p=L->next;
//如果只有一个节点则需要进行特殊的处理
if(LinkListLength(L)==1&&p->next->data==e){
LNode*s=p->next;
p->next=L->next;
L=p;
free(s);
return ;
}
while(p!=L){
LNode*s=p->next;
//如果是尾节点的话需要进行特殊的处理，因为L也是指向尾节点的
if(s==L&&s->data==e){
while(L!=p){
L=L->next;
}
L->next=s->next;
free(s);
return ;
}
if(s->data==e){
p->next=s->next;
free(s);
}else{
p=p->next;
}
}
}（8）打印和主函数
//打印操作
void DisplayList(LinkList L){
LNode*p=L->next;
while(p!=L){
p=p->next;
printf("%d\t",p->data);
}
printf("\n");
}
int main(){
LinkList L;
InitList(L);
//对顺序表进行插入操作
ElemType x;
int flag=-1;
LNode*p=L;
//各种操作
while(1) {
int i=0;
ElemType e=0;
MenuLinkList();
printf("请输入操作: ");
scanf("%d",&flag);
int len=0;
bool exist=false;
LNode*s;
switch(flag){
case 1:
printf("请输入元素(-1_end): ");
scanf("%d",&x);
while(x!=-1) {
InsertLNode(L,x);
printf("请输入元素(-1_end): ");
scanf("%d",&x);
}
break;
case 2:
printf("请输入元素插入位置: \n");
scanf("%d",&i);
printf("请输入元素: ");
scanf("%d",&x);
InsertILNode(L,i,x);
break;
case 3:
printf("请输入查找元素位置: ");
scanf("%d",&i);
s=FindILNode(L,i);
printf("查找的元素为 = %d\n",s->next->data);
break;
case 4:
printf("请输入要查找的值: ");
scanf("%d",&x);
exist=FindElem(L,x);
if(exist){
printf("查找的元素存在!\n");
}else{
printf("查找的元素不存在!\n");
}
break;
case 5:
printf("请输入删除的定位位置: ");
scanf("%d",&i);
DeleteILNode(L,i,e);
printf("删除的元素为 = %d\n",e);
break;
case 6:
printf("请输入要删除的元素: ");
scanf("%d",&e);
DeleteElemLNode(L,e);
printf("删除节点成功!\n");
break;
case 7:
DestryList(L);
printf("删除成功!\n");
break;
case 8:
len=LinkListLength(L);
printf("表的长度 = %d\n",len);
break;
case 9:
DisplayList(L);
break;
default:
DestryList(L);
printf("结束操作\n");
}
if(flag==10){
break;
}
}
return 0;
} （9）测试
