1、 课课 程程 设设 计计 报报 告告 课程设计名称：数据结构课程设计数据结构课程设计 课程设计题目：约瑟夫环约瑟夫环 院（系）： 专 业： 班 级： 学 号： 姓 名： 指导教师： 沈阳航空航天大学课程设计报告 I 目目 录录 1 1 课程设计介绍课程设计介绍 1 1.1 课程设计内容 1 1.2 课程设计要求 1 2 课程设计原理课程设计原理 2 2.1 课设题目粗略分析. 2 2.2 原理图介绍. 2 2.2.1 功能模块图（如图 2.1） . 2 2.2.2 流程图分析 . 3 3 数据结构分析数据结构分析 5 3.1 存储结构. 5 3.2 算法描述. 5 4 调试与分析调试与分析 6
2、 4.1 调试过程. 6 4.2 程序执行过程. 6 参考文献参考文献 8 附附 录（关键部分程序清单）录（关键部分程序清单） 9 沈阳航空航天大学课程设计报告 1 1 1 课程设计介绍课程设计介绍 1.1 课程设计内容课程设计内容 编号为 1,2，n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码 （正整数） 。一开始任选一个正整数作为报数的上限值 m，从第一个人开始按顺时 针方向自 1 开始顺序报数，报到 m 时停止报数，报 m 的人出列，将他的密码作为 新的 m 值，从他的顺时针方向上的下一个开始重新从 1 报数，如此下去，直至所 有人全部出列为止，设计一个程序求出出列顺序。使用单循
3、环链表作为存储结构 分析： 由题意可以将每个人看做链表上的一个节点， 每个人持有的密码即为 每个节点所存储的数据；相邻的人之间存在连结关系，即链表的两个相邻节点之 间由指针来进行关联；最后一个人和第一个人也存在连结关系，即链表的末尾节 点和头结点相连构成了单循环链表存储结构。执行报数过程可以看做一个单独指 针依次指向每一个节点，有人出列即删除掉链表中相应的节点。 1.2 课程设计要求课程设计要求 1.参考相应的资料，独立完成课程设计任务。 2.交规范课程设计报告和软件代码。 沈阳航空航天大学课程设计报告 2 2 课程设计原理 2.1 课设题目粗略分析课设题目粗略分析 根据课设题目要求，程序应该
4、分为两大部分： 1、单循环链表储存结构的建立：建立所需的单循环链表数据存储结构，对每 个节点输入所需的密码、序号数据并通过指针连接成单循环链表。 2、实现约瑟夫环数据出列顺序的算法：依照题目要求按照报数上限对节点进 行查找和删除操作，按顺序输出出列的节点序号，依照每次出列的节点存 储的密码修改报数上限循环操作直到全部节点出列完毕程序运行结束。 2.2 原理图介绍原理图介绍 2.2.1 功能模块图功能模块图（如图（如图 2.1） 图 2.1 功能模块图 建立单循环链表 输出出列顺序 约瑟夫环 沈阳航空航天大学课程设计报告 3 2.2.2 流程图分析流程图分析 1.主程序图，如图 2.2：首先建立
5、单循环链表作为数据存储结构并存储数据，然 后如果执行报数。如果链表中剩余节点数大于 1，执行报数操作，得到节点的序 号数据并输出；若链表中只剩一个节点，输出节点的序号数据，程序运行结束。 图 2.2 主程序图 开始 构建单循环链表； 选定报数上限 m； 链表中节点数大于 1 报数并保存数据 删除节点 选定新的报数上 限m为删除节点 储存的密码 是 否 结束 输出结果 沈阳航空航天大学课程设计报告 4 2.构建单循环链表流程图，如图 2.3：首先为链表存储空间，然后判断节点数是 否达到上限，若没有到达上限，构建新节点；若已到达上限，将末尾节点的指针 指向头结点形成单循环链表并结束建立链表操作。
6、图 2.3 构建单循环链表流程图 开始 分配存储空间 节点数达到最大 构建新节点 末尾节点指向表头 结束 是 否 沈阳航空航天大学课程设计报告 5 3 数据结构分析 3.1 存储结构存储结构 typedef struct LNode int data; /每个人持有的密码 int num; /每个人的编号 struct LNode *next; /指向下一个节点的指针 LNode, *LinkList; /定义一个结构体为一个持有密码的人 3.2 算法描述算法描述 1.构建单循环链表： 首先定义结构体节点指针节点p， 链表L， 头指针head。 使 head 指向 L 的头结点，p 指向 L。对结构体 p 的数据部分进行输入赋值作为 L 的一个节点然后向后移一位。循环此步操作形成单链表。最后将末尾节点的指针 指向头结点形成单循环链表。 2.约瑟
