数据结构：线性表链式存储结构（循环单链表） C语言版

循环链表( circular linked list)：

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

循环链表的定义：将单链表中最后一个数据元素的next指针指向第一个元素。 循环链表拥有链表的所有操作。

循环链表解决了如何从链表当中一个结点出发，访问到链表的全部结点。
为了使空链表与非空链表处理一直，通常设一个头结点，当然并不是说，循环链表一定要头节点，这需要注意。循环链表带有头结点的空链表如图：

对于非空循环链表如下图：

循环链表与单链表的主要差异就在于循环的主要条件判断上，原来判断 pHeader->next !=NULL 是否为空，现在则判断 pHeader->next !=pHeader 不等于头节点，则循环未结束。
在单链表中，如果设置了头结点，可以用 $O(1)$O(1) 的时间访问第一个结点， 单要访问最后一个结点，却需要 $O(n)$O(n) 的时间，因为需要将链表全部扫描一遍。
但在循环链表中，只要一下链表，不用头指针，而是用指向终端结点的尾指针来表示循环链表，此时查找开始结点和终端结点都是很方便了。如下图：

从上图可以看出，终端结点用尾指针 rear 指示，则查找终端结点是 $O(1)$O(1) 而查找开始结点，其实就是rear->next->next ，其时间复杂度也是 $O(1)$O(1) 。

如果要将两个循环链表合并成一个表时，有了尾指针就非常简单了。如下图：两个循环链表，位指针分别是 rearA , rearB .

想要合并只需如下操作即可：

p=rearA->next; //保存A表的头结点 即 1 步
rearA->next=rearB->next->next; //将本是指向B表的第一个结点（不是头节点） 赋值给 原来A表尾部结点的指针域，相当于A,B 表进行连接 ，即 2 步
rearB->next=p; //将原A表的头结点赋值给 b 表尾部结点的指针域，相当于连接环形 ，即 3 步
free(p); //释放 p

循环单向链表的代码实现：

基于 Linux 内核链表实现。

1 定义头文件，声明数据结构和操作方法。

/************************************************************************
*
*  单向循环链表，基于 LINUX 内核链表数据模型
*
*
*
************************************************************************/
#ifndef _CIRCLE_LIST_H_
#define _CIRCLE_LIST_H_

#define  CIRCLE_LIST_ERROR		(-1)							/*错误  FALSE*/
#define  CIRCLE_LIST_VAILD      (CIRCLE_LIST_ERROR+1)			/*正确  TRUE*/

#define  SCL_ERR_NULL			(CIRCLE_LIST_ERROR+2)			/*Data Or Parameters Is NULL*/
#define  SCL_ERR_POST			(CIRCLE_LIST_ERROR+3)			/*Element Subscripts Are Out Of Range*/




typedef void CircleList;				/*单向循环链表数据抽象模型*/

typedef struct _Tag_Circle_List_Node
{
	struct _Tag_Circle_List_Node* next;
}CTNode;								/*单向循环链表节点数据抽象类型，其他数据结构将其包含，必须位于包含数据结构的第一个变量位置*/
 

/**************************************************************
* 创建链表。
* -------------------------------------------------------------
* 参数		： void
*
* 返回值		： CircleList*    --- 链表指针
			   NULL			--- 空

**************************************************************/
CircleList* CircleList_Create();

/**************************************************************
* 释放销毁链表存储空间。
* -------------------------------------------------------------
* 参数		： CircleList* list  --- 链表指针
*
* 返回值		： void
**************************************************************/
void CircleList_Destroy(CircleList* list);

/**************************************************************
* 清除链表数据。
* -------------------------------------------------------------
* 参数		： CircleList* list  --- 链表指针
*
* 返回值		： void
**************************************************************/
void CircleList_Clear(CircleList* list);

/**************************************************************
* 获取链表数据个数。
* -------------------------------------------------------------
* 参数		： CircleList* list  --- 链表指针
*
* 返回值		： int             --- 链表数据个数
**************************************************************/
int CircleList_Length(CircleList* list);

/**************************************************************
* 向链表指定位置插入数据。
* -------------------------------------------------------------
* 参数		： CircleList* list      --- 链表指针
			   CTNode* node      --- 待插入的元素
               int pos             --- 插入位置下标
*
* 返回值		： int                 --- 1 | 0
**************************************************************/
int CircleList_Insert(CircleList* list, CTNode* node, int pos);

