下载文档原格式
数学与计算机学院课程设计说明书课程名称: 数据结构课程设计课程代码: 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指导教师签名日期年月日系主任审核日期年月日目录摘要................................. 错误！未定义书签。
数据结构课程设计报告题目：猴子选大王院（系）：计算机工程学院专业：计算机科学与技术班级：嵌入式109（1）学生：秦姚指导教师：寇海洲孙成富邱军林殷路2010年12月目录一、设计目的 (1)二、设计内容 (1)三、程序设计步骤 (1)四、调试分析 (5)五、测试结果 (5)六、课程设计小结： (6)一、设计目的1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，分析并正确确定数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。
2、提高程序设计和调试能力。
学生通过上机实习，验证自己设计的算法的正确性。
学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。
3、初步掌握软件开发过程中问题分析、系统设计、程序编码、测试等基本方法和技能。
4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。
5、培养根据选题需要选择学习书籍，查阅文献资料的自学能力。
二、设计内容1、系统名称：猴子选大王按照规定的要求，选出最后的一只猴子，为大王。
2、要求：一堆有编号的猴子，编号为1，2，3……m，这群猴子（m个）按照1-m的顺序围坐一圈，从第一开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中剩下最后一只猴子，则该猴子为大王。
三、程序设计步骤1）功能分析说明图：2）采用主要的数据结构类型。
采用了链表的存储方式，属于链接存储结构。
for(i=1;i<n;i++) //建立链表的存储结构{p=(LINK)malloc(sizeof(Monkey));p2->next=p;p2=p;}以下是用于存储结点的结构体的定义:typedef struct monkey{int num;struct monkey *next;} Monkey,*LINK;基本算法：这个算法的主要流程为：从控制台读取猴子的数量和报数的最大数——>对猴子进行编号，并用链表来存储——>让链表中的猴子进行报数，对于报数为m的猴子则从链表中删除——>当链表中只剩下一个报数后则停止这个过程，这最后一个猴子即选出来的大王。
#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;}}。
上海应用技术学院课程设计报告课程名称《数据结构课程设计》设计题目猴子选大王；建立二叉树；各种排序；有序表的合并；成绩管理系统；院系计算机科学与信息工程专业计算机科学与技术班级姓名学号指导教师日期一.目的与要求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) 尚未解决的问题或改进方向尚未解决的问题：该成绩管理系统还存在不少缺陷，而且它提供的功能也是有限的，只能实现学生成绩的输入、输出、删除、插入。
《数据结构》课程设计题目(程序实现采用C语言)题目1：猴子选王（学时：3）一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。
题目2：字符逆转（学时：3）从键盘读入一个字符串，把它存入一个链表（每个结点存储1个字符），并按相反的次序将字符串输出到显示屏。
题目3：工资核算（学时：3）设有一个单位的人员工资有如下信息：name、department、 base pay、allowance、total。
现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的base pay增加100元，增加后将工资数据显示于屏幕(每行1人)。
题目4：满足条件的有序表生成（学时：3）已知三个有序表A、B、C，它们皆由同一类元素构成，现要求对于表A作以下运算而获得有序表D：排出A中所有的既在B中又在C中出现的元素。
另外该任务要求具有建立有序表功能以及输出有序表到屏幕的功能。
题目5：一元多项式的减法（学时：6）设有两个一元多项式A(x),B(x)，请完成运算A(x)+B(x)、A(x)-B(x)，要求多项式采用链表进行存储。
另外该任务要求具有建立多项式链表以及输出多项式到屏幕的功能。
题目6：床位分配（学时：6）某客店有N个等级的房间，第k级客房有A（k）个，每个房间有B（k）个单人床，以菜单调用方式设计为单身旅客分配床位以及离店时收回床位的程序。
要求分配成功时，印出旅客姓名、年龄、性别、到达日期、客房等级、房间号及床位号；分配不成功时，允许更改房间等级，若不更改等级，印出“满客”提示。
题目7：文本文件单词的检索及计数（学时：6）要求编程建立一个文本文件，每个单词不包括空格及跨行，单词由字符序列构成且区分大小写，完成以下功能：统计给定单词在文本文件中出现的总次数、检索输出某单词在文本文件中首次出现的行号及位置。
引言概述:数据结构猴子选大王（二）是继第一部分后的深入探讨。
本文将详细介绍猴子选大王问题的背景和相关算法，探讨不同数据结构在解决该问题时的优劣，并提出一种性能更高的改进算法。
通过对本文的阅读，读者将对数据结构在解决复杂问题中的应用有更深入的理解。
正文内容：一、背景介绍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不同数据结构的比较：循环链表适用于猴子选大王问题的普遍情况，而队列作为改进算法可以在处理大规模数据时提高效率。
五、总结本文详细介绍了数据结构猴子选大王（二）的相关算法和背景，在对循环链表和基于队列的改进算法进行比较后，提出了一种性能更高的改进算法。
一. 需求分析：猴子选大王是一个小游戏，其规则是：假设n个猴子围成一堆，取数字m为将要被淘汰的数字，从第一个猴子开始数，数到数字m时，则该猴子出列，被淘汰，然后从被淘汰的猴子的下一个开始数，再数到数字m时，这个猴子也被淘汰，从下一个开始数，依次进行，直到剩下一个猴子结束。
该猴子即猴子大王。
二. 概要设计：该程序没有抽象数据类型，主要用循环和数组实现，先用数组存放猴子，假定一个猴子的最大个数，再通过参数传递一个正确的猴子（将要做游戏的猴子数），先将猴子初始化为0，用一个计数器存countone存放剩余的猴子的个数，用sum存放数字，即从1到m 的数字，当countone>0时，进行循环，先将countone记为0，当循环等于m时，一次循环结束，否则countone加1，依次进行第二次的循环，直到剩下一个猴子为止，并记下当m！sum是的猴子，为幸运猴子大王。
三. 详细设计：int choose(int num,int del) //num表示猴子总数，del表示将要被淘汰的猴子总数{for(i=0;i<num;i++)a[i]=1; //猴子初始化，为1表示还有希望被选为大王while(countOne>1) //是否进行继续淘汰的判断，其中放剩余的猴子个数{countOne=0;for(i=0;i<num;i++){sum+=a[i];if(sum==del) //del同时也记录了每次数数的结束sum=a[i]=0; //淘汰倒霉猴子；countOne+=a[i]; //是和if相匹配语句，当判断条件不成立时执行}for(i=0;i<num;i++)if(a[i]!=0)return i; //找到幸运猴子编号（从0开始的）；}void main(){int num,del;cout<<"请输入猴子总数和淘汰数字：";cin>>num>>del;cout<<"第"<<choose(num,del)+1<<"个猴子为王！"<<endl;}四.调试分析:输入猴子总个数，在输入将要淘汰的猴子的个数时，能正确输出所选的大王猴子，调试正确无误。
