《数据结构课程设计报告猴子选大王.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计报告猴子选大王.doc（21页珍藏版）》请在三一文库上搜索。
1、数据结构课程设计报告题目：猴子选大王采用循环链表及动态存储的实现班 级：计算机082班姓 名：指导教师：成 绩： 信息工程学院 2010年01 月 20 日 目录课程设计摘要(题目) 03 1.引言 032.需求分析 04 2.1问题分析 04 2.2总体设计 053.概要设计 073.1模块分析 073.1.1链表循环输入删除输出073.1.2各个函数之间的调用关系 09 3.2函数的流程分析 104.详细设计 124.1函数设计 124.2程序源代码 135.测试结果 166.设计体会 187.结束语 19参考文献 20摘要(题目):猴子选大王任务：一堆猴子都有编号，编号是1，2，3 .m
2、 ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求：输入数据：输入m,n ；m,n 为整数（nnext=p-next; e=p-shifang;释放结点p并且返回被删除猴子的编号。删除函数为：void Delete - ()删除算法的图形表示为：当猴子报号数n时： 图2 循环链表释放结点循环链表模块图层分析（具体如下图2所示）循环链表模块输入功能删除释放功能报数查找功能释放出非猴子大王结点释放出猴子大王图3 链表循环删除输出模块3.1.2各个函数之间的调用关系整个函数调用关系：主函数由数据
3、输入、链表循环删除输出操作、数据输出等组成（如下图3所示）主函数最后元素输出操作链表循环删除输出操作数据输入输出猴子大王序号图4 函数调用关系图3.2函数的流程分析（如下图5 流程图所示）设定链表抽象数据类型的定义ADT struct 对象数据（猴子总数，m为整数） 操作对象:struct monkey *create() 建立循环链表 struct monkey *findout(start,n) 找出被淘汰的猴子的上一个 Struct monkey *letout(last) 删掉被淘汰的猴子，返回的指针值指向下一个猴子。在循环链表填入数据：猴子总数m、报号数nfrontdata= =n?
4、= = n-1？建立循环单链表定义结构体及变量front、rear、m、n结束开始释放第n个猴子，指针front指向第n+1个结点rear=rear-next猴王就是第rear-data 个猴子front= =rear?= = n-1？front +YNNY输出已删除的猴子节点和猴子大王结点 图5 流程图4.详细设计4.1函数设计程序设计中主要包括下列函数LinkList initring(int n,linklist r) 构造一个含n个元素的循环链表;LinkList delete(int n,int k,linklist r) 循环删除报k号的元素； 循环输出所删除的元素；记录链表最后所
5、保留的元素的位置；void main ( )void outring(int n,linklist r) 输出链表最后保留的元素，即猴子大王的序号；4.2程序源代码#include stdio.h #include stdlib.h typedef struct node int data; struct node *next; listnode,*linklist; /* /* 函数名称:创建一个循环链表 /* 功能描述:输入猴子总数数据m和猴子报数数据n，每报到n的猴子就删除此猴子结点， /下一个猴子开始报数，每报到n的均删除，如此循环，循环m-1次，即只需删除m-1个 / 节点,最后剩下
6、猴子大王 /* 参数:循环链表的头指针front，尾指针rear /* linklist initring(int n,linklist r) /创建一个循环单链表 linklist front,rear; int i; r=rear=(listnode *)malloc(sizeof(listnode); /两个指针指向首位置 for(i=1;idata=i; rear-next=front; rear=front; front-data=n; front-next=r; /头尾相连 r=front; /指向头节点位置 return r; linklist deleted(int n,int
7、 k,linklist r) int i,j; linklist front,rear; front=r; /p移至头节点位置 for(i=1;i=n-1;i+) /循环m-1次，即只需删除m-1个节点,最后剩下猴子大王 for(j=1;jnext; /front循环移至下一个位置 rear=front-next; front-next=rear-next; /报n号的猴子出列，即删除front-next printf(%4d,rear-data); if(i % 6=0) printf(n); free(rear); printf(n); r=front;return r; /记录猴子大王位
8、置并传递 void outring(int n,linklist r) int i; linklist front; front=r; /获得猴子大王位置 printf(猴子大王：); printf(%4dn,front-data); /* /* 函数名称:主函数/* 功能描述:输入猴子总数m，猴子报数数据n /* 参 数:m，n，j /* void main() /* /* 功能描述:猴子选大王游戏C语言工作界面，动态显示日期和时间 /* printf(n); printf(n); system(date /t); system(time /t); system(color 16); pri
9、ntf(n); printf(n); printf( n); printf( n); printf( n); printf( .欢 迎 进 入. n); printf( n); printf( .猴子选大王游戏C语言工作界面. n); printf( n); printf( n); printf( n); printf( n); printf( n); int xuliehao; printf(n); printf(n); printf(n); printf( 请输入密码:); scanf( %d,&xuliehao);printf(n); while(xuliehao!=39) printf
10、(不好意思，您的序列号输入错误，请重新输入序列号:); scanf(%d,&xuliehao);system(cls); linklist r; int m,n; linklist initring(int m,linklist r); linklist deleted(int m,int k,linklist r); void outring(int m,linklist r); int j; while(j) printf（ n); printf( n); printf( 作者: 庞康永 9 n); printf( 工具: C-Free 4.1 n); printf( 题目: 猴子选大王.
11、 n); printf( M个猴子围成一圈坐在一起,从第一个(1,2,3.)开始 n); printf( 报数,报到n(nM)的那个退出,然后从退出的下一个重 n); printf( 新开始报数,如此类推.剩下最后一个为王. n); printf( 创建时间: 2010年01月20日. n); printf( n); printf( n); printf(请输入猴子总数 monkey number M= ); scanf(%d,&m); printf(请输入将出列猴子的报数号n= ); scanf(%d,&n); printf(下列序号的猴子因报%d号而依次出列：n,n); r=initrin
12、g(m,r); r=deleted(m,n,r); outring(m,r); 5.程序运行结果1登陆主界面2. 输入序列号进入功能界面3. 输入猴子总数m=54结果显示界面4.输入猴子报号n=6后运行结果界面6.设计体会经过了两周的数据结构课程设计，我是受益颇多，从选题到定稿，从理论到实践，在这短短的两个星期的日子里，可以说得是苦多于甜，但是可以学到很多很多的的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识，使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，从而提高自己的实际动手能力和独
13、立思考的能力。在设计的过程中遇到问题，可以说得是困难重重，这毕竟第一次做的，不可避免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，上课时老师讲的理论知识，似乎很容易接受，以及各种算法都能够较为理解，但是在真正的运用过程中，并不能把理论知道很好的和实践结合起来。在平时做实验时，尤其是这次课程设计，总感到有些无从下手。因此，在学知识的过程中，一定要多动手、动脑，将所学的知识熟练掌握，自如运用。通过这次课程设计，对我的逻辑思维能力是一个很大的锻炼，再有，它还加强了我们的系统思考问题的能力，在编程方面，我们开始从整体的角度来考虑问题了，而不再像以前一样的，胡乱动手。也就是因为先前的这
14、种编程习惯，使得我们在课程设计过程中浪费了不少的时间，尝到了教训。此次课程设计也对我的独自解决问题的能力有了极大的提高。说实在的，刚看到课程设计题目是猴子选大王，一开始我是蒙了，听都没听过的游戏而且还要用算法实现，这对我是一个打击，第一次要我一个人单独完成一个课程设计，难度可想而知，后来慢慢的静下来冷静思考理解题目，经过较长时间的调试代码和修改代码，才得出了最后的结果，并且在这个过程中，我掌握了不少专业知识，是一次知识的大汇总，并且在这个问题的思考的过程中，还更正了不少我们各自自身对于某个知识点的误区。这次程序设计也是一个毅力的考验过程。有时候往往只是一个小小的错误，却要费很多的时间来解决。在
15、这个过程不能过于急躁，并且要很有耐心才行程序需要反复调试，其过程很可能相当令人头疼，有时花很长时间设计出来还是需要重做，那时心中未免有点灰心，此时更加需要静下心，查找原因。7. 结束语感谢学校给我提供一次这样的动手机会，运用循环链表的基本操作顺利的解决猴子选大王问题，主要利用循环链表的环状结构，循环地执行删除操作并输出其值，记录最后保留元素的位置，而整个过程不需要不需要移动元素使程序在空间复杂度上降小很多，采用指针的移动大大加快了程序的执行效率。系统整体上比较完美，可以从键盘获取输入元素，整体输出画面效果整洁、大方。课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能
16、力的重要环节,是对学生实际工作能力的具体训练和考察过程我想这不只是一次简简单单的课程设计，更体现了数据结构算法和生活的紧密联系。让人不得不深思，这一个学期的学习，这两年来的大学学习生涯，自己究竟学会了什么，掌握了多少，是否能胜任以后作编译人员的职位。我想大家都心里都有很多的感触。对于自己，我想我已经认识到了自己的不足，在今后的学习过程中，一定会以严谨的态度来对待编程，以最好的面貌来迎接大三的计算机专业课程，并且要经常上机调试，坚持理论与实践相结合。参考文献【1】严蔚敏,吴伟民 数据结构(C语言版) 清华大学出版社【2】谭浩强 C程序设计(第三版) 清华大学出版社【3】胡学钢. 数据结构算法设计指导M . 北京:清华大学出版社,1999【4】罗宇等. 数据结构M . 北京:北京邮电大学出版社, 2003【5】 ./【6】. - 21 - / 21文档可自由编辑打印