/**************************************************************
* 获取指定位置的元素。
* -------------------------------------------------------------
* 参数		： CircleList* list      --- 链表指针
			   int pos             --- 元素位置下标
*
* 返回值		： CTNode*  | NULL  (元素指针 或 NULL)
**************************************************************/
CTNode* CircleList_Get(CircleList* list, int pos);


/**************************************************************
* 删除定位置的元素。
* -------------------------------------------------------------
* 参数		： CircleList* list      --- 链表指针
			   int pos             --- 元素位置下标
*
* 返回值		： CTNode*  | NULL  (元素指针 或 NULL)
**************************************************************/
CTNode* CircleList_Delete(CircleList* list, int pos);

/**************************************************************
* 删除元素。
* -------------------------------------------------------------
* 参数		： CircleList* list      --- 链表指针
			   CTNode* node          --- 要删除的元素
*
* 返回值		： CTNode*  | NULL  (元素指针 或 NULL)
**************************************************************/
CTNode* CircleList_DeleteNode(CircleList* list, CTNode* node);

/**************************************************************
* 重置链表游标，并返回游标指针的元素。
* -------------------------------------------------------------
* 参数		： CircleList* list      --- 链表指针
*
* 返回值		： CTNode*  | NULL  (元素指针 或 NULL)
**************************************************************/
CTNode* CircleList_Reset(CircleList* list);

/**************************************************************
* 返回当前游标指针的元素。
* -------------------------------------------------------------
* 参数		： CircleList* list      --- 链表指针
*
* 返回值		： CTNode*  | NULL  (元素指针 或 NULL)
**************************************************************/
CTNode* CircleList_Current(CircleList* list);


/**************************************************************
* 返回当前游标指针的元素，并且游标指针下移一位。
* -------------------------------------------------------------
* 参数		： CircleList* list      --- 链表指针
*
* 返回值		： CTNode*  | NULL  (元素指针 或 NULL)
**************************************************************/
CTNode* CircleList_Next(CircleList* list);


#endif // !_CIRCLE_LIST_H_

在循环链表中可以定义一个“当前”指针，这个指针通常称为游标，可以通过这个游标来遍历链表中的所有元素。

2：实现操作方法：

#include "CircleList.h"
#include <stdlib.h>
#include <memory.h>


typedef struct _Tag_Circle_List
{
	CTNode		pHeader;	/*链表头部*/
	CTNode*		silder;		/*链表游标*/
	int			length;		/*链表数据长度*/
}CTList;					/*单向链表内部数据类型*/


//创建单向循环链表
CircleList* CircleList_Create()
{
	CTList*  sList = (CTList*)malloc(sizeof(CTList));
	if (sList == NULL)
	{
		return NULL;
	}
	memset(sList, 0x00, sizeof(CTList));
	sList->length = 0;
	sList->pHeader.next = NULL;
	sList->silder = NULL;

	return sList;
}

//释放链表
void CircleList_Destroy(CircleList* list)
{
	if (list==NULL)
	{
		return;
	}
	free(list);
}

//清除链表
void CircleList_Clear(CircleList* list)
{
	CTList*  listTmp = (CTList*)list;
	if (listTmp == NULL)
	{
		return;
	}
	listTmp->length = 0;
	listTmp->pHeader.next = NULL;
	listTmp->silder = NULL;
}

//获取链表数据长度（元素个数）
int CircleList_Length(CircleList* list)
{
	int      result = CIRCLE_LIST_ERROR;
	CTList*  listTmp = (CTList*)list;
	if (listTmp == NULL)
	{
		return result;
	}
	result = listTmp->length;
	return result;
}

//插入元素
int CircleList_Insert(CircleList* list, CTNode* node, int pos)
{
	int		ret = CIRCLE_LIST_VAILD;
	int		i = 0;
	CTList* sList = (CTList*)list;
	if (sList==NULL||node==NULL)
	{
		ret = SCL_ERR_NULL;
		return ret;
	}
	if (pos<0)
	{
		ret = SCL_ERR_POST;
		return ret;
	}
	CTNode* currNode = (CTNode*)sList; //备份链表指针
	for (i = 0; i < pos && (currNode->next != NULL); i++)
	{
		currNode = currNode->next;//指针向前
	}
	//替换原有位置节点元素
	node->next = currNode->next;
	currNode->next = node;

	//如果是第一次插入节点，游标指向插入的元素节点
	if (sList->length==0)
	{
		sList->silder = node;
	}
	sList->length++;//元素个数加1

	//如果是头部插入 currNode循环后还指向头部指针
	if (currNode==(CTNode*)sList)
	{
		//获取最后一个元素
		CTNode* lastNode = CircleList_Get(sList, sList->length - 1);
		lastNode->next = currNode->next;//尾部衔接 或 lastNode->next =node;
	}

	return ret;
}

