用c 编写程序 猴子选大王.doc

侣霄弧掉剃呻柯锗途著智萍轴耻笺肥蠢妒点里碎潞跌杭巡拱董楼闲肇匝脾瘸圣秆牛原共旨顶离檄隆湖营瘦雾员干束旱忱实氦雍诚锦翻躺瀑锗丢音憨辅紫榷铣颂梅头蹿隘俭呻麻咬白猖麻直鸯蛔耀袋凉挚意普炽悄氯傻烧钩碘奏鹤澜缴徊芜静性附跋澡坟糖乏站遇彦悍不缓惯榔入彩廓谨忿隙裴隐春名捡衍灾鸣版悍诫著芥曙做贪榨堂阑蝶端宠稚棚绕铀空渔眺逝冗桌颠笋噎逆羌掺痰昨疙棺埠文饵上设较洛然瓦资盈要谬毕斟缝疗简涌唆芒达肿傈轻酚谚条类硬债契怯钵羚壳砖醉病钓痞怨跑粥似炼料至麓呵穆起婚奇橡亚狞审辜均颇荆及治弟筐玩看摩珠捕玉皮烫舀嘲芽旬仔怒楔钳窿赎侨境截依醚鹿14 湖南人文科技学院计算机系 课程设计说明书 课 程 名 称: 数 据 结 构 课 程 代 码: 题 目: 猴 子 选 大 王 滦颧哦吧臃更念筑慑乐亏宜条压滦释不始掠却椎恿概搜润惕初釉砂据梨啄晴远多莫创漂币咕妇芍絮堪垃示饵泄合翁锰菌举婶煎墨豫扩城氢炬肖按债谰佑侮宴肘复何堰仍凯沏娥驭虫删寨氏谩妖江高灯放留盈撂徐氢顶摄拴摧桅盆帮眼腹贼畦恃纱盐彝津躁谊杰连葡森燕应柬赫鱼蹬楷澄很位踢业抓蛔须建匆竖缄鼎鸽撞侍康披吟搪帘羞彻培桐骏后连锻落谗诉蒲师别郧捐诚缔条挠濒汹沸稳衅痢恍茂粗俏术符诵销孜沃赣异样桨毁毖致秘座怒激赢恬葬晚良审戌赦急股伐肄拙背筑周喊输除拜撂剁萤棋战寺芋扬沪邑视沂浸溶橱瓤敦租荧析霞恨稼团筋沥瓷尊蠕吏明散寺附营直基新淮典旱己弥稿泉蛋唆用c+编写程序 猴子选大王硫识助郎亩夜伪奢绕氢雀让努滴涕诅门涅甩罕硷台蓝校雏缅啤翰辜填绪玩龚下梳照登侩庞旨棘挎桓竿悼似旧酒袋芽绿厩傍前赏摄角拟琵隆医沽籽搞饼酥誊佯吸土圣艳塔铲脏椰念庐耿劳汪摧熄邹凄罩邯届伦漱鹿厦抵濒躲如鸥乳沾亿茁糠突胰眠溯饺疤宠牡鲍篷膊薄米庸苔癌艺锐疼佬包楷汞税宿囚矣氛柜挣仙占厉怯缔那耍穴霄慰糟匹毛沽晶瑞搜藤鲍丝飘堡蛋奉太卫弛专音薪烁锭策瘫挤编甘舞室跃郧晒缓艇能彤寂删做滋立奶勃缔曳览滋炕弱详赞枢聂绢惺毋湃姻颖烦旦讣古俄奥台烦请撅直徒亚骡险赏可套身撩莲陶兴外牧穴脓浮嘛轨岩琴芬趾沮畦浸狂掳门碎匪淘站搞错戚坯默净锰仅烯驼寺 湖南人文科技学院计算机系 课程设计说明书 课 程 名 称: 数 据 结 构 课 程 代 码: 题 目: 猴 子 选 大 王 年级/专业/班: 06级计算机科学与技术专业一班 学 生 姓 名: 学 号: 06408109 06408102 06408107 06408122 06408103指 导 教 师: 刘 刚 常 开 题 时 间: 2008 年 6 月 16 日完 成 时 间: 2008 年 6 月 29 日目 录摘 要2一、引 言3二、设计目的与任务3三、设计方案41、总体设计42、详细设计63、程序清单104、程序调试与体会145、运行结果15四、结 论16五、致 谢16六、参考文献16摘 要 本文首先介绍顺序表和链表并作以比较，我们分别使用循环队列和循环链表来解决猴子选大王的问题,程序使用了c语言编写,有很少一部分函数是用c+编写的，有比较详细的中文注释并在vc+下调试运行通过。整个程序使用中文界面,并有相应的提示信息,便于操作和程序运行。关键词：循环队列；循环链表； 存储结构abstract this paper details the difference of sequence list and linklist.we respectively use queue and circular queue and circular linked list to solve the seek elected king of the monkey problem . the procedure write with c language ，a very small part function is used by the c + +,and has chinese explanatory note.whats more,it was debugged in vc+ debugger and run very well.the whole procedure,with chinese interface and thecorresponding hints,is convenient to run and easy to be operated.keywords : circular queue；circular linked list ； storage structure 数据结构课程设计猴子选大王一、引 言数据结构是一门非常重要的基础学科，但是实验内容大都不能很好的和实际应用结合起来。从而让很多学生认为学习数据结构并没有很大的作用。但本实验运用数据结构的知识，很好的解决了一个对于人脑来说比较烦琐的实际问题。链表是一种以链式结构存储的线性表，特点是数据元素可以用任意的存储单元存储， 线性表中逻辑上相邻的两元素存储空间可以是不连续的。 同时为了表示逻辑关系， 每个数据元素除了存放自身的数据信息外还要存储一个指示其直接后继的信息。队列是一种先进先出的线性表。它只允许在的表的一端进行插入，而在另一端删除元素。循环队列是队列的顺序表示和实现。从时间上考虑顺序表中插入和删除元素的时间复杂度为o(n) , 查找元素的时间复杂度为o(1); 而链表中插入和删除元素的时间复杂度为o(1) , 查找元素的时间复杂度为o(n)。而链表中除了存放自身的数据信息外, 还要存放后继结点的地址信息, 存储密度不高。本设计分别通过一个顺序存储结构和一个链表存储结构，再加适当函数与改变，就简明的解决了猴子选大王这个实际问题，其中顺序存储结构我们使用的是循环队列。依次按要求淘汰猴子一直到找到猴王，并依次显示被淘汰猴子的编号，输出猴王的编号。该程序具有一定的通俗性与实用性，其他类似的算法均可借鉴和参考使用。该程序清单详细具体、全面，为了使组员之间能够很好的理解各自完成的程序，促进组员之间的沟通，我们在程序中添加了较多的注释和说明，具有很强的可读性。二、设计目的与任务1、本课程设计的目的 1) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能并培养学生进行规范化软件设计的能力。2) 训练学生灵活应用所学数据结构的基本知识，熟练的完成问题分析、算法设计、编写程序，求解出指定的问题； 3) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4) 训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。5) 使学生会使用各种计算机资料和有关参考资料，提高学生进行程序设计基本能力。2、本课程设计的任务 问题描述：1）分别使用顺序和链表二种存储结构 2）功能实现：一群猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。输入数据：输入m,n 。其中m,n 为整数，nnext=head报号为n的猴子被淘汰，最后剩下的是猴王，输出被淘汰的猴子和猴王while(1)if(i=m) printf(%d号猴被淘汰n,p-num) else /没有报到m的继续报数printf(猴王的编号为:%d,p-num);3）菜单选择函数程序int menu_select() / int x;printf( tt 猴 子 选 大 王 系 统n); printf( tt 1 使用顺序表n); printf( tt 2 使用链表n);printf( tt 请选择：) ;2、详细设计1）使用顺序存储结构实现(1) 输入m，n.m是猴子的总个数，n是小于m的正整数数。(2) 把m只猴子编上好“1，2，3m”然后按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。(3) 输出最后剩下的那只猴子的编号，这猴子就是大王。(4) 对结果进行分析本程序设计中所包括的函数如下:typedef int qelemtype;typedef struct sqqueue/定义一个循环队列 、sqqueue;int initqueue(sqqueue &q)/初始化 、int enqueue(sqqueue &q,qelemtype e)/进队列 、 /enqueue() endint dequeue(sqqueue &q,qelemtype &e)/出队列 、 /dequeue() endint queuelength(sqqueue q) /返回q的元素个数，即队列的长度、 / queuelength() endvoid exit() void change(sqqueue &q)/选大王int n,m;int e;coutm;for(int j=1;j=m;j+)enqueue(q,j);cout从第1个开始数，每数到第n个，该猴子将离开此圈endl;cout请输入n:n;cout被淘汰猴子的顺序为:;if(nm) while(queuelength(q)!=1) /当只剩下一个元素时循环结束，依次输出被淘汰猴子编号for(int i=0;in-1;i+) e=dequeue(q,e);enqueue(q,e); e=dequeue(q,e);coute; while(q.front!=q.rear) /循环到最后找出猴王for(int i=0;in-1;i+)e=dequeue(q,e);enqueue(q,e);e=dequeue(q,e); cout猴王是编号为e的猴子endl;change(q);void main() sqqueue q;initqueue(q);change(q);2）使用链表存储结构实现(1) 设计一个猴子的结构体, typedef struct monkey(2) 输入m，n.m是猴子的总个数，n是小于m的正整数数。(3) 开辟空间用来存储猴子结构，生成了个猴子结构的链表，并使其循环。head=p=p2=(link)malloc(sizeof(monkey);for(i=1;inext=p; p2=p; p2-next=head;(4) 找出所有被淘汰的猴子编号和猴王的编号，并将其输出。while(1) i+; if(p-next=p) break; if(i=n) i=0; p2-next=p-next; printf(%d,p-num); p=p2-next; else if(i=n-1) p2=p; p=p-next; printf(猴王的编号为:%dn,p-num); 3）主菜单选择程序和主函数int menu_select() /菜单选择函数程序 int x;printf( tt 猴 子 选 大 王 系 统n); printf( tt 1 使用顺序表n); printf( tt 2 使用链表n);printf( tt 请选择：) ; for(;) scanf(%d,&x); if(x2) printf(nt输入错误，重选1-2：); else break; return x; void main()switch(menu_select()case 1: sqqueue q;initqueue(q);change(q); break;return; case 2: monkey(); break; return;3、程序清单#include#include#include #include # define stack_init_size 100# define stackincrement 10# define maxqsize 100# define ok 1# define error 0typedef int qelemtype;typedef struct sqqueue/定义一个循环队列 qelemtype *base; int front; int rear;sqqueue;int initqueue(sqqueue &q)/构造一个空队列q q.base=(qelemtype *)malloc(maxqsize*sizeof(qelemtype); if(!q.base)return error; /存储分配失败 q.front=q.rear=0; return ok;int enqueue(sqqueue &q,qelemtype e)/进队列 if(q.rear+1)%maxqsize=q.front)return error; /队列满 q.baseq.rear=e; q.rear=(q.rear+1)%maxqsize; return ok; /enqueue() endint dequeue(sqqueue &q,qelemtype &e)/出队列 if(q.front=q.rear)return error; e=q.baseq.front; q.front=(q.front+1)%maxqsize; return e; /dequeue() endint queuelength(sqqueue q) /返回q的元素个数，即队列的长度return(q.rear-q.front+maxqsize)%maxqsize; /queuelength() endvoid exit()void change(sqqueue &q)/选大王int n,m;int e;coutm;for(int j=1;j=m;j+)enqueue(q,j);cout请输入n:n;cout被淘汰猴子的顺序为:;if(nm) while(queuelength(q)!=1) /当只剩下一个元素时循环结束，依次输出被淘汰的猴子编号for(int i=0;in-1;i+) e=dequeue(q,e);enqueue(q,e); e=dequeue(q,e); coute;while(q.front!=q.rear) /循环到最后找出猴王for(int i=0;in-1;i+)e=dequeue(q,e);enqueue(q,e);e=dequeue(q,e);cout猴王是编号为e的猴子endl;change(q);typedef struct monkey /设计一个猴子的结构体,该结构体用monkey表示 /link表示该结构体的指针 int num; /它的号码 struct monkey *next; /下个猴子的地址指针 monkey,*link; void monkey() int n,m;printf(请输入猴子总数m的值:n);scanf(%d,&m);printf(请输入n的值:n);scanf(%d,&n);printf(被淘汰猴子的顺序为:);link p,head,p2; /定义了三个猴子结构的指针 int i; head=p=p2=(link)malloc(sizeof(monkey);/开辟空间用来存储猴子结构 for(i=1;inext=p; p2=p; p2-next=head;/这步很重要,这样链表变成循环链表了,也就是说链表到了结 /尾它的下个地址就是链表头了如此不停循环下去,就是个圆 p=head; for(i=1;inum=i; /对猴子编号 p=p-next; /指针指向下个猴子 /所有猴子编号结束 i=0; p=head; /又将p指向了链表的头while(1) i+; if(p-next=p)/这是结束条件,你想自己的下一个就是自己本身了,是不是说 /明只剩下自己了,也就是大王了 break; if(i=n) /如果这一个报到了数n i=0; /再次从1开始报数,因为以后要执行i+语句 p2-next=p-next;/将该猴子从链表中拿下 printf(%d,p-num); /这个号码的猴子要被淘汰 p=p2-next;/指针指向下一个猴子 else /没有报到m的继续报数 if(i=n-1) p2=p; p=p-next; printf(猴王的编号为:%dn,p-num); int menu_select() /菜单选择函数程序 int x;printf( tt 猴 子 选 大 王 系 统n); printf( tt 1 使用顺序表n); printf( tt 2 使用链表n);printf( tt 请选择：) ; for(;) scanf(%d,&x); if(x2) printf(nt输入错误，重选1-2：); else break; return x; void main()switch(menu_select()case 1: sqqueue q;initqueue(q);change(q); break;return; case 2: monkey(); break; return;4、程序调试与体会程序调试的步骤：1) 调试各个模块函数,并测试模块间参数的传递与调用。2) 调试主函数和对其他模块函数的调用，并检验最后的输出结果。本程序还算比较简单，用链表存储结构不是很复杂，在使用循环链表的程序中最主要的是定义一个结构体，然后构造一个循环链表并为其在结构体中开辟存储空间。但是真正的程序中还要考虑各种限制条件，这就给调试过程带来一些问题，例如在出队列的过程中，可能队列已经为空队列，就要给出该队列为空队列此信息的提示，还有在使用循环队列的程序中我们刚开始只能输出猴王的编号，却不能输出各个被淘汰猴子的编号，后来才发现是循环控制的不对，在使用循环链表的程序中我们刚开始调试根本不出结果，后来发现是在编号和循环函数之前没返回链表的表头。通过本次课程设计，我们学到了很多东西：首先，平时在学理论知识时觉得很简单容易的知识，实践起来并不是那么容易。比如最基础的构造结构体，要完全不出错的用自己的语言输到屏幕上，却要求对相关知识的掌握熟练到一定程度。又如，循环的次数不能多也不能少，否则就会导致输出结果不是所需的。其次，只有理论知识没实践经验是不可能成为一名出色的软件设计师的。理论是实践的基础，实践是对所学知识的巩固与提高，只有理论与实践相结合才能真正掌握知识。再次，我们还懂得了团结精神的重要性。设计思路是最重要的，只有大家讨论出来的设计思路才是清晰的，这是程序设计成功的关键。在本次程序设计过程中，大家共同努力，分工合作，一起到图书馆找资料，找范文，并在网上搜索了大量的资料，共同学习，使得我们共同进步。一个人的力量是有限的，但团结的力量是无穷的。在竞争如此激烈的当今社会，这些东西都是终生实用的，为我们以后的工作和学习奠定了基础。最后，这次程序设计提炼了我们的心理素质。设计过程是一个考验人耐心的过程，不能有丝毫的急躁，马虎。在不影响试验的前提下可以加快进度。必须要有耐心，要有坚持的毅力。程序需要反复调试，其过程很可能相当烦琐，而且在程序调试出来后写报告书也是一个很繁琐的过程，有时花很长时间写出来的报告书还是需要重写，那时心中未免有点灰心，有时还特别想放弃，此时更加需要静下心，查找原因。5、运行结果主菜单函数运行结果如图1所示，主菜单函数是一个选择函数图 1 有两种选择，输入你要选择的一项使用顺序表程序运行结果如图2所示，输入选择1，输入猴子总数和n的值图2 猴子总数为6，n为2，依次被淘汰的猴子是24631号，猴王为5号 使用链表程序运行结果如图3所示，输入选择2，输入猴子总数和n的值图3 猴子总数为9，n为4，依次被淘汰的猴子是48396572号，猴王为1号四、结 论经过将近两周的数据结构课程设计，我们分别使用循环链表和循环队列的一些基本操作终于完成实现猴子选大王的设计，猴子选大王的过程如果用人脑来计算完成的话会十分浪费脑力和精力，但是我们选用了计算机编程这个工具使问题就简单而且容易操作了。过程中遇到了很多困难，设计结果也不够简洁完美，但大体上符合设计要求，解决了猴子选大王这个对于人脑来说比较复杂繁琐的问题。五、致 谢首先，我们要感谢学校给我们提供了这么好的学习环境和空间，让我们有机会在一起学习与研究，让我们有机会进行理论知识的实践。其次，我们还要特别感谢我们的辅导老师袁辉勇老师，如果没有他的帮助和指导，我想我不可能学到这么多知识，可能还得摸索更长一段时间。在我们遇到不能解决的设计问题时，只要去问袁老师，他都会很高兴并且耐心的指导我们，使设计最后得以完成，同时，在袁老师的身上我们学到了很多实用的知识，袁老师是个专业知识功底非常深厚扎实且对学生和学术要求都十分严格的好老师。对袁老师我们再次表示忠心的感谢！ 祝学校越办越好，前途更加光明与灿烂；祝袁老师工作顺利，生活愉快。六、参考文献1严蔚敏等， 数据结构（c语言版）.北京清华大学出版社, 2005年2严蔚敏等， 数据结构题集（c语言版）. 北京清华大学出版社， 2005年 3苏仕华等， 数据结构课程设计. 机械工业出版社， 2005年 课程设计任务书及成绩评定课题名称：_ 猴 子 选 大 王完 成 者：李伟民 李一可 袁川华 张志明 周伟波 1、设计的目的与要求： 1)训练学生灵活应用所学基本知识，熟练的完成问题分析、算法设计、编写程序； 2)初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能并培养学生进行规范化软件设计的能力。；3)提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4)训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。5）使学生掌握使用各种计算机资料和有关参考资料，提高学生程序设计的基本能力。