《约瑟夫生死游戏(C++)数据结构实现》由会员分享，可在线阅读，更多相关《约瑟夫生死游戏(C++)数据结构实现（11页珍藏版）》请在金锄头文库上搜索。
1、题目二：约瑟夫生者死者游戏(链表存储）一:【内容与规定】约瑟夫游戏的大意是：每30个旅客同乘一条船,由于严重超载,加上风高浪大,危险万分;因此船长告诉乘客，只有将全船一半的旅客投入还中，其别人才干幸免遇难。无奈,人们只得批准这种措施，并议定30个人围成一圈，由第一种人数起,依次报数，数到第人，便把她投入大海中,然后再从她的下一种人数起，数到第人,再将她扔进大海中，如此循环地进行,直到剩余1个乘客为止。问哪些位置是将被扔下大海的位置。二:概要设计运用链表循环来解决。一方面,就必须先定义一种链表,按照所需要的长度进行定义，然后令其为指针指向头指针，即完毕了一种循环链表的创立。接下来先打印链表输出。
2、另一方面，就是算法实现，需要运用指针来进行，数据域标记人员编号，先用一种指针循环查找，找到第一种需要删除的人，标记为，先输出节点数,再进行删除。依次循环查找,直到被删除的节点数量为总人数的一半的时候则结束。三：程序执行流程图开始否是输出该节点并且删除，指针后移，标记下一次的起始位置从报数位置起，依次循环数到找到第m个人程序结束鉴定剩余人数与否为一半循环找到报数起始位置，用指针标记创立N个节点的循环链表打印输出链表三:具体代码构造1. 链表的创立（1） 创立头节点oephring() heanew Node；/为头结点申请空间head-no=1;/为数据域赋值head-nexead;形成循环链表
3、(） 循环插入链表vidJosphrng:Createsephus（int n)Ndes=head;标记头结点totalnum=n;fo(n =;noi;w-nexthead;s-next=;s=w；/S作为尾指针一方面申请一种节点,并且指针指向它，然后从2开始赋值,此时先令新节点的指针指向头结点,再令指针指向它,依次循环插入创立。2. 打印输出链表voidJoshring:show()cutonext;whle（!d) coutonet; 先打印输出头结点,然后循环鉴定，将不等于头结点的所有输出。3. 程序主算法vid Josephring:Jsp(int k,int )/从第k个人开始数数
4、,数到m的人出列Node*p=head;/工作指针it j=1;/计数器 whl(j!)j+;=-next;/指针后移 /找到第k个人开始数1的那个人or（int i=;nt;/找到了数的那个人coutw-nonext=wet;/此人出列并删除节点p=p-net;一方面,先要找到第一种报数人的位置，用一种计数器进行循环对比查找，从第一种位置起依次后移一种位置,直到输入的数值等于链表上的某个位置数据域上的数值时，停止查找并且标记为指针。另一方面,从P位置开始,再用一种W指针标记,两个指针一次后移循环查找,当W指针指向的数据域等于所输入的报数间隔M时,则打印输出该节点上的数据，并且删除该节点,指针
5、后移,作为下一次开始数的起始位置。最后,依次循环打印输出，懂得人数为总人数的一半时候,程序停止。四: 运营成果图如下1. 输出船上的总人数2. 输入报数的起始位置3. 输入报数人的间隔之后便是最后界面五：设计过程重要问题 在设计过程中，开始需要掌握是就是思想,重要就是链表的创立跟删除,在设计过程中,我不懂得如何去循环查找,以及如何循环输出，因此刚刚开始无从下手。之后我就开始查找资料,网上参照别人的算法实现，在去征询同窗跟教师,最重要是这个程序不是很难,只要思想掌握好,理解指针链表的创立删除就可以编写。因此在掌握好循环算法之后就可以完毕编写。 六：心得体会通过本次的实训,使我得到了不少的收获。使
6、我的动手能力有了一定的提高，并且学会了如何真正去设计一种简朴的程序，在实训之前，我对程序整体的构造基本上没什么底子，自己历来没完整的编写过一种程序，而这次无疑对我来说我一种最佳的练习。虽然每次去询问都是很简朴的问题,很遭反感,但是每次我均有收获。本次实训的重要运用就是链表,从而也加强了我对链表这背面的理解，最重要的收获就是对程序整体的构造以及其构造，对我此后的学习有很大的协助,此后我会多编写程序来提高自己的综合水平。附录：源程序完整代码ncludeiotream.h#includetli#define mxse10/最大人数sruode no;/第几种人 Nod*ne; ; classoser
7、inprivat：Node*head;in toalnu;public:eprin(）h=w Nod;hea-no=1；had-next=head；voi Createoephu（tn);void sow(）;Jeh(int,int m）;id Josphrng:CeatJosepu(int n）/创立n个节点的链表Nde*ead;ttalnum=n；for（int =2;ino;next=head；s-next=；s=w;voidJoehri:sh()/输出链表outnonxt；hile(!ad)oqnonet;/指针后移 /找到第k个人开始数1的那个人(inti1；inext；/找到了数m的那个人cotnet=w-ex;/此人出列并删除节点=qnt;int min()int k,m；/船上的总数，k为从第几种人开始数,m为数到m的那个人出列Jsephring osephus;cotk;wile(kmazek;ouendl;cotnden;joephus.CreaeJphus（k);cotk;tendlendlm;cotnded;cut船上的人站好队: edlnl;josusshow(）;otedlendl被丢下大海的人： enlendl;joseph.osph(,m);eturn 0;
