学士学位论文—-数据结构课程设计猴子选大王课程设计.doc

《学士学位论文—-数据结构课程设计猴子选大王课程设计.doc》由会员分享，可在线阅读，更多相关《学士学位论文—-数据结构课程设计猴子选大王课程设计.doc（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、LULIANG UNIVERSITY数据结构课程设计题 目: 猴子选大王 系 别: 计算机科学与技术系 专业年级: 软件工程1502班 姓 名: 学 号: 指导教师: 2016年11月25日目 录一、设计任务与要求11.1 总体目标与任务要求11.2 题目选择与目的意义11.3 所选题目的主要工作1二、需求分析22.1 用户需求分析12.2 功能需求分析2三、概要设计2四、详细设计（源代码）3五、调试分析9六、运行结果分析10七、收获与体会12八、主要参考资料13数据结构课程设计一、设计任务与要求1.1 总体目标与任务要求 一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m

2、的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。输入数据：输入m,n m,n 为整数，nm输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能 1.2 题目选择与目的意义完成此系统，需要综合运用数据结构课程中学到的几种典型数据结构，以及程序设计语言（C语言），自行实现一个较为完整的应用系统的设计与开发。通过课程设计，自己通过系统分析、系统设计、编程调试，写实验报告等环节，进一步掌握应用系统设计的方法和步骤，灵活运用并深刻理解典型数据结构在软件开发中的应用。学会将知识应用于实

3、际的方法，提高分析和解决问题的能力，增加综合能力。1.3 所选题目的主要工作一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。二、需求分析2.1 用户需求分析用户使用此程序所要完成的工作主要为：查询所有航线信息、查看已订票客户信息、查询航线、办理订票业务、办理退票业务。通过此系统可以方便的进行上述工作。每条航线所涉及的信息有：终点站名、航班号、飞行时间、票价、乘员定额、余票量。已订票的客户名单信息包括姓名、订票量、舱位等级（1，2或3）。等候替补的客户名

4、单信息包括姓名、所需票量。查询航线功能可以根据旅客提出的终点站名输出航班号、飞行时间、票价、乘员定额、余票量。订票业务功能根据客户提出的要求（航班号、订票数额）查询该航班票额情况，若尚有余票，则为客户办理订票手续，输出座位号；若已满员或余票额少于定票额，则需重新询问客户要求。若需要，可登记排队候补购票。退票业务功能根据客户提供的情况（航班号、姓名）为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其他排队候补的客户。2.2 功能需求分析问题定义：一堆猴子都有编号，编号是1，2，3n,这群猴子（n个）按照1-n的

5、顺序围坐一圈，从第1个开始数，每数到第m个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。m，n键盘输入，且mn，输出为大王猴子的号数。问题分析：根据任务描述可知，编号是1，2，3n的一群猴子按照1-n的顺序围坐一圈，因此可以用指针指向数组的方法给数组赋值，输入n值和m值，为保证mn，用一个while()语句实现，如果输错，报错，再输入。用for循环实现猴子编号。从1开始数到m的猴子出列，即用指针移动查找法将计数器数到m的指针指向的内容变为0，用for循环，直到只有一个元素不为0时，最后不为0的元素的值即为大王。实现这个程序功能需3个模块，一个模块用数组指针实现

6、猴子编号，一个模块用指针移动查找法实现猴子出局，最后主模块将前两个模块要用到的函数，数组定义。具体步骤如下：第一步 建立数组，填入猴子编号及猴子出局时报的数第二步 从第一个猴子报数第三步 数到m让指针指向元素变为0第四步 继续报数，重复第三步三、概要设计四、详细设计（源代码）#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=

7、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

8、(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

9、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+;/计数加1 if(x=n&ai%m!=0) ai%m=0; x=0; printf(第%

10、d次，要删除的猴子号为：%dn,count+,i%m+1); y-;/当前的猴子数减1 for(i=0;im;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); prin

11、tf(n); printf(* 请输入周期数 n : ); do scanf(%d,&n); printf(n); if(mn) printf(m应该大于n，请重新输入n：); while(mn); printf(= 请选择 : =nn); printf(* 1.链表处理 *n); printf(* 2.数组处理 *nn); scanf(%d,&select); switch(select) case 1 : Link_solve();/调用链表 break; case 2 : Array_solve();/调用数组 break; defult: break; 五、调试分析1）输入猴子数与出局

12、时报的数95第6个猴子是大王2）输入猴子数与出局时报的数53第5个猴子是大王3)输入猴子数与出局时报的数68输入数据有误，请重新输入!输入猴子数与出局时报的数77第2个猴子是大王4）输入猴子数与出局时报的数145145第94个猴子是大王5）输入猴子数与出局时报的数51第6个猴子是大王六、运行结果分析七、收获与体会在课程设计中，首先要看清问题，将问题要求理解透彻，在构思要如何实现，要用到哪些函数，要用什么算法，在课程构思中选算法是一个很重要的概念，只有确定用这么算法后才能接下来的工作，将流程图画在纸上，再依次编写代码，在程序设计中，编写代码只是一个方面，调试才是关键。它是一个相当繁琐的过程，有许

13、多新的问题需要被解决，但同时它也是一个比较重要的过程，因为在程序调试过程中，你会学到很多新的东西，从而增加你编程的经验。通过本次实习，温固了数据结构的相关知识，加深对课内所学的有关数据的逻辑结构和存储表示、数据结构的选择和应用、算法的设计和时空效率分析等课程基本内容的理解，进一步熟悉了VC+编程环境，巩固并提高了分析问题、解决实际问题的能力。八、主要参考资料1、严蔚敏、吴伟民，数据结构C语言版，清华大学出版社，1997年4月2、夏涛，C语言程序设计，北京邮电大学出版社，2007年3月3、谭浩强，C程序设计（第三版），清华大学出版社，2006年2月4、百度：百度知道，百度文库指导教师签字： 2016年 12月11日13