/*約瑟夫問題的一種描述是：編號為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


初始密碼m=10；
游戲人數n=8；
8個人的密碼依次是：7,9,5,4,1,2,6,3；
則出列的順序為：2,4,8,5,6,1,3,7
*/

/*源程序如下：其中的clinklist.c為循環單鏈表的結構及其一些基本操作*/

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include "clinklist.c"

void game(CLinkList l)/*元素依次根據密碼值出圈*/
{
	int m,k=0;
	CLNode *p,*pre,*u;
	p=l;
	printf("\nCount Number m==? ");
	scanf("%d",&m);
	printf("\n%40s\n\n","GAME START");
	while(p->next!=p)
	{
		pre=p;
		p=p->next;
		if(p==l) 
		{ 
			pre=p;
			p=p->next;
		}
		k++;
		if(k==m)
		{ 
			printf("%d ",p->i);
			m=p->data;
			pre->next=p->next;
			u=p;
			free(u);
			p=pre;
			k=0;
		}
	}
	printf("\n\n%40s","GAME OVER");
}

void exitgame()
{
	printf("\n\n%40s","GOOD_BYE_GOOD !!");
}


void main()/*主控函數*/
{
	int select;
	CLinkList list;
	init_CLinkList(&list);
	do
	{
		printf("%s%15s%15s%15s%15s","\n\n\n\n\n\n",
			"1:Create",
			"2:Display",
			"3:Game",
			"4:Exit");
		printf("\n\n%33c",' ');
		select=getche();
		switch(select)
		{
		case '1': 
			crt_CLinkList(list);
			disp_CLinkList(list);
			break;
		case '2': 
			disp_CLinkList(list);
			break;
		case '3': 
			game(list);
			break;
		case '4': 
			exitgame();
			break;
		default: 
			printf("\nWrong select ! Try again. ");
		}/*switch*/
	}
	while(select!='4');
	release_CLinkList(list);
	getch();
}

//////////////////////////////////
/*clinklist.c的程序內容如下*/


typedef int ElemType;
typedef struct CLNode
{
	ElemType data;
	ElemType i;
	struct CLNode *next;
} CLNode, *CLinkList;              /*循環單鏈表結構*/

void init_CLinkList(CLinkList *l)/*對循環單鏈表進行初始化*/
{
	(*l)=(CLinkList)malloc(sizeof(struct CLNode));
	(*l)->data=-1;
	(*l)->i = 0;
	(*l)->next=(*l);
}

void clear_CLinkList(CLinkList l)/*對循環單鏈表清空*/
{
	CLNode *p,*useless;
	p=l->next;
	l->next=l;
	while(p!=l)
	{
		useless=p;
		p=p->next;
		free(useless);
	}
}

void crt_CLinkList(CLinkList l)/*輸入數據創建約瑟夫環表*/
{
	int num,n;
	int j;
	CLNode *p,*r;
	clear_CLinkList(l);
	r = l;
	j = 1;
	printf("\nInput the number of people:\n");
	scanf("%d",&n);
	
	while(j <= n)
	{
		printf("Please input the %d people's password:",j);
		scanf("%d",&num);
		p=(CLNode *)malloc(sizeof(struct CLNode));
		p->data=num;
		p->i = j;
		r->next=p;
		r=p;		
		j++;
	}
	r->next=l;
}

void disp_CLinkList(CLinkList l)/*顯示表中元素內容*/
{ 
	int row=1;
	CLNode *p;
	p = l->next;
	printf("\n");
	while(p!=l)
	{
		if(row==7)
		{
			row=1;
			printf("\n");
		}
		printf("%5d:%-5d|",p->i,p->data);
		row++;
		p=p->next;
	}
}

void release_CLinkList(CLinkList l)/*銷毀循環單鏈表（約瑟夫環）*/
{
	clear_CLinkList(l);
	free(l);
}