约瑟夫环(数据结构｜循环链表与约瑟夫环)

时间：2023-02-16 10:16 来源：黑土直播

循环链表是一种特殊的单链表，其最后一个结点的指针域指向链表的头结点或者直接指向第一个元素结点。

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

约瑟夫环运作如下：

1、一群人围在一起坐成环状；
2、从某个编号开始报数（如：K）；
3、数到某个数（如：M）的时候，此人出列，下一个人重新报数；
4、一直循环，直到所有人出列，约瑟夫环结束。

传说，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓。于是决定了自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀。然后下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

这是一个典型的循环链表题目。我们需要创建一个循环链表，依照游戏规则，依次进行删除结点操作。直至链表为空，打印出的元素顺序即为出局顺序！

下面用C语言写出约瑟夫环问题的程序，创建链表，添加数据，依次删除结点操作，直到链表为空表，

源代码如下：

我们可以任意设置个数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：

#include<stdio.h>
typedef struct node
{
int data;
struct node *next;
}node;
node *create(node *head,int n)
{
int i=1;
node *s,*p=head;
while(i<=n)
{
s=(node *)malloc(sizeof(node));
s->data=i++;
p->next =s;
p=p->next;
}
p->next=head->next;
free(head);
return p->next;
}
int main()
{
int i,n,m,j=1;
node *head,*newstart,*h,*t;
head=(node *)malloc(sizeof(node));
printf("请输入数据长度n、数据间隔m，如：41,3\n");
scanf("%d,%d",&n,&m);
newstart = create(head,n);
h=newstart;
while(h!=h->next)
{
for(i=1;i<m-1;i++)
{
h=h->next;
}
t=h->next;
printf("\t%d→",h->next->data);
if(j%3==0)
printf("\n");
h->next=t->next;
h=t->next;
j++;
free(t);
}
printf("%d",h->data);
printf("\n");
system("pause");
return 0;
}

附源码2：

#include "stdio.h"
#include "malloc.h"
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");
}