2022年约瑟夫环Java课程方案大 .pdf

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

1、个人资料整理仅限学习使用上海电力学院数据结构 Java课程设计题目: 约瑟夫环学生姓名：学号：院系：计算机与信息工程学院专业年级：软件工程级 2018 年7月13 日精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 14 页个人资料整理仅限学习使用目录1.需求分析 31.1 运行环境 31.2 输入的形式和输入的范围31.3 输出的形式描述 31.4 功能描述 41.5 测试数据 42.概要设计 42.1 抽象数据类型定义描述42.2 功能模块设计 52.3 模块层次调用关系图53.详细设计 63.1 类函数解读 63.2 主函数解读 8

2、4.调试分析 94.1 所遇问题 94.2 实验心得 105.用户使用说明 105.1 每一步操作说明 106.测试结果 117.附录：程序源代码11精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 14 页个人资料整理仅限学习使用一、需求分析【问题描述】约瑟夫 Joseph）问题的一种描述是：编号为1，2， ，n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1 开始顺序报数，报到m 时停止报数。报m 的人出列，将他的密码作为新的m 值，从他在顺时针方向上的

3、下一个人开始重新从1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。【基本要求】利用单向循环链表存储结构或顺序存储结构模拟此过程，按照出列的顺序印出各人的编号。【测试数据】 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）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 14 页个人资料整理仅限学习使用 图） 1.3.2 4、功能描述约瑟夫环代码约瑟夫环Josephus）

5、问题是由古罗马的史学家约瑟夫Josephus）提出的，他参加并记录了公元66 70 年犹太人反抗罗马的起义。约瑟夫作为一个将军，设法守住了裘达伯特城达47 天之久，在城市沦陷之后，他和40 名死硬的将士在附近的一个洞穴中避难。在那里，这些叛乱者表决说“ 要投降毋宁死” 。于是，约瑟夫建议每个人轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签，并且，作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降了罗马。本次实验的不同点在于有一个初始密码M 、每人又有个密码，在他死后出局）之后将作为下一个循环的步数，这样以此类推得出最后一个幸存者。这个实验主要是模仿约瑟夫环的

6、意思模拟约瑟夫环。差别在与每人的密码将作为下一个循环步数继续开始另一个约瑟夫环的循环处理。最后得到一个出此链表的数字下标代号。5、测试数据初始密码M=20 人数为 7 7 个人的密码依次为：3， 1，7，2，4， 8，4 最后得到一个出此链表顺序，用每个链表中元素的下标输出数据。二、概要设计1、抽象数据类型定义描述对各类的成员及成员函数进行抽象描述）创建 Node 和 LinkList这两个类，在Node类中定义一些函数，为主程序中调用这些函数所服务；LinkList类 Head 指针调用SetLink函数，然后遍历结点，一次删除结点，使得指针后移。在主函数中运用一个For循环作为足要算法，一

7、次实现约瑟夫环的功能。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 14 页个人资料整理仅限学习使用2、功能模块设计 。把输入的内容转化成 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

8、(q。/ 删除 Q节点p = p.getLink(。/Q 结点后移j+ 。if (j = inCount break。/ 如果等于总人数就跳出FOR循环continue。/ 继续进行下一个循环 q = q.getLink(。 /Q 的指针往后移p = q.getLink(。 /P等于 Q的下一个指针3、模块层次调用关系图精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 14 页个人资料整理仅限学习使用三、详细设计实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。class Node privateintdata

9、 = newint2。private Node link。privatestaticintcount = -1。public Node(int data this. data 0 = data。this. data 1 = +count。link = null。 publicvoid setData(int data this. data 0 = data。 publicint getData( returndata 0。 publicint getCount( returndata 1。 publicvoid setLink(Node link this. link = link。 publ

10、ic Node getLink( returnlink。 在 这 个 结 点NODE 类 中 定 义 了 诸 如setData、 getData、 getData、getCount、setLink、 getLink等一些函数，为主函数调用这些函数做好准备。这也是前期工作的准备。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 14 页个人资料整理仅限学习使用class LinkList public Node head 。public Node last。public LinkList(int data head = new Node(d

11、ata。/Head调用 NODE的构造函数，初始化Headhead .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 。 publicboolean removeNode(No

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

13、向 tempN returntrue。/操作成功返回 true publicboolean removeAll( / 此函数的作用是删除所有的节点head .setLink(head 。/Head=Headlast = head 。/Last=Headhead .setData(0。/head的数据设置为 0returntrue。 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 14 页个人资料整理仅限学习使用publicvoid append(int data /此函数的作用是加一个节点Node temp = new Node(dat

14、a。/申明 TEMP节点last.setLink(temp。/ 尾指针指向 TEMP指针last = temp。/ 尾指针指向 TEMP指针last.setLink(head 。/ 尾指针指向头指针 在 LinkList类中申明头尾指针head和 last，head和 last分别调用Node和setLink函数，在进行结点的遍历和，当删除一个结点之后便产生了指针后移的问题，直到头尾指针相同。publicclass约瑟夫环 privatestatic LinkList link = new LinkList(0。/ 申明一个 LinkList 的对象privatestaticintinCoun

15、t。privatestaticintresultInCount。/ 申明两个变量publicstaticvoid main(String args throws IOException / 主函数抛出异常int enter。String inputString = new String(。BufferedReader input = newBufferedReader(newInputStreamReader(System.in 。/ 定义一个缓冲流对象System.out .print( 这个程序是解决约瑟夫环的问题。n 请输入人数( 正整数 :。inCount = Integer.pars

16、eInt(input.readLine(。/ 把输入的内容转化成INT 类型，赋值给 INCOUNTSystem.out .print( 请输入初始密码: 。int m = Integer.parseInt(input.readLine(。System.out .println( 请输入每个人的密码: 。for( resultInCount= 0。resultInCount inputString = input.readLine(。enter = Integer.parseInt(inputString。link.append(enter。 / 循环输入的内容放到链表中link.remove

17、Node(link. last。/去掉链表中最后一个节点Node p = link. head , q = link. last。int i = 0。/ 每个人的密码int j = 0。/ 人数for ( 。 i+ 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 14 页个人资料整理仅限学习使用if (i = m i = 0。m = p.getData(。System.out .print(p.getCount( + 。link.removeNode(q。/ 删除 Q节点p = p.getLink(。/Q 节点后移j+ 。if (j

18、= inCount break。/ 如果等于总人数就跳出FOR循环continue。/ 继续进行下一个循环 q = q.getLink(。 /Q 的指针往后移p = q.getLink(。 /P等于 Q的下一个指针 这是一个主函数代码，里面包括一个For循环，从键盘输入总人数和初始的密码，元素的定义通过数组下标输出来，inCount= Integer.parseInt(input.readLine(通过这个方法进行强制类型转换，将其转换成 INT 类型。再调用函数得到出此链表的的元素的下标。四、调试分析1.所遇问题程序的编写和调试基本正常。遇到的问题主要是：链表的删除，和主要算法的一个循环算法

19、问题，最后在同学们的帮助和我上网找资料和同学们的帮助之下终于解决问题。本实验采用数据抽象程序设计方法。思路清晰，实现时调试顺利：1由于刚开始忽略了该链表没有头结点这样一个特殊性，没有把第一个结点单独拿出来建立，因而出现了一些逻辑上的错误2刚开始写的时候很不适应，不知道从何下手，虽然核心算法的设计早就在心中有一个酝酿，但是实际操作起来还是不能很好的运用3由于是第一次用“以数据结构为中心”的思想编程，所以并不是很习惯，在主函数中还是充斥着很多基本语句，以后仍要多多练习4算法的时空分析该程序不占用额外空间，因此空间复杂度是O this. data 0 = data。this. data 1 = +c

20、ount。link = null。 publicvoid setData(int data 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 14 页个人资料整理仅限学习使用this. data 0 = data。 publicint getData( returndata 0。 publicint getCount( returndata 1。 publicvoid setLink(Node link this. link = link。 public Node getLink( returnlink。 classLinkList p

21、ublic 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 = s + next.getData( + 。/把指针 next指向的对象添加到字符串S中next = next.getLink(。/ 把指针后移，获取下一个指针 while (next != head 。return s 。

22、 publicboolean removeNode(Node node / 去掉 node 的下一个结点if (node = last head = head .getLink(。/ 把头指针指向下一个节点精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 14 页个人资料整理仅限学习使用last.setLink(head 。 elseif (node.getLink( = last last = node。last.setLink(head 。 else Node tempN = node.getLink(。/申明一个临时的指针Temp

23、N指向 Node 的下一个节点tempN = tempN.getLink(。node.setLink(tempN。/Node指向 TempN returntrue。 publicboolean removeAll( head .setLink(head 。last = head 。head .setData(0。returntrue。 publicvoid append(int data /次函数的作用是加一个节点Node temp = new Node(data。last.setLink(temp last = temp。last.setLink(head 。 publicclass约瑟夫环

24、 privatestaticLinkListlink = new LinkList(0。/ 申明一个 LinkList 的对象privatestaticintinCount。privatestaticintresultInCount。publicstaticvoid main(String args throws IOException / 主函数抛出异常int enter。String inputString = new String(。BufferedReaderinput = newBufferedReader(newInputStreamReader(System.in 。System

25、.out .print( 这个程序是解决约瑟夫环的问题。n 请输入人数( 正整数 :。inCount = Integer.parseInt(input.readLine(。/ 把输入的内容转化成INT 类型，赋值给 INCOUNT精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 14 页个人资料整理仅限学习使用System.out .print( 请输入初始密码: 。int m = Integer.parseInt(input.readLine(。System.out .println( 请输入每个人的密码: 。for( resultI

26、nCount= 0。resultInCount inputString = input.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的下一个指针 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 14 页