..
题目二:
约瑟夫生者死者游戏(链表存储)
一:【内容与要求】
约瑟夫游戏的大意是:每30个旅客同乘一条船,因为严重超载,加上风高浪大,危险万分;因此船长告诉乘客,只有将全船一半的旅客投入还中,其余人才能幸免遇难。无奈,大家只得同意这种办法,并议定30个人围成一圈,由第一个人数起,依次报数,数到第9人,便把他投入大海中,然后再从他的下一个人数起,数到第9人,再将他扔进大海中,如此循环地进行,直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。
二:概要设计
利用链表循环来解决。首先,就必须先定义一个链表,按照所需要的长度进行定义,然后令其为指针指向头指针,即完成了一个循环链表的创建。接下来先打印链表输出。其次,就是算法实现,需要利用指针来进行,数据域标记人员编号,先用一个指针循环查找,找到第一个需要删除的人,标记为1,先输出节点数,再进行删除。依次循环查找,直到被删除的节点数量为总人数的一半的时候则结束。
三:程序执行流程图
开始
开始
否是输出该节点并且删除,指针后移,标记下一次的起始位置从报数位置起,依次循环数到找到第m个人程序结束判定剩下人数是否为一半循环找到报数起始位置,用指针标记创建N个节点的循环链表打印输出链表
否
是
输出该节点并且删除,指针后移,标记下一次的起始位置
从报数位置起,依次循环数到找到第m个人
程序结束
判定剩下人数是否为一半
循环找到报数起始位置,用指针标记
创建N个节点的循环链表打印输出链表
三:详细代码结构
链表的创建
创建头节点
Josephring()
{
head=new Node;//为头结点申请空间
head->no=1;//为数据域赋值
head->next=head;//形成循环链表
}
(2) 循环插入链表
void Josephring::CreateJosephus(int n)
{
Node*s=head;//标记头结点
totalnum=n;
for(int i=2;i<=n;i++)
{ Node*w=new Node;//新建一个节点
w->no=i;
w->next=head;
s->next=w;
s=w;//S作为尾指针
}
}
首先申请一个节点,并且W指针指向它,然后从2开始赋值,此时先令新节点的W指针指向头结点,再令S指针指向它,依次循环插入创建。
打印输出链表
void Josephring::show()
{
cout<no<
Node*q=head->next;
while(q!=head)
{
cout<no<
q=q->next;
}
}
先打印输出头结点,然后循环判定,将不等于头结点的全部输出。
程序主算法
void Josephring::Joseph(int k,int m)//从第k个人开始数数,数到m的人出列
{
Node*p=head;//工作指针
int j=1;//计数器
while(j!=k)
{
j++;
p=p->next;//指针后移
}//找到第k个人开始数1的那个人
for(int i=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<
p->next=w->next;//此人出列并删除节点
p=p->next;
}
}
首先,先要找到第一个报数人的位置,用一个计数器进行循环对比查找,从第一个位置起依次后移一个位置,直到输入的数值等于链表上的某个位置数据域上的数值时,停止查找并且标记为P指针。
其次,从P位置开始,再用一个W指针标记,两个指针一次后移循环查找,当W指针指向的数据域等于所输入的报数间隔M时,则打印输出该节点上的数据,并且删除该节点,P指针后移,作为下一次开始数的起始位置。
最后,依次循环打印输出,知道人数为总人数的一半时候,程序停止。
四: 运行结果图如下
输出船上的总人数
输入报数的起始位置
输入报数人的间隔之后便是最终界面
五:设计过程主要问题
在设计过程中,开始需要掌握是就是思想,主要就是链表的创建跟删除,在设计过程中,我不知道如何去循环查找,以及如何循环输出,因此刚刚开始无从下手。之后我就开始查找资料,网上参考别人的算法实现,在去咨询同学跟老师,最主要是这个程序不是很难,只要思想掌
如果觉得《约瑟夫生死者游戏实验报告c语言 约瑟夫生死游戏(C++)数据结构实现.docx》对你有帮助,请点赞、收藏,并留下你的观点哦!