)用不带头结点的单向循环链表为存储结构模拟整个过程

来源：百度知道 编辑：UC知道 时间：2024/07/06 00:20:49
n只猴子要选大王，选举方法如下：所有猴子按 1，2 ……… n 编号并按照顺序围成一圈，从第 k 个猴子起，由1开始报数，报到m时，该猴子就跳出圈外，下一只猴子再次由1开始报数，如此循环，直到圈内剩下一只猴子时，这只猴子就是大王。
问题的另一种描述
一个旅行社要从n个旅客中选出一名旅客，为他提供免费的环球旅行服务。旅行社安排这些旅客围成一个圆圈，从帽子中取出一张纸条，用上面写的正整数m(<n)作为报数值。游戏进行时，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人被淘汰出列，然后从他顺时针方向上的下一个人开始重新报数，如此下去，直到圆圈中只剩下一个人，这个最后的幸存者就是游戏的胜利者，将得到免费旅行的奖励。

#include <stdio.h>
#include <stdlib.h>
#define n 5 //宏定义,设定猴子个数
#define m 4 //报数最大报到4
typedef struct monkey //设计一个猴子的结构体,该结构体用monkey表示//link表示该结构体的指针
{
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;
printf("对猴子进行编号！\n");
for(i=1;i<=n;i++)
{
p->num=i; //对猴子编号
printf("%d号猴子：%d\n",p->num,p->num);
p=p->next; //指针指向下个猴子
} //所有猴子编号结束
i=0;
p=head; //又将p指向了链表的头
while(1)
{
i++;
printf("%d号猴子报：%d\n",p->nu