约瑟夫环问题（循环链表）C语言

约瑟夫环问题（循环链表）C语言

问题描述
约瑟夫环问题是由古罗马的史学家约瑟夫提出的，他参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军，设法守住了裘达伯特城达47天之久，在城市沦陷之后，他和40名死硬的将士在附近的一个洞穴中避难。在那里，这些叛乱者表决说“要投降毋宁死”。于是，约瑟夫建议每个人轮流杀死他旁边的人，而这个顺序是由抽签决定的。
规则：
在一间房间总共有m个人，只能有最后一个人活命。
1.所有人围成一圈
2.轮流报数，报到n的人将被杀掉
3.被杀的人出圈
4.然后从下一个人重新报数，报到n的人再被清除，直到剩余一人
求解思路
定义人员结构体，创建一个没有空表头的循环链表，把每个人的信息进行储存。
（很多时候链表如果没有空表头，插入删除查询等操作会变得相对复杂，但是对于这个问题，没有哑元的循环链表比较方便）
从表头开始遍历，设置计数器k，当k是n的倍数时删除一个节点，直到链表只剩下一个节点，遍历删除操作使用了两个指针Head，Tail来实现，当两个指针指向同一个节点时操作结束。
完整代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct people{
	char number[20];
	struct people * next;
} Node;
typedef Node * Linklist;//结构体 
int main(){
	Linklist Head,Current,Tail;
	int m,n;
	printf("请输入人数m\n");
	scanf("%d",&m);
	char num[m][20];
	int i=0;
	printf("请输入%d个人的名字，每个人的名字结束后输入【Enter】键再输入下一个人的名字\n",m); 
	while(i<m+1&&fgets(num[i],19,stdin)!=NULL){   //循环输入m个人的名字，用数组存储 
		i++;
	}
	Head=(Linklist)malloc(sizeof(Node));
	Head->next=NULL;
	Tail=Head;   //创建空表
	for(int j=1;j<m+1;j++){	
	Current=(Linklist)malloc(sizeof(Node));
	strcpy(Current->number,num[j]);
	Tail->next=Current;
	Current->next=Head->next;
	Tail=Current;}  //尾插法插入名字 
	printf("请输入被杀掉的人报的数字n\n");
	scanf("%d",&n);
	Head=Head->next;
	int k=1;
	while(Head!=Tail){
		if(k%n!=0) {Head=Head->next;Tail=Tail->next;}
		else {Current=Head;Head=Head->next;Tail->next=Head;free(Current);}
		k++; 
	}   //循环遍历，删除
	printf("最后的剩下的人是%s",Head->next->number); 
    return 0;
}