数据结构-猴子选大王-课程设计

1、 ?数据结构?课程设计题目：猴子选大王 一、 需求分析： 猴子选大王是一个很古老经典的题目，融知识性、娱乐性与一体，能让人产生较大的兴趣，因此，编写程序实现之是意见很有意思的事情。猴子选大王的问题可以归结为筛选和排序的问题，筛选主要是从一群猴子中，比方M个中每次选出一只猴子，该猴子离开；排序主要是第N只猴子离开后，剩下的猴子要重新编号，继续上面的过程，知道选出猴子大王。为了增强与用户的交互，程序需要一个比拟好的操作界面，用户在其中输入猴子总数M和被淘汰猴子数目游戏规那么数字N，输入要符合要求，即M>N,否那么要提示错误信息；在点了确定以后要弹出信息提示对话框，告知使用

2、者猴子大王的编号。二、 概要设计：1程序中使用的存储结构：Node结构体struct nodeint num;struct node *link; node;结构体指针变量node *head,*p,*q;2由于此题数据元素的个数不可预知，同时对于报完一次之后对于下一次的报数，由于已经排除了一局部猴子，猴子的顺序被打乱，所以使用链表。链表是动态的，可以在需要的时候增长和减少其长度，而静态数据结构数组是在编译时分派内存的，其大小是不可改变的，而且会出现内存浪费的情况。我认为单循环链表能较好的解决问题，在建立循环链表时，因为链表的大小由输入决定，因此与匹配的结点数也是变化的，所以要进行动态内存分配

3、。假设猴子的个数是n，m是要淘汰的编号，那么建立一个n长的链表，链表最后一个元素的next指针指向第一个元素，这样就形成一个循环链表，而链表的数据域储存的就是猴子的编号。3整体流程图如下：开  始输入M的值输入N的值M > N提示输入错误信息要求重新输入输出猴子大王的编号结   束三、 详细设计： 1程序首先定义一个结构体如下，其中num用来指示猴子的编号；结构体类型的指针link放在链表中操作；以及一个结构体变量node; struct nodeint num;struct node *next;2用链表实现课题功能、程序中的异常处理主要放在“确

