《约瑟夫环(Joseph)问题》由会员分享，可在线阅读，更多相关《约瑟夫环(Joseph)问题（15页珍藏版）》请在金锄头文库上搜索。
1、约瑟夫环 Joseph 问题 姓名 学号 系别 指导老师 目录 1 程序设计目标2 问题描述3 概要设计4 详细设计5 测试报告6 总结 1 程序设计目标 约瑟夫 Joseph 环问题是数据结构中的经典问题 在学习线性表的时候常用到约瑟夫环问题 通过学习约瑟夫环问题能提高对线性表的理解和应用能力 约瑟夫环问题可利用多种方法求解 本设计主要利用单向循环链表存储结构模拟此过程 按照出列的顺序输出各个人的编号 同时 通过查找C语言相关知识 分析约瑟夫环问题与循环链表之间的联系 然后形成算法的思想对约瑟夫环问题用C语言进行编译实现 2 问题描述 编号是1 2 n的n个人按照顺时针方向围坐一圈 每个人只
2、有一个密码 正整数 一开始任选一个正整数作为报数上限值m 从第一个人开始顺时针方向自1开始顺序报数 报到m时停止报数 报m的人出列 将他的密码作为新的m值 从他在顺时针方向的下一个人开始重新从1报数 如此下去 直到所有人全部出列为止 设计一个程序来求出出列顺序 2 问题描述 图1Joseph环示意图 3 概要设计 本设计实现约瑟夫环问题主要由三个模块构成 主模块 链表的创建 输出序列 图2各模块调用关系 3 概要设计 单向循环链表 将单链表尾节点的指针端由空指针改为指向头节点 使整个单链表形成一个环 图3所示为带头节点的循环单链表 图3循环单链表 4 详细设计 链表的创建主要用到CreateL
3、inkList 函数 首先从主函数main 函数中读取个人信息 包括人数 每个人持有的密码以及第一个报数值 然后开始创建循环单链表来存储每个人的密码 创建完成后返回main 函数 4 详细设计 图4链表的生成 4 详细设计 输出出对序列主要用到Joseph 函数 首先从创建好的循环链表中按初始密码依次找出对应出列序列 然后依次输出每个人持有的密码c 当所有密码输出后 删除相应的节点 并释放所占有的存储空间 返回主函数 4 详细设计 图5输出序列的实现 5 测试报告 尾插入法创建链表voidCreateLinkList LinkList 5 测试报告 voidJoseph LinkList 5 测试报告 图6Joseph环编译结果 6 总结 通过本次的课程设计 我了解到约瑟夫环问题是由古罗马著名的史学家Josephus提出的问题基础上演变而来 所以也称为Josephus问题 Joseph问题的解决方案主要采用循环单链表 循环链表的数据结构 是将一个链表的尾元素指针指向队首元素 在完成设计的同时 我将书上线性表章节的内容复习了一遍 从中也体会到学习数据结构的乐趣
