数据结构课程设计-约瑟夫环.doc

课课 程程 设设 计计 报报 告告 课程设计名称 数据结构课程设计数据结构课程设计 课程设计题目 约瑟夫环约瑟夫环 院 系 专 业 班 级 学 号 姓 名 指导教师 I 目目 录录 1 1 课程设计介绍课程设计介绍 1 1 1 课程设计内容 1 1 2 课程设计要求 1 2 2 课程设计原理课程设计原理 2 2 1 课设题目粗略分析 2 2 2 原理图介绍 2 2 2 1 功能模块图 2 2 2 2 流程图分析 3 3 数据结构分析数据结构分析 7 3 1 存储结构 7 3 2 算法描述 7 4 4 调试与分析调试与分析 8 4 1 调试过程 8 4 2 程序执行过程 9 参考文献参考文献 12 附附 录 关键部分程序清单 录 关键部分程序清单 13 1 1 1 课程设计介绍课程设计介绍 1 11 1 课程设计内容课程设计内容 编号为 1 2 n 的 n 个人按顺时针方向围坐一圈 每人持有一个密码 正 整数 一开始人选一个正整数作为报数的上限值 m 从第一个人开始顺时针 方向自 1 开始顺序报数 报道 m 时停止报数 报 m 的人出列 将他的密码作 为新的 m 值 从他的顺时针向上的下一个开始重新从 1 报数 如此下去 直 至所有人全部出列为止 设计一个程序求出出列顺序 使用单循环链表作为 存储结构 1 21 2 课程设计要求课程设计要求 1 参考相应的资料 独立完成课程设计任务 2 交规范课程设计报告和软件代码 2 2 2 课程设计原理课程设计原理 2 12 1 课设题目粗略分析课设题目粗略分析 根据课设题目要求 拟将整体程序分为 2 大模块 此 2 个模块相互独立 没 有嵌套调用的情况 以下是 2 个模块的大体分析 1 建立初始化单循环链表 将每个结点的座位号及密码给定 2 建立伴随指针 将循环进行一边 使跟随指针指向头结点前一个结点 然 后进行遍历 循环 m 1 次时输出此时所指向的结点的座位号 将此结点的密码作 为新的 m 值 删除这个结点 循环至剩下最后一个结点 输出该结点的座位号 2 22 2 原理图介绍原理图介绍 2 2 12 2 1 功能模块图功能模块图 mian yue list init list 图 2 1 功能模块图 3 2 2 22 2 2 流程图分析流程图分析 1 如图 2 1 通过主函数进行座位号 n 和初始值 m 的输入 调用建立单煦暖链表函 数 init list 和约瑟夫环出列函数 yue list 图 2 2 主函数 main 流程图 4 2 如图 2 2 建立单循环链表 并且将链表的座位号赋值给 q info 输入每个座 位号的密码给 q code 图 2 3 建立单循环链表流程图 5 3 如图 2 3 进行约瑟夫环出列算法 按先后顺序输出座位号 6 图 2 4 进行约瑟夫环出列算法 yue list 流程图 7 3 数据结构分析数据结构分析 3 1 存储结构存储结构 typedef struct Node int info 节点的座位数 int code 节点的密码 struct Node next PNode LinkList 3 2 算法描述算法描述 1 建立 n 个结点的单循环链表 简单算法说明如下 定义 p q 两个结点指针 使头结点的 next 指针指向自己 先给第一个结 点的密码 code 及座位号 info 赋值 从第二个结点开始用 for 循环进行建立链表并给链表中结点的 code 和 info 赋值 2 进行约瑟夫环算法的循环 将出列的人按顺序输出 简单算法说明如下 定义两个指针 一个为 p 一个为 p 的前一个指针 pre 先进行一次遍历 使 pre 的指针指向头结点的前一个位置 进行循环遍历 用 while p p next 判断结点数是否大于 1 若大于 1 用 for 循环找到第 m 个结点 并输出这个结点的座位号 将结点的座位密码赋给 m 值 并且删除这个结点 如果要删除的结点是头结点 需要将头结点移动到下一个位置 重新进行 for 循环 直到剩下最后一个结点 跳出循环 输出最后一个结点的座位号 并释放 8 4 4 调试与分析调试与分析 4 14 1 调试过程调试过程 在调试程序是主要遇到一下几类问题 问题 1 问题描述 当输入 m 值等于 1 的时候总是从第二个作为开始输出 问题分析 由于程序遍历的结点先进行了一步 才开始遍历 解决方法 建立伴随指针的时候先将程序遍历一遍 使初始化伴随指针指向头结 点的上个位置 问题 2 问题描述 先输出第一个结点后总是无法正确输出 问题分析 没有判断输出的是否是头结点 解决方法 判断输出的是否是头结点 如果是把头结点向后移动 问题 3 问题描述 输入 n m 的时候如果输入的不是正整数 程序无法正常运行 问题分析 没有判断 n m 是否是正整数 解决方法 用 do while 循环语句 如果不是正整数需要重新输入 9 4 24 2 程序执行过程程序执行过程 1 第一次的具体的测试结果如图 4 1 所示 图 4 1 第一次测试结果 2 第二次的具体的测试结果如图 4 2 所示 图 4 2 第二次测试结果 10 3 第三次的具体的测试结果如图 4 3 所示 图 4 3 第三次测试结果 4 第四次的具体的测试结果如图 4 4 所示 图 4 4 第四次测试结果 11 5 第五次的具体的测试结果如图 4 5 所示 图 4 5 第五次测试结果 系统使用说明 1 输入的数据座位数 n 初始值 m 密码必须是正整数 2 输入结束后自动输出结果 按任意键退出 12 参考文献参考文献 1 数据结构 用面向对象的方法与 C 描述 殷人昆等 清华大学出版社 2009 2 算法与数据结构习题精解和实验指导 宁正元等 清华大学出版社 2007 3 谭浩强 C 程序设计 M 北京 清华大学出版社 2005 13 附附 录 关键部分程序清单 录 关键部分程序清单 程序代码程序代码 include include include define ERROR 0 define OK 1 typedef struct Node int info 节点的座位数 int code 节点的密码 struct Node next PNode LinkList typedef LinkList PLinkList int init list PLinkList plist int n 建立循环链表 从 1 到 n 输入节点的密码 struct Node p q int i q PNode malloc sizeof struct Node if q NULL return ERROR 14 plist q q info 1 q next q printf 请输入第 1 个座位的密码 scanf d if q code 0 return ERROR if n 1 return OK for i 2 icodenext q next q next p q p scanf d q info i 15 return OK void yue list PLinkList plist int m 约瑟夫算法 PNode p pre int i p plist pre p p p next while p plist pre p p p next while p p next 当链表中结点个数大于 1 时 for i 1 inext 16 printf 输出 d n p info m p code if plist p 该结点是第一个结点时 首节点应移向下一个 plist p next pre next p next 删除该结点 free p p pre next 循环结束 剩下最后一个节点 printf 输出 d n p info plist NULL free p main LinkList y list int n m 输入所需各参数的值 do 17 printf n 输入总座位数 n n 0 否则重新输入 scanf d while n0 否则重新输入 scanf d while m 1 if init list else printf 输入有错误 n 18 课程设计总结 课程设计总结 本次课程设计涉及到的范围很广 让本人能够比较系统的对 C 语言和数据 结构进行一次整理和复习 同时有了很多的体会和经验 1 巩固了以前学过的 C 语言的知识 在这次课程设计中我体会到 C 语言超 强的逻辑性 能够熟练使用 VC 的编译环境 也对这两门课程有了新的认识 他们既有联系 又相互区别 在编写程序过程中要灵活应用 2 对数据结构的理解有待加强 算法的知识面也有待于提高 不同的人会 选择不同的算法 所以即使同样的程序 不同的人必然会设计出不同的方案 所以以后的学习生活中 一定要广泛涉猎 掌握更多更好的解决问题的方法 3 此次设计让我意识到程序设计是