4、定事件响应中实现：typedef struct node NODE; NODE *create_link_list(int m)int i; NODE *head, *p, *q; /if (m=0) return NULL; head = (NODE *) malloc(sizeof(NODE); p = head; for (i=1; i<m; i+)p->num=i; q=(NODE *)malloc(sizeof(NODE); p->next=q; p=q; p->num=m; p->next=head; return (head); NODE

5、*select_king(NODE *head,int m,int n) NODE *p,*q,*u; int i,d; p=*head;/ printf("The header of the list is %dn",p->num); /指向创立动态链的表头 for(i=m;i>1;i-) / printf("Now，the number of monkey is %dn",i); /检测当前还有多少只猴子 for(d=1;d<n;d+) q=p; p=q->next;/ printf("Monkey %dn"

6、;,q->num); /显示此次参与循环的猴子的编号 u=p->next; q->next=p->next; free(p); p=u; /printf("the next number is %dn",p->num); /显示下一次循环中的第一个猴子编号 return(p); /容易出错点，长返回值不能清楚 3该程序的主程序如下：void main() int a,b; NODE *my_head,*k; printf("请输入猴子个数：n"); scanf("%d",&a); printf(&

7、quot;请输入游戏规那么中的数字：n"); scanf("%d",&b); if(a<1|b<1) printf("您输入的数字超出了规定的范围！n"); else if(b>=a) printf("输入游戏中的数字只能小于猴子个数！n"); else my_head=create_link_list(a); k=select_king(&my_head,a,b); printf("按照这种规那么，猴王的编号是 %dn",k->num); 四、 调试分析：1 程序

8、运行将会出现如下的界面：2 程序输入数据运行后又将会出现如下的界面： 2测试数据  尽可能多的选择几组不同的数据进行测试，并且要对软件进行边缘数据测试猴子总数M游戏规那么数N选出的猴子大王编号523846105312310159153结果分析通过以上数据对程序的测试分析可知，本程序很好地完成了题目的要求，并且增加了许多有趣的功能，对意外情况也处理得比拟到位。程序运行结果正确，性能稳定可靠，界面友好充满活力，具有较高的使用和参考价值。4.调试过程中的问题：在课程设计的过程中，写代码是一个方面，程序的调试才是最重要的，它是一个相当繁琐的过程，有许多新的问题需要被解决；但是同时它

9、也是一个比拟重要的过程，因为在程序调试的过程中你可以学到很多新的知识，从而增加你编程的经验。下面来谈谈调试的问题：1第一个最简单的关于赋值语句的问题，虽然很简单，一说就懂，但是却很容易屡次出错。  在程序中有下面的代码：if (p->link = = p)，刚开始做的时候，写成了if (p->link = p)，错误不太容易发现，主要是混淆了判断语句与赋值语句的区别。查到一个小小的建议，变量和常量比拟时，把常量放在 = = 号的左边，这样如果你错写为 = 时，编译器就会报出禁止为常量赋值的错。因此，好的编程习惯的很重要。2内存空间分配问题在编写语句head = new n

10、ode ；和 q = new node；时，刚开始使用的是C中的malloc，且语法格式也搞错了，屡次调试没有解决，后来突然想起了C+中的new 比拟方便，且自动返回正确的指针类型，于是就采用了，解决了问题。但是，不管是C 的malloc() ，free()；或是C+的 new和 delete都是很费时间的事，所以我们可以想方法减少空间分配和回收的次数来提高效率。一次分配足够的空间，再一次回收，或许是一个很好的想法。3链表的一系列的问题 本程序主要用链表实现，在对链表的操作上还是存在一些问题。 4经典的指针问题 5对算法的分析和改良的思考程序通过循环链表较好的实现

11、了猴子选大王的功能，但是还是有许多值得思考改良的地方。1由于N = 1的情况比拟复杂，程序中对它作了模糊处理，没有复杂化，直接返回猴子的总数作为大王的编号。详细的功能只有留待新版本的时候再去设计实现，是个不小的挑战哦！2无论是用链表还是用数组实现都有一个共同点：要模拟整个过程，不仅程序比拟烦，而且时间复杂度高达O(n*m)，当n，m非常大的时候，几乎是没有方法在短时间算内出结果的。我们注意到原问题仅仅是要求出最后的猴子大王的序号，而不是要模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。为了讨论方便，先把问题稍微改变一下，并不影响原意：问题描述：n个人编号0(n-1)，从0开始

12、报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。 我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环以编号为k=m%n的人开始:k k+1 k+2 . n-2, n-1, 0, 1, 2, . k-2并且从k开始报0。现在我们把他们的编号做一下转换：k -> 0k+1 -> 1k+2 -> 2.k-2 -> n-2k-1 -> n-1变换后就完完全全成为了(n-1)个人报数的子问题，假设我们知道这个子问题的解：例如x是最终的猴王，那么根据上面这个表把这个x变回到x'=(x+k)%n不刚

13、好就是n个人情况的解吗！如何知道(n-1)个人报数的问题的解？只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 - 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：令fi表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是fn递推公式f1=0;fi=(fi-1+m)%i; (i>1)有了这个公式，我们要做的就是从1-n顺序算出fi的数值，最后结果是fn。因为实际生活中编号总是从1开始，我们输出fn+1由于是逐级递推，不需要保存每个fi，程序也是异常简单：#include “Void main()int n, m, i, s=0;print

14、f ("n和m的值是：n ");scanf("%d%d", &n, &m);for (i=2; i<=n; i+) s=(s+m)%i;printf ("猴王是 %dn", s+1);这个算法的时间复杂度为O(n)，相对于模拟算法已经有了很大的提高。可见，适当地运用数学策略，不仅可以让编程变得简单，而且往往会成倍地提高算法执行效率。3课题的要求类似与Josephus环问题，还可以考虑下面的函数  int   Josephus(int   M,int &#

15、160; N)          int i,k;     for(i=2,k=0;i<=M;i+)   / 每次淘汰1个，剩下的个数是2、3、.M        k=(k+N)%i;              /这一句是令牌在i个猴子中传递N次的算法