循环链表是一种特殊的单链表，其最后一个结点的指针域指向链表的头结点或者直接指向第一个元素结点。
约瑟夫环是一个数学的利用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全体出列。文章源自微观生活（93wg.com）微观生活-https://93wg.com/17587.html
约瑟夫环运作如下：文章源自微观生活（93wg.com）微观生活-https://93wg.com/17587.html
1、一群人围在一块儿坐成 环状；文章源自微观生活（93wg.com）微观生活-https://93wg.com/17587.html
2、从某个编号开始报数（如：K）；文章源自微观生活（93wg.com）微观生活-https://93wg.com/17587.html
3、数到某个数（如：M）的时候，这人出列，下一个人从新报数；文章源自微观生活（93wg.com）微观生活-https://93wg.com/17587.html
4、一直循环，直到所有人出列 ，约瑟夫环收场。文章源自微观生活（93wg.com）微观生活-https://93wg.com/17587.html
传说，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人抉择宁愿死也不要被敌人抓。于是抉择了自杀方式，41个人排成一个圆圈，由第1个人开始报数，每一报数到第3人该人就必需自杀。然后下一个从新报数，直到所有人都自杀身亡为止。但是Josephus以及他的朋友其实不想遵从，Josephus要他的朋友先伪装遵从，他将朋友与自己支配在第16个与第31个位置，于是逃过了这场死亡游戏。文章源自微观生活（93wg.com）微观生活-https://93wg.com/17587.html
这是一个典型的循环链表题目。咱们需要创立一个循环链表，按照游戏规则，顺次进行删除了结点操作。直至链表为空，打印出的元素顺序即为出局顺序！文章源自微观生活（93wg.com）微观生活-https://93wg.com/17587.html
下面用C语言写出约瑟夫环问题的程序，创立链表，添加数据，顺次删除了结点操作，直到链表为空表，文章源自微观生活（93wg.com）微观生活-https://93wg.com/17587.html
源代码如下：文章源自微观生活（93wg.com）微观生活-https://93wg.com/17587.html
咱们可以任意设置个数n，和间隔m。下图为一个实例的运行结果，摹拟了经典的约瑟夫问题，41人，间隔3人，最后就是16号以及31号逃脱！
如果是10人，间隔3，则是如下效果：
较繁杂的约瑟夫问题：
已知n个人（以编号1，2，3...n分别表示，此外每一个人手上都有一个密码数p）围坐在一张圆桌周围。从编号为k的人开始报数，顺时钟方向数到m的那个人出列，并将手中的密码作为新的报数上限M，从他的顺时钟方向的下一个人又从1开始报数，数到的那个人又出列；依此规律重复下去，直到圆桌周围的人全体出列，求出这些人的出列顺序：
最简单的解法就是使用一个不带头结点的循环链表来存储约瑟夫环中每一个人的编号以及手中的密码，然后依照规则进行报数以及出列的动作。其中报数对应循环链表的循环遍历操作，出列对应的是循环链表的删除了结点操作。
在main函数中，首先调用CreatJosephRing创立一个包括n个结点的约瑟夫环并用指针list指向其第一个元素的结点，然后设置指针p以及q分别指向循环链表的第一个结点以及它的先驱结果。这样便形成了一个初始状况，如下图所示：
接下来就能够动态地执行“报数→出列”的动作，每一出列一个成员，实际上就是循环链表中删除了一个结点，并输出该结点的编号id作为出队序列，同时将结点的密码key作为下一次的报数上限M。这个进程可以通过下面的程序片断来实现：
当指针p不等于q时表明该循环链表中不只有一个结点，所以循环继续。每一次循环进程中，指针p以及q都顺序后移m-1次，终究指针p指向要出列的成员结点，指针q指向其先驱结点。然后通过指针q从链表中删除了该结点，通过指针p读出出列成员结点的id以及key。将id输出作为出列序列，将key赋值给m作为下一次循环的报数上限。
当循环链表只剩下一个结点时，指针p以及q指向同一结点，如下图所示：
此时约瑟夫环中只剩下一个成员，其他成员都已出列，那么这个成员手中的密码也没有用了，于是输出该结点的成员编号id便可。
运行效果：
附源码1：
typedef struct node{
int id;/*成员编号*/
int key; /*密码*/
struct node *next ;/*指针域*/
}LNode,*LoopLinkList;
LoopLinkList CreatJosephRing(int n)
{
LoopLinkList list,p,r;
int e;
int i;
scanf(\"%d\",&e); /*得到第一个元素结点数据*/
r = list = (LoopLinkList) malloc(sizeof(LNode));/*创立第一个结点*/
list->next = list;/*指针指向本身*/
list->key = e;/*复制第一个结点的数据元素*/
list->id = 1;
for(i=2;i<=n;i++)
{
/*循环创立后续的n-1个结点*/
scanf(\"%d\",&e);
p=(LoopLinkList)malloc(sizeof(LNode));
p->key = e;
p->id = i;
p->next = list;/*指向链表第一个结点*/
r->next = p;/*将新结点连入循环链表*/
r = r->next;/*指针r后移*/
}
return list;
}
main()
{
LoopLinkList list=NULL,p=NULL,q=NULL;
int n,m,i;
printf(\"Input the number of the people in Joseph Ring\\n\");
scanf(\"%d\",&n);
printf(\"Input the password of the people\\n\");
list = CreatJosephRing(n);
printf(\"Input the first Maximum Number M\\n\");
scanf(\"%d\",&m);
printf(\"The order of leaving Joseph Ring\\n\");
q = p = list;
while(q->next!=list)
{
q = q->next;/*q指向p的先驱结点*/
}
while(p!=q)
{
for(i=0;i<m-1;i++)
{
p = p->next;
q = q->next;
}
printf(\"%3d\",p->id);/*输出出队者的编号*/
m = p->key;/*下一次的报数上限*/
q->next = p->next;/*删除了结点*/
free(p);/*释放删除了的结点空间*/
p = q->next;
}
printf(\"%3d\",p->id);
free(p);
list = p = q = NULL;
printf(\"\\n\");
system(\"pause\");
}
－End－
以上就是微观生活（93wg.com）关于“数据结构｜循环链表与约瑟夫环”的详细内容，希望对大家有所帮助！
评论