【数据结构】【C语言】【环形链表约瑟夫问题】

1.问题描述及背景：

著名的Josephus问题
据说著名犹太
历史学家
Josephus有过以下的故事：在罗⻢⼈占领乔塔帕特后，39 个犹太⼈与
Josephus及他的朋友躲到⼀个洞中，39个犹太⼈决定宁愿死也不要被⼈抓到，于是决定了⼀个⾃杀
⽅式，41个⼈排成⼀个圆圈，由第1个⼈开始报数，每报数到第3⼈该⼈就必须⾃杀，然后再由下⼀
个重新报数，直到所有⼈都⾃杀⾝亡为⽌。
然⽽Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与⾃⼰安排在
第16个与第31个位置，于是逃过了这场死亡游戏。

描述
编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。
下一个人继续从 1 开始报数。
n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

说明：
开始5个人 1，2，3，4，5 ，从1开始报数，1->1，2->2编号为2的人离开
1，3，4，5，从3开始报数，3->1，4->2编号为4的人离开
1，3，5，从5开始报数，5->1，1->2编号为1的人离开
3，5，从3开始报数，3->1，5->2编号为5的人离开
最后留下人的编号是3

2.代码实现：

一：创建环形链表
二：一前一后创建两个指针，

#include
#include
typedef struct SLNode
{
	int data;
	int* next;
}SLNode;
//申请空间：
SLNode* SLBuyNode(int x)
{
  SLNode* node=(SLNode*)malloc(sizeof(SLNode));
  node->data=x;
  node->next=NULL;
}
//创建环形链表：
SLNode*Create(int n)
{
  SLNode* phead=SLBuyNode(1);
  SLNode*ptail=phead;
  for(int i=2;i<=n;i++)
  {
   SLNode* node=SLBuyNode(i);
   ptail->next=node;
   ptail=ptail->next;
  }
  ptail->next=phead;
  return ptail;
//实现约瑟夫函数：
int ysf(int n,int m)
{
SLNode*prev=Create(n);
SLNode*cur=prev->next;
int count=1;
while(cur!=cur->next)
{
 if(count==m)
 {
  prev->next=cur->next;
  free(cur);
  cur=prev->next;
  count=1;
 }
  else
  {
   prev=cur;
   cur=cur->next;
   count++;
  }
}
return cur->data;

int main()
{
int tem=ysf(5,3)
printf("%d\n",tem);
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57