数据结构：循环链表实现约瑟夫环

通过循环链表实现约瑟夫环

• 要求：1）要求设计一个程序模拟次过程，输入总的人数n，所报的出列的数字k，计数开始的位置p;
• 程序所能达到的功能：构造链表；输入数据；执行报数；储存出列人的序号，删除出列人的信息以及把指向出列人的指针移到出列人的下一个人，然后重新开始执行报数；直到最后一个人报数完毕，程序结束。
• 测试数据：n=9，9个人的序号分别为：1,2,3,4,5,6,7,8,9。然后p=1，从第一个开始报数。k=5，则确定输出的序列为：5,1,7,4,3,6,9,2,8。

代码

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <limits.h>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <string>
#define ll long long
#define ull unsigned long long
#define ms(a) memset(a,0,sizeof(a))
#define pi acos(-1.0)
#define INF 0x7f7f7f7f
#define lson o<<1
#define rson o<<1|1
const double E=exp(1);
const int maxn=1e6+10;
const int mod=1e9+7;
using namespace std;
typedef struct Node
{
	int num;
	struct Node *next;
}Node,*Linklist;
int n,k,m;
Linklist Link_init()
{
	Linklist head,cycle,body;
	head=(Node *)malloc(sizeof(Node));
	head->next=head;
/*-----------------------------------*/
	head->num=1;
	cycle=head;
/*----------------------------------*/
	for(int x=2;x<=n;x++)
	{
		body=(Node *)malloc(sizeof(Node));
		body->num=x;
		body->next=cycle->next;
		cycle->next=body;
		cycle=body;
	}
	cycle->next=head;
	return head;
}
void Play(Node *head,int k,int m)
{
	Linklist first=head;
	while(first->next!=head)
		first=first->next;
	Node *p=head;
	while(p->num!=k)
	{
		first=p;
		p=p->next;
	}
	int _=0;
	while(p->next!=p)
	{
		for(int i=1;i<m;i++)
		{
			first=p;
			p=p->next;
		}
		first->next=p->next;
		cout<<"第"<<++_<<"个出列的人的编号是："<<p->num<<endl;
		free(p);
		p=first->next;
	}
	cout<<"第"<<++_<<"个出列的人的编号是："<<p->num<<endl;
	free(p);
}
int main(int argc, char const *argv[])
{	
	freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
	ios::sync_with_stdio(false);
	while(cin>>n)
	{
		cout<<"请出入参与游戏的总人数：";
		cin>>n;
		Node *person=Link_init();
		cout<<"请输入最开始报数的编号（编号从1~n）：";
		cin>>k;
		cout<<"请输入出列的序号：";
		cin>>m;
		Play(person,k,m);	
		cout<<endl;
	}
	return 0;
}