约瑟夫问题数据结构实验报告

中南民族大学管理学院中南民族大学管理学院 学生学生实验报实验报告告 实验项实验项目目 约约瑟夫瑟夫问题问题 课课程名称 程名称 数据数据结结构构 年年 级级 专专 业业 信息管理与信息系信息管理与信息系统统 指指导导教教师师 实验实验地点 地点 管理学院管理学院综综合合实验实验室室 完成日期 完成日期 小小组组成成员员 2012 学年至学年至 2013 学年度第学年度第 1 学期学期 中南民族大学管理学院学生中南民族大学管理学院学生实验报实验报告告 一 一 实验实验目的目的 1 掌握线性表表示和实现 2 学会定义抽象数据类型 3 学会分析问题 设计适当的解决方案 二 二 实验实验内容内容 问题描述 编号为 1 2 n 的 n 个人按顺时针方向围坐一圈 每人 持有一个密码 正整数 一开始任选一个正整数作为报数上限值 m 从 第一个人开始按顺时针方向自 1 开始顺序报数 报到 m 时停止报数 报 m 的人出列 将他的密码作为新的 m 值 从他在顺时针方向上的下一个 人开始重新从 1 报数 如此下去 直至所有人全部出列为止 试设计一个 程序求出出列顺序 基本要求 利用单向循环链表存储结构模拟此过程 按照出列的顺序 印出各人的编号 测试数据 m 的初值为 20 密码 3 1 7 2 4 8 4 正确的 结果应为 6 1 4 7 2 3 5 三 三 实验实验步步骤骤 需求分析需求分析 对于这个程序来说 首先要确定构造链表时所用的插入方法 当数到 m 时一个人就出列 也即删除这个节点 同时建立这个节点的前节点与后节 点的联系 由于是循环计数 所以才采用循环列表这个线性表方式 程序存储结构程序存储结构 利用单循环链表存储结构存储约瑟夫数据 即 n 个人的 编码等 模拟约瑟夫的显示过程 按照出列的顺序显示个人的标号 编号 为 1 2 n 的 n 个人按顺时针方向围坐一圈 每人持有一个密码 正整 数 一开始任选一个正整数作为报数上限值 m 从第一个人开始按顺时 针方向自 1 开始顺序报数 报到 m 时停止报数 报 m 的人出列 将他的 密码作为新的 m 值 从他在顺时针方向上的下一个人开始重新从 1 报数 如此下去 直至所有人全部出列为止 试设计一个程序求出出列顺序 基 本要求是利用单向循环链表存储结构模拟此过程 按照出列的顺序印出各 人的编号 程序执行的命令程序执行的命令 1 构造单向循环链表 2 按照出列的顺序引出各个人的标号 测试数据测试数据 m 的初值为 20 密码 3 1 7 2 4 8 4 正确的结果 应为 6 1 4 7 2 3 5 1 插入 在把元素插入到循环链表中时 由于是采用的头插法 所以 我保留了 front 头结点 在每加入一个节点时 都会直接连接在 front 后 面 从而保证一开始就赋值的 rear 尾节点不用修改 伪代码阐释如下 中南民族大学管理学院学生中南民族大学管理学院学生实验报实验报告告 1 在堆中建立新节点 Node s new Node 2 将 a i 写入到新节点的数据域 s data a i 3 修改新节点的指针域 s next front next 4 修改头结点的指针域 将新节点加入到链表中 front next s 时间复杂度为 1 2 删除 首先通过 p 指针查找到所要删除的节点的前一个节点 继而通 过 q p next 简单地删除掉 假设所要查找的为第 i 个元素 伪代码阐释如下 1 在堆中建立新节点 p 通过循环查找到 i 1 将此节点的地址赋给 p 2 设 q 指向第 i 个节点 若 p rear 则 q front next 否则 q p next 3 摘链 即将 q 从链表中摘除 若 q rear 则 p next front next 否则 则 p next q next 4 保存 q 元素的数据 x q data 5 释放 q 元素 delete q 时间复杂度为 1 3 约瑟夫问题的基本思想 在这个循环查找问题中 通过循环链表实 现了循环查找到节点 一个关键部分就是删除节点后进行链表的链接 从 而保证链表的循环性 在查找方面上 我利用了一个 for 循环来计数所查 找过的节点 其中查找的时间复杂度也为 1 2 概要概要设计设计 测试主函数流程 流程图如下 否 是 开始 输入 m 和 n 创建 Clinklist 类的对象 首先建立循环链表 之后 调用 Josef 函数 判断 m n 是否符合要 求 中南民族大学管理学院学生中南民族大学管理学院学生实验报实验报告告 跳出函数 否 是 否 三 三 详细设计详细设计 include using namespace std const int d 50000 struct Node int data 判断所要删除节点 是否为最后一个 删除该节点 并从该节点的直接 后继结点重新计数 此时要判断 P 和 q 是否存在恰好为 rear 指 针的情况 输出 m 的位置 结束 循环查找到所要删除节点 的前一个节点 判断链表 是否为空 中南民族大学管理学院学生中南民族大学管理学院学生实验报实验报告告 struct Node next 声明 next 指针 class Clinklist public Clinklist int a int n void Josef int m int n private Node rear 声明 rear 和 front 指针 Node front int n Clinklist Clinklist int a int n rear new Node front new Node front next rear 构造空单链表 rear next front rear data a n 1 for int i n 2 i 0 i Node s new Node 循环插入元素来建立链表 s data a i s next front next front next s void Clinklist Josef int m int n Node p front int j 0 while front next front int i 0 while i m 1 实现第 m 1 个节点的查找 if p rear p front next 中南民族大学管理学院学生中南民族大学管理学院学生实验报实验报告告 else p p next i Node q p next if p rear 排除 p 恰好为 rear 节点的情况 q front next front next q next p next front next else if q rear 排除 q 恰好为 rear 节点的情况 p next front next 完成摘链 else p next q next 完成摘链 int x q data 保留 q 点数据 delete q 完成 q 节点的删除 j if j n cout 所出的最后一个人的编号是 x endl int main int m n cout 请输入人数 1 n 50000 n int member d for int i 0 i n i 建立数组 member i i 1 cout 1 m if n 0 m 0 throw 所输入的数不符合要求 Clinklist pro member n 构造 Clinklist 类的对象 pro Josef m n return 0 中南民族大学管理学院学生中南民族大学管理学院学生实验报实验报告告 四 四 调试调试分析分析 调试时调试时出出现现的的问题问题及解决的方法及解决的方法 1 早期程序只写了约瑟夫的实现部分 没有对输入的数据进行筛选 测试 时会出错 2 在先前的程序循环过程中没有进行优化 导致循环次数过多 浪费了一 定的时间 3 为了限制在输入过程中不会上溢 只在输入中限定为四个不全为零的数 字 但是做的是一个循环 在约瑟夫的实现在程序中 为 for 循环 时间 复杂度为 o m n 1 当 n 1 时 复杂度为 o 1 4 在调试时一开始用的是模板类 调试时就总会遇到 无法解析的外部指 令 之类的问题 由于无法解决 对模板类的理解不好 所以就去掉了模 板类的应用 Templete还需要再次加强 5 rear 指针找不到声明 这个的解决方案是参照别的线性表例子 加 上了如下 struct 类型的语句 才得以运行正常 struct Node int data struct Node next 6 这个是最严重的逻辑错误 就是编译的时候没有任何问题 在程序运行 时会出现乱码或者出错的情况 这个完全靠一点点的逻辑判断了 又用了 最笨的方法 在纸上画一个循环链表才搞定 五 用 五 用户户手册手册 1 我们这个程序的运行环境为 VC 6 0 操作系统 2 进入演示程序后即显示文本方式的用户界面 中南民族大学管理学院学生中南民族大学管理学院学生实验报实验报告告 六 六 测试结测试结果果 中南民族大学管理学院学生中南民族大学管理学院学生实验报实验报告告 七 心得体会 七 心得体会 数据结构的课程设计 相对来说还是一个较大的工程 我们小组各个 成员相互合作 虽然里面的内容不是很完备 但总体上还是一个比较能要 体现数据结构的知识点能力的程序了 这个设计让我们在课堂中学到的理 论知识 解决相应的实际问题 深入理解和灵活掌握所学的内容 使我们 在实践的过程中收获匪浅 认真去做 踏踏实实 静静思考 慢慢进步 会有收获的 八 八 团队团队介介绍绍 小小组组成成员员基本情况介基本情况介绍绍 组长 雷灵花 11056024 组员 涂艺 11056022 伍雨豪 11056029 小小组组成成员员分工情况分工情况 组长 雷灵花 选择的实验设计为第一模块的约瑟夫问题 完成了第一个实 验的程序设计和最终实验报告的总结 组员 涂艺 完成了第二个实验的程序设计和实验报告的撰写工作 选择的 程序设计为第一模块的城市链表实验 组员 伍宇豪 在进行实验当中查阅了大量的相关资料 给出了实验的程序 设计和源代码上的文件资料和指导 小小组组成成员员任任务务完成情况完成情况 程序一和程序二的调试工作完成情况良好 各个结果都能运行 组长实验一 中南民族大学管理学院学生中南民族大学管理学院学生实验报实验报告告 的程序和实验报告完成符合老师要求格式 组员涂艺程序和实验报告完成 情况基本一致 组员伍宇豪也提供了很多的资料和技术支持 总体来说 团 队意识很好 一起共同完成学习任务 九 附 九 附录录 源程序清 源程序清单单 源程序文件名清单 include using namespace std const int d 50000 struct Node int data struct Node next 声明next指针 class Clinklist public Clinklist int a int n void Josef int m int n private Node rear 声明rear和front指针 Node front int n Clinklist Clinklist int a int n rear new Node front new Node front next rear 构造空单链表 rear next front rear data a n 1 for int i n 2 i 0 i Node s new Node 循环插入元素来建立链表 s data a i s next front next front next s void Clinklist Josef int m int n Node p front int j 0 while front next front int i 0 while i m 1 实现第m 1个节点的查找 中南民族大学管理学院学生中南民族大学管理学院学生实验报实验报告告 if p rear p front next else p p next i Node q p next if p rear 排除p恰好为rear节点的情况 q front next front next q next p next front next else if q rear 排除q恰好为rear节点的情况 p next front next 完成摘链 else p next q next 完成摘链 int x q data 保留q点数据 delete q 完成q节点的删除 j if j n cout 所出的最后一个人的编号是 x endl int main int m n cout 请输入人数 1 n 50000 n int member d for int i 0 i n i 建立数组 member i i 1 cout 1 m if n 0 m 0 throw 所输入的数不符合要求 Clinklist pro member n 构造Clinklist类的对象 pro Josef m n return 0 中南民族大学管理学院学生中南民族大学管理学院学生实验报实验报告告 指指导导教教师师批批阅阅 指指标标 最高分最高分 评评分要素分要素评评分分 设计设计技技术术水平水平