文章目录
C语言 循环单链表的基本操作与实现
原理
实现
结构体
初始化
创建链表
获取链表长度
根据节点位置删除节点
根据节点的位置插入数据
打印链表
``欢迎大家在评论区赐教,谢谢``

C语言 循环单链表的基本操作与实现
原理
循环链表于单链表的区别在于,表中最后一个节点不是指向NULL,而是改为指向头节点,从而形成一个环如图



再循环单链表中,表尾节点 d 的Next指向L,所以表中没有NULL的节点,因此循环单链表判空条件不是头节点的指针是否为空,而是头节点是否等于头节点.
实现
结构体
typedef struct SqNode
{
	int data;
	struct SqNode* Next;
}SqNode,*Sqlist;

初始化
Sqlist Initlist(Sqlist L)
{
	L = (Sqlist)malloc(sizeof(SqNode));
	if (!L)
		return NULL;
	L->Next = L;
	return L;
}

创建链表
Sqlist CreateList(Sqlist L)
{
	Sqlist s;
	Sqlist r;
	int Value;
	s = L->Next;
	printf("请输入您要创建的链表,输入999结束创建\n");
	scanf_s("%d", &Value);
	getchar();
	while (Value!=999)
	{
		r = (Sqlist)malloc(sizeof(SqNode));
		if (!r)
		{
			printf("内存分配失败,结束创建\n");
			return L;
		}
		r->data = Value;
		r->Next = s->Next;
		s->Next = r;
		s = r;
		scanf_s("%d", &Value);
		getchar();
	}
	return L;
}

获取链表长度
int LengthList(Sqlist L)
{
	Sqlist s;
	s = L->Next;
	int Length = 0;
	while (s != L)
	{
		s = s->Next;
		Length++;
	}
	return Length;
}

根据节点位置删除节点
Sqlist DeleteList(Sqlist L, int Locate)
{
	Sqlist s=L;
	Sqlist q;
	int Length = 0;
	int i = 0;
	Length = LengthList(L);
	if (Locate > Length || Locate < 0)
	{
		printf("你输入的位置超出范围\n");
		return NULL;
	}
	while (i<Locate-1 && s->Next!=L)
	{
		i++;
		s = s->Next;
	}
	q=s->Next;
	s->Next = s->Next->Next;
	return q;
}

根据节点的位置插入数据
Sqlist InsertList(Sqlist L, int Locate) 
{
	Sqlist s;
	Sqlist r;
	int i=0;
	int Value;
	int Length = LengthList(L);
	s = L;
	if (Locate > Length || Locate < 0)
	{
		printf("您输入的位置超出有效范围\n");
		return NULL;
	}
	while (i<Locate-1 &&s->Next!=L)
	{
		s=s->Next;
		i++;
	}
	r = (Sqlist)malloc(sizeof(SqNode));
	if (!r)
	{
		printf("申请空间失败\n");
		return NULL;
	}
	s;
	printf("请输入您需要插入的数据\n");
	scanf_s("%d", &Value);
	getchar();
	r->data = Value;
	r->Next = s->Next;
	s->Next = r;
	return L;
}

打印链表
void PrintfList(Sqlist L)
{
	Sqlist s;
	s = L->Next;
	while (s!=L)
	{
		printf("%d\t", s->data);
		s = s->Next;
	}
	printf("\n");
}

欢迎大家在评论区赐教,谢谢

一、循环链表的定义

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表


二、带头结点的循环链表的判空条件


p->next 不等于头结点


在设计循环单链表时，仅设计指向终端结点的尾指针可以提高效率，此时查找开始结点和终端结点就很方便了，下面以此来实现循环单链表

三、循环单链表的基本操作
1.循环单链表的整表创建
typedef int ElemType;
typedef struct Node
{
	ElemType data;
	struct Node* next;
}Node, * LinkList;

