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