数据结构课程设计 猴子选王.doc

实验报告班级： 姓名: 学号：日期:课题四：猴子选大王一问题:一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。二.功能要求： 1输入数据：输入m,n m,n 为整数，n=0数据关系：R1=|ai-1,aiD,I=2,，n基本操作：InitList(&L)操作结果：构造一个空的线性表L。DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。ClearList(&L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TURE,否则返回FALSE。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中数据元素个数。GetElem(L,i,&e)初始条件：线性表L已存在,1=i=ListLength(L)。操作结果：用e返回L中第I个数据元素的值。locateElem(L,e,compare()初始条件：现行表L已经存在，compare()是数据元素判定函数。操作结果：返回L第一个与e满足关系compare()得的数据元素的序位。若这样的数据元素不存在，则返回值为零。PriorElem(L,cur_e,&pre_e)初始条件：线性表L已经存在。操作结果：若cur_e是L的数据元素，且不是第一个，则用 pre_e返回它的前驱，否则操作失败，pre_e无定义。NextElem(L,cur_e,&next_e)初始条件：现性表L存在.操作结果：若cur_e是L的数据元素，且不是最后一个，用next_e返回它的后继，否则操作失败，next_e无定义。ListInsert(&L,I,e)初始条件: 现性表L存在，1=I=ListLength(L)+1. 操作结果：在L中第i个位置之前插入新的数据元素 e,L的长度加1.ListDelete(&L,I,&e)初始条件：现性表L已存在且非空，1=I循环链表模块节点结构单元模块四详细设计#include #include typedef struct lnode /定义一个循环链表L int num; struct lnode *next; node,*L; Void xuanwang( )getchar(); l=(L)malloc(sizeof(node); /设立好循环链表的头节点 l-next=NULL; l-num=0; q=l; i=0; while(i+next=NULL; p-num=i; q-next=p; q=p; q-next=l-next; /形成了循环链表，实现了单向循环链表的建立 p=l-next; q=l; /然后进行以n为周期的一次删除节点，直到链表中只有最后一个节点为止 i=1; /使用i作为计数器，用以表示被删除的节点的数量，当I=m-1时删除结束 while(i+=m) c=1; /c表示循环的临时变量 while(c+next; q=q-next; /顺时针向后进行查找直到p指向第n个节点，然后将当前p所指向的节点找出 q-next=p-next; p=p-next; printf(第%d个猴子为大王n,p-num);/输出大王的位置 void main() int n,m,i,c; L p,l,q; printf(一共有多少个猴子竞选大王？输入m的值：n); /输入总的猴子个数scanf(%d,&m); getchar(); printf(第几个猴子退出竞争？输入N的值：n); scanf(%d,&n); /输入循环的周期xuanwang( );函数的调用关系：Mainxuanwang（）五调试分析:1.构造循环连表时忘记对其定义一个头节点导致程序无法运行。2.在编程的过程中将m和n的位置颠倒了，造成结果完全错误。3.定义的变量值过少，导致在使用中又要重新定义变量。4.在如何退出循环的选择当中 ，刚开始是没有定义计数器，直接使用，这会显得非常麻烦，改进方法之后使用了计数器的方法，用来记录删除节点的个数的次数，然后对其进行判断，直到连表中只剩下最后一个节点就结束循环，得到相应的节点的顺序5.本程序的结构比较清晰简单，主要是构造好一个单向循环链表，用每个节点代表一个猴子，使用删除节点的方式一次淘汰掉竞争的猴子，选出大王。6.算法的时空分析：1） 程序中所使用的链表是单向的循环链表，设置了头指针和链表长度，并且头指针是按照周期变化的，各种操作的算法时间度是比较合理的，由于在对单向循环链表删除节点的操作一共使用了（m-1）次，并且每一次删除节点的执行过程中又要进行n次的判断查找，所以它的时间复杂度为：O(m-1)*n)。六.用户手册:1.本程序的运行环境为DOS操作系统,执行文件为:hzxw.cpp。2进入演示程序后即显示用户界面：一共有多少个猴子竞选大王：第几个猴子退出竞争：输入总的猴子数即m的值输入周期数即n的值操作结果3在出现“一共有多少个猴子仅选大王”时输入总的猴子的数量即m的值，按回车键，再根据提示输入n的值，再按回车键，索要的结果就出来了即位当大王的