约瑟夫问题-循环链表

约瑟夫问题
简介：
约瑟夫问题，是一个计算机科学和数学中的问题，在计算机编程的算法中，类似问题又称为约瑟夫环，又称“丢手绢问题”。

一般形式：
约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。

例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。

问题描述：
设有n个人围做一圈，现从某个人开始报数，数到m的人出列，接着从出列的下一个人开始重新报数，数到m的人又出列，如此下去，知道所有人都出列为止。

问题分析：
从第一个人开始报数，报到m的人将出去，再从下一人继续报。

第N个人报完后，又从第一个人开始，相当于一个循环链表，因此可以通过循环链表再结合删除链表 *** 作完成如上 *** 作。

算法设计：

/*
输入要求：输入两个数n，m。

分别表示n个人和报到第m个时被杀掉
例如输入：6 5
	输出：5 4 6 2 3 
*/

#include 
#include 

struct LNode		
{
	int data;
	struct LNode *next;
};

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	LNode *p,*s,*head;
	p=head=(LNode *)malloc(sizeof(LNode));
	p->data=1;
	int i;
	for(i=2;i<=n;i++)
	{
		s=(LNode *)malloc(sizeof(LNode));
		s->data=i;
		p->next=s;
		p=p->next;
	}
	p->next=head;            
	for(i=1;i<=n-1;i++)
	{
		int j;
		for(j=0;j<m-1;j++)
		{
			p=p->next;
		}
		printf("%d ",p->next->data);
		p->next=p->next->next;
	}
	printf("%d",p->data);
	return 0;
}