约瑟夫环问题，是一个经典的循环链表问题，题意是：已知 n 个人（分别用编号 1，2，3，…，n 表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从 1 开始，还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，直到圆桌上剩余一个人。 如图所示，假设此时圆周周围有 5 个人，要求从编号为 3 的人开始顺时针数数，数到 2 的那个人出列：
出列顺序依次为： 编号为 3 的人开始数 1，然后 4 数 2，所以 4 先出列； 4 出列后，从 5 开始数 1，1 数 2，所以 1 出列； 1 出列后，从 2 开始数 1，3 数 2，所以 3 出列； 3 出列后，从 5 开始数 1，2 数 2，所以 2 出列； 最后只剩下 5 自己，所以 5 胜出。 实现代码如下：
代码语言：javascript复制#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int number;
struct node * next;
}Person;
Person * InitList(int n)
{
Person * head=(Person*)malloc(sizeof(Person));
/*准备一个头结点*/
head->number=1;
head->next=NULL;
Person * cyclic=head;
/*循环创建*/
for (int i=2; i<=n; i )
{
/*申请空间存储数据*/
Person * body=(Person*)malloc(sizeof(Person));
body->number=i;
body->next=NULL;
/*连接*/
cyclic->next=body;
/*cyclic继续用作循环变量*/
cyclic=cyclic->next;
}
/*首尾相连*/
cyclic->next=head;
return head;
}
void FindAndKillK(Person * head,int k,int m)
{
Person * tail=head;
/*找到链表第一个结点的上一个结点，为删除操作做准备*/
while (tail->next!=head)
{
tail=tail->next;
}
Person * p=head;
/*找到编号为k的人*/
while (p->number!=k)
{
tail=p;
p=p->next;
}
/*从编号为k的人开始，只有符合p->next==p时，说明链表中除了p结点，所有编号都出列了*/
while (p->next!=p)
{
/*找到从p报数1开始，报m的人，并且还要知道数m-1的人的位置tail，方便做删除操作*/
for (int i=1; i<m; i )
{
/*存储下上一个位置*/
tail=p;
p=p->next;
}
/*从链表上将p结点摘下来*/
tail->next=p->next;
printf("出列人的编号为:%dn",p->number);
free(p);
/*继续使用p指针指向出列编号的下一个编号，游戏继续*/
p=tail->next;
}
printf("胜利的人的编号为:%dn",p->number);
free(p);
}
int main() {
printf("输入圆桌上的人数n:");
int n;
scanf("%d",&n);
Person * head=InitList(n);
printf("从第k人开始报数(k>1且k<%d)：",n);
int k;
scanf("%d",&k);
printf("数到m的人出列：");
int m;
scanf("%d",&m);
FindAndKillK(head, k, m);
return 0;
}版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
测试结果
