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

北京化工大学北方学院课程设计报告课程名称 数据结构课程设计 设计题目 猴子选大王 专业、班级 软件工程0803 班 学 号 姓 名 指导教师 设计时间 2011/10/22011/10/10 2011年 10 月 10 日一、 引言（简要说明设计题目的目的、意义、内容、主要任务等）1、 目的 (1)训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 (2)初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；(3)提高综合运用所学的理论知识和方法独立分析和解决问题的能力；(4)训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风(5)本次程序程序设计的主要目的是解决变相的“约瑟夫环”问题-猴子大王。从而使复杂的甄选工作变得明朗简单化。同样，这种解决问题的思想还可以运用到其他具有类似问题的领域，达到一点窥面的效果。2、 意义熟练掌握数据结构这门课程，掌握经性表、栈、队列、串、数组、广义表、树和二叉树以及图等基本类型的数据结构及其应用。 进一步熟悉抽象数据类型的定义和实现、如何利用数组的动态分酚实现顺序结构、继承的实现方式。学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、想念结构及基相应的算法并初步掌握算法的时间分析和空间分析的技术。基本掌握程序设计的基本思路和方法。利用所学的基本知识和技能，解决简单的程序设计问题各算法描述培养我们的数据抽象能力。利用单向循环链表模拟此过程，输出选出的大王编号。通过本课程设计，可加深我们对链表的了解，对今后的学习有很大帮助。3、 内容全程序以数据结构（Java语言）中的循环单链表为主要的设计支柱，利用了Java语言简洁紧凑、灵活方便，语法限制不太严格，程序设计自由度大，生成目标代码质量高，程序执行效率高等方面的优点。循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环，基于这样的特点，它适合处理具有环形结构的数据元素序列。在程序代码的编写中，运用了链表类型（List，ArrayList），动态申请内存空间方法add()，释放动态申请内存空间方法remove()等类型，同时也具有多种循环、条件语句控制程序流向，如：嵌套if else语句，多重for循环语句，还有链表中结点元素（list.get(i)），从而使程序完全结构化。这样编写出的完整程序代码可以实现“猴子选大王”功能，输入猴子的数目m，循环数n，对m个猴子进行编号，通过嵌套if else语句，for语句，一遍一遍的循环，判断，删除，直到只剩下最后一个猴子，即大王。这样就可以实现所需的基本功能了。4、 主要任务 现在需要用数据结构（Java语言）解决“猴子选大王”的问题，具体问题如下：一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求解决问题的程序必须满足以下条件：1、输入数据：输入m,n 为整数2、输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能。3、使用循环单链表实现。二、 正文（课程设计的主要内容，包括实验与观测方法和结果、仪器设备、计算方法、编程原理、数据处理、设计说明与依据、加工整理和图表、形成的论点和导出的结论等。正文内容必须实事求是、客观真切、准确完备、合乎逻辑、层次分明、语言流畅、结构严谨，符合各学科、专业的有关要求。）1、实验内容：M只猴子要选大王，选举办法如下：所有猴子按1，2n编号围成一圈，从第一号开始顺序1,2m,凡是报m号的退出圈外，如此循环报数直到圈内只剩一只猴子时这只猴子就是大王。2、实验要求： (1) 熟练设计链表并实现插入、删除、遍历等接口；(2) 设计出简单界面，实现用户参数输入和结果输出； (3) 设计函数，实现循环删除第N个猴子，剩下的最后一个是大王. 3、程序的设计思想：（1） 问题分析：“猴子选大王”问题是约瑟夫环问题的一个特例。由于本题目的数据元素个数不可知，所以可使用链表来动态的分配内存空间。而该问题又是一个不断的循环问题所以用循环链表来实现。（2）总体设计：首先生成一个空链表，并给n个结点分配空间，让单链表的表尾指针指向头结点则生成一个带有n个结点的循环单链表。再给每只猴子建立顺序的编号。现从第一个结点开始报数，依次顺序查找出报数为m的待出列的结点（猴子）通过remove()删除该结点后继续运行。最后list.size()=1时停止运行，得到的结点即为猴子选出大王的编号。4、开发及运行环境课程设计使用Java语言工具，Java语言作为一种面向对象的程序设计语言，Java语言发展迅速，而且成为最受欢迎的语言之一，主要因为它具有强大的功能。许多著名的系统软件。用Java 语言加上一些jsp、php语言子程序，就更能显示Java 语言的优势了，像PC- DOS 、WORDSTAR等就是用这种方法编写的。常用的Java语言IDE（集成开发环境）有MyEclipse、Eclipse、Emacx、JCreator、JBulider等等对于一个初学者，MyEclipse、Eclipse 是一个比较好的软件。界面友好，功能强大，调试也很方便硬件平台：CPU：P4 1.8GHZ内存：256MB以上软件平台：操作系统：Windows XP/Win7开发工具包：JDK Version1.6.14 MyEclipse 8.5 分辨率：最佳效果1024*768像素5、提供测试结果： 定义 n=8, m=3,测试结果如下：对猴子进行编号！1号猴子：1 1号猴子报：12号猴子：2 2号猴子报：23号猴子：3 3号猴子报：3 3号猴被淘汰4号猴子：4 4号猴子报：15号猴子：5 5号猴子报：26号猴子：6 6号猴子报：3 6号猴被淘汰7号猴子：7 7号猴子报：18号猴子：8 8号猴子报：2 1号猴子报：3 1号猴被淘汰2号猴子报：14号猴子报：2 5号猴子报：3 5号猴被淘汰 7号猴子报：1 8号猴子报：2 2号猴子报：3 2号猴被淘汰 4号猴子报：17号猴子报：2 8号猴子报：3 8号猴被淘汰 4号猴子报：1 7号猴子报：24号猴子报：3 4号猴被淘汰7号猴子报：1胜出:7号猴子Press any key to continue下一组数据：m = 30,n = 2;运行结果如下：得到了预期结果6：程序源代码package com.bluedot.bfxy;import java.util.ArrayList;import java.util.List;import java.util.Scanner;public class DaWang public static void main(String args) daWang(); public static void daWang() Scanner sc = new Scanner(System.in);/从键盘获得输入 System.out.println(请输入n和m的值(nm)：); int n = sc.nextInt(); int m = sc.nextInt(); if(nm) List list = new ArrayList();/在此使用了泛型 for(int i=0;im;i+) list.add(i); /将元素添加到list中 int n0 = 0; /表示当前报数的人 while(true) if(list.size()=1) break; for(int j=0;jn-1;j+) n0+; if(n0 = list.size() n0=0; list.remove(n0); /删除 if(n0 = list.size() n0=0; System.out.println(按照+m+个猴子,数+n+ 个数的方法,输出为大王的猴子是 +(list.get(0)+1)+ 号);/ else System.out.println(输入错误，请重新输入。); 三、 结论（应当准确、完整、明确精练；也可以在结论或讨论中提出建议、设想、尚待解决问题等。）本次课程设计在整整一周的时间内得以完成，全部内容主要包括：目录，课题设计背景，详细设计，设计结果及分析等方面的内容，主要通过上网收集资料，查找参考书目，了解图书管理的设计背景，明确设计方向和内容，在此基础上形成了该课程设计的的基础框架。再进行源代码的创作以及整合，并及时上级进行调试，保证代码的有效性。具体内容在程序设计各章节均有体现。在本次课程设计中，我收获了许多。首先，在课程设计中通过对相关资料的搜索，设计猴子选大王实际上是一个约瑟夫环问题，设计这个程序比较简单，更重要的是在看到现象的同时我看到了它的本质，程序设计确实是一门神奇的工具，它可以通过普普通通的程序代码实现很多法在的流程，在减少人力劳动的同时，展现着科学的魅力。这样是我更加清楚地认识到自身存在的差距，所学的那点知识是远远不够的，学无止境才是真道理。其次，课程设计的主要内容和目的是解决实际问题，同时运用所学的知识。这是我认识到了将知识活学活用的重要性。以往的我们只是简简单单的将书本上的知识以模板的形式刻入脑袋中，而在面对实际问题时却往往不知所措，这是理论泛滥带来的直接后果。这次的实践，让我将上学期所学的Java语言和本学期所学的数据结构在实际的操作运用中进一步巩固，对于那些没有学透的知识，如，函数调用，结构体等，在不停摸索，商讨的过程中最终将它们一一解决，同时也新增了许多没有学到过的内容。最后，对于我来说，独立完成这项课程设计是十分困难的，在学习和复习知识的过程中，难免要请教同学老师，他们的热心，让我感受到了团队的力量和团队的温暖，使我能顺利的完成任务。课程设计的结束并不代表着学习的结束。这次的设计，把我带入到了一个全新的不曾接触过的领域，让我在以往只是注重操作的基础上，更多的思考到了，这是如何实现的，运用我所学到的知识是不是可以同样做出这样的网站，实现不一样的操作，达到同样的效果？我似乎有所领悟了，学习的本质不是让你牢牢的掌握一个知识，而是让你掌握一种方法，一种思想。同时，我知识的局限是毋庸置疑的，在纵多高级语言中，如，C+，JAVA ，C#，java语言编程是我目前唯一能做到的，并且还做得很不完善，所以在以后的学习中一定要抓紧现在的大好时光扩充自己的知识储备，掌握更多的方法，为将来实现更多领域功能所用！同时本次课程设计让我学习知识的同时，也锻炼了自己面对新问题时的抗压能力，直面困难，不抛弃不放弃，坚持到底！在以后的学习和生活中，我将发扬这些优点，劈荆斩浪，挑战自我，一步一步往前走。由于时间有限，本人水平有限，报告中可能存在诸多不完善之处，还望见谅。四、参考文献1.H M Peitel，P J Deitei.C How to progrom,second Edition. 蒋才鹏等译，C程序设计教程，北京：机械工业出版社，20002.Herbert Schild著，王曦若，李沛译，ANSIC标准详解，北京：学院出版社，19943. (美)Joshua Bloch 著 杨春华