约瑟夫环Java课程设计大作业.pdf

《约瑟夫环Java课程设计大作业.pdf》由会员分享，可在线阅读，更多相关《约瑟夫环Java课程设计大作业.pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 上海电力学院 数据结构 Java 课程设计 题 目:约瑟夫环 学生姓名：学 号：院 系：计算机与信息工程学院 专业年级：软件工程 级 2010 年 7 月 13 日 目录 1.需求分析.3 1.1 运行环境.3 1.2 输入的形式和输入的范围.3 1.3 输出的形式描述.3 1.4 功能描述.4 1.5 测试数据.4 2.概要设计.4 2.1 抽象数据类型定义描述.4 2.2 功能模块设计.5 2.3 模块层次调用关系图.5 3.详细设计.6 3.1 类函数解析.6 3.2 主函数解析.8 4.调试分析.9 4.1 所遇问题.9 4.2 实验心得.错误!未定义书签。5.用户使用说明.错误!未

2、定义书签。5.1 每一步操作说明.错误!未定义书签。6.测试结果.错误!未定义书签。7.附录：程序源代码.错误!未定义书签。一、需求分析【问题描述】约瑟夫（Joseph）问题的一种描述是：编号为 1，2，n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值 m，从第一个人开始按顺时针方向自 1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。【基本要求】利用单向循环链表存储结构或顺序存储结构模拟此过程，

3、按照出列的顺序印出各人的编号。【测试数据】m 的初值为 20；n7，7 个人的密码依次为：3，1，7，2，4，8，4，首先 m 值为 6（正确的出列顺序应为 6，1，4，7，2，3，5）。1、运行环境（软、硬件环境）开发工具：JDK1.6 eclipse6.0 运行环境：Windows XP 及其以上系统 2、输入的形式和输入值的范围 本个实验所输入的值都强制转化为 Int 数据类型，因为人数一定是个正整数，而每个人所持的密码将会作为下一次循环的步数，所以也一定是一个整数；初始密码也是步数，所以也是一个正整数。在输入值的取值范围上，每人的密码是一个大于零的整数，初始密码也是一个大于零的整数，人

4、数同样也是一个正整数。3、输出的形式描述 1.可以在以下环境中运行本次实验 在 DOS 环境中编译“约瑟夫环.Java”文件 在 Eclipse6.0 及其以上编译环境下运行 2.根据文字要求依次输入人数、每人密码、初始密码等一些数据（见图 1.3.2）（图）1.3.2 4、功能描述 约瑟夫环代码约瑟夫环（Josephus）问题是由古罗马的史学家约瑟夫（Josephus）提出的，他参加并记录了公元 6670 年犹太人反抗罗马的起义。约瑟夫作为一个将军，设法守住了裘达伯特城达 47 天之久，在城市沦陷之后，他和 40 名死硬的将士在附近的一个洞穴中避难。在那里，这些叛乱者表决说“要投降毋宁死”。

5、于是，约瑟夫建议每个人轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签，并且，作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降了罗马。本次试验的不同点在于有一个初始密码 M、每人又有个密码，在他死后（出局）之后将作为下一个循环的步数，这样以此类推得出最后一个幸存者。这个实验主要是模仿约瑟夫环的意思模拟约瑟夫环。差别在与每人的密码将作为下一个循环步数继续开始另一个约瑟夫环的循环处理。最后得到一个出此链表的数字下标代号。5、测试数据 初始密码 M=20 人数为 7 7 个人的密码依次为：3，1，7，2，4，8，4 最后得到一个出此链表顺序，用每个链表中元素的下标

