使用C语言实现循环单链表（带头节点）

目录

1.循环单链表

2.循环单链表相关操作

（1）单链表的定义

（2）初始化和销毁操作

（3）判空，判满和表的长度

（4）插入操作

（5）按序插入到第i个位置

（6）按值查找节点

（7）按值删除和按序删除第i个节点

（8）打印和主函数

（9）测试

---

1.循环单链表

 

 特点：表中最后一个节点的指针域指向头结点，整个链表形成一个环。

使用C语言实现带头节点的单链表

使用C语言实现不带头节点的单链表

2.循环单链表相关操作

（1）单链表的定义

#include
#include
 
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
	while(p!=L&&j
		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）测试