约瑟夫生死游戏(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 ino i w next head s next w s w S 作为尾指针 首先申请一个节点 并且 W 指针指向它 然后从 2 开始赋值 此时先令新节点 的 W 指针指向头结点 再令 S 指针指向它 依次循环插入创建 2 打印输出链表 void Josephring show cout no next while q head cout no 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 inext 找到了数 m 的那个人 cout no next w next 此人出列并删除节点 p p next 首先 先要找到第一个报数人的位置 用一个计数器进行循环对比查找 从第一个位置起依次后移一个位置 直到输入的数值等于链表上的某个位置 数据域上的数值时 停止查找并且标记为 P 指针 其次 从 P 位置开始 再用一个 W 指针标记 两个指针一次后移循环 查找 当 W 指针指向的数据域等于所输入的报数间隔 M 时 则打印输出该 节点上的数据 并且删除该节点 P 指针后移 作为下一次开始数的起始位 置 最后 依次循环打印输出 知道人数为总人数的一半时候 程序停止 四 运行结果图如下运行结果图如下 1 输出船上的总人数 2 输入报数的起始位置 3 输入报数人的间隔之后便是最终界面 五 设计过程主要问题设计过程主要问题 在设计过程中 开始需要掌握是就是思想 主要就是链表的创建跟删 除 在设计过程中 我不知道如何去循环查找 以及如何循环输出 因此刚刚 开始无从下手 之后我就开始查找资料 网上参考别人的算法实现 在去咨询 同学跟老师 最主要是这个程序不是很难 只要思想掌握好 了解指针链表的 创建删除就可以编写 因此在掌握好循环算法之后就可以完成编写 六 心得体会心得体会 经过本次的实训 使我得到了不少的收获 使我的动手能力有了一定 的提升 并且学会了如何真正去设计一个简单的程序 在实训之前 我对程序 整体的结构基本上没什么底子 自己从来没完整的编写过一个程序 而这次无 疑对我来说我一个最好的练习 虽然每次去询问都是很简单的问题 很遭反感 但是每次我都有收获 本次实训的主要运用就是链表 从而也加强了我对链表 这反面的了解 最主要的收获就是对程序整体的结构以及其构造 对我今后的 学习有很大的帮助 今后我会多编写程序来提高自己的综合水平 附录 源程序完整代码 include iostream h include stdlib h define maxsize 100 最大人数 struct Node int no 第几个人 Node next class Josephring private Node head int totalnum public Josephring head new Node head no 1 head next head void CreateJosephus int n void show void Joseph int k int m void Josephring CreateJosephus int n 创建 n 个节点的链表 Node s head totalnum n for int i 2 ino i w next head s next w s w void Josephring show 输出链表 cout no next while q head cout no 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 inext 找到了数 m 的那个人 cout no next w next 此人出列并删除节点 p q next int main int k m 船上的总数 k 为从第几个人开始数 m 为数到 m 的那个人出列 Josephring josephus cout k while k maxsize k 0 cout k cout endl cout endl endl josephus CreateJo