数据结构课程设计报告约瑟夫环完整版[1]

实践教学实践教学 兰州理工大学兰州理工大学 软件职业技术学院 2011 年春季学期 算法与数据结构算法与数据结构课程设计课程设计 题 目 约瑟夫环 专业班级 姓 名 学 号 指导教师 成 绩 1 摘要摘要 约瑟夫环问题是典型的线性表的应用实例 其开发主要包括后台数据库的 建立和维护以及前端应用程序的开发两个方面 对于前者要求建立起数据一致 性和完整性强 数据安全性好的库 而对于后者则要求应用程序功能完备 易 使用等特点 经过分析 我们使用 MICROSOFT 公司的 Microsoft Visual C 6 0 开发工 具 利用其提供的各种面向对象的开发工具 尤其是数据窗口这一能方便而简 洁操纵数据库的智能化对象 首先在短时间内建立系统应用原型 然后 对初 始原型系统进行需求迭代 不断修正和改进 直到形成用户满意的可行系统 关键词 关键词 单循环链表 c 语言 约瑟夫环 2 序言序言 数据结构是研究数据元素之间的逻辑关系的一门课程 以及数据元素及其 关系在计算机中的存储表示和对这些数据所施加的运算 该课程设计的目的是 通过课程设计的综合训练 培养分析和编程等实际动手能力 系统掌握数据结 构这门课程的主要内容 本次课程设计的内容是用单循环链表模拟约瑟夫环问题 循环链表是一种 首尾相接链表 其特点是无须增加存储容量 仅对表的链接方式稍作改变 使 表处理更加灵活 约瑟夫环问题就是用单循环链表处理的一个实际应用 通过 这个设计实例 了解单链表和单循环链表的相同与不同之处 进一步加深对链 表结构类型及链表操作的理解 通过该课程设计 能运用所学知识 能上机解决一些实际问题 了解并初 步掌握设计 实现较大程序的完整过程 包括系统分析 编码设计 系统集成 以及调试分析 熟练掌握数据结构的选择 设计 实现以及操作方法 为进一 步的应用开发打好基础 3 目录目录 摘要 1 序言 2 目录 3 正文 4 一 问题描述 4 二 逻辑设计 5 三 详细设计 7 四 程序代码 13 五 程序调试与测试 13 设计总结 18 参考文献 19 致谢 20 附录 21 4 正文正文 一 问题描述一 问题描述 约瑟夫环问题描述的是 设编号为 1 2 n 的 n n 0 个人按顺时针 方向围坐一圈 每个人持有一正整数密码 开始时选择一个正整数作为报数上 限 m 从第一个人开始顺时针方向自 1 起顺序报数 报到 m 时停止报数 报 m 的人出圈 将他的密码作为新的 m 值 从他在顺时针方向上的下一个人起重新 从 1 报数 如此下去 直到所有人都出圈为止 令 n 最大值为 100 要求设计 一个程序模拟此过程 求出出圈的编号序列 如下图分析 1 2 3 4 5 6 7 8 9 0 这是第一个人 他的 密码是 1 个他输 一个 m 值 如果 m 3 则从他开始向 下走 3 个 这就是第二步的位置 这时他的密码作为新 的 m 值 即 m 4 同时 得到的第一个密码为 4 4 号出去向下走 4 到 9 这儿 这这 一步完了剩余的为 1 2 3 5 6 7 8 9 0 这就是第三步的位置 这时他的密码作为新的 m 值 即 m 9 同时得 到的第二个密码为 9 9 号出去向下走 9 到 0 这儿 继续走就行了 这儿剩余的就是 1 2 3 5 6 7 8 0 图 1 约瑟夫环问图 解 5 3271 4 84 约瑟夫环原理演示图约瑟夫环原理演示图 1 234567 第二部 第一次停下的位置 此时 6 号出列 并将他的值作 为新的 m 值 即 新的 m 8 从 7 好开始继续向下走 8 次 到 1 号的位置 最后排序后的密码序列 本图只演示前两步 8 第三步 第二次 1 号出列 第四步 第三次 4 号出列 3 第一步 给第一个人 赋初始密码为 20 则 从它开始向下走 20 次 到 6 号位置 24 174 6147235 图 2 约瑟夫环原理演示图 二 逻辑设计二 逻辑设计 1 循环链表抽象数据类型定义 typedef struct LNode 定义单循环链表中节点的结构 int num 编号 int pwd password struct LNode next 指向下一结点的指针 LNode 2 本程序包含一下几个模块 1 构造结点模块 LNode createNode int m num int m pwd 6 LNode p p LNode malloc sizeof LNode 生成一个结点 p num m num 把实参赋给相应的数据域 p pwd m pwd p next NULL 指针域为空 return p 2 创建链表模块 void createList LNode ppHead int n 3 出队处理模块 void jose LNode ppHead int m pwd 4 约瑟夫环说明输出模块 void instruction 5 菜单模块 void menu 6 主函数模块 int main 函数的调用关系图如下 7 Case 2 建立的约瑟夫环 并输出 已建立的约瑟夫环 createList LNode ppHead int n 输出该约瑟夫环的每个人的出列 顺序 jose LNode ppHead int m pwd 图 3 约瑟夫环函数调用关系图 菜单函数 void menu 主函数调用函数 main Case 1 一个简单的输出函数 用于说明约瑟夫环 void instruction Case 0 default 输入 0 退出 exit 0 三 详细设计三 详细设计 1 主函数 8 Main 开始 Menu 功能菜单 功能 1 约瑟 夫环说明 功能 2 按要求 求解约瑟夫环 功能 3 退出系 统 输入总人数 n 输入开始上线数 m 输入每个玩家的密码 调用 createList jose ppHead m 函数求解所需 的密码序列 选择要执行 的操作 程序运行完 自 动返回到功能菜 单 图 4 主函数数据流程图 根据流程图 主函数程序如下 int main int n m x LNode ppHead NULL menu for printf n 请选择要执行的操作 scanf d system cls switch x case 1 printf n 9 printf 约瑟夫环 n printf 编号为 1 2 3 4 n 的 n 个人按顺时针方向围坐一圈 每人持有一个密 n printf 码 正整数 一开始任选一个正整数作为报数的上限值 m 从第一个人开始 n printf 按顺时针方向自 1 开始顺序报数 报到 m 时停止 报 m 的人出列 将他的 密码 n printf m 作为新的 m 值 从他在顺时针方向上的下一人开始重新从 1 报数 如此 下去 n printf 直到所有人全部出列为止 编程打印出列顺序 n printf n main break case 2 printf n 请输入总人数 n scanf d printf 请输入开始上限数 m scanf d createList printf n printf 出队顺序 n jose ppHead m printf n 约瑟夫环游戏结束 n main break case 0 exit 0 default system cls printf n 您选择的操作有误 请重新选择 n n n main return 0 2 链表的创建 10 否 是 createList 从主函数中获取玩 家信息 n 如果 n 0 创建循环单链表 储存各个玩家密码 退出 创建链表完成返回 主函数 main 创建储存玩家密码 的循环单链表的方 法 Main 函数 图 5 创建链表函数的数据流程图 创建单向循环链表 ppHead 人数个数为 n 并输入每个人的密码值 若建立 失败则生成头结点 让 cur 指向他 若建立成功则插入结点 P cur 指向的数据 元素为 p 后续为 空 的节点 再把 P 插入循环链表 ppHead 中 根据流程图 创建链表函数程序如下 void createList LNode ppHead int n int i m pwd LNode p cur cur 浮标指针 for i 1 inext ppHead cur 的指针域指向自身 else 如果不为空 则插入结点 p next cur next cur next p cur p cur 指向新插入结点 printf 完成创建 n 提示链表创建完成 3 出队处理 Main 函数 从循环链表中按初始密 码依次扫描 找出对应 的玩家序列 输出其持有的密码 i ppHead pwd j ppHead num 移动浮标指针 m pwd ppHead pwd 输出密码后 删除相应的结点 并释放所占的储存空间 free ppHead ppHead p next 执行完后返回 主函数 jose 出队函数 出队处理 的方法 图 6 出队函数的数据流程图 p 指向要删除节点的前一个节点 ppHead 指向要删除的节点 使 p ppHead ppHead 再指向要删除节点的下一个节点 使 p 和 ppHead 链接 输 12 出 p 指向节点的编号和密码值 释放 ppHead 如此循环 直至把所有节点都打 印和删除为止 根据流程图 出队函数程序如下 void jose LNode ppHead int m pwd int i j LNode p p del 定义指针变量 for i 1 p ppHead i for j 1 jnext ppHead 指向下一个元素 p next ppHead next p 结点与头结点链接 i ppHead pwd i 赋值为 ppHead pwd j ppHead num j 赋值为 ppHead num j 为要删除的密码值 printf 第 d 个人出列 密码 d n j i m pwd ppHead pwd m pwd 赋值为 ppHead pwd free ppHead 释放头结点 ppHead p next ppHead 重新赋值给 p next 即释放前的 ppHead pwd 指针 删除报数结点 i ppHead pwd i 赋值为 ppHead pwd j ppHead num j 赋值为 ppHead num printf 最后一个出列是 d 号 密码是 d n j i free ppHead 释放头结点 4 约瑟夫环说明模块 void instruction printf n printf 约瑟夫环 n printf 编号为 1 2 3 4 n 的 n 个人按顺时针方向围坐一圈 每人持有一 个密 n printf 码 正整数 一开始任选一个正整数作为报数的上限值 m 从第一个人 开始 n printf 按顺时针方向自 1 开始顺序报数 报到时停止 报 m 的人出列 将他 的密码 n printf m 作为新的 m 值 从他在顺时针方向上的下一人开始重新从 1 报数 如此下去 n printf 直到所有人全部出列为止 编程打印出列顺序 n 13 printf n return 0 5 菜单模块 void menu printf 约瑟夫环 n printf n printf 1 约瑟夫环问题的阐述 n printf 2 按要求求解约瑟夫环 n printf 0 退出 n printf 欢迎使用 n 四 程序代码四 程序代码 见附录源程序 五 五 程序调试与测试程序调试与测试 1 调用模块时 结点结构的调用与其他模块产生冲突 导致每一行都出现 两次错误 加入子函数的声明后错误消失 2 刚开始时曾忽略了一些变量参数的标识 编号 int pwd password struct LNode next 指向下一结点的指针 LNode 构造结点 LNode createNode int m num int m pwd LNode p p LNode malloc sizeof LNode 生成一个结点 p num m num 把实参赋给相应的数据域 p pwd m pwd p next NULL 指针域为空 return p 创建循环链表 void createList LNode ppHead int n 创建单向循环链表 ppHead 人数个数为 n 并输入每个人的密码值 若 建立失败则生成头结点 让 cur 指向他 若建立成功则插入结点 P cur 指 向的数据元素为 p 后续为 空 的节点 再把 P 插入循环链表 ppHead 中 int i m pwd LNode p cur cur 浮标指针 for i 1 inext ppHead cur 的指针域指向自身 else 如果不为空 则插入结点 22 p next cur next cur next p cur p cur 指向新插入结点 printf 完成创建 n 提示链表创建完成 出队处理 void jose LNode ppHead int m pwd p 指向要删除节点的前一个节点 ppHead 指向要删除的节点 使 p ppHead ppHead 再指向要删除节点的下一个节点 使 p 和 ppHead 链接 输 出 p 指向节点的编号和密码值 释 放 ppHead 如此循环 直至把所有节点都打印和删除为止 int i j LNode p p del 定义指针变量 for i 1 p ppHead i for j 1 jnext ppHead 指向下一个元素 p next ppHead next p 结点与头结点链接 i ppHead pwd i 赋值为 ppHead pwd j ppHead num j 赋值为 ppHead num j 为要删除的密码值 printf 第 d 个人出列 密码 d n j i m pwd ppHead pwd m pwd 赋值为 ppHead pwd free ppHead 释放头结点 ppHead p next ppHead 重新赋值给 p next 即释放前的 ppHead pwd 指针 删除报数结点 i ppHead pwd i 赋值为 ppHead pwd j ppHead num j 赋值为 ppHead num printf 最后一个出列是 d 号 密码是 d n j i free ppHead 释放头结点 void instruction printf n printf 约瑟夫环 n printf 编号为 1 2 3 4 n 的 n 个人按顺时针方向围坐一圈 每人持有一 个密 n printf 码 正整数 一开始任选一个正整数作为报数的上限值 m 从第一个人 开始 n 23 printf 按顺时针方向自 1 开始顺序报数 报到时停止 报 m 的人出列 将他 的密码 n printf m 作为新的 m 值 从他在顺时针方向上的下一人开始重新从 1 报数 如此下去 n printf 直到所有人全部出列为止 编程打印出列顺序 n printf n return