Question

数据结构猴子选大王问题

一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。输入数据：输入m,n ；m,n 为整数，n<m，输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能
要求：1、要有必要的注释；2、 实验设计总结：包括 : 课程设计 过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容；3、具体的算法实现步骤（流程图就更好了）；写的好的还可以再加分
也可在此程序上直接注释一下和修改只输出获胜的编号而不是全部输出：
#include<iostream.h>
struct Node
{ int data;
Node *pNext;};
void main()
{ int n,k,m,i;
Node *p,*q,*head;
cout<<"输入n的值:"; cin>>n;
/*cout<<"输入起始报数人号码k的值:"; cin>>k;*/
k=1;
cout<<"输入数到m出列的m的值:"; cin>>m;
head=(Node*)new Node;
p=head;
for(i=1;i<=n-1;i++)
{ p->data=i;
p->pNext=(Node*)new Node;
p=p->pNext; }
p->data=n;
p->pNext=head;
p=head;
while(p->data!=(p->pNext)->data)
{ while(p->data !=k)
p=p->pNext;
if(m==1)
{ for(i=1;i<=n;i++)
{ cout<<p->data<<'\t' ;
p=p->pNext ; }
cout<<'\n';
return; }
else for(i=1;i<m-1;i++)
{p=p->pNext;}
q=p->pNext;
cout<<q->data<<"\t";
k=(q->pNext)->data;
p->pNext=q->pNext;}
cout<<p->data<<'\n';
}

Answer 1

#include <stdio.h>
#include <stdlib.h>
#define n 19
#define m 4

typedef struct monkey
{
int num;
struct monkey *next;
} Monkey,*LINK;

void main()
{
LINK p,head,p2;
int i;
head=p=p2=(LINK)malloc(sizeof(Monkey));//三个指针指向同一块内存

for(i=1;i<n;i++)
{
p=(LINK)malloc(sizeof(Monkey));
p2->next=p;
p2=p;
}

p2->next=head;//把链表的首尾相连
p=head;//p指向了第一个结点

printf("对猴子进行编号！\n");
for(i=1;i<=n;i++)
{
p->num=i;//从第一个结点到最后一个结点依次给猴子编号
printf("%d号猴子：%d\n",p->num,p->num);
p=p->next;
}//循环结束，p指向了最后一个结点

i=0;
p=head;//再把p指向第一个结点

while(1)
{
i++;
printf("%d号猴子报：%d\n",p->num,i);
if(p->next==p)
break;//此为while循环的出口

if(i==m)//if语句中是删除结点的过程
{
i=0;
printf("%d号猴被淘汰\n",p->num);
printf("\n");
p2->next=p->next;//在此删除结点p
p=p2->next;//p指向它的下一个结点
continue;
}
else
{
if(i==m-1)
p2=p;//保存将要退出结点的前一个结点（存到p2中）
p=p->next;
}
}

printf("胜出:%d",p->num);//最后剩下的结点就是获胜的结点

}

这个程序其实就是形成了一个有19个结点的循环链表，当碰到m的时候，用这两句话p2->next=head;p=head删除当前的结点，然后再继续判断。