约瑟夫环

   要求：约瑟夫环的一种描述为：序号为1，2，...，n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数），开始时任选一个数作为报数上限m，从第一个人开始顺时针自1开始顺序报数，报到m时停止报数，报的m的人出列，将他的密码作为新的m值，从他开始在顺时针方向的下一个人开始重新从1报数，如此下去，直至所有人全部出列，请设计一个程序，求出出列顺序。

如：当m的初始值为20，n=7，7个人的密码依次为：3，1，7，2，4，8，4，出列的顺序为6，1，4，7，2，3，5.

思路：因为n个人围坐一圈，所以可以很自然的想到用单向循环链表作为存储结构来模拟此过程，然后按一定的条件删除某个结点，将该结点打印出来。

基于此思路代码如下：

# include<stdio.h>
# include<stdlib.h>
# include<windows.h>
typedef struct people
{
	int order; 
	int password; 
	int nextorder;
	struct people * pnext;
}p,*linklist;
void main()
{
	int n,m;
	printf("请输入人的个数n
");
	scanf("%d",&n);
	int count =0;
	int i=1;
	linklist phead=(linklist)malloc(sizeof(p));
	linklist ptail=phead;
	while(count!=n)//构建约瑟夫环
	{
	
		linklist pnew=(linklist)malloc(sizeof(p));
		pnew->order=i;
		pnew->nextorder=i;
		printf("请输入该人的密码
");
		scanf("%d",&pnew->password);
		ptail->pnext=pnew;
		pnew->pnext=NULL;
		ptail=pnew;
		i++;
		count++;
	}
	ptail->pnext=phead;
	printf("请输入报数上限值m
");
	scanf("%d",&m);
	linklist ptemp=phead;
	linklist pre; 
//	linklist ptemp=phead->pnext;
	int k=0;
	while(ptemp->pnext!=ptemp)//模拟出列过程
	{
		pre=ptemp;
		ptemp=ptemp->pnext;
		if(ptemp==phead) 
		{
			pre=ptemp;
			ptemp=ptemp->pnext;
		}
		k++;
		if(k==m)
		{
			printf("%d ",ptemp->order);
			m=ptemp->password; 
			pre->pnext=ptemp->pnext;
			//linklist p=ptemp;
			free(ptemp);
			//ptemp=pre->pnext;不能这样写，因为头结点phead中无数据，如果是最后一个元素删除了则加1后ptemp到了phead，
			//k=1;			   而phead中无数据所以多算了一步
			ptemp=pre;
			k=0;
		}

	}
}

程序运行结果如下：