void CreateCycleList(LinkList* rear,int n)
{
	int data;
	LinkList p,head;
	(*rear) = (LinkList)malloc(sizeof(Node)); //创建头结点
	head = (*rear);  //记录下头结点的位置
	(*rear)->next = head; //初始化头结点的后继结点指向自己
	for(int i=0;i<n;i++)
	{
		scanf("%d",&data);  //假设数据域是int类型
		 p = (LinkList)malloc(sizeof(Node)):
		 p->data = data;
		 p->next = head; //新结点的后继结点指向头结点
		 (*rear)->next = p; //尾指针指向结点的后继结点指向新结点
		 (*rear)  = p;//更新尾指针
	}
}

2.循环单链表结点的获取
/*初始条件：表已经存在*/
/*操作结果：返回第i个位置的结点*/
LinkList GetNode(LinkList rear,int i)
{
	if(i==0)
		return rear->next; //i等于0时可以选择返回头结点
	LinkList p,head;
	int j = 1;
	head = rear->next; //记下头结点位置
	p = head->next; //给p赋值为第一个结点
	while(p!=head&&j<i) //当p等于头结点说明已经遍历完整个链表
	{
		 p = p->next;
		 j++;
	}
	if(p==head||j>i)
		return NULL;
	return p;
}

3.循环链表获取表长
/*初始条件：表已经存在*/
/*操作结果：返回表长*/
int GetLength(LinkList rear)
{
	int count = 0;
	LinkList p,head;
	head = rear->next; //记下头结点
	p = head->next; //从第一个结点开始
	while(rear!=head)
	{
	 	P = P->next;
	 	count++;
	}
	return count;
}

4.循环单链表插入
/*初始条件：表已经存在*/
/*操作结果：在第i个结点插入结点*/
Status ListInsert(LinkList* rear,int i,ElemType e)
{
	LinkList p,s;
	p = GetNode((*rear),i-1);
	if(p==NULL)
		return false;.
	s = (LinkList)malloc(sizeof(Node));
	if(i>GetLength(*rear))
		(*rear) = s; //如果i>表长,说明是在表尾插入元素，则尾指针要及时更新
	s = (LinkList)malloc(sizeof(Node));
	if (i > GetLength(*rear))
		(*rear) = s;
	s->data = e;
	s->next = p->next; //p的后继指针赋值给s的后继指针，如果s是插入在表尾的元素，则s的后继指针就指向的了头结点
	p->next = s;  //p的后继指针指向s
	return true;
}

5.循环单链表的删除
/*初始条件：表已经存在*/
/*操作结果：删除第i个位置上的结点，并用e回收删除结点的数据域*/
Status ListDelete(LinkList* rear, int i, ElemType* e)
{
	LinkList p, s;
	p = GetNode((*rear), i - 1);
	if (p == NULL)
		return false;
	if (i == GetLength(*rear))
		(*rear) = p;
	s = p->next;
	p->next = s->next;
	*e = s->data;
	free(s);
	return true;
}

5.循环单链表整表删除
/*初始条件：表已经存在*/
/*操作结果：删除所有数据元素，将表重置为空表*/
void ClearList(LinkList* rear)
{
	LinkList p, q, head;
	head = (*rear)->next; //记下头结点位置
	p = head->next;  //从第一个结点开始
	while (p != head) //当p等于头结点说明已经清空完毕
	{
		q = p;
		p = p->next;
		free(q);
	}
	(*rear) = head; //更新尾指针
	(*rear)->next = head; //尾指针的后继指针指向头结点
}

循环单链表与单链表不同的是最后一个元素不为null，而是指向开头的第一个元素，形成一个环。

若temp=head，且没有头节点。

判满条件：temp.next=head

判空条件：head=null;

添加元素：若为第一个元素，head=newNode;head.next=head;//指向自己 temp=head;

若不是第一个元素：

temp.next=newNode; newNode.next=head; temp=newNode;

