约瑟夫生死游戏(c++)数据结构实现

约瑟夫生死游戏(c++)数据结构实现

ID:27115081

大小:104.32 KB

页数:8页

时间:2018-12-01

约瑟夫生死游戏(c++)数据结构实现_第1页
约瑟夫生死游戏(c++)数据结构实现_第2页
约瑟夫生死游戏(c++)数据结构实现_第3页
约瑟夫生死游戏(c++)数据结构实现_第4页
约瑟夫生死游戏(c++)数据结构实现_第5页
资源描述:

《约瑟夫生死游戏(c++)数据结构实现》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

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

2、成了一个循环链表的创建。接下来先打印链表输出。其次,就是算法实现,需要利用指针来进行,数据域标记人员编号,先用一个指针循环查找,找到第一个需要删除的人,标记为1,先输出节点数,再进行删除。依次循环查找,直到被删除的节点数量为总人数的一半的时候则结束。三:程序执行流程图开始否是输出该节点并且删除,指针后移,标记下一次的起始位置从报数位置起,依次循环数到找到第m个人程序结束判定剩下人数是否为一半循环找到报数起始位置,用指针标记创建N个节点的循环链表打印输出链表三:详细代码结构1.链表的创建(1)创建头节点Josephring(){head=newNode;

3、//为头结点申请空间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指针指向它,依次循环插入创

4、建。2.打印输出链表voidJosephring::show(){cout<no<<"t";//先输出头节点Node*q=head->next;while(q!=head){cout<no<<"t";q=q->next;}}先打印输出头结点,然后循环判定,将不等于头结点的全部输出。1.程序主算法voidJosephring::Joseph(intk,intm)//从第k个人开始数数,数到m的人出列{Node*p=head;//工作指针intj=1;//计数器while(j!=k){j++;p=p->next;//指针后移}//

5、找到第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<no<<"t";//输出此人的编号p->next=w->next;//此人出列并删除节点p=p->next;}}首先,先要找到第一个报数人的位置,用一个计数器进行循环对比查找,从第一个位置起依次后移一个位置,直到输入的数值等于链表上的某个位置数据域上的数值时,停止查找并且标记

6、为P指针。其次,从P位置开始,再用一个W指针标记,两个指针一次后移循环查找,当W指针指向的数据域等于所输入的报数间隔M时,则打印输出该节点上的数据,并且删除该节点,P指针后移,作为下一次开始数的起始位置。最后,依次循环打印输出,知道人数为总人数的一半时候,程序停止。四:运行结果图如下1.输出船上的总人数2.输入报数的起始位置3.输入报数人的间隔之后便是最终界面五:设计过程主要问题在设计过程中,开始需要掌握是就是思想,主要就是链表的创建跟删除,在设计过程中,我不知道如何去循环查找,以及如何循环输出,因此刚刚开始无从下手。之后我就开始查找资料,网上参考别人

7、的算法实现,在去咨询同学跟老师,最主要是这个程序不是很难,只要思想掌握好,了解指针链表的创建删除就可以编写。因此在掌握好循环算法之后就可以完成编写。六:心得体会经过本次的实训,使我得到了不少的收获。使我的动手能力有了一定的提升,并且学会了如何真正去设计一个简单的程序,在实训之前,我对程序整体的结构基本上没什么底子,自己从来没完整的编写过一个程序,而这次无疑对我来说我一个最好的练习。虽然每次去询问都是很简单的问题,很遭反感,但是每次我都有收获。本次实训的主要运用就是链表,从而也加强了我对链表这反面的了解,最主要的收获就是对程序整体的结构以及其构造,对我今

8、后的学习有很大的帮助,今后我会多编写程序来提高自己的综合水平。附录:源程序完整代码#inclu

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。