下载文档原格式
1.需求分析问题定义：一堆猴子都有编号，编号是1，2，3…n,这群猴子（n个）按照1-n的顺序围坐一圈，从第1个开始数，每数到第m个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
m，n键盘输入，且m<n，输出为大王的猴子的号数。
问题分析：根据任务描述可知，编号是1，2，3…n的一群猴子按照1-n的顺序围坐一圈，因此可以用指针指向数组的方法给数组赋值，输入n值和m值，为保证m<n，用一个while( )#include<stdio.h>#include<stdlib.h> //使用calloc()函数void FindKing_pointer(int,int,int*);//移动指针法找大王void Initialize(int,int*);//初始化数组整形和指针型int main(){int m,n,*ptr;printf("输入猴子数与出局时报的数\n");scanf("%d %d",&n,&m);while(n<m){printf("输入数据有误，请重新输入!\n"); printf("输入猴子数与出局时报的数\n"); scanf("%d %d",&n,&m);}ptr=(int *)calloc(n,sizeof(int));Initialize(n,ptr);FindKing_pointer(m,n,ptr);free(ptr);return 0;if(ptr2==ptr+n)ptr2=ptr;/*指针所指元素不为0时计数器加1.*/if(*ptr2!=0)i++;/*计数器数到m时将指针所指元素设为0*/ if(i==m){*ptr2=i=0;count--; //用于终止循环}}/*最后不为0的元素的值即为大王的编号*/for(ptr2=ptr;;ptr2++){if(*ptr2!=0){printf("第%d个猴子是大王\n",*ptr2);break;}}}/*思想是猴子围坐一圈，有N个猴子，开始数数，数到第M个猴子，该猴子就出列，然后再从该猴子的下一个猴子开始数到第M个猴子，直到只剩下一个猴子时。
数学与计算机学院课程设计说明书课程名称: 数据结构课程设计课程代码: 6014389题目: 猴子选大王年级/专业/班: 2010级软件工程2班学生姓名: 蒋童学号:开始时间: 2011 年11 月9 日完成时间: 2011 年12 月30 日课程设计成绩：指导教师签名：年月日数据结构课程设计任务书学院名称：数学与计算机学院课程代码：__ 6014389______ 专业：软件工程年级：2班一、设计题目猴子选大王二、主要内容一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
三、具体要求及应提交的材料要求：使用数组和循环链表等两种以上的存储方式来做输入数据：输入m,n m,n 为整数，n<m输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能用C/C++语言编程实现上述内容，对每个问题写出一个算法实现，并按数学与计算机学院对课程设计说明书规范化要求，写出课程设计说明书，并提交下列材料：1)课程设计说明书打印稿一份2)课程设计说明书电子稿一份；3)源程序电子文档一份。
四、主要技术路线提示可采用数组、链表数据结构实现。
在此基础上用C/C++实现其操作。
五、进度安排按教学计划规定，数据结构课程设计为2周，其进度及时间大致分配如下：六、推荐参考资料[1] 严蔚敏，吴伟民.数据结构.清华大学出版社出版。
[2] 严蔚敏，吴伟民. 数据结构题集(C语言版) .清华大学出版社.2003年5月。
[3] 唐策善，李龙澎.数据结构(作C语言描述) .高等教育出版社.2001年9月[4] 朱战立.数据结构(C++语言描述)（第二版本）.高等出版社出版.2004年4月[5] 胡学钢.数据结构(C语言版) .高等教育出版社.2004年8月[6] 徐孝凯等著.数据结构（C语言描述）.清华大学出版社.2004指导教师签名日期年月日系主任审核日期年月日目录摘要................................. 错误！未定义书签。
#include<stdio.h>#include<stdlib.h>struct Monkeyking{int data;struct Monkeyking *next;};void main(){struct Monkeyking *head, *s, *q, *t,*p,*h;int n, k, count=0, i,j;printf("输入猴子总数:");scanf("%d",&k);printf("\n");printf("输入报号起始猴子编号:");scanf("%d",&j);printf("\n");printf("输入报号间隔数:");scanf("%d",&n);printf("\n");for(i=0; i<k; i++){s=(struct Monkeyking *)malloc(sizeof(struct Monkeyking)); s->data=i+1;s->next=NULL;if(i==0){head=s;q=head;}else{q->next=s;q=q->next;}}//建立一个单链表q->next=head;//将单链表组成环状printf("输出猴子原始的编号:");q=head;while(q->next!=head){printf("%d ",q->data);q=q->next;}//依次输出节点的值printf("%d ",q->data);printf("\n");printf("\n");q=head;for (i=0;i<j;i++){p=q;q=q->next;}q=p;printf("输出被淘汰的猴子编号:");if (n==1){for (i=1;i<=k;i++){t=q;q=q->next;t->next=h;h=t;}for (i=1;i<=k;i++){printf("%d ",h->data);//倒序输出淘汰猴子的编号，第一个编号为大王h=h->next;}printf("\n");}else{do{count++;if(count==n-1){t=q->next;q->next=t->next;t->next=h;h=t;count=0;}q=q->next;}while(q->next!=q);q->next=h;h=q;}for(i=1;i<=k;i++){printf("%d ",h->data);//倒序输出淘汰猴子的编号，第一个编号为大王h=h->next;}}。
5.4.8 实验项目5-14：猴子选大王1、实验名称：猴子选大王2、实验目的：（1）熟练使用循环控制。
（2）熟练理解和掌握二维数组存储结构的使用技巧。
3、实验任务（1）实验内容：一群猴子要选新猴王。
新猴王的选择方法是：让n只候选猴子围成一圈，从某位置起顺序编号为1~n号。
从第1号开始报数（从1到3），凡报到3的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。
如此不断循环，最后剩下的一只猴子就选为猴王。
请问是原来第几号猴子当选猴王？（2）实验要求：输入一个正整数n（n<=100），写一个程序来模拟这个过程，输出猴王的序号。
测试用例：4、实验要点分析（1）问题分析：用循环的方法模拟选猴王的过程。
一种简单的方法是对n只猴子用1~n 编号，编号存放在大小为n的一维整数数组中，若某编号的猴子要退出圈子，则把其编号改为-1。
若数组中只剩一个非-1的编号时，该编号的猴子就是大王。
开始时数组中的元素是从1到n的整数，表示都在“圈子”中，凡报到3的猴子退出圈子，即置为-1。
再依次查找下一只在“圈子”中的猴子，并重新开始报数。
这个过程进行n-1次，就只剩下一只编号不是-1的猴子了。
这种方法在寻找“下一个在圈子中的猴子”时可能会遇到很多“-1”而浪费时间。
另一种改进的方法是把n只猴子用0~n-1编号，数组的下标表示猴子的编号，数组元素的值表示相邻下一只在圈子中的猴子编号。
比如，n=5时，初始的数组M的内容如下表: 下标：0 1 2 3 4当2号猴子（报数轮到3）退出圈子时，1号猴子的下一只相邻猴子就是3号猴子了，实现时只需一个赋值M[1]=M[2]（即原来2号猴子的下一只相邻猴子成了1号猴子的下一只相邻猴子）。
数组M的内容变成了下表:下标：0 1 2 3 4这样做的好处有两个，一是第i号猴子的下一只相邻猴子就是M[i]，不需要用一个循环去找了；二是不用当心数组M下标的访问会越界。
（2）实现要点：1）循环控制结构。
上海应用技术学院课程设计报告课程名称《数据结构课程设计》设计题目猴子选大王；建立二叉树；各种排序；有序表的合并；成绩管理系统；院系计算机科学与信息工程专业计算机科学与技术班级姓名学号指导教师日期一.目的与要求1. 巩固和加深对常见数据结构的理解和掌握2. 掌握基于数据结构进行算法设计的基本方法3. 掌握用高级语言实现算法的基本技能4. 掌握书写程序设计说明文档的能力5. 提高运用数据结构知识及高级语言解决非数值实际问题的能力表。
3、输出功能：void print(LinkList *head);通过一个while的循环控制语句，在指针p!=NULL时，完成全部学生记录的显示。
知道不满足循环语句，程序再次回到菜单选择功能界面。
4、删除功能：LinkList *Delete(LinkList *head);按想要删除的学生的学号首先进行查找，通过指针所指向结点的下移来完成，如果找到该记录，则完成前后结点的连接，同时对以查找到的结点进行空间的释放，最后完成对某个学生记录进行删除，并重新存储。
5、插入功能：LinkList *Insert(LinkList *head)；输入你想插入的位置，通过指针所指向结点的下移，找到该位置，将该新的学生记录插入到该结点，并对该结点后面的指针下移。
链表长度加一，重新存储。
(5) 程序的输入与输出描述输入：调用LinkList *create()函数，输入学生的姓名、学号、三门功课的成绩；输出：调用void print(LinkList *head)函数，输出学生的记录。
(6) 程序测试主菜单：成绩管理系统的主界面：学生成绩记录的输入：输出学生成绩记录：学生成绩记录的删除（删除学号是1101的学生记录）插入新的学生成绩记录（插入学号为1103的学生记录）(7) 尚未解决的问题或改进方向尚未解决的问题：该成绩管理系统还存在不少缺陷，而且它提供的功能也是有限的，只能实现学生成绩的输入、输出、删除、插入。
《数据结构》课程设计报告题目猴子选大王学生姓名学号专业班级指导老师设计日期 2009年12月19日指导老师评阅意见：一、问题定义1、课程设计目的：数据结构课程设计是学习数据结构课程的一个重要环节。
能巩固和加深课堂教学内容，提高学生实际工作能力，培养科学作风，为学习后续课程和今后的系统开发奠定基础。
通过课程设计，使学生熟练掌握数据结构课程中所学的理论知识，并实际应用，通过综合运用数据结构的基本知识来解决实际问题，加强学生分析和解决问题的能力。
2、课程设计的要求：本次课程设计要求学生正确理解课题，考虑问题要细致，全面，解决问题的方法要科学合理，切合实际。
并能上机实现。
3、课程设计的意义：1、有利于基础知识的理解。
学生对计算机运行的机理等知识内容的理解比较肤浅。
如果接触了程度设计，就能真正理解，从而进一步打破计算机的神秘感。
2、有利于逻辑思维的锻炼。
程序设计是公认的、最能直接有效地训练学生的创新思维，培养分析问题、解决问题能力的学科之一。
即使一个简单的程序，从任务分析、确定算法、界面布局、编写代码到调试运行，整个过程学生都需要有条理地构思，这中间有猜测设想、判断推理的抽象思维训练，也有分析问题、解决问题、预测目标等能力的培养。
3、有利于治学态度的培养。
程序设计中，语句的语法和常量变量的定义都有严格的要求，有时输了一个中文标点、打错了一个字母，编译就不通过，程序无法正常运行。
因此，程序设计初学阶段，学生经常会犯这样的错误，可能要通过几次乃至十多次的反复修改、调试，才能成功，但这种现象会随着学习的深入而慢慢改观。
这当中就有一个严谨治学、一丝不苟的科学精神的培养，又有一个不怕失败、百折不挠品格的锻炼猴子选大王任务：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
引言概述:数据结构猴子选大王（二）是继第一部分后的深入探讨。
本文将详细介绍猴子选大王问题的背景和相关算法，探讨不同数据结构在解决该问题时的优劣，并提出一种性能更高的改进算法。
通过对本文的阅读，读者将对数据结构在解决复杂问题中的应用有更深入的理解。
正文内容：一、背景介绍1.1问题描述:数据结构猴子选大王问题是一个经典的计算机科学问题，它描述了一群猴子按一定规则进行选举的过程。
1.2算法原理：猴子选大王问题可以通过循环链表和递归两种方法进行解决，其中循环链表是最常用的解法。
1.3算法过程：通过将猴子按一定顺序编号，然后循环一个圈，每次淘汰某一编号的猴子，直到只剩下最后一只为止，即为大王。
二、循环链表算法2.1数据结构选择：循环链表是解决猴子选大王问题的主要数据结构。
其特点是每个节点都有一个指针指向下一个节点，且最后一个节点指向第一个节点。
2.2算法流程：在循环链表中，通过不断遍历并淘汰节点，最终得到最后剩下的节点作为大王。
2.3时间复杂度分析：循环链表算法的时间复杂度为O(mn)，其中m是猴子的总数，n是每次淘汰的数量。
三、改进算法3.1基于队列的改进算法：针对循环链表算法中的时间复杂度较高的问题，可以考虑采用队列的数据结构进行改进。
3.2算法优化：通过将猴子的编号依次入队，然后每次从队首取出一个猴子，再将其编号入队尾，直到只剩下一只为止。
3.3时间复杂度分析：改进算法的时间复杂度为O(m)，其中m 是猴子的总数。
四、数据结构选择4.1循环链表的优势：循环链表是解决猴子选大王问题的经典数据结构之一，具有结构简单、操作灵活等优点。
4.2队列的优势：队列是改进算法中的数据结构选择，具有先进先出、操作高效等特点。
4.3不同数据结构的比较：循环链表适用于猴子选大王问题的普遍情况，而队列作为改进算法可以在处理大规模数据时提高效率。
五、总结本文详细介绍了数据结构猴子选大王（二）的相关算法和背景，在对循环链表和基于队列的改进算法进行比较后，提出了一种性能更高的改进算法。
目录一、需求分析 (1)1、问题描述： (1)2、基本要求： (1)3、需求分析： (1)二、概要设计 (2)三、详细设计 (3)1、循环队列 (3)2、循环链表 (4)3、伪代码 (5)4、具体函数分析及变量分析 (6)四、调试分析和测试结果 (6)五、总结 (9)六、参考文献 (10)七、附录 (11)一、需求分析1、问题描述：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
2、基本要求：输入数据：输入m,n。
m,n 为整数，n<m。
输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能。
3、需求分析：①输入数据m,n②计算出最终猴子大王的序号。
③模拟出整个过程。
④找到合适的数据结构处理这个问题。
⑤找到正确的方法解决这个问题。
二、概要设计对题意进行分析后，可以画出整个过程的流程图。
具体流程图:这个问题属于约瑟夫环问题，我们对这个题目进行具体分析：假如现在m=5,n=2,即有5只猴子，按照循环数2的方法，我们演变这个过程：第一次：1 2 3 4 5× 2号出局第二次：1 2 3 4 5×× 4号出局第三次：1 2 3 4 5××× 1号出局第四次：1 2 3 4 5×××× 5号出局最后得到猴子大王的序号是3号。
那么一般化，对于m猴子，n只猴子我们该怎么做？三、详细设计1、循环队列队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。
进行插入操作的端称为队尾，进行删除操作的端称为队头。
队列中没有元素时，称为空队列。
仔细分析整个过程，我发现这个过程和学过的循环队列特别像，在学习循环队列的时候，如果采取数组来存储队列，那么在front端弹出元素就执行front=（front+1)%MAX，在rear端进入队列的时候就执行rear=（rear+1)%MAX，以实现绕圈的操作。