约瑟夫问题:简化说法，有K个小孩，编号为1，2，3，…,k,围成一个圈，现在假设让第n个小孩开始从1报数，需要报m次，数到m的那个小孩出列，下一个小孩重新从1开始报数，依次类推，直到所有的人都出列，问最后一个出列的小孩编号是多少?

代码如下：
package LinkedList;

public class Josefu     
{
	public static void main(String[] args) {
		ChildNode c1=new ChildNode(1);
		ChildNode c2=new ChildNode(2);
		ChildNode c3=new ChildNode(3);
		ChildNode c4=new ChildNode(4);
		ChildNode c5=new ChildNode(5);
		ChildNode c6=new ChildNode(6);
		CircleSingleLinkedList clist=new CircleSingleLinkedList();
		clist.add(5);
		clist.print();
		System.out.println("--------------");
		clist.rankNode(5, 1, 2);
	}
}
class CircleSingleLinkedList{
	//num数量 start开始位置 countnum数的数
	ChildNode head=new ChildNode(0);//没有头节点，只有头指针
	ChildNode last;//指向链表的最后一个元素
	//添加元素 辅助变量
	ChildNode cur=head;//遍历指针
	//添加
	public void add(int nums) {
		for(int i=1;i<=nums;i++) {
			ChildNode cnode=new ChildNode(i);
			if(i==1) {
				head=cnode;//第一个节点
				cnode.setNext(head);//指向自己
				cur=head;//保存当前节点
				continue;
			}
			cur.setNext(cnode);//该节点的下一个不再指向开头，指向下一个元素
			cnode.setNext(head);//下一个元素的指向开头
			cur=cnode;//右移
		}
		last=cur;
	}
	//显示
	public void print() {
		ChildNode helper=head;//辅助遍历
		while(true) {//开始等于最后
			System.out.println(helper.getCno());
			if(helper.getNext()==head) {
				break;
			}
			helper=helper.getNext();//不能将其写入在while中，会少一个右移
		}
	}
	
	//出圈顺序 先找到位置，再删掉
	public void rankNode(int nums,int start,int countnum) {
		if(head==null||start<1||start>nums) {
			System.out.println("输入无效");
			return;
		}
		
		// 找到开始位置 走了n-1步
		for (int i = 0; i < start - 1; i++) {
			last = last.getNext();// 右移
			head = head.getNext();
		}
		while(true) {
			if(last==head) {
				break;//走完了
			}
			
			//报数 报n-1步到
			
			for(int i=0;i<countnum-1;i++) {
				last=last.getNext();//指向要出队列的元素
				head=head.getNext();
			}
			
			System.out.println(head.getCno());
			head=head.getNext();//指针右移head=head.next
			last.setNext(head);//相当于last=first.next
		}
		System.out.println("最后出圈的人是"+last.getCno());
	}


}
//孩子节点类
class ChildNode
{
	ChildNode next;
	int cno;
	public ChildNode getNext() {
		return next;
	}
	public void setNext(ChildNode next) {
		this.next = next;
	}
	public int getCno() {
		return cno;
	}
	public void setCno(int cno) {
		this.cno = cno;
	}
	public ChildNode(int cno) {
		this.cno = cno;
	}
	
}

循环单链表


从任何一个结点出发都能访问到链表的每一个元素

判空条件不是头节点的后继指针是否为空，而是它是否等于头指针
有时对单链表常做的操作实在表头和表尾进行的，此时可对循环单链表不设头指针而仅设尾指针，从而使得操作效率更高。

循环双链表


在循环双链表L中，尾结点的后继指针指向表头结点，头节点的前驱指针指向表尾结点
当循环双链表为空表时，其头结点的prior域和next域都等于L

静态链表




静态链表以next=-1作为其结束的标志。

静态链表虽然是数组存储的，但对静态链表的插入、删除操作与动态链表相同，只需要修改指针，而不需要移动元素。
参考资料
王道数据结构