约瑟夫生死游戏C++数据结构实现

1、约瑟夫生者死者游戏（链表存储）一：【内容与要求】约瑟夫游戏的大意是：每30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入还中，其余人才能幸免遇难。无奈，大家只得同意这种办法，并议定30个人围成一圈，由第一个人数起，依次报数，数到第9人，便把他投入大海中，然后再从他的下一个人数起，数到第9人,再将他扔进大海中，如此循环地进行，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。二：概要设计利用链表循环来解决。首先，就必须先定义一个链表，按照所需要的长度进行定义，然后令其为指针指向头指针，即完成了一个循环链表的创建。接下来先打印链表输出。其次

2、，就是算法实现，需要利用指针来进行，数据域标记人员编号，先用一个指针循环查找，找到第一个需要删除的人，标记为1,先输出节点数，再进行删除。依次循环查找，直到被删除的节点数量为总人数的一半的时候则结束。:程序执行流程图三：详细代码结构1 .链表的创建(1) 创建头节点Josephring()(head=newNode;为头结点申请空间head->no=1;/为数据域赋值head->next=head;/形成循环链表(2)循环插入链表voidJosephring二CreateJosephus(intn)(Node*s=head;/标记头结点totalnum=n;for(inti=2;i

3、<=n;i+)Node*w=newNode;/新建一个节点w->no=i;w->next=head;s->next=w;s=w;/S作为尾指针首先申请一个节点，并且W指针指向它，然后从2开始赋值，此时先令新节点的W指针指向头结点，再令S指针指向它，依次循环插入创建。2 .打印输出链表voidJosephring:show()cout<<head->no<<"t"先输出头节点Node*q=head->next;while(q!=head)cout<<q->no<<"t"

4、;q=q->next;先打印输出头结点，然后循环判定，将不等于头结点的全部输出。3 .程序主算法voidJosephring:Joseph(intk,intm)/从第k个人开始数数，数到m的人出列Node*p=head;/工作指针intj=1;/计数器while(j!=k)j+;p=p->next;/指针后移找到第k个人开始数1的那个人for(inti=1;i<=totalnum/2;i+)Node*w=p;/指针w指向开始数1的第k个人j=1;/计数器，为了找到数m的那个人while(j!=m)j+;p=w;w=w->next;找到了数m的那个人cout<<

5、;w->no<<"t"/输出此人的编号p->next=w->next;/此人出列并删除节点p=p->next;首先，先要找到第一个报数人的位置，用一个计数器进行循环对比查找，从第一个位置起依次后移一个位置，直到输入的数值等于链表上的某个位置数据域上的数值时，停止查找并且标记为P指针。其次，从P位置开始，再用一个W指针标记，两个指针一次后移循环查找，当W指针指向的数据域等于所输入的报数间隔M时，则打印输出该节点上的数据，并且删除该节点，P指针后移，作为下一次开始数的起始位置。最后，依次循环打印输出，知道人数为总人数的一半时候，程序停止。四：

6、运行结果图如下1.输出船上的总人数输入报数的起始位置"C:Userdmin-stratorDe5IrtopDebugsadaw,自2.强上的总人数为30w数起始的位置日报数人间隔J输入报数人的间隔之后便是最终界面3.五：设计过程主要问题在设计过程中，开始需要掌握是就是思想，主要就是链表的创建跟删除，在设计过程中，我不知道如何去循环查找，以及如何循环输出，因此刚刚开始无从下手。之后我就开始查找资料，网上参考别人的算法实现，在去咨询同学跟老师，最主要是这个程序不是很难，只要思想掌握好，了解指针链表的创建删除就可以编写。因此在掌握好循环算法之后就可以完成编写。六：心得体会经过本次的实训，使

7、我得到了不少的收获。使我的动手能力有了一定的提升，并且学会了如何真正去设计一个简单的程序，在实训之前，我对程序整体的结构基本上没什么底子，自己从来没完整的编写过一个程序，而这次无疑对我来说我一个最好的练习。虽然每次去询问都是很简单的问题，很遭反感，但是每次我都有收获。本次实训的主要运用就是链表，从而也加强了我对链表这反面的了解，最主要的收获就是对程序整体的结构以及其构造，对我今后的学习有很大的帮助，今后我会多编写程序来提高自己的综合水平。附录：源程序完整代码#include"iostream.h"#include"stdlib.h"#definemaxs

8、ize100/最大人数structNodeintno;/第几个人Node*next;classJosephringprivate:Node*head;inttotalnum;public:Josephring()head=newNode;head->no=1;head->next=head;voidCreateJosephus(intn);voidshow();voidJoseph(intk,intm);)；voidJosephring:CreateJosephus(intn)/创建n个节点的链表(Node*s=head;totalnum=n;for(inti=2;i<=n;

9、i+)(Node*w=newNode;w->no=i;w->next=head;s->next=w;s=w;)voidJosephring:show()/输出链表(cout<<head->no<<"t"Node*q=head->next;while(q!=head)(cout<<q->no<<"t"q=q->next;)voidJosephring:Joseph(intk,intm)/从第k个人开始数数，数到m的人出列(Node*p=head;/工作指针intj=1

10、;/计数器while(j!=k)(j+;p=p->next;/指针后移找到第k个人开始数1的那个人for(inti=1;i<=totalnum/2;i+)(Node*w=p;/指针w指向开始数1的第k个人Node*q;j=1;计数器，为了找到数m的那个人while(j!=m)(j+;q=w;w=w->next;/找到了数m的那个人cout<<w->no<<"t"/输出此人的编号q->next=w->next;/此人出列并删除节点p=q->next;intmain()(intk,m;/船上的总数，k为从第几个人

11、开始数，m为数到m的那个人出列Josephringjosephus;cout<<"船上的总人数为："cin>>k;while(k>maxsize|k<0)(cout<<"超出范围，请重新输入："cin>>k;cout<<endl;cout<<endl<<endl;josephus.CreateJosephus(k);cout<<"报数起始的位置："cin>>k;cout<<endl<<endl<<"报数人间隔："；cin>>m;cout<<endl<<endl;cout&l