循环链表解决约瑟夫斯问题

循环链表解决约瑟夫斯问题

问题描述：设有n个人围坐成一个圆圈，按一定指向方向，从第s个人开始报数，数到m的人出列，然后从下一个人重新报数，数到m的人又出列，…，直到n个人全部出列为止。
输入：n m s，按次序输出得到的n个人的顺序表。

#include<iostream>
using namespace std;
typedef int datetype;

typedef struct node//构建链表节点 
{
	datetype data;
	struct node* next;
}ListNode,*LinkList;//节点与表头指针

void CreateCircleLinkList(LinkList &rear,int n)//创建链表 
{
	ListNode *p,*pre;
	p = NULL;
	rear=pre= NULL;
	for (int i = 0; i < n; i++)
	{
		p = new ListNode;
		p->data = i + 1;
		if (rear == NULL) rear = p;
		if (pre != NULL) pre-> next= p;
		pre = p;
	}
	p->next = rear;//循环链表的构建 
	pre = rear;//pre 指向链首节点
	rear=p;//rear 指向链尾节点 
}

void josephus(LinkList &rear,int m,int s)//约瑟夫斯 问题 
{
	ListNode *p;
	for(int i=1;i<s;i++)//移到s-1个节点，从第s个人开始报数 
	{
		rear=rear->next;
	}
	while(rear->next!=rear)//当循环链表不为一个节点 
	{
		for(int i=1;i<m;i++)//移动m-1个人后再将第m个出列 
		{
			rear=rear->next;
		}
		p=rear->next;
		cout<<p->data<<"  ";
		rear->next=p->next;//将报到m的人出列
		delete p;
	}
	cout << rear->data;
}

int main()
{
	LinkList rear;
	int n,m,s;
	cin>>n>>m>>s;
	cout << endl;
	CreateCircleLinkList(rear,n);
	josephus(rear,m,s);
}