//获取指定位置元素节点
CTNode* CircleList_Get(CircleList* list, int pos)
{
	int      i = 0;
	CTNode*  ret = NULL;
	CTList*  sList = (CTList*)list;
	
	if (pos<0||sList==NULL)
	{
		return NULL;
	}

	{
		CTNode* currNode = (CTNode*)sList;
		for (i = 0; i < pos;i++)
		{
			currNode = currNode->next;
		}
		ret = currNode->next;
	}
	return ret;
}


//删除指定位置元素
CTNode* CircleList_Delete(CircleList* list, int pos)
{
	int      i = 0;
	CTNode*  ret = NULL;
	CTList*  sList = (CTList*)list;
	if (sList != NULL&&pos >= 0 && sList->length > 0)
	{
		CTNode*		currTmp = (CTNode*)sList;//currTmp = (CTNode*)(&sList.pHeader) --> sList 与 sList.pHeader 的地址是重叠的
		CTNode*		last = NULL;
		for (i = 0; i < pos;i++)
		{
			currTmp = currTmp->next;//移动到要删除节点的前一元素节点
		}

		if (currTmp==(CTNode*)sList)//如果删除节点是第一个元素
		{
			last = CircleList_Get(sList, sList->length - 1);
		}
		ret = currTmp->next;
		currTmp->next = ret->next;//跳过删除的元素
		sList->length--;

		if (last!=NULL)//判断链表是否为空
		{
			sList->pHeader.next = ret->next;
			last->next = ret->next;  //衔接链表
		}

		if (sList->silder=ret)//如果游标等于当前删除的节点
		{
			sList->silder = ret->next;//游标向前移动
		}

		//如果删除元素后，链表长度为0
		if (sList->length==0)
		{
			sList->pHeader.next = NULL;
			sList->silder = NULL;
		}
	}

	return ret;
}


//根据给定节点元素删除
CTNode* CircleList_DeleteNode(CircleList* list, CTNode* node)
{
	int	i = 0;
	CTNode* ret = NULL;
	CTList* sList = (CTList*)list;
	if (sList!=NULL)
	{
		CTNode* currTmp = (CTNode*)sList;
		//查找 node 在链表中的为位置
		for (i = 0; i < sList->length;i++)
		{
			if (currTmp->next==node)
			{
				ret = currTmp->next;
				break;
			}
			currTmp = currTmp->next;
		}

		//如果 i 下标匹配 node 根据 i 删除 node
		if (ret!=NULL)
		{
			CircleList_Delete(sList, i);
		}

	}
	
	return ret;
}

//重置游标
CTNode* CircleList_Reset(CircleList* list)
{
	CTList* sList = (CTList*)list;
	CTNode* ret = NULL;
	if (sList!=NULL)
	{
		sList->silder = sList->pHeader.next;
		ret = sList->silder;
	}
	return ret;
}

//获取当前游标的指向元素
CTNode* CircleList_Current(CircleList* list)
{
	CTList* sList = (CTList*)list;
	CTNode* ret = NULL;
	if (sList!=NULL)
	{
		ret = sList->silder;
	}
	return ret;
}

//把当前位置节点元素返回，并且游标下移
CTNode* CircleList_Next(CircleList* list)
{
	CTList* sList = (CTList*)list;
	CTNode* ret = NULL;
	if (sList != NULL&&sList->silder != NULL)
	{
		ret = sList->silder;
		sList->silder = ret->next;
	}
	return ret;
}

3：调用示例：

#define  _CRT_SECURE_NO_WARNINGS
#include "CircleList.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct _User_info
{
	CTNode* node;
	int age;
	char name[16];
}User;

//循环链表实现约瑟夫问题
void JosephProblem_fun();

