#include<stdlib.h>
#include<iostream.h>

//構件鏈表數據結構
typedef struct Node
{
	int Num;											//約瑟夫環成員所在的位置
	int Pwd;											//約瑟夫環成員的密碼
	struct Node *Next;									//鏈表的下一成員的指針
}ListNode;
typedef ListNode *LinkList;

//建立約瑟夫環成員的循環鏈表
LinkList BuildYSFCircle(int _Member)
{
	LinkList Head;										//Head為頭節點的指針
	LinkList Prev;										//Prev為當前指針的前一指針
	LinkList Now;										//Now為當前指針
	Head = (LinkList)malloc(sizeof(ListNode));			//分配Head內存空間
    Prev = Head;
    for(int i = 1;i < _Member;i++)
	{
		Now = (LinkList)malloc(sizeof(ListNode));
		Prev -> Next= Now;
		Prev = Now;
	}
	Now -> Next = Head;									//頭指針與尾指針相連建立循環鏈表
	Now = Head;
	Prev = Head;
	return (Head);										//返回鏈表斗指針
}

//輸出各人的編號
void PrintYSFCircle(int _Member,LinkList _Head,int _Count)
{
	LinkList Prev;										//Prev為當前指針的前一指針
	LinkList Now;										//Now為當前指針
	Prev = _Head;
	for(int i = 1;i <= _Member;i++)
	{
		for(int a = 1;a < _Count;a++)					//按密碼獲取當前節點
		{
			 Prev = Prev -> Next;
		}
		Now = Prev -> Next;								
		_Count = Now -> Pwd;							//獲取訪問的當前節點的密碼
		cout<<Now -> Num;								//打印訪問的當前節點
		Prev -> Next = Now -> Next;						//刪除訪問的當前節點
		free(Now);										//釋放訪問的當前節點空間
		Now = Prev; 
	}
}

//輸入個人的密碼
void InputYSFCirclePwd(int _Member,LinkList _Head)
{
	int Pwd;											//約瑟夫環成員的密碼
	LinkList Next;										//定義約瑟夫環頭當前下一指針
	Next = _Head;										//初始化約瑟夫環頭當前下一指針
    cout<<"請輸入約瑟夫環成員的密碼:"<<endl;			//輸出控制臺信息
    for(int i = 1;i <= _Member;i++)						//輸入約瑟夫環成員的密碼
	{
		cin>>Pwd;
		Next ->Num = i;
		Next -> Pwd = Pwd;
		Next = Next -> Next;
	}
	Next = _Head;
}

void main()
{
	int Count;											//第一次報數的間隔
	int Member;											//約瑟夫環成員的個數
	LinkList YSFhead;									//定義約瑟夫環頭指針
	YSFhead = (LinkList)malloc(sizeof(ListNode));		//分配指針內存空間
	cout<<"請輸入約瑟夫環成員的個數:"<<endl;			//輸出控制臺信息
	cin>>Member;										//從控制臺獲得約瑟夫環成員的個數
	cout<<"請輸入約瑟夫環第一次報數的間隔:"<<endl;		//輸出控制臺信息
    cin>>Count;											//從控制臺獲得約瑟夫環第一次報數的間隔
	YSFhead = BuildYSFCircle(Member);					//建立約瑟夫環成員的循環鏈表
	InputYSFCirclePwd(Member,YSFhead);					////從控制臺獲得約瑟夫環成員的密碼
	cout<<"輸出的位置排列為："<<endl;					//輸出控制臺信息
	PrintYSFCircle(Member,YSFhead,Count);				//打印約瑟夫環成員排列的位置
	cout<<endl;
}