引言
约瑟夫问题是循环链表的一个典型应用，其描述如下：m个人围成了一圈，从其中任意一个人开始，按顺时针顺序使所有人一次从1开始报数，报道n的人出列；然后使n之后的人接着从1开始报数，再次使报到n的人出列。。。。。。如此下去，求出列的顺序及最后留下来的人的编码。
举个栗子
为了更清晰的描述问题，可以将m与n设定为具体数字，如m=8，n=3，即8个人围着坐成一圈。
给这8个人编号，使编号为1的人开始从1开始报数，报到3的人出列；
编号为4的人接着从1开始报数，报到3出列。。。
如此重复，知道最后只剩下一个人。额，有点不太好想，那我们来画图看看吧。
来，我们来把步骤总结一下
第一轮：从1到3，第三个人出列
第二轮：第4个人从1开始报数，第6个人报到3，则第6个人出列
第三轮：第7个人从1开始报数，第1个人报到3，则第1个人出列
第四轮：第2个人从1开始报数，第5个人报到3，则第5个人出列
第五轮：第7个人从1开始报数，第2个人报到3，则第2个人出列
第六轮：第4个人从1开始报数，第8个人报到3，则第8个人出列
第七轮：第4个人从1开始报数，这个时候只剩下4和7，第4个人又报到3，则第4个人出列。
最后，只剩下第7个人，此时，报数终止。
看图发现
当数据量较小时，通过作图很容易就能找到出局顺序；
但是当数据量较大时，人工计算几乎是不可能的。
要解决这样的问题，需要借助一定的编程算法，而循环链表就正好可以用来解决此问题。
首先用这些数据创建一个循环链表；
然后设置限定条件；
并循环遍历链表；
当遍历到要出局的元素时，就将其删除；
这样循环操作指导链表中只剩下一个结点。
代码实现
clist.h （头文件）
#ifndef _CLIST_H_
#define _CLIST_H_
struct Node;
typedef struct Head *pHead;//定义头结点类型为pHead
typedef struct Node * pNode;//数据结点类型
//定义头结点
struct Head{
int length;
pNode next;//指向下一个结点的指针
};
//定义数据结点
struct Node
{
int data;
pNode next; //指向后继结点的指针
};
pHead ClistCreate(); //声明创建循环链表的方法
int getLength(pHead ph); //获取循环链表的长度
int IsEmpty(pHead ph); //判断链表是否为空
int ClistInsert(pHead ph,int pos,int val); //在链表的pos位置插入元素 val
void print(pHead ph); //打印循环链表中的元素
#endif
clist.c（文件）
#include "clist.h"
#include <stdio.h>
#include <stdlib.h>
pHead ClistCreate(){ //创建循环链表
pHead ph=(pHead)malloc(sizeof(struct Head));//为头结点分配空间
if(ph==NULL){
printf("分配头结点失败");//为了方便运行结果查看，不设置return返回值
}
//创建好头结点后，初始化头结点中的数据
ph->length=0;
ph->next=NULL;
return ph;//带头结点返回
}
int IsEmpty(pHead ph)//判断链表是否为空
{
if(ph=NULL)
printf(“传入的循环链表有误”);
if(ph->length==0){
return 1; //说明为空
}
else{
return 0;//说明不为空
}
}
//在链表的pos位置插入元素val
int ClistInsert(pHead ph,int pos,int val){
if(ph==NULL||pos<0||pos>ph->length){
printf(“插入元素时，参数传入有误!\n”);
}
pNode pval=val;//将值val保存到此结点中
//判断在哪个位置插入元素，先判断链表是否为空
if(IsEmpty(ph)){
//如果链表为空
ph->next=pval;//直接将结点插入到头结点后
pval->next=pval;//将第一个结点指向他自己
}
else{
//循环链表不为空，则分为在头部插入（即在头结点后）和普通位置插入
pNode pRear=ph->next;
if(pos==0)//在第一个位置（头结点后）插入
{
//在0号位置插入，需要先找到尾节点
while(pRear->next!=ph->next) //循环结束的条件
{
pRear=pRear->next;//pCur指针向后移动
}
//while循环结束后，pRear指向尾节点
//然后插入元素
pval->next=ph->next;
ph->next=pval;
pRear->next=pval;//这3个步骤顺序不能更改
}
else{//如果不是0号位置插入，这和单链表无区别
pNode pCur=ph->next;
for(int i=1;i<pos;i++){
//遍历链表找到要插入的位置
pCur=pCur->next;//pCur指针往后移
}
//循环结束，此时pCur指向的是要插入的位置
pval->next=pCur->next;//指针断开再连接的过程
pCur->prev=pval;
}
}
ph->length++;
return 1;
}
//打印循环链表中的元素
void print(pHead ph){
if(ph==NULL||ph->length==0){
printf("参数传入有误！");
}
pNode pTmp=ph->next;
for(int i=0;i<ph->length;i++){
printf("%d",pTmp->data);
pTmp=pTmp->next;
}
printf("\n");
}
ok,以上就讲循环链表的一些方法都已经第一好了，接下来我们来测试一下
Joseph.c(测试文件)
#define _CRT_SECURE_NO_WARNINGS
#include "clist.h"
#include <stdio.h>
#include <stdlib.h>
int main(){
int m,n;
printf("请输入约瑟夫环的总人数：\n");
scanf("%d",&m);
if(m<=0){
printf(“请输入正确的数字！\n”);
return 0;
}
printf("请输入被提出的报数：\n");
scanf("%d",&n);
if(n<=0){
printf("请输入正确的数字!\n");
return 0;
}
//根据输入的m创建链表 m即链表的长度
pHead ph=NULL;
ph=ClistCreate();
if(ph==NULL){
printf("创建循环链表失败！\n");
return 0;
}
//插入元素
for(int i=m;i>0;i--){
ClistInsert(ph,0,i);//使用头插法从m到1倒序插入
}
print(ph);
printf("被踢顺序：\n");
//插入元素后，就循环遍历链表
pNode node=ph->next; //node指针指向第一个结点
while(node->next!=node){
//循环结束条件，结点指向其自身，此时剩下最后一个结点
for(int i=1;i<n-1;i++){
//i<n-1,即报数报到n就重新开始
node=node->next;
}
//for 循环条件结束后，node指针指向待出局的结点的前驱结点
pNode pTmp=node->next;//pTmp指向要出局的结点
//接下来要先判断这个结点是0号位置的结点还是其他位置的结点
if(pTmp==ph->next){
//如果此结点在0号位置
ph->next=pTmp->next;//对头结点进行处理
node->next=pTmp->next;
printf("%d",tTmp->data);
free(pTmp);
ph->length--;
}
else{
//如果此结点在其他位置
node->next=pTmp->next;
printf("%d",pTmp->data);
free(pTmp);
ph->length--;
}
node=node->next;
}
node->next=node;//循环结束，只剩下node一个结点，让其指向自身
printf("\n");
printf("链表中最后留下的是");
printf(ph);
system("pause");
return 0;
}
上方的测试代码中，创建了一个循环链表，以循环链表为基础来计算这一圈人的出局序列，并求出最后留下来的人。
解决约瑟夫问题并没有用到循环链表的全部算法，因此，在本例子中只涉及到了此问题的相关方法实现。即：
首先创建一个循环链表
两个变量去设置这个循环链表的长度即报数单位
然后开始遍历
如果报到指定的报数单位，就将这个报数的位置的结点移除，并free
直到链表中只剩下一个结点时，终止循环
完事~~~
总结一下啦
我们从第六篇文章到本篇文章讲解了最简单的数据结构——线性表，具体包括常用的顺序表、单链表、双链表、循环链表。
我们通过使用线性表来解决一些简单的问题，从而为以后的数据结构的学习打下结实的基础。
下一篇，我们来看一下android中的 LinkedList 的源码，看看这个LinkedList内部是怎样一个构成~~，敬请期待
