数据结构猴子选王问题.doc

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类型的变量。四、算法设计 头文件说明 #include 此程序主要以C语言为编写语言，因此在程序中要用到系统提供的标准库函数中的输入，输出函数，例如：scanf()函数,printf()函数。所以必须在程序开头一行写上#include。 #include 在这个程序中，用到的主要是数据结构中的循环单链表方面的相关知识。我们把由一个数据元素域及一个或若干个指针域组成的结构体称为一个结点。而在单链表中的每个结点，实在需要时才向系统申请的，也就是所谓的动态内存空间申请。动态申请的内存空间，当不再需要时，必须由申请者自己释放。C语言提供了动态申请内存空间的函数malloc（）和动态释放内存空间的函数free（）。这些函数都包含在头文件malloc.h中。所以也必须在程序开头写上#include。 例如：head=q=p=(monkey *)malloc(sizeof(monkey)； 这一句就是申请占用字节个数为sizeof(monkey)的monkey类型的一个结点，并且让head，q，p三个指针同时指向这个结点。 main() 主程序，包括输入输出和主要函数的调用。调用 Link_solve() 用链表解决这个问题的方法。调用Array_solve() 用数组解决这个问题的方法。 typedef int DataType; 我们都知道，没有实际含义的数据元素称作抽象数据元素。在设计时遇到抽象数据元素，我们将用DataType表示该抽象数据元素的数据类型；而当软件设计问题具体确定时，抽象数据元素的数据类型将被具体的数据类型所取代。在本程序中，要求线性表的数据类型为int类型，可以通过重新定义抽象数据元素为int类型，来确定该抽象数据元素的数据类型。 循环链表：首先生成一个空链表，并给n个结点分配空间，让单链表的表尾指针指向头结点则生成一个带有n个结点的循环单链表。再给每只猴子建立顺序的编号。现从第一个结点开始报数，依次顺序查找出报数为m的待出列的结点（猴子）通过q-next=p-next删除该结点后继续运行否则让q成为p的前驱指针。最后当p-next=p时停止运行，得到p所指向的结点即为猴子选出大王的编号。 数组：定义一个空的数组，有足够多的元素并分配空间。给所有元素赋值为1表示猴子存在。执行for循环，淘汰的猴子赋值为0，直到只剩一只猴子，即为猴王。数组处理输出结果nm,重新输入n主菜单输入m,n选择处理方法链表处理输出结果五、详细程序清单#include #include int m,n; typedef int DataType; typedef struct LNode DataType data; struct LNode *next;monkey;/定义结点void Link_solve() int i; int a=m;int count=1;/统计次数monkey *head,*p,*q,*s;head=q=p=(monkey *)malloc(sizeof(monkey); printf(n* 对猴子进行编号：*n);for(i=1;idata=i; p-next=q;/使链表循环起来p=q;printf(第%d位猴子的编号是：%dn,i,i); printf(第%d位猴子的编号是：%dn,i,i);q-next=head; head-data=m; p=head; q=p-next; printf(n); if(m=1)printf(n按照1个猴子，猴子大王的编号是:1n);else if(m!=1) if(n=1) for(i=1;im;i+) printf(第%d次，要删除的猴子号为:%dn,i,i); printf(n按照%d个猴子，数1个数n猴子大王的编号是:%d n,m,m); else for(i=1;inext;q=q-next; if(i=n-1) printf(第%d次,要删除的猴子号为:%dn,count+,q-data);s=q; q=q-next;/q即为被点到的猴子p-next=q;/删除q结点free(s);/释放内存 i=0;/计数器清零，重新开始计数a-; if(a=1) break; printf(n按照%d个猴子，数%d个数n猴子大王的编号是:%d n,m,n,q-data); /此时的结点就是大王 void Array_solve()int a1000;/定义一个较大的数组存储数据int x,count=1,y,i;printf(n* 对猴子进行编号：*n);for(i=0;im;i+)ai=1; printf(n第%d位猴子的编号是：%d,i+1,i+1); printf(nn);x=0;/令x初始值为零y=m;for(i=0;y!=1;i+)/ 执行循环，淘汰的猴子值为0，直到只剩一只猴子，即为猴王 if(ai%m!=0)x+;/计数加1if(x=n&ai%m!=0)ai%m=0;x=0;printf(第%d次，要删除的猴子号为：%dn,count+,i%m+1);y-;/当前的猴子数减1 for(i=0;i=m;i+) /输出值不为0的猴子，即猴王if(ai!=0)printf(n按照%d个猴子，数%d个数n猴子大王的编号是:%d n,m,n,i+1);void main() int select;int x; for(x=0;x19;x+) printf(=); printf(n); printf(t猴子选王问题求解tn); for(x=0;x19;x+) printf(=); printf(nn);printf(* 请输入猴子的总数 m : );scanf(%d,&m);printf(n); printf(* 请输入周期数 n : );do scanf(%d,&n); printf(n); if(mn) printf(m应该大于n，请重新输入n：); while(mm重新输入n七心得体会 本次数据结构课程设计是运用所学知识，锻炼实际解决问题的能力，是对学生实际对数据结构掌