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

上海电力学院数据构造Java课程设计题 目: 学生姓名：学 号：院 系： 计算机与信息工程学院专业年级： 软件工程 级2023年7 月13日名目需求分析 3运行环境 3输入的形式和输入的范围 3输出的形式描述 3功能描述 4测试数据 4概要设计 4抽象数据类型定义描述 4功能模块设计 5模块层次调用关系图 5具体设计 6类函数解析 6主函数解析 8调试分析 9所遇问题 9试验心得 错误!未定义书签。用户使用说明 错误!未定义书签。每一步操作说明 错误!未定义书签。测试结果 错误!未定义书签。附录：程序源代码 错误!未定义书签。一、需求分析【问题描述】约瑟夫〔Joseph〕问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码〔正整数。一开头任选一个正整数作为报数上限值m，从第一个1开头挨次报数，报到m时停顿报数。报m的人出列，将他的密码作为的m1报数，如此下去，直至全部人全部出列为止。试设计一个程序求出出列挨次。【根本要求】利用单向循环链表存储构造或挨次存储构造模拟此过程号。【测试数据】确的出列挨次应为，，72，，。1、运行环境〔软、硬件环境〕开发工具：JDK1.6 eclipse6.0运行环境：WindowsXP2、输入的形式和输入值的范围本个试验所输入的值都强制转化为Int数据类型，由于人数肯定是个正整数，而每个人所持的密码将会作为下一次循环的步数码也是一个大于零的整数，人数同样也是一个正整数。3、输出的形式描述可以在以下环境中运行本次试验①在DOS环境中编译“约瑟夫环.Java”文件②在Eclipse6.0及其以上编译环境下运行依据文字要求依次输入人数、每人密码、初始密码等一些数据〔见图1.3.2〕4、功能描述

〔图〕1.3.2约瑟夫环代码约瑟夫环〔Josephus〕问题是由古罗马的史学家约瑟夫〔Josephus〕提出66—70年犹太人抵抗罗马的起义。约瑟夫作为一个将军，设法守4740名死硬的将士在四周的一个地窖中“要投降毋宁死”。于是，约瑟夫建议每个人轮番杀死他旁边的人，而这个挨次是由抽签打算的。约瑟夫有预谋地抓到了最终一签，并且，作为地窖中的两个幸存者之一，他说服了他原先的牺牲品一起投降了罗马。本次试验的不同点在于有一个初始密码M、每人又有个密码，在他死后〔出局〕之后环的循环处理。最终得到一个出此链表的数字下标代号。5、测试数据①初始密码M=207③73，1，7，2，4，8，4最终得到一个出此链表挨次，用每个链表中元素的下标输出数据。二、概要设计1、抽象数据类型定义描述〔对各类的成员及成员函数进展抽象描述〕NodeLinkListNode类中定义一些函数，为主程序中调用这些函数所效劳；LinkListHeadSetLink函数，然后遍历结点，一次删除结点，使得指针后移。在主函数中运用一个For循环作为足要算法，一次实现约瑟夫环的功能。2、功能模块设计〔如主程序模块设计〕先创立了一个linklist对象，然后分别申明inCountresultIncount员变量。然后通过inCount=Integer.parseInt(input.readLine);把输入的内容转化成INTinCount。ForNodep=link.head,q=link.last;inti=0;//每个人的密码intj=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的下一个指针}3、模块层次调用关系图三、具体设计要的模块写出伪码算法。classNode{privateintdata[]=newint[2];privateNodelink;privatestaticintcount=-1;publicNode(intdata){this.data[0]=data;this.data[1]=++count;link=null;}publicvoidsetData(intdata){this.data[0]=data;}publicintgetData{returndata[0];}publicintgetCount{returndata[1];}publicvoidsetLink(Nodelink){this.link=link;}publicNodegetLink{returnlink;}}NODEsetDatagetDatagetDatagetCount、setLink、getLink等一些函数，为主函数调用这些函数做好预备。这也是前期工作的预备。classLinkList{publicNodehead;publicNodelast;publicLinkList(intdata){head=newNode(data);head.setLink(head);last=head;

//Head调用NODE的构造函数，初始化Head//Head调用SetLink的函数}publicStringvistAllNode{Nodenext=head;Strings=newString;do{s=s+next.getData+““;//把指针next指向的对象添加到字符串S中

//遍历节点next=next.getLink; //把指针后移，猎取下一个指针}while(next!=head);returns;}publicbooleanremoveNode(Nodenode){//去掉node的下一个结点if(node==last){head=head.getLink; //把头指针指向下一个节点last.setLink(head); //尾指针=头指针}elseif(node.getLink==last){last=node;last.setLink(head);}else{NodetempN=node.getLink;

//Last指向头指针//申明一个临时的指针TEMPN指向NODE的下一个节点tempN=tempN.getLink; //把tempN向后移一个node.setLink(tempN); //node指向tempN}returntrue;}

//操作成功返回truepublicbooleanremoveAll{ //此函数的作用是删除全部的节点head.setLink(head); //Head=Headlast=head; //Last=Headhead.setData(0);returntrue;}

//head的数据设置为0publicvoidappend(intdata){Nodetemp=newNode(data);last.setLink(temp);last=temp;last.setLink(head);}