6、输出数据。二、概要设计 1、抽象数据类型定义描述（对各类的成员及成员函数进行抽象描述）创建 Node 和 LinkList 这两个类，在 Node 类中定义一些函数，为主程序中调用这些函数所服务；LinkList 类 Head 指针调用 SetLink 函数，然后遍历结点，一次删除结点，使得指针后移。在主函数中运用一个 For 循环作为足要算法，一次实现约瑟夫环的功能。2、功能模块设计（如主程序模块设计）先创建了一个 linklist 对象，然后分别申明 inCount 和 resultIncount 这两个私有成员变量。然后通过inCount=Integer.parseInt(input.r

7、eadLine();把输入的内容转化成INT 类型，赋值给inCount。通过一个 For 循环语句作为其主要算法实现。Node p=link.head,q=link.last;int i=0;/每个人的密码 int j=0;/人数 for(;)i+;if(i=m)i=0;m=p.getData();System.out.print(p.getCount()+);link.removeNode(q);/删除Q节点 p=p.getLink();/Q结点后移 j+;if(j=inCount)break;/如果等于总人数就跳出FOR循环 continue;/继续进行下一个循环 q=q.getLink

8、();/Q的指针往后移 p=q.getLink();/P等于Q的下一个指针 3、模块层次调用关系图 三、详细设计 实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。class Node private int data=new int2;private Node link;private static int count=-1;public Node(int data)this.data0=data;this.data1=+count;link=null;public void setData(int data)this.data0=data;public int

9、getData()return data0;public int getCount()return data1;public void setLink(Node link)this.link=link;public Node getLink()return link;在这个结点 NODE 类中定义了诸如 setData、getData、getData、getCount、setLink、getLink 等一些函数，为主函数调用这些函数做好准备。这也是前期工作 的准备。class LinkList public Node head;public Node last;public LinkList(

10、int data)head=new Node(data);/Head调用NODE的构造函数，初始化Head head.setLink(head);/Head调用SetLink的函数 last=head;public String vistAllNode()/遍历节点 Node next=head;String s=new String();do s=s+next.getData()+;/把指针next指向的对象添加到字符串S中 next=next.getLink();/把指针后移，获取下一个指针 while(next!=head);return s;public boolean removeN

11、ode(Node node)/去掉node的下一个结点 if(node=last)head=head.getLink();/把头指针指向下一个节点 last.setLink(head);/尾指针=头指针 else if(node.getLink()=last)last=node;last.setLink(head);/Last指向头指针 else Node tempN=node.getLink();/申明一个临时的指针TEMPN指向NODE的下一个节点 tempN=tempN.getLink();/把tempN向后移一个 node.setLink(tempN);/node指向tempN ret

12、urn true;/操作成功返回true public boolean removeAll()/此函数的作用是删除所有的节点 head.setLink(head);/Head=Head last=head;/Last=Head head.setData(0);/head的数据设置为0 return true;public void append(int data)/此函数的作用是加一个节点 Node temp=new Node(data);/申明TEMP节点 last.setLink(temp);/尾指针指向TEMP指针 last=temp;/尾指针指向TEMP指针 last.setLink(

13、head);/尾指针指向头指针 在 LinkList 类中申明头尾指针 head 和 last，head 和 last 分别调用 Node 和setLink 函数，在进行结点的遍历和，当删除一个结点之后便产生了指针后移的问题，直到头尾指针相同。public class 约瑟夫环 private static LinkList link=new LinkList(0);/申明一个LinkList 的对象 private static int inCount;private static int resultInCount;/申明两个变量 public static void main(Strin

14、g args)throws IOException /主函数抛出异常 int enter;String inputString=new String();BufferedReader input=new BufferedReader(new InputStreamReader(System.in);/定义一个缓冲流对象 System.out.print(这个程序是解决约瑟夫环的问题。n请输入人数(正整数):);inCount=Integer.parseInt(input.readLine();/把输入的内容转化成INT类型，赋值给INCOUNT System.out.print(请输入初始密码

15、:);int m=Integer.parseInt(input.readLine();System.out.println(请输入每个人的密码:);for(resultInCount=0;resultInCount inCount;resultInCount+)inputString=input.readLine();enter=Integer.parseInt(inputString);link.append(enter);/循环输入的内容放到链表中 link.removeNode(link.last);/去掉链表中最后一个节点 Node p=link.head,q=link.last;in

16、t i=0;/每个人的密码 int j=0;/人数 for(;)i+;if(i=m)i=0;m=p.getData();System.out.print(p.getCount()+);link.removeNode(q);/删除Q节点 p=p.getLink();/Q节点后移 j+;if(j=inCount)break;/如果等于总人数就跳出FOR循环 continue;/继续进行下一个循环 q=q.getLink();/Q的指针往后移 p=q.getLink();/P等于Q的下一个指针 这是一个主函数代码，里面包括一个 For 循环，从键盘输入总人数和初始的密码，元素的定义通过数组下标输出来

17、，inCount=Integer.parseInt(input.readLine()通过这个方法进行强制类型转换，将其转换成 INT 类型。再调用函数得到出此链表的的元素的下标。四、调试分析 1.所遇问题 程序的编写和调试基本正常。遇到的问题主要是：链表的删除，和主要算法的一个循环算法问题，最后在同学们的帮助和我上网找资料和同学们的帮助之下终于解决问题。本实验采用数据抽象程序设计方法。思路清晰，实现时调试顺利：1由于刚开始忽略了该链表没有头结点这样一个特殊性，没有把第一个结点单独拿出来建立，因而出现了一些逻辑上的错误 2刚开始写的时候很不适应，不知道从何下手，虽然核心算法的设计早就在心中有一个

18、酝酿，但是实际操作起来还是不能很好的运用 3由于是第一次用“以数据结构为中心”的思想编程，所以并不是很习惯，在主函数中还是充斥着很多基本语句，以后仍要多多练习 4算法的时空分析 该程序不占用额外空间，因此空间复杂度是 O（n）。2.实验心得体会 此次课程设计通过具体的试验设计操作，巩固了数据结构中关于链表的知识。尤其是通过具体的操作，提高了自己的分析问题、解决问题的能力，将以前以为没有实际意义的东西运用到实际中去，去解决实际问题。开始学着分析算法的优劣，并且选择最优算法解决问题，与此同时，从实践中规范了自己编程语言的书写，获益匪浅。课程设计真的在一定程度上提高了同学们对 JAVA 学习得积极性

19、。也为今后的 JAVA学习打下扎实的基础。此次课程设计对我的目的已经基本达到，在今后的 JAVA学习中我一定不断推敲 JAVA，继续在 JAVA 学习的路上奋斗。五、用户使用说明 详细列出每一步的操作说明。当用户编译.JAVA 文件后。1.按照要求输入一个数字。然后按一下回车键会自动跳转到下一个指令。见图 5.1 图 5.1 2.按照要求输入一个数字。然后按一下回车键会自动跳转到下一个指令。见图 5.2 图 5.2 3.按照要求输入一个数字。然后按一下回车键之后设置好了第一个人的密码，然后美输入一个密码都按一下回车键，以此类推。当完成 7 个人的密码设置之后会自动跳出一个出链表的编号，次即为约

20、瑟夫环的理念。见图 5.3 和图 5.4 图 5.4 图 5.3 六、测试结果 七、附录：程序设计源代码 import java.io.*;class Node private int data=new int2;private Node link;private static int count=-1;public Node(int data)this.data0=data;this.data1=+count;link=null;public void setData(int data)this.data0=data;public int getData()return data0;publ

21、ic int getCount()return data1;public void setLink(Node link)this.link=link;public Node getLink()return link;class LinkList public Node head;public Node last;public LinkList(int data)head=new Node(data);head.setLink(head);last=head;public String vistAllNode()Node next=head;String s=new String();do s=

22、s+next.getData()+;/把指针next指向的对象添加到字符串S中 next=next.getLink();/把指针后移，获取下一个指针 while(next!=head);return s;public boolean removeNode(Node node)/去掉node的下一个结点 if(node=last)head=head.getLink();/把头指针指向下一个节点 last.setLink(head);else if(node.getLink()=last)last=node;last.setLink(head);else Node tempN=node.getLi

23、nk();/申明一个临时的指针TempN指向Node的下一个节点 tempN=tempN.getLink();node.setLink(tempN);/Node指向TempN return true;public boolean removeAll()head.setLink(head);last=head;head.setData(0);return true;public void append(int data)/次函数的作用是加一个节点 Node temp=new Node(data);last.setLink(temp)last=temp;last.setLink(head);pub

24、lic class 约瑟夫环 private static LinkList link=new LinkList(0);/申明一个LinkList 的对象 private static int inCount;private static int resultInCount;public static void main(String args)throws IOException /主函数抛出异常 int enter;String inputString=new String();BufferedReader input=new BufferedReader(new InputStreamR

25、eader(System.in);System.out.print(这个程序是解决约瑟夫环的问题。n请输入人数(正整数):);inCount=Integer.parseInt(input.readLine();/把输入的内容转化成INT类型，赋值给INCOUNT System.out.print(请输入初始密码:);int m=Integer.parseInt(input.readLine();System.out.println(请输入每个人的密码:);for(resultInCount=0;resultInCount inCount;resultInCount+)inputString=i

26、nput.readLine();enter=Integer.parseInt(inputString);link.append(enter);link.removeNode(link.last);/去掉链表中最后一个节点 Node p=link.head,q=link.last;int i=0;int j=0;for(;)i+;if(i=m)i=0;m=p.getData();System.out.print(p.getCount()+);link.removeNode(q);/删除Q结点 p=p.getLink();/Q结点后移 j+;if(j=inCount)break;continue;q=q.getLink();/Q的指针往后移 p=q.getLink();/P等于Q的下一个指针