借鉴了别人的代码，在经过自己的理解
/*
设有n个人围成一圈 , 编号从1到n ,
约定从编号为k(1 <= k <= n)的人从1开始报数 ,
数到 m 的那个人被淘汰 , 接着下一个人重新从1开始报数 ,
数到 m 再淘汰一人 , 如此反复 , 直至剩下最后一个人为止
我们可以知道约瑟夫问题是一个不断循环而且数据不断减少的过程 , 使用单向循环链表可以很方便地对数据进行删除 , 而且遍历链表非常方便
理清思路过程:
1、首先一个带有n个结点的单循环链表 , 从第k个人开始从1报数
2、 需要将头指针指向第k个人 , 辅助删除指针指向第(k-1)个人
3、 定义辅助删除指针的意义是为了方便当第k个人淘汰时 , 可以很方便的将第(k-1)的next指针指向第(k+1)个人
4、当人数剩下一个人时 , 则认为这场游戏已经结束了 , 最后剩下的那个人就是胜利者
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next; //struct Node类型指针
}LinkList;
LinkList * CreatList(int n)//创建链表，结点个数为n
{
LinkList *p, *q, *head;
p = (LinkList *)malloc(sizeof(LinkList));
p->data = 1;
p->next = NULL;
head = p;
for (int i = 2; i <= n; i++)
{
q = (LinkList *)malloc(sizeof(LinkList));
q->data = i;
q->next = NULL;
p->next = q;
p = q;
}
p->next = head;
return head;//头指针
}
int Find(LinkList *a,int k , int m)
{
for (int i = 1; i < k; i++)//从第K个人开始计数
{
a = a->next;
}
printf("第%d个人的值为%d
", k, a->data);//思路正确，从第k个人开始计数，故指针要相应移动
LinkList *q = a;
while (a->next != a) //a->next == a代表只剩下一个人
{
for (int j = 1; j < m; j++)
{
q = a; //q代表上一个人的指针
a = a->next;
}
printf("被删除的数为%d
", a->data);
q->next = a->next; //将q指向被删除人的下一个人
free(a);//将a所指向的空间释放，但a指针仍然存在，应该置为空指针a=NULL;
a = q->next;//将下一个人给a
}
//跳出循环后只剩一个人
printf("最后活下来的是%d
", a->data);
return 0;
}
int main()
{
int k = 1;
int m = 3;
int n = 41;
LinkList *a = CreatList(n);
Find(a,k,m);//从1开始报数 , 数到 m 的那个人被淘汰
return 0;
}
