#include <iostream>
using namespace std;

typedef struct Monkey {
	int MonkeyNum;//猴子的編號
	struct Monkey * next;//指向下一個猴子
	struct Monkey * pre;//指向前一個猴子
} MonkeyNode;//創建猴子的循環鏈表節點

int MonkeyNumber,CountNumber;//用于存儲輸入的猴子數目和選擇數字

int main()
{

	MonkeyNode * CreatMonkeyCircle(MonkeyNode *,int);//創建循環鏈表函數
	int	SelectTheKing(MonkeyNode *,int);//選大王函數
	cout<<"請輸入猴子數目：";
	cin>>MonkeyNumber;
	cout<<"\n請輸入所數數字：";
	cin>>CountNumber;

	cout<<endl<<endl;
	MonkeyNode *Start=NULL;

	Start=CreatMonkeyCircle(Start,MonkeyNumber);//創建循環雙向鏈表，并將編號為1的猴子節點返回給Start保存
	SelectTheKing(Start,CountNumber);
	return 0;
}

//創建循環鏈表 start標記鏈表創建的開始位置，Num標記鏈表的節點個數
MonkeyNode * CreatMonkeyCircle(MonkeyNode *start,int Num)
{
	start=new MonkeyNode;//創建第一個節點
	start->MonkeyNum=1;
	start->next=start->pre=NULL;
	MonkeyNode *cur;//創建鏈表的游歷指針，指向當前以創建的節點
	MonkeyNode *p;//指向當前正在創建的節點
	cur=start;//將游歷指針指向第一個節點
	for(int i=2;i<=Num;i++) {//從第二個節點開始創建循環雙向鏈表
		p=new MonkeyNode;
		if(!p)
			exit(-2);
		p->MonkeyNum=i;
		p->next=NULL;//當前節點指向下一個節點的指針初始化
		p->pre=cur;//將當前正在創建節點指向上一個已創建好的節點
		cur->next=p;//將上一個已創建好的節點的指向下一個節點的指針指向當前正在創建的節點
		cur=cur->next;//游歷指針后移

	}
	cur->next=start;//循環鏈表收尾,最后一個創建的節點的next指針指向第一個節點
	start->pre=cur;//第一個節點的pre指針指向最后一個節點

	return start;//返回循環鏈表的第一個節點
}

int SelectTheKing(MonkeyNode *start,int CountNum) 
{
	int count=0;//計數變量，存儲已經淘汰的猴子的數目
	int CurNum;//在求模操作中，保存模數
	int MonkeyDel;//存儲當前數數過程淘汰的猴子編號
	MonkeyNode * curT;//游歷指針，
	MonkeyNode *q;//臨時指針，指向被淘汰節點，方便釋放內存
	curT=start;//將游歷指針指向第一個節點

	while(curT->next!=curT)//如果當前節點的next指針指向其本身，即只剩下一個節點時，大王選出，循環結束
	{
		CurNum=CountNum%(MonkeyNumber-count);//將所數數字對當前循環鏈表中節點數求模

		if(CurNum==0) {//如果模數為0，則逆序移至一個節點，該節點即被數到節點
			curT=curT->pre;
		}
		else {//如果模數不為0，則順序查找至所數節點

			while(CurNum!=1){
				CurNum--;
				curT=curT->next;
			}
		}

		//將被淘汰節點的前后兩節點連接起來，然后取出被淘汰節點中猴子編號，并釋放該節點
	
		curT->next->pre=curT->pre;
		curT->pre->next=curT->next;
	
		q=curT;
		curT=curT->next;
		MonkeyDel=q->MonkeyNum;
		delete q;


		count++;//淘汰猴子數目加1
		cout<<"\t\t編號為\t"<<MonkeyDel<<"的猴子被淘汰"<<endl;
	}
	//循環鏈表中只剩下一個節點，大王選出
	cout<<"\n\n\t\t猴大王為"<<curT->MonkeyNum<<"!"<<endl;
	return 0;
}