数据结构猴子选王问的题.docVIP

2015年《数据结构与算法》课程设计 学 院： 数学与信息科学学院 专 业： 数学与应用数学 班 级： 2013级1班 姓 名： 解坚杰 课题名称： 猴子的选王问题 指导老师： 覃美珍 2015年 8 月 22 日 目录 一、问题的描述----------------------------------- 二、问题分析------------------------------------- 三、数据结构描述--------------------------------- 四、算法设计------------------------------------- 五、详细程序清单--------------------------------- 六、程序运行结果--------------------------------- 七、心得体会------------------------------------- 八、参考资料------------------------------------- 猴子选王问题 一、问题的描述 猴子选王问题求解： 一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 【基本要求】 (1)利用单循环链表作为存储结构模拟此过程； (2)输入数据：输入m,n, m,n 为整数，nm； (3)输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能。 【选做内容】 (1)添加在顺序结构上实现的部分； (2)界面设计的优化。 二、问题的分析 对题意进行分析后，可以画出整个过程的流程图。 具体流程图: 这个问题属于约瑟夫环问题，我们对这个题目进行具体分析： 假如现在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只猴子设计程序 三、数据结构描述 以数据结构（C语言）中的循环单链表为主要的设计支柱，利用了C语言简洁紧凑、灵活方便，语法限制不太严格，程序设计自由度大，生成目标代码质量高，程序执行效率高等方面的优点。循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环，基于这样的特点，它适合处理具有环形结构的数据元素序列。 typedef struct LNode{ int data; struct Lnode *next; }monkey; 算法函数中定义了单链表的结构体struct LNode，其中data域用来存放数据素，next域用来存放一个结点的指针。monkey是struct LNode类型的变量。 四、算法设计 ①头文件说 #includestdio.h 此程序主要以C语言为编写语言，因此在程序中要用到系统提供的标准库函数中的输入，输出函数，例如：scanf()函数,printf()函数。所以必须在程序开头一行写上#includestdio.h。 ② #includemalloc.h 在这个程序中，用到的主要是数据结构中的循环单链表方面的相关知识。我们把由一个数据元素域及一个或若干个指针域组成的结构体称为一个结点。而在单链表中的每个结点，实在需要时才向系统申请的，也就是所谓的动态内存空间申请。动态申请的内存空间，当不再需要时，必须由申请者自己释放。C语言提供了动态申请内存空间的函数malloc（）free（）。这些函数都包含在头文件malloc.h中。所以也必须在程序开头写上#includemalloc.h。 例如：head=q=p=(monkey *)malloc(sizeof(monkey))；