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

题目二：

约瑟夫生者死者游戏（链表存储）

一：【内容与要求】

约瑟夫游戏的大意是：每30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入还中，其余人才能幸免遇难。无奈，大家只得同意这种办法，并议定30个人围成一圈，由第一个人数起，依次报数，数到第9人，便把他投入大海中，然后再从他的下一个人数起，数到第9人，再将他扔进大海中，如此循环地进行，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。

二：概要设计

利用链表循环来解决。首先，就必须先定义一个链表，按照所需要的长度进行定义，然后令其为指针指向头指针，即完成了一个循环链表的创建。接下来先打印链表输出。其次，就是算法实现，需要利用指针来进行，数据域标记人员编号，先用一个指针循环查找，找到第一个需要删除的人，标记为1，先输出节点数，再进行删除。依次循环查找，直到被删除的节点数量为总人数的一半的时候则结束。

三：程序执行流程图

开始 创建N个节点的循环链表打印输出链表 循环找到报数起始位置，用指针标记 判定剩下人数是否为一半 否 是 从报数位置起，依次循环数到找到第m个人 输出该节点并且删除，指针后移，标记下一次的起始位置 程序结束 三：详细代码结构 1. 链表的创建

（1） 创建头节点

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指针指向它，依次循环插入创建。

2. 打印输出链表

void Josephring::show() {

cout<no<<\先输出头节点 Node*q=head->next; while(q!=head) {

cout<no<<\ q=q->next; } }

先打印输出头结点，然后循环判定，将不等于头结点的全部输出。

3. 程序主算法

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指针后移，作为下一次开始数的起始位置。

最后，依次循环打印输出，知道人数为总人数的一半时候，程序停止。

四： 运行结果图如下

1. 输出船上的总人数

2. 输入报数的起始位置

3. 输入报数人的间隔之后便是最终界面

本文来源：https://www.bwwdw.com/article/2w2d.html