猴子选大王系统的设计与实现

猴子选大王系统的设计与实现

2. 猴子选大王系统的设计与实现

2.1 问题的描述

一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1--m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

2.2 问题分析和任务定义

（1）输入数据：输入m,n。m,n 为整数，n<m；

（2）输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能。

2.3 数据类型和系统设计

（1）存储结构设计

采用循环链表来存储“猴子的编号”，无需头结点。

（2）系统功能设计

①创建循环链表；

②向单链表中填入猴子的编号；

③找到第一个开始报数的猴子；

④数到n让猴子出列；

⑤接着开始报数，重复第三步；只剩下最后一只猴子；

⑥输出猴子的信息。

2.4 编码实现

#include<stdio.h>

#include<stdlib.h>

（1）定义猴子群的结构体

typedef struct Node

{   int data;   //数据域，用来存储猴子编号

      struct Node *next;//指针域

}Node,*LinkList;

（2）创建一个链表，将猴子编号并入链表中

LinkList CreateList(int n)

{    int i;

      Node *head,*p;//定义两个指针变量

      head=(LinkList)malloc(sizeof(struct Node));

      head->next=head;

      for(i=1;i<n;++i)

      {   p=(LinkList)malloc(sizeof(struct Node));//申请头结点，并赋予空间

             p->next=head->next;

             head->next=p;

      }

      p=head;

      for(i=0;i<n;++i)

      {   p->data=i+1;

             p=p->next;

      }

      return head;//返回头指针

}

（3）循环遍历链表

int LinkedList(LinkList head,int num_monkey,int number)

{    int j=1,k;

      Node *p=head,*q;

      for(;num_monkey>1;num_monkey--)

      {            k=1;

             while(k!=number)

             {     p=p->next;

                    k++;

             }

             printf("第%d个出队列的是%d号猴子,n",j++,p->data);

             p->data=p->next->data;

             q=p->next;

             p->next=p->next->next;

      }

      return p->data;

}

（4）主函数

int main()

{    int m,n,king;

      printf("请输入猴子个数：");

      scanf("%d",&m);

      LinkList head=CreateList(m);

      printf("请输入要报的数：");

      scanf("%d",&n);

      king=LinkedList(head,m,n);

      printf("%d号猴子是大王n",king);

}

2.5 测试结果

筛选过程及结果，如图