经典例题如下：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（n个）按照1-n的顺序围坐一圈，从第1开始数，每数到第m个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。请设计算法编写程序输出为大王的猴子的编号。
分析完之后，无非是解决循环到间隔之后的删除指针操作，和循环队列的创建这两个问题
首先来解决循环队列的问题，代码如下（如有错误，还请指正！）：
void add(Node*head)//增加结点
{int num;//定义总数
int count=2;
Node*pd=head;
printf("输入猴子总数\n");
scanf("%d",&num);
pd->d=1;
for(int i=0;i<num-1;i++)//遍历总数创建结点
{Node*pn=(Node*)malloc(sizeof(Node));
pn->d=count++;//分配序号
pn->next=NULL;
pd->next=pn;
pd=pn;
if(num-2==i)
{pn->next=head;//实现循环队列
}
}
}接下来是到一定间隔后的删除指针操作
void search(Node*head)//查找函数
{Node*pd=head;
int interval;//定义间隔
printf("输入间隔\n");
scanf("%d",&interval);
while(pd!=pd->next)
{for(int i=0;i<interval-2;i++)
{pd=pd->next;
}
Node*e=pd->next;
pd->next=e->next;
free(e);//释放删除的空间
e=NULL;//删除找到的结点
pd=pd->next;}
printf("找到的号码为%d",pd->d);//输出找到的结点
}完整代码如下
#include"stdio.h"
#include"stdlib.h"
typedef struct node
{
int d;
struct node*next;
}Node;
Node*ctlist()//创建头指针
{Node*head=(Node*)malloc(sizeof(Node));//分配空间
head->next=NULL;//指针指向空
return head;
}
void add(Node*head)//增加结点
{int num;//定义总数
int count=2;
Node*pd=head;
printf("输入猴子总数\n");
scanf("%d",&num);
pd->d=1;
for(int i=0;i<num-1;i++)//遍历总数创建结点
{Node*pn=(Node*)malloc(sizeof(Node));
pn->d=count++;//分配序号
pn->next=NULL;
pd->next=pn;
pd=pn;
if(num-2==i)
{pn->next=head;//实现循环队列
}
}
}
void search(Node*head)//查找函数
{Node*pd=head;
int interval;//定义间隔
printf("输入间隔\n");
scanf("%d",&interval);
while(pd!=pd->next)
{for(int i=0;i<interval-2;i++)
{pd=pd->next;
}
Node*e=pd->next;
pd->next=e->next;
free(e);//释放删除的空间
e=NULL;//删除找到的结点
pd=pd->next;}
printf("找到的号码为%d",pd->d);//输出找到的结点
}
int main()//执行主函数
{Node*Pd=ctlist();
add(Pd);
search(Pd);
}