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

./题目二：约瑟夫生者死者游戏〔链表存储一：[内容与要求]约瑟夫游戏的大意是：每30个旅客同乘一条船,因为严重超载,加上风高浪大,危险万分；因此船长告诉乘客,只有将全船一半的旅客投入还中,其余人才能幸免遇难。无奈,大家只得同意这种办法,并议定30个人围成一圈,由第一个人数起,依次报数,数到第9人,便把他投入大海中,然后再从他的下一个人数起,数到第9人,再将他扔进大海中,如此循环地进行,直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。二：概要设计利用链表循环来解决。首先,就必须先定义一个链表,按照所需要的长度进行定义,然后令其为指针指向头指针,即完成了一个循环链表的创建。接下来先打印链表输出。其次,就是算法实现,需要利用指针来进行,数据域标记人员编号,先用一个指针循环查找,找到第一个需要删除的人,标记为1,先输出节点数,再进行删除。依次循环查找,直到被删除的节点数量为总人数的一半的时候则结束。三：程序执行流程图开始开始否是输出该节点并且删除,指针后移,标记下一次的起始位置从报数位置起,依次循环数到找到第m个人程序结束判定剩下人数是否为一半循环找到报数起始位置,用指针标记创建N个节点的循环链表打印输出链表否是输出该节点并且删除,指针后移,标记下一次的起始位置从报数位置起,依次循环数到找到第m个人程序结束判定剩下人数是否为一半循环找到报数起始位置,用指针标记创建N个节点的循环链表打印输出链表三：详细代码结构链表的创建创建头节点Josephring<> {head=newNode;//为头结点申请空间 head->no=1;//为数据域赋值head->next=head;//形成循环链表}<2>循环插入链表voidJosephring::CreateJosephus<intn>{ Node*s=head;//标记头结点 totalnum=n; for<inti=2;i<=n;i++> {Node*w=newNode;//新建一个节点 w->no=i; w->next=head; s->next=w; s=w;//S作为尾指针 }}首先申请一个节点,并且W指针指向它,然后从2开始赋值,此时先令新节点的W指针指向头结点,再令S指针指向它,依次循环插入创建。打印输出链表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;//计数器 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<<w->no<<"\t";//输出此人的编号 p->next=w->next;//此人出列并删除节点 p=p->next; }}首先,先要找到第一个报数人的位置,用一个计数器进行循环对比查找,从第一个位置起依次后移一个位置,直到输入的数值等于链表上的某个位置数据域上的数值时,停止查找并且标记为P指针。其次,从P位置开始,再用一个W指针标记,两个指针一次后移循环查找,当W指针指向的数据域等于所输入的报数间隔M时,则打印输出该节点上的数据,并且删除该节点,P指针后移,作为下一次开始数的起始位置。最后,依次循环打印输出,知道人数为总人数的一半时候,程序停止。四：运行结果图如下输出船上的总人数输入报数的起始位置输入报数人的间隔之后便是最终界面五：设计过程主要问题在设计过程中,开始需要掌握是就是思想,主要就是链表的创建跟删除,在设计过程中,我不知道如何去循环查找,以及如何循环输出,因此刚刚开始无从下手。之后我就开始查找资料,网上参考别人的算法实现,在去咨询同学跟老师,最主要是这个程序不是很难,只要思想掌握好,了解指针链表的创建删除就可以编写。因此在掌握好循环算法之后就可以完成编写。六：心得体会经过本次的实训,使我得到了不少的收获。使我的动手能力有了一定的提升,并且学会了如何真正去设计一个简单的程序,在实训之前,我对程序整体的结构基本上没什么底子,自己从来没完整的编写过一个程序,而这次无疑对我来说我一个最好的练习。虽然每次去询问都是很简单的问题,很遭反感,但是每次我都有收获。本次实训的主要运用就是链表,从而也加强了我对链表这反面的了解,最主要的收获就是对程序整体的结构以及其构造,对我今后的学习有很大的帮助,今后我会多编写程序来提高自己的综合水平。附录：源程序完整代码#include"iostream.h"#include"stdlib.h"#definemaxsize100//最大人数structNode{intno;//第几个人Node*next;};classJosephring{private: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;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;//计数器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为从第几个人开始数,m为数到m的那个人出列Josephringjosephus;cout<<"船上的总人数为:";cin>>k;while<k>maxsize||k<0>{cout<<"超出范围,请重新输入:";cin>>k;cout<<endl;}cout<<endl<<endl;josephus.CreateJosephus<k>;cout<<"报数起始的位置:";cin>>