int main(void)
{

	int ret = 0;
	int i = 0;
	User u1, u2, u3, u4, u5, u6;
	{
		u1.age = 11;
		u2.age = 12;
		u3.age = 13;
		u4.age = 14;
		u5.age = 15;
		u6.age = 16;
		strcpy(u1.name, "AAAA");
		strcpy(u2.name, "BBBB");
		strcpy(u3.name, "CCCC");
		strcpy(u4.name, "DDDD");
		strcpy(u5.name, "EEEE");
		strcpy(u6.name, "FFFF");
	}


	CircleList* list = CircleList_Create();
	if (list!=NULL)
	{
		//插入元素
		CircleList_Insert(list, (CTNode*)&u1.node, 0);
		CircleList_Insert(list, (CTNode*)&u2.node, 0);
		CircleList_Insert(list, (CTNode*)&u3.node, 0);
		CircleList_Insert(list, (CTNode*)&u4.node, 0);
		CircleList_Insert(list, (CTNode*)&u5.node, 0);
		CircleList_Insert(list, (CTNode*)&u6.node, 0);

		for (int i = 0; i < CircleList_Length(list) * 2;i++)
		{
			User* u =(User*) CircleList_Get(list, i);
			if (u==NULL)
			{
				printf("获取元素为空\n");
				break;
			}
			printf("%d ; %s \n", u->age, u->name);
		}

		//删除元素
		while (CircleList_Length (list)>0)
		{
			User* u = (User*)CircleList_Delete(list, 0);
			if (u==NULL)
			{
				printf("删除元素失败 \n");
			}
		}

		//释放链表
		CircleList_Destroy(list);
	}

	printf("循环链表实现约瑟夫问题 \n\n");
	JosephProblem_fun();


	system("PAUSE");
	return 0;
}

void JosephProblem_fun()
{
	/*
	 *题意是：已知 n 个人（分别用编号 1，2，3，…，n 表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从 1 开始，还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，直到圆桌上剩余一个人。
	 */
	int ret = 0;
	int i = 0;
	User u1, u2, u3, u4, u5, u6,u7,u8; // 8 个人
	{
		u1.age = 11;
		u2.age = 12;
		u3.age = 13;
		u4.age = 14;
		u5.age = 15;
		u6.age = 16;
		u7.age = 17;
		u8.age = 18;
		strcpy(u1.name, "AAAA");
		strcpy(u2.name, "BBBB");
		strcpy(u3.name, "CCCC");
		strcpy(u4.name, "DDDD");
		strcpy(u5.name, "EEEE");
		strcpy(u6.name, "FFFF");
		strcpy(u7.name, "GGGG");
		strcpy(u8.name, "HHHH");
	}


	CircleList* list = CircleList_Create();
	if (list != NULL)
	{
		//插入元素
		CircleList_Insert(list, (CTNode*)&u1.node, CircleList_Length(list)); //0
		CircleList_Insert(list, (CTNode*)&u2.node, CircleList_Length(list)); //1
		CircleList_Insert(list, (CTNode*)&u3.node, CircleList_Length(list)); //2
		CircleList_Insert(list, (CTNode*)&u4.node, CircleList_Length(list)); //3
		CircleList_Insert(list, (CTNode*)&u5.node, CircleList_Length(list)); //4
		CircleList_Insert(list, (CTNode*)&u6.node, CircleList_Length(list)); //5
		CircleList_Insert(list, (CTNode*)&u7.node, CircleList_Length(list)); //6
		CircleList_Insert(list, (CTNode*)&u8.node, CircleList_Length(list)); //7

		for (i = 0; i < CircleList_Length(list);i++)
		{
			User* uTmp = (User*)CircleList_Next(list);//根据游标获取元素,游标向前
			if (uTmp==NULL)
			{
				printf("游标获取元素失败！\n");
			}
			printf("元素 %d : age=%d ; name=%s \n",i+1, uTmp->age, uTmp->name);
		}

		CircleList_Reset(list);//重置游标

		printf("\n 设定数字 3 为出局编号\n");
		while (CircleList_Length (list)>0)
		{
			User* user = NULL;
			for (i = 0; i < 3;i++)
			{
				CircleList_Next(list);//游标向前
			}
			user = (User*)CircleList_Current(list);//获取当前游标指向的元素
			printf("出局：age=%d ; name=%s \n", user->age, user->name);
			User* ptr=(User*) CircleList_DeleteNode(list, (CTNode*)user);//删除选中节点
			if (ptr==NULL)
			{
				printf("删除元素失败\n");
			}
		}
		
		CircleList_Destroy(list);//释放链表
	}
	else
	{
		printf("链表创建失败! \n");
	}
}

4: 输出：

优点和缺点

优点：

• 功能强了。循环链表只是在单链表的基础上做了一个加强。
• 循环链表可以完全取代单链表的使用
• 循环链表的Next和Current操作可以高效的遍历链表中的所有元素

缺点：

• 代码复杂度提高了

约瑟夫问题-循环链表典型应用
n 个人围成一个圆圈，首先第 1 个人从 1 开始一个人一个人顺时针报数，报到第 m 个人，令其出列。然后再从下一 个人开始从 1 顺时针报数，报到第 m 个人，再令其出列，…，如此下去，求出列顺序。