数据结构课程设计报告(猴子选大王).doc

《数据结构课程设计报告(猴子选大王).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、北京化工大学北方学院课程设计报告课程名称数据结构课程设计设计题目猴子选大王专业、班级软件工程0803班学号姓名指导教师设计时间2011/10/2—2011/10/102011年10月10日...一、引言（简要说明设计题目的目的、意义、容、主要任务等）1、目的(1)训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。(2)初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；(3)提高综合运用所学的理论知识和方法独立分析和解决问题的能力；(4)训练用系统的观点和软件开发一般规进行软件开发，巩固、深化学生的理

2、论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风(5)本次程序程序设计的主要目的是解决变相的“约瑟夫环”问题---猴子大王。从而使复杂的甄选工作变得明朗简单化。同样，这种解决问题的思想还可以运用到其他具有类似问题的领域，达到一点窥面的效果。2、意义熟练掌握数据结构这门课程，掌握经性表、栈、队列、串、数组、广义表、树和二叉树以及图等基本类型的数据结构及其应用。进一步熟悉抽象数据类型的定义和实现、如何利用数组的动态分酚实现顺序结构、继承的实现方式。学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、想念结构及基相应的算法

3、并初步掌握算法的时间分析和空间分析的技术。基本掌握程序设计的基本思路和方法。利用所学的基本知识和技能，解决简单的程序设计问题各算法描述培养我们的数据抽象能力。利用单向循环链表模拟此过程，输出选出的大王编号。通过本课程设计，可加深我们对链表的了解，对今后的学习有很大帮助。3、容全程序以数据结构（Java语言）中的循环单链表为主要的设计支柱，利用了Java语言简洁紧凑、灵活方便，语法限制不太严格，程序设计自由度大，生成目标代码质量高，程序执行效率高等方面的优点。循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结

4、点，从而使链表形成一个环，基于这样的特点，它适合处理具有环形结构的数据元素序列。...在程序代码的编写中，运用了链表类型（List，ArrayList），动态申请存空间方法add()，释放动态申请存空间方法remove()等类型，同时也具有多种循环、条件语句控制程序流向，如：嵌套ifelse语句，多重for循环语句，还有链表中结点元素（list.get(i)），从而使程序完全结构化。这样编写出的完整程序代码可以实现“猴子选大王”功能，输入猴子的数目m，循环数n，对m个猴子进行编号，通过嵌套ifelse语句，for语句，一遍一遍的循环，判断，删除，直到只剩下最后一个猴子

5、，即大王。这样就可以实现所需的基本功能了。1、主要任务现在需要用数据结构（Java语言）解决“猴子选大王”的问题，具体问题如下：一堆猴子都有编号，编号是1，2，3...m,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求解决问题的程序必须满足以下条件：1、输入数据：输入m,n为整数2、输出形式：中文提示按照m个猴子，数n个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能。3、使用循环单链表实现。二、正文（课程设计的主要容，包括实验与观测方法和结果、仪器设备

6、、计算方法、编程原理、数据处理、设计说明与依据、加工整理和图表、形成的论点和导出的结论等。正文容必须实事求是、客观真切、准确完备、合乎逻辑、层次分明、语言流畅、结构严谨，符合各学科、专业的有关要求。）1、实验容：M只猴子要选大王，选举办法如下：所有猴子按1，2……n编号围成一圈，从第一号开始顺序1,2……m,凡是报m号的退出圈外，如此循环报数直到圈只剩一只猴子时这只猴子就是大王。2、实验要求：(1)熟练设计链表并实现插入、删除、遍历等接口；(2)设计出简单界面，实现用户参数输入和结果输出；(3)设计函数，实现循环删除第N个猴子，剩下的最后一个是大王.3、程序的设计思想

7、：...（1）问题分析：“猴子选大王”问题是约瑟夫环问题的一个特例。由于本题目的数据元素个数不可知，所以可使用链表来动态的分配存空间。而该问题又是一个不断的循环问题所以用循环链表来实现。（2）总体设计：首先生成一个空链表，并给n个结点分配空间，让单链表的表尾指针指向头结点则生成一个带有n个结点的循环单链表。再给每只猴子建立顺序的编号。现从第一个结点开始报数，依次顺序查找出报数为m的待出列的结点（猴子）通过remove()删除该结点后继续运行。最后list.size()==1时停止运行，得到的结点即为猴子选出大王的编号。4、开发及运行环境课程设计使用J