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

选猴王计科专业数据结构A课程设计选猴王作 者 姓 名： 王显衡 专业、班级 ： 计科123 学 号 ： 12422003 指 导 教 师： 赵晶 完 成 日 期： 2013年11月17日 大连大学Dalian University目 录题 目 描 述11、算法思想22、详细设计24 调试分析45 用户使用说明56课程设计总结6参 考 文 献7 题 目 描 述任务：一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：输入数据：输入m,n m,n 为整数，nnext =NULL；（非空表） （空表） 单循环链表2）、函数void hzxdw(M，N)读取数据M、N后,然后就根据N的值，用for循环数猴子结点用a指向开始结点，往后数到第N个结点，就把第N-1个结点与第N+1个结点链在一起，即实现了删除第N个结点。如此反复，直到L的后继结点是它自己，即圈中只剩最后一只猴王。其源代码如下： void hzxdw(int m,int n)/猴子选大王 Mnode *q,*p,*L,*pre; int i; /s作为n的标志 for( i=0; idata=i+1; L=p; p-next=L; else q=(Mnode*)malloc(sizeof(Mnode); q-data=i+1; q-next=L; p-next=q; p=q; p=L;/从第一个猴子开始报数 while(p!=p-next)/当pp-next时表明猴子大王已选出 for(i=1; inext=p-next; p=p-next; free(q); else pre=p; p=p-next; printf(选出的猴王是%d号猴子n,p-data); 本算法只用了两个简单的for循环，所以时间复杂度为O(N+MN-M)。其中难点是如何实现数到第N就删除它。4 调试分析程序运行截图如下：5 用户使用说明用户根据提示输入两个整数，分别代表猴子M总数和报数N。6课程设计总结要提高自己的编程能力，你必须亲自去体验、去设计、编辑、编译、调试、运行。在此之前，我也以为自己对C语言已经比较懂了，可还是遇到了一系列问题，也学到很多东西。每一个人都是在失败、尝试、失败、尝试与收获中成长起来的。我本学识尚浅，无权谈论这些，只是希望能对大家有所警醒，编程之道漫漫无边，吾将上下而求索.当你看着自己把功能一个个实现，把错误一个调试出来，那种感觉给了自己某种安慰，还有自信！让自己对语言有了更深一层的了解！参 考 文 献1 严蔚敏，吴伟民.数据结构（C语言版）。清华大学出版社,1997.4附录一 * 程序代码#include#includetypedef struct Mnode int data; struct Mnode *next; Mnode;void hzxdw(int m,int n)/猴子选大王 Mnode *q,*p,*L,*pre; int i; /s作为n的标志 for( i=0; idata=i+1; L=p; p-next=L; else q=(Mnode*)malloc(sizeof(Mnode); q-data=i+1; q-next=L; p-next=q; p=q; /为猴子编号 p=L; while(p!=p-next)/当pp-next时表明猴子大王已选到 for(i=1; inext=p-next; p=p-next; free(q); /q-data号猴子出列 else pre=p; p=p-next; printf(选出的猴王是%d号猴子n,p-data);int main() int m,n; printf(请输入猴子总数m和规定猴子报数n的值(当n或m等于0时程序结束)：n); while(sc