//此函数的作用是加一个节点//申明TEMP节点//尾指针指向TEMP指针//尾指针指向TEMP指针//尾指针指向头指针}LinkListheadlast，headlastNode和setLink函数，在进展结点的遍历和，当删除一个结点之后便产生了指针后移的问题，直到头尾指针一样。publicclass约瑟夫环{privatestaticLinkListlink=newLinkList(0);//申明一个LinkList的对象privatestaticintinCount;privatestaticintresultInCount; //申明两个变量publicstaticvoidmain(String[]args)throwsIOException{//主函数抛出特别intenter;StringinputString=newString;BufferedReader input = newInputStreamReader(

BufferedReader(newSystem.in)); //定义一个缓冲流对象System.out.print(“这个程序是解决约瑟夫环的问题。\n请输入人数(正整数):“);inCount=Integer.parseInt(input.readLine);//把输入的内容转化成INT类型，赋值给INCOUNTSystem.out.print(“请输入初始密码:“);intm=Integer.parseInt(input.readLine);System.out.println(“请输入每个人的密码:“);for (resultInCount = 0; resultInCountresultInCount++){inputString=input.readLine;enter=Integer.parseInt(inputString);link.append(enter);}//循环输入的内容放到链表中

< inCount;link.removeNode(link.last); //去掉链表中最终一个节点Nodep=link.head,q=link.last;inti=0;intj=0;for(;;){i++;

//每个人的密码//人数if(i==m){i=0;m=p.getData;System.out.print(p.getCount+““);link.removeNode(q);p=p.getLink;j++;if(j==inCount)break;continue;}q=q.getLink;p=q.getLink;}}}

//删除Q节点//Q节点后移//假设等于总人数就跳出FOR循环//连续进展下一个循环//Q的指针往后移//P等于Q的下一个指针这是一个主函数代码，里面包括一个For循环，从键盘输入总人数和初始的密码，元素的定义通过数组下标输出来，inCountInteger.parseInt(input.readLine)通过这个方法进展强制类型转换，将其转换成INT类型。再调用函数得到出此链表的的元素的下标。四、调试分析1.所遇问题算法问题，最终在同学们的帮助和我上网找资料和同学们的帮助之下最终解决问题。本试验承受数据抽象程序设计方法。思路清楚，实现时调试顺当：由于刚开头无视了该链表没有头结点这样一个特别性，没有把第一个结点单独拿出来建立，因而消灭了一些规律上的错误刚开头写的时候很不适应，不知道从何下手，虽然核心算法的设计早就在心中有一个酝酿，但是实际操作起来还是不能很好的运用由于是第一次用“以数据构造为中心”的思想编程，所以并不是很习惯，在主函数中还是充满着很多根本语句，以后仍要多多练习算法的时空分析该程序不占用额外空间，因此空间简单度是〔。2.试验心得体会此次课程设计通过具体的试验设计操作，稳固了数据构造中关于链表的学问。尤其是通过具体的操作，提高了自己的分析问题、解决问题的力量，将以前以为没有实际意义的东西运用到实际中去，去解决实际问题。开头学着分析算法的优劣，并且选择最优算法解决问题，与此同时，从实践中标准了自己编程语言的书写，获益匪浅。课程设计真的在肯定程度上提高了同学们对 JAVA学习得乐观性。也为今后的JAVA学习打下扎实的根底。此次课程设计对我的目的已经根本到达，在今后的JAVA学习中我肯定不断推敲JAVA，连续在JAVA学习的路上奋斗。五、用户使用说明具体列出每一步的操作说明。当用户编译.JAVA依据要求输入一个数字。然后按一下回车键会自动跳转到下一个指令。见图5.15.1依据要求输入一个数字。然后按一下回车键会自动跳转到下一个指令。见图5.25.2依据要求输入一个数字。然后按一下回车键之后设置好了第一个人的密码，然后美输入一个密码都按一下回车键，以此类推。当完成7个人的密码设置之后会自动跳出一个出链表的编号，次即为约瑟夫环的理念。见图5.35.4

5.4

5.3七、附录：程序设计源代码importjava.io.*;classNode{privateintdata[]=newint[2];privateNodelink;privatestaticintcount=-1;publicNode(intdata){this.data[0]=data;this.data[1]=++count;link=null;}publicvoidsetData(intdata){this.data[0]=data;}publicintgetData{returndata[0];}publicintgetCount{returndata[1];}publicvoidsetLink(Nodelink){this.link=link;}publicNodegetLink{returnlink;}}LinkListclass {LinkListpublicNodehead;publicNodelast;publicLinkList(intdata){head=newNode(data);head.setLink(head);last=head;}publicStringvistAllNode{Nodenext=head;Strings=newString;do{s=s+next.getData+““;//把指针next指向的对象添加到字符串S中next=next.getLink; //把指针后移，猎取下一个指针}while(next!=head);returns;}publicbooleanremoveNode(Nodenode){//去掉node的下一个结点if(node==last){head=head.getLink; //把头指针指向下一个节点last.setLink(head);}elseif(node.getLink==last){last=node;last.setLink(head);}else{NodetempN=node.getLink;//申明一个临时的指针TempN指向Node的下一个节点tempN=tempN.getLink;node.setLink(tempN);}

//Node指向TempNreturntrue;}publicbooleanremoveAll{head.setLink(head);last=head;head.setData(0);returntrue;}publicvoidappend(intdata){//次函数的作用是加一个节点Nodetemp=newNode(data);last.setLink(temp)last=temp;last.setLink(head);}}LinkListpublicclass约瑟夫环{LinkListprivatestatic//申明一个LinkList的对象

link=newLinkList(0);privatestaticintinCount;privatestaticintresultInCount;publicstaticvoidmain(String[]args)throwsIOException{//主函数抛出特别intenter;StringinputString=newString;Buf