1.概念
循环链表是链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
判断空链表的条件是
head==head->next;
rear==rear->next;
循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。①循环链表中没有NULL指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p-＞next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。 ②在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。
约瑟夫环问题由来：
据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第
k个人。接着，再越过k-1个人，并杀掉第
k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。
代码实现为第m个人（如m=3）
2.代码
//循环链表(circular linked list)的实现 增减删查
#include
#include
/*链表存储结构的定义*/
typedef struct CLinkList
{
int data;
struct CLinkList *next; //指向下一个链表元素的指针
}node;
/*****************************************************/
/* 对循环链表的操作 */
/*****************************************************/
/*函数作用：初始化循环链表*/
/*参 数：pNode-循环链表第一个结点*/
void ds_init(node **pNode)
{
int item; //存储输入内容
node *temp; //临时存储的结点指针
node *target; //用于动态查找的结点指针
printf("请输入结点的值，输入0完成初始化 \n");
while (1)
{
scanf("%d", &item); //将输入内容存入变量item对应的地址中
fflush(stdin); //清空缓存区
if (item == 0)
{
return;
}
if ((*pNode) == NULL) //循环链表中 插入第一个结点
{
*pNode = (node*)malloc(sizeof(struct CLinkList)); //为结点分配内存地址
if (!(*pNode)) exit(0); //分配地址失败为0，退出程序
(*pNode)->data = item; //将第一个结点数据设成item
(*pNode)->next = *pNode; //链表仅有一个结点时，该结点的next指向自己
}
else
{
/*找到最后一个结点赋值给target 即next指向第一个结点的结点*/
for (target = (*pNode); target->next != (*pNode); target = target->next);
/*生成新的结点*/
temp = (node*)malloc(sizeof(struct CLinkList));
if (!temp) exit(0);
temp->data = item;
temp->next = *pNode;
target->next = temp;
}
}
}
/*函数作用：插入结点*/
/*参 数： pNode-链表第一个结点， i-插入位置*/
void ds_insert(node **pNode, int i)
{
node *temp; //临时存储新插入的结点指针
node *target; //用于动态查找的结点指针
node *p; //存储要插入位置的原来的元素
int item;
int j = 1; //线性表起始下标为1
printf("请输入要插入的结点的值 \n");
scanf("%d", &item); //将输入内容存入变量item对应的地址中
if (i == 1) //在第一个位置插入结点//
{
temp = (node*)malloc(sizeof(struct CLinkList));
if (!temp) exit(0);
temp->data = item;
/*找到最后一个结点赋值给target 即next指向第一个结点的结点*/
for (target = (*pNode); target->next != (*pNode); target = target->next);
temp->next = (*pNode); // 使插入结点指向 原来的头结点(变成了第二个元素)
target->next = temp; //将尾结点 指向 插入的结点
*pNode = temp; //设置新的头结点为 插入的结点
}
else
{
target = *pNode; //将头结点赋给target
//i为插入的位置，获取要插入位置的的前一个结点，并赋给target
//如i=4,则jnext;
}
temp = (node*)malloc(sizeof(struct CLinkList));
if (!temp) exit(0);
temp->data = item;
p = target->next; //将要插入位置i原来的元素提取出来
target->next = temp; //将要插入的元素放到i的位置
temp->next = p; //将原来的元素 连接到 新插入的元素的后面
}
}
/*函数作用：删除结点*/
/*参 数：pNode-链表第一个结点， i-删除位置*/
void ds_delete(node **pNode, int i)
{
node *target;
node *temp;
int j = 1;
if (i == 1) //删除第一个结点时
{
//找到最后一个结点
for (target = *pNode; target->next != *pNode; target = target->next);
temp = *pNode; //提取出第一个结点
*pNode = (*pNode)->next; //将结点2赋给第一个结点
target->next = *pNode; //最后一个结点指向 新的第一个结点(原结点2)
free(temp); //释放原来的第一个结点内存空间
}
else
{
target = *pNode; //将头结点赋给target
for (; j < (i - 1); j++) //获取要删除的结点的前一个结点
{
target = target->next;
}
temp = target->next; //提取要删除的结点i
target->next = temp->next; //要删除结点i的前一结点的next 指向 要删除结点i的后一结点
free(temp);
}
}
/*函数作用：返回结点所在位置 int*/
/*参 数：pNode-链表第一个结点地址， elem-查找位置*/
int ds_search(node *pNode, int elem)
{
node *target;
int i = 1;
//直到查找到要删除元素，或链表结尾为止，将查找到的结点赋给target ,此时i加到该结点对应位置
for (target = pNode; target->data != elem && target->next != pNode; i++)
{
target = target->next;
}
if (target->next == pNode) //若到链表结尾未找到元素
return 0;
else
return i;
}
/*函数作用：遍历显示链表中元素*/
/*参 数：pNode-链表第一个结点地址 */
void ds_traverse(node *pNode)
{
node *temp;
temp = pNode;
printf("********************链表中元素如下*********************\n");
do
{
printf("%4d ", temp->data);
} while ((temp = temp->next) != pNode);
printf("\n");
}
int main()
{
node *pHead = NULL;
char opp = 'A'; //记录操作字符
int find; //记录结点位置
printf("1.初始化链表 \n\n2.插入结点 \n\n3.删除结点 \n\n4.返回结点位置 \n\n5.遍历链表 \n\n请选择你的操作\n");
while (opp != '0')
{
scanf("%c", &opp);
switch (opp)
{
case '1':
ds_init(&pHead);
printf("\n");
ds_traverse(pHead);
break;
case '2':
printf("输入要插入结点的位置？");
scanf("%d", &find);
ds_insert(&pHead, find);
printf("在位置%d插入值后：\n", find);
ds_traverse(pHead);
printf("\n");
break;
case '3':
printf("输入要删除的结点的位置？");
scanf("%d", &find);
ds_delete(&pHead, find);
printf("删除第%d个结点后：\n", find);
ds_traverse(pHead);
printf("\n");
break;
case '4':
printf("你要查找数值为多少的结点的位置？");
scanf("%d", &find);
printf("元素%d所在位置：%d\n", find, ds_search(pHead, find));
printf("\n");
break;
case '5':
ds_traverse(pHead);
printf("\n");
break;
case '0':
exit(0);
}
}
return 0;
}/*
* JosephProblem
* 41个人一群人围坐成一圈，从1号开始，每三人个去除一个人，然后以原去除的人后面的那个人为第一个，每三个人去除一个人，知道所有人全部去除 求去除编号顺序
*/
#include
#include
/*链表存储结构的定义*/
typedef struct node
{
int data;
struct node *next; //指向下一个链表元素的指针
}node;
/*初始化循环链表*/
node *create(int n)
{
node *p = NULL; //临时结点，作为指针使用
node *head; //头结点，作为开始索引
head = (node*)malloc(sizeof(node));
p = head; //指向头结点
node *s = NULL; //作为当前结点
int i = 1; //循环链表开始索引
if (0 != n) //创建元素个数不为0
{
while (i data = i++; //i结点值为i
p->next = s; //指向下一节点
p = s; //当前结点赋给指针P
}
s->next = head->next; //尾结点指向第一个结点
free(head);
return s->next;
}
}
int main()
{
int n = 41; //环总数
int m = 3; //步长
int i;
node *p = create(n); //创建循环链表
node *temp;
m %= n; //设定步长使用
while (p != p->next) //未删除到空链表时
{
for (i = 1; i < m - 1; i++)
{
p = p->next; //若步长为m=3，循环1次，执行for后p指向结点2,输出结点3的值
}
printf("%d->", p->next->data);
temp = p->next; //提取要去除的结点（p是node2 temp是node3）
p->next = temp->next; //删除结点的前一结点指向删除结点的后一结点
free(temp);
p = p->next; //原删除结点的后一结点重新作为第一个结点进行下一轮循环
}
printf("%d\n", p->data); //输出最后结点
return 0;
}3.结果
