monkey.cpp

数据结构课设题目。一堆猴子都有编号

#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;
}