约瑟夫环的课程设计实验报告

1 数据结构课程设计报告 学 院 专 业 2005 7 班 课程设计 论文 题目 约瑟夫约瑟夫 二 课程设计 论文 工作自 20072007 年 1 1 月 8 8 日起至 20072007 年 1 1 月 1212 日止 三 课程设计 论文 地点 软件学院机房软件学院机房 四 课程设计 论文 内容要求 1 本课程设计的目的 本课程设计的目的 1 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结 构 存储结构和操 作实现算法 以及它们在程序中的使用方法 2 使学生掌握软件设计的基本内容和设计方法 并培养学生进行规范化 软件设计的能力 3 使学生掌握使用各种计算机资料和有关参考资料 提高学生进行程序 设计的基本能力 2 课程设计的任务及要求 课程设计的任务及要求 1 基本要求 基本要求 1 分析题目 查阅相关资料 2 算法设计 数据结构设计 3 编写代码并调试 4 完成课程设计报告 年 月 日 2 目录目录 一 问题描述 5 二 基本要求 5 三 测试数据 6 四 算法思想 7 五 模块划分 8 六 数据结构 11 七 源程序 12 八 测试情况 26 正文正文 一 问题描述一 问题描述 约瑟夫 Joseph 问题的一种描述是 编号为 1 2 3 n 的 n 个人按顺时针方向围坐一圈 每人持有一个密码 正整数 一 开始任选一个正整数作为报数上限值 m 从第一个人开始按顺时针 方向自 1 开始顺序报数 报到 m 时停止报数 报 m 的人出列 将他 的密码作为新的 m 值 从他的顺时针方向上的下一个人开始重新从 1 报数 如此下去 直至所有人全部出列为止 试设计一个程序求 出出列顺序 以及密码顺序 3 二 基本要求二 基本要求 利用单向循环链表存储结构模拟此过程 按照出列的顺序印出 各人的编号 4 三 测试数据三 测试数据 注注 由于表格有限 特在此注明 当输入的人数大于 30 时 系统提示 输入数字无效 重新输入 当输入的上限值大于 10 时 系统提示 输入数 字无效 重新输入 当输入的密码大于 10 时 系统提示 输入数字无效 重新输入 有两组数字的方格中 有两组数字的方格中 下面的数字为有效数值 下面的数字为有效数值 1234 测试结果 1 出队 密码 顺序 顺序 测试结果 2 出队 密码 顺序 顺序 测试结果 3 出队 密码 顺序 顺序 测试结果 4 出队 密码 顺序 顺序 参与人数4 35 12 69 上限值5811 第一人的 密码 36151 38 151 1 第二人的 密码 47594 112 132 5 第三人的 密码 612662 43 123 6 第四人的 密码 181253 66 56 1 第五人的 密码 3841 64 12 第六人的 密码 51210 55 8 第七人的 密码 987 9 第八人的 密码 24 15 24 8 第九人的 密码 54 20 32 7 第十人的 密码 55 3 第十一人 的密码 119 20 第十二人 的密码 1311 11 次 数 值 项 目 数 5 四 算法思想四 算法思想 为了解决这一问题 可以先定义一个长度为 30 人数 的数组 作为线性存储结构 并把该数组看成是一个首尾相接的环形结构 那么每次报 m 的人 就要在该数组的相应位置做一个删除标记 该 单元以后就不再作为计数单元 这样做不仅算法较复杂 而且效率 低 还要移动大量的元素 用单循环链表来解决这一问题 实现的方法相对要简单得的多 首先定义链表结点 单循环链表的结点结构与一般单链表的结点结 构完全相同 只是数据域用一个整数来表示位置 然后将它们组成 一个具有 n 个结点的单循环链表 接下来从位置为 1 的结点开始数 数到第 m 个结点 就将此结点从循环链表中删去 然后再从删去结 点的下一个结点开始数起 数到第 m 个结点 再将其删去 如此进 行下去 直至全部删去为止 6 五 模块划分五 模块划分 1 1 创建单循环链表模块 创建单循环链表模块 void CreatLinkList LinkList L 构建单循环链表 L LinkList malloc sizeof Node if L NULL printf memory allocation failed goodbye exit 1 void InitLinkList LinkList L int personNumber 初始化单循环链表 Node p q 定义结构体类型指针变量 int i p L 初始化第一个结点 并赋值给 p p data 1 p password GetPassword 调用 GetPassword 输入密码 for i 2 i password GetPassword q data i p next q p q p next L 7 2 2 约瑟夫环约瑟夫环 的操作模块 的操作模块 void GetOutputOrder LinkList L int personNumber int reportValue int array MAXPERSONNUMBER int key MAXPERSONNUMBER Node p q int count 1 i 0 j 0 p L if reportValue 1 q p while q next p q q next 寻找 p 的头一个节点 array i p data reportValue key j p password q next p next 删除结点 p free p 释放 p 中所有数值 p q next count 1 重新记当前位置为 1 personNumber 人数减 1 while personNumber 0 while count reportValue q p p p next count array i p data reportValue key j p password q next p next free p p q next count 1 重新记当前位置为 1 personNumber 8 3 3 输出出列顺序及密码顺序块 输出出列顺序及密码顺序块 void printResult int array int personNumber 输出出列顺序 int i printf n 出队的顺序为 for i 0 i personNumber i printf 3d array i void printkey int key int personNumber 输出密码顺序 int i printf n 出队的密码为 for i 0 i personNumber i printf 3d key i printf n printf n 4 4 主程序模块 主程序模块 int main void 初始化 do 接受命令 处理命令 while 命令 Y return 0 9 六 数据结构六 数据结构 基本抽象数据类型 建立线性表的链式存储结构 利用链式存储结 构建立一单向循环链表 typedef struct Node int data 整型 注 基本数据类型 int password 整型 注 基本数据类型 struct Node next 结点类型 指针类型 Node LinkList 基本抽象数据类型 int array 整型数组 注 存放出对序列 int keyp 整型数组 注 按出队的正确序列 存放密码 int personNumber 整型 注 输入参与的人的个数 int reportValue 整型 注 每次执行的上限值 char I 字符型 注 用于控制是否重新进入运行程序 10 七 源程序及流程图七 源程序及流程图 include stdio h include stdlib h include define MAXPASSWORDVALUE 20 define MAXPERSONNUMBER 30 输入人数的最大值 define MAXFIRSTCOUNTVALUE 10 最大初始上限值 define MAXPASSWORD 20 输入密码最大值 void jiemian cout endl cout 欢迎您进入 约瑟夫环 运行界面 endl cout 请按照提示执行程序 endl cout endl cout 设计者 毛敏 endl cout data 1 p password GetPassword 调用 GetPassword 输入密码 for i 2 i password GetPassword q data i p next q p q p next L int GetPassword 给每个人赋密码 int password static int count 1 定义静态局部整性变量 printf n 请输入第 d 的密码 count scanf d while password MAXPASSWORDVALUE password MAXPERSONNUMBER personNumber MAXFIRSTCOUNTVALUE firstCountValue next p q q next 寻找 p 的头一个节点 array i p data reportValue key j p password q next p next 删除结点 p free p 释放 p 中所有数值 p q next count 1 重新记当前位置为 1 personNumber 人数减 1 while personNumber 0 while count reportValue q p p p next count array i p data reportValue key j p password q next p next free p 14 p q next count 1 重新记当前位置为 1 personNumber void printResult int array int personNumber 输出出列结果 int i printf n 出队的顺序为 for i 0 i personNumber i printf 3d array i void printkey int key int personNumber 输出密码顺序 int i printf n 出队的密码为 for i 0 i 30 personNumber30 firstCountValue 0 重新输入一数值 返回参数 假假 真真 19 3 3 InitLinkList 定义结构体类型指针 p q 定义整型变量 i 初始化第一个结点 并赋值给 p 调用 GetPassword 输入密码 i重新记当前位置为 人数减 假假 真真 真真 假假 删除并释放结点 p personNumber 0 cout reportValue q p p p next cout 调用结束 假假 假假 真真 真真 把 p date 赋值给 array i i 把 p password 赋值给 reportValue 和 key j 22 6 6 printResult 定义整型变量 输入一数值 i重新记当前位置为