Question

猴子选大王的编程，数据结构方法

Answer 1

如果给好评的话，麻烦写一句：
章鱼桶是个好人

不确定具体题目，从网上摘抄来的题目：

　　山上有n只猴子要选大王,选举办法如下：所有猴子从1到n进行编号并围坐一圈,从第一号开始按顺序1,2,...m继续报数,凡是报m号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。

这个题目是循环链表的应用，循环链表参见：

http://baike.baidu.com/view/178643.htm

#include <stdio.h>
#include <stdlib.h>
struct CircularLinkedListElement
{
 int position;
 CircularLinkedListElement* next;
};
int main(void)
{
 /*
 变量声明
 */
 int n,m;
 int i;
 CircularLinkedListElement* start;
 CircularLinkedListElement* p;
 CircularLinkedListElement* q;
 int step;
 /*
 读入猴子数量n，以及淘汰的号码m
 注意输入的是正整数，为了满足一般从0开始计数的规律，读入后将n、m均减一
 */
 printf("Please enter monkeys number n: ");
 scanf("%d",&n);
 n--;
 if(n<=0)
 {
  fprintf(stderr,"**Error: Monkey's number should be positive.\n");
  return 1;
 }
 printf("Please enter obsolete number m: ");
 scanf("%d",&m);
 if(m<=0)
 {
  fprintf(stderr,"**Error: Obsolete number should be poistive.\n");
  return 1;
 }
 m--;
 
 /*
 创建循环链表
 */
 start=(CircularLinkedListElement*)malloc(sizeof(CircularLinkedListElement));
 if(start==NULL)
 {
  fprintf(stderr,"**Error: malloc error.\n");
  return 1;
 }
 start->position=0;
 start->next=NULL;
 p=start;
 for(i=1;i<=n;i++)
 {
  q=(CircularLinkedListElement*)malloc(sizeof(CircularLinkedListElement));
  if(q==NULL)
  {
   fprintf(stderr,"**Error: malloc error.\n");
   return 1;
  }
  q->position=i;
  q->next=NULL;
  p->next=q;
  p=q;
 }
 p->next=start;
 
 /*
 开始淘汰猴子
 */
 step=1;
 while(start->next!=start)
 {
  printf("#step %d\n",step++);
  printf("Current monkeys: ");
  p=start;
  while(p->next!=start)
  {
   printf("%d ",p->position+1);
   p=p->next;
  }
  printf("%d\n",p->position+1);
  p=start;
  for(i=0;i<(m-1);i++)
   p=p->next;
  q=p->next;
  p->next=q->next;
  start=q->next;
  printf("Obsolete monkey is: %d\n",q->position+1);
  free(q);
 }
 /*
 输出猴王
 */
 printf("The monkey king is %d.\n",start->position+1);
 return 0;
}

 英文系统，所以输出都写的是英文，见谅