猴子选大王 课程设计文档.doc

湖南人文科技学院课程设计XXXX大学计算机系课程设计说明书课程名称:数据结构课程代码:题 目:猴子选大王年级/专业/班:学生姓名:学 号 :指导老师:开题时间:完成时间:2009 年 月 日目 录摘 要2一、引 言(小三号、黑体、加粗)3二、设计目的与任务31、课程设计的目的32、课程设计的任务4三、设计方案与实施(小三号、黑体、加粗)41、总体设计42、详细设计63、程序清单74、程序调试与体会95、运行结果（截图）10四、结 论11五、致 谢12六、参考文献121、设计的目的与要求：132、设计进度及完成情况13摘 要线性链表是一种重要而且使用广泛的数据结构，用链表所表示数据元素之间的逻辑关系是由节点中的指针指示的，而循环链表的特点是表种最后一个节点的指针指向头结点，整个链表形成一个环，用循环链表作为本课题的数据存储结构，充分考虑了循环链表的特点仅通过对两个循环链表的出、入列操作，大大降低空间复杂度就简单的实现了要求，动态地模拟出了猴子选大王问题中猴子循环报数的情况。关键词：数据结构 线性链表 存储结构 空间复杂度（35个）Abstract Linear list is an important and extensive use of the data structure,List said that the data used by the logic of relations between the elements by the node in the direction of the pointer,The circulation list of the characteristics of the species list is the last node of the indicators point to the first node, the entire list to form a ring,With the cycle of the list as the subject of data storage structures, taking into account the full cycle through the list of the characteristics of only two out of circulation list, out into operation, greatly reduce the complexity of space on the realization of a simple request,To simulate the dynamics of the monkey king election issue in a number of monkeys circulation SituationKey words: Data Structure, Linear List, Storage structure,Space complexity数据结构课程设计 -猴子选大王问题设计一、引 言数据结构是一门专业技术基础课，它对学习者的的要求很明确：学会分析、研究计算机加工的数据结构的特性，以便为应用设计所需的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。其次，该课程的学习过程也是复杂程序设计的训练过程，要求学习者编写的程序结构或设计的程序结构体清楚、正确、易读，符合软件工程的规范。循环链表是一种重要的链式结构，其特殊性在于需附设两个指针分别指示表头元素及表尾元素的位置且表头和表尾相邻接，臆造的环状空间巧妙的解决了需循环依次删除元素的约瑟夫问题。本设计采用目前最通用的程序设计语言之一C语言作为数据结构和算法的描述语言，循环链表作为数据存储结构。 充分考虑了循环链表的特点仅通过对两个循环链表的出、入列操作，就简单的实现了要求，动态的模拟出了猴子选大王问题中猴子循环报数的情况。该程序通俗易懂且实用性强，其他类似的算法均可借鉴和参考使用。并且该程序清单详细具体、全面、具有很强的可读性。 二、设计目的与任务1、课程设计的目的1) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 训练学生灵活应用所学数据结构的基本知识，熟练的完成问题分析、算2) 法设计、编写程序，求解出指定的问题；3) 训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养严谨的科学态度和良好的工作作风；4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力。2、课程设计的任务问题描述：一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1到m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。课题要求：输入数据m,n 其中m,n 为整数，n输出形式为提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号三、设计方案与实施1、总体设计/写总体的设计思想采用两个循环队列反复出队列与入队列来进行“舞伴配对”。程序中主要用到以下抽象数据类型：1) 设定链表抽象数据类型的定义ADT struct 对象数据（整数） 操作对象:struct monkey *create() 建立链表 struct monkey *findout(start,n) 找出被淘汰的猴子的上一个 Struct monkey *letout(last) 删掉被淘汰的猴子，返回的指针值指向下一个猴子。基本操作(1) initring(int n,linklist r) 操作结果：构造一个具有n个元素的循环链表r。(2) iinklist delete(int n,int k,linklist r)初始条件：链表r已存在。操作结果：循环依次删除问题对应所需位置的元素并当即输出其值，用指针r记录其最后元素的位置。ATD linklist(3) outring(int n,linklist r)特殊输出链表保留的最后一个元素，即猴子大王的序号。程序包含两个模块(1) 主程序模块，其中主函数为int main输入信息；根据输入要求进行删除和输出；输出结果；(2) 循环链表模块实现具体删除输出操作。2) 两模块之间的简单调用关系主函数模块循环队列模块循环链表模块图1 模块调用图2、详细设计/对几个主要功能函数作出相应的说明1) 各个函数之间的调用关系主函数最后元素输出操作链表循环删除输出操作数据输入输出序号图2 函数调用关系图2) 函数设计程序设计中主要包括下列函数LinkList initring(int n,linklist r) 构造一个含n个元素的循环链表;LinkList delete(int n,int k,linklist r) 循环删除报k号的元素； 循环输出所删除的元素；记录链表最后所保留的元素的位置；void outring(int n,linklist r) 输出链表最后保留的元素，即猴子大王的序号；3、程序清单/整个程序的运行清单 #include stdio.h #include stdlib.h typedef struct node int data; struct node *next; listnode,*linklist; linklist initring(int n,linklist r) /创建一个循环单链表 linklist p,q; int i; r=q=(listnode *)malloc(sizeof(listnode); /两个指针指向首位置 for(i=1;idata=i; q-next=p; q=p; p-data=n; p-next=r; /头尾相连 r=p; /指向头节点位置 return r; linklist deleted(int n,int k,linklist r) int i,j; linklist p,q; p=r; /p移至头节点位置 for(i=1;i=n-1;i+) /循环n-1次，即只需删除n-1个节点,最后剩下猴子大王 for(j=1;jnext; /p循环移至下一个位置 q=p-next; p-next=q-next; /报k号的猴子出列，即删除p-next printf(%4d,q-data); if(i % 6=0) printf(n); free(q); printf(n); r=p;return r; /记录猴子大王位置并传递 void outring(int n,linklist r) int i; linklist p; p=r; /获得猴子大王位置 printf(猴子大王：); printf(%4dn,p-data); void main() /主函数 linklist r; int n,k; linklist initring(int n,linklist r); linklist deleted(int n,int k,linklist r); void outring(int n,linklist r); printf(请输入猴子总数 monkey number= ); scanf(%d,&n); printf(请输入将出列猴子的报数号：); scanf(%d,&k); printf(下列序号的猴子因报%d号而依次出列：n,k); r=initring(n,r); r=deleted(n,k,r); outring(n,r); 4、程序调试与体会通过这次课程设计，我们受益颇多：首先，上课时请的理论知识，似乎很容易接受，以及各种算法都能够比较轻松的理解，但是在真正的运用过程中，并不能把理论知道很好的和实践结合起来。在平时做实验时，尤其是这次课程设计，总感到有些无从下手。因此，在学知识的过程中，一定要多动手、动脑，将所学的知识熟练掌握，自如运用。其次，通过这次课程设计，对我的逻辑思维能力是一个很大的锻炼，再有，它还加强了我们的系统思考问题的能力，在编程方面，我们开始从整体的角度来考虑问题了，而不再像以前一样的，胡乱动手。也就是因为先前的这种编程习惯，使得我们在课程设计过程中浪费了不少的时间，尝到了教训。另外，此次课程设计也对我的独自解决问题的能力有了极大的提高，以前做的都是小程序，就都是一个人做，做了后，甚至还洋洋得意，可这一次，一开始是对我们的一个打击，没有一个人能单独完成，最后还是大家一齐出力，共同商讨，才得出了最后的结果，并且在这个过程中，我们相互之间还掌握了其他人掌握了但自己还没有掌握的知识，是一次知识的大汇总，并且在这个讨论的过程中，还更正了不少我们各自自身对于某个知识点的误区。这次程序设计也是一个毅力的考验过程。有时候往往只是一个小小的错误，却要费很多的时间来解决。在这个过程不能过于急躁，并且要很有耐心才行程序需要反复调试，其过程很可能相当令人头疼，有时花很长时间设计出来还是需要重做，那时心中未免有点灰心，有时还特别想放弃，此时更加需要静下心，查找原因。通过这次课程设计，我学习了很多平时很少关注的知识点，比如循环链；也明白了很多道理，比如做不要事萎缩害怕，要尽力去思考，努力去解决，不要太依赖别人，要有团结精神，齐心协力一起解决。5、运行结果（截图）程序运行如下：图（1）、输入总元素个数 图（2）、输入循环中所需删除元素的位置 图（3）、程序运行的输出结果四、结 论运用循环链表的基本操作顺利的解决约瑟夫猴子选大王问题，主要利用循环链表的环状结构，循环地执行删除操作并输出其值，记录最后保留元素的位置，而整个过程不需要不需要移动元素使程序在空间复杂度上降小很多，采用指针的移动大大加快了程序的执行效率。系统整体上比较完美，可以从键盘获取输入元素，整体输出画面效果整洁、大方。五、致 谢首先，我要感谢学校给我们提供了此次课程设计的机会，能让同学们在一起学习与研究，让我们有机会对所学的理论知识进行实践。其次，在论文的写作过程中，也得到了许多同学的宝贵建议，同时还得到许多学长的支持和帮助，在此一并致以诚挚的谢意。最后，我们还要特别感谢我们的辅导老师，在她的精心辅导和帮助下，我们的设计才得以顺利完成。对她为我们的设计所提出的宝贵意见表示忠心的感谢！六、参考文献 1 谭浩强. C程序设计M . 北京:清华大学出版社,2005 2罗宇等. 数据结构M . 北京:北京邮电大学出版社, 2003 3严藯敏. 数据结构M . 北京:清华大学出版社, 2001 4 胡学钢. 数据结构算法设计指导M . 北京:清华大学出版社,1999课程设计任务书及成绩评定课题名称： 猴子选大王 完成者： 1、设计的目的与要求： 1) 灵活应用所学数据结构知识，独立完成问题分析。2) 初步掌握软件开发过程的问题分析、