《约瑟夫环问题课程设计报告》由会员分享,可在线阅读,更多相关《约瑟夫环问题课程设计报告(16页珍藏版)》请在金锄头文库上搜索。
1、约瑟夫环问题课程设计报告 数据结构 课 程 设 计 报 告 设计课题: 约瑟夫问题 院 系: 计算机科学与技术学院 专业班级: 计算机网络技术 1102 班 学生姓名: 张 利 学 号: 1 1 0 8 0 4 0 2 1 1 指导教师: 王 昱 哲 1 约瑟夫环问题课程设计报告 目 录 1. 需求剖析 . . 3 1.1 问题描绘 . 3 1.2 功能剖析 . 4 2. 纲要设计 . . 5 3. 详尽设计 . . 6 4. 调试与操作说明 . 1 错误 ! 不决义书签。 总 结 . . 16 2 约瑟夫环问题课程设计报告 一需求剖析 1.1 问题描绘 瑟夫 描绘的是: 号 1,2, n 的
2、 n(n0)个人按 方向 坐一圈,每一个人拥有一正整数密 。开始 一个正整数作 数上 限 m,从第一个人开始 方向自 1 起 序 数, 到 m 停止 数, m 的人出圈,将他的密 作 新的 m ,从他在 方向上的下一个人起从头从 1 数。这样下去,直到所有人都出圈 止。令 n 最大 100。要求 一个程 序模 此 程,求出出圈的 号序列。以下 剖析: 这是第一个人,他的 密码是“ 1”,个他输 一个 m 值,假如 m=3, 则从他开始向下走 3 个 2 1 3 这就是第二步的地点, 这时他的密码作为新 的 m 值,即 m=4,同时获得的第一个密码为 4;4 号出去处下走 4, 到 9 这儿;(
3、这这一步完 了 剩 余 的 为 : 0 4 1,2,3,5,6 , 7,8,9,0 ,) 9 5 8 6 7 这就是第三步的地点, 这 时他的密码作为新的 m 值,即 m=9 ,同时获得 的第二个密码为 9;9 号 出去处下走 9,到 0 这儿; 持续走就行了(这儿节余 的就是: 1 , 2, 3, 5, 6,7,8,0 ) 图 1 约瑟夫环问图解 3 约瑟夫环问题课程设计报告 第三步: 约瑟夫环原理演示图 第二次, 1 号出列 1 2 3 4 5 6 7 3 1 7 2 4 8 4 第四步:第三次, 第一步: 给第一个人 第二部:第一次停下的地点, 此 赋初始密码为: 20 则 4 号出列
4、时 6 号出列,并将他的值作为新 从它开始向下走 20 的 m 值,即:新的 m=8;从 7 次,到 6 号地点 好开始持续向下走 8 次,到 1 号 最后排序后的密码序列: 的地点 (本图只演示前两步) 8 3 2 4 1 7 4 6 1 4 7 2 3 5 图 2 约瑟夫环原理演示图 1.2 功能剖析 约瑟夫环问题是一个古老的数学识题,本次课题要求用程序语言的方式解 决数学识题。此问题仅使用单循环链表就能够解决此问题。而改良的约瑟夫问 题经过运用双向循环链表,相同也能方便地解决。 在成立双向循环链表时,由于约瑟夫环的大小由输入决定。为方便操作, 我们将每个结点的数据域的值定为生成结点时的次
5、序号和每一个人拥有的密码。 进行操作时,用一个指针 current 指向目前的结点,指针 front 一直指向头结 点。而后成立双向循环链表, 由于每一个人的密码是经过 rand() 函数随机生成的, 所以指定第一个人的次序号,找到结点,不停地从链表中删除链结点,直到链 表剩下最后一个结点,经过一系列的循环就能够解决改良约瑟夫环问题。 4 约瑟夫环问题课程设计报告 二、纲要设计 1、循环链表抽象数据种类定义 typedef struct LNode/ 定义单循环链表中节点的结构 int num;/ 编号 int pwd;/password struct LNode *next;/ 指向下一结点
6、的指针 LNode; 2、本程序包含一下几个模块 ( 1)结构结点模块 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; ( 2)创立链表模块 void createList(LNode *ppHead,int n) ( 3)出队办理模块 void jose(LNode *ppHead,int m_pwd) ( 4)约瑟夫环说明输
7、出模块 void instruction() ( 5)菜单模块 5 约瑟夫环问题课程设计报告 void menu() ( 6)主函数模块 int main () 函数的调用关系图以下: Case 1 :一个简单的输出函数, 用于说明约瑟夫环; void instruction() 菜单函数; Case 2: 成立的约瑟夫环 , 并输 主 函 数 调 用 函 出已成立的约瑟夫环: 数; void menu() createList(LNode *ppHead,int main() n) 输出该约瑟夫环的每一个人的 出列次序 : jose(LNode *ppHead,int m_pwd) Case
8、 0:default : 输入 0,退出 图 3 约瑟夫环函数调用关系 exit(0) ; 图 三、详尽设计 1. 主函数 6 约瑟夫环问题课程设计报告 Main() 开始 选 择 要 执 行 的 操作 Menu() 功能菜单 功能 1: 约瑟夫环 功能 2:按要求求解 功能 3:退出系统 说明 约瑟夫环 输入总人数 n 输入开始上线数: m 输入每个玩家的密码 调用: createList(&ppHead,n); jose(ppHead,m); 函数求解所需的密码 序列 图 4 主函数数据流程图 依据流程图,主函数程序以下: int main() int n,m,x; LNode *ppHe
9、ad=NULL; menu(); for(;) printf(n 请选摘要履行的操作: ); scanf(%d,&x); system(cls); switch(x) case 1: printf(* *n); printf( 约瑟夫环 :n); 程序运转完, 自动返回到功能菜单 7 约瑟夫环问题课程设计报告 printf( 号 1,2,3,4 ,n 的 n 个人按 方向 坐一圈 , 每人拥有一 个密 n); printf( ( 正整数 ). 一开始任 一个正整数作 数的上限 m,从第一个人 开始 n); printf( 按 方向自 1 开始 序 数 , 到 m 停止 . m 的人出列,将他
10、的密 n); printf(m 作 新的 m , 从他在 方向上的下一人开始从头从 1 数 , 这样 下去 ,n); printf( 直到所有人所有出列 止 . 程打印出列 序 .n); printf(* *n); main(); break; case 2: printf(n 入 人数 n:); scanf(%d,&n); printf( 入开始上限数 m:); scanf(%d,&m); createList(&ppHead,n); printf(n); printf( 出 序: n); jose(ppHead,m); printf(n 瑟夫 游 束 !n); main(); break;
11、 case 0: exit(0); default: system(cls); printf(n 您 的操作有 , 从头 .nnn); main(); return 0; 2. 表的 建 8 约瑟夫环问题课程设计报告 Main() 函数 createList () ; 创 建 储 存 玩 家 密 码 的 循 环 单 链 表 的方法 从主函数中获得玩 家书息 n 假如 n0 否 是 退出 创立循环单链表, 储藏各个玩家密码 创立链表达成返回 主函数 main() 图 5 创立链表函数的数据流程图 /* 创立单向循环链表 ppHead ,人数个数为 n,并输入每一个人的密码值,若成立失败则生成头结
12、点,让 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); / 提示链表创立
13、达成 3. 出队办理 Main() 函数 jose() ;出队函数 从循环链表中按初始密 码挨次扫描,找出对应 的玩家序列 输 出 其 持 有 的 密 码 i=ppHead-pwd; j=ppHead-num; 挪动浮标指针 m_pwd=ppHead-pwd; 输出密码后, 删除相应的结点, 并 释 放 所 占 的 储 存 空 间 free(ppHead); ppHead=p-next; 出 队 处 理 的方法 履行完后返回 主函数 图 6 出队函数的数据流程图 10 约瑟夫环问题课程设计报告 /*p 指向要 除 点的前一个 点, ppHead 指向要 除的 点,使 p=ppHead ,ppH
14、ead 再指向要 除 点的下一个 点, 使 p 和 ppHead 接, 出 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 ppH
15、ead-num,j 要 除的密 printf( 第%d 个人出列,密 : %dn,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 号,密 是 :%dn,j,i); free(ppHead);/ 放 点 4. 瑟夫 明模 void instruction()
16、 printf(* *n); printf( 瑟夫 :n); printf( 号 1,2,3,4 ,n 的 n 个人按 方向 坐一圈 , 每人拥有一个密 n); printf( ( 正整数 ). 一开始任 一个正整数作 数的上限 m,从第一个人开始 n); printf( 按 方向自 1 开始 序 数 , 到 停止 . m 的人出列,将他的密 n); 11 约瑟夫环问题课程设计报告 printf(m 作为新的 m 值, 从他在顺时针方向上的下一人开始从头从 1 报数 , 这样下去 ,n); printf( 直到所有人所有出列为止 . 编程打印出列次序 .n); printf(*n); retu
17、rn 0; 5. 菜单模块 void menu() printf(* 约 瑟 夫 环 *n); printf( n); printf( 1 约 瑟 夫 环 问 题 的 阐 述 n); printf( 2 按 要 求 求 解 约 瑟 夫 环 n); printf( 0 退 出 n); printf(* 欢 迎 使 用 ! *n); 四、程序调试与测试 1. 调用模块时,结点结构的调用与其余模块产生矛盾,致使每一行都出现 两次错误,加入子函数的申明后错误消逝。 2 . 刚开始时曾忽视了一些变量参数的表记 & 和“ * ”,使调试程序时费时 许多。此后应重视确立参数的变量和赋值属性的区分和表记。 3
18、. 本次课程设计采纳数据抽象的程序设计方法,将程序区分为三个层次结 构:元素节点、单向循环链表, 主控制模块。 思路较为清楚, 实现调用顺利。 经过本次实验,使我对数据结构这门课程有了进一步的认识,每一个程序经过需 求剖析、纲要设计、详尽设计以后,思路即清楚体现,程序也很快就出来了,最后经过调试、运转又有新的体验。 12 约瑟夫环问题课程设计报告 这是一个使用循环链表的经典问题。本程序开始运转界面以下: 图 7 约瑟夫环开始运转界面 选择 1 进入约瑟夫环问题论述。 图 8 约瑟夫环问题论述 选择 2,输入以下数据测试: 13 约瑟夫环问题课程设计报告 请输入总人数 n:7 请输入开始上限数
19、m:20; 请挨次输入每一个人的密码: 3 1 7 2 4 8 4 出队次序: 6 1 4 7 2 3 5 图 9 约瑟夫环测试 1 持续选择 2,输入以下数据测试: 请输入总人数 n:5 请输入开始上限数 m:30 请挨次输入每一个人的密码: 3 4 5 6 7 出队次序: 5 3 1 2 4 14 约瑟夫环问题课程设计报告 图 11 约瑟夫环测试 3 测试达成,选择 0 退出。 设计总结 我的此次数据结构课程设计的题目是 :约瑟夫环, 经过对该题目的设计 , 我加深了对数据结构及储存结构的理解 , 进一步地理解和掌握了课本中所学的各样 数据结构,特别是对单循环链表上基本运算的实现 , 学会
20、了怎样把学到的知识用于解决实质问题 , 锻炼了自己着手的能力。 经过此次数据结构课程设计, 我感觉最深的就是对 15 约瑟夫环问题课程设计报告 于循环链表的使用,能够说对循环链表有了比从前更进一步的认识,从前不过一孔之见的,假如只给个题目自己根本不可以把程序完好地编写出来,所以此次课程设计最大的收获就在于对循环链表有了必定的理解,包含此中的一系列操作,如成立一个循环链表,删除链表中的一个结点,增添一个结点等。 在调试程序的时候我也有所领会, 固然约瑟夫环问题不是很难,但调试的时候仍是会出现好多错误,所以我们不可以以为简单就不仔细对待。在此后的学习 中,要能不停发现问题,提出问题,解决问题,从不足之处出发,在不停学习中提升自己。 一周的课程设计很短暂,但此间的内容是很充分的,在此中我学习到了好多平常书籍中没法学到的东西,累积了经验,锻炼了自己剖析问题,解决问题的能力,并学会了怎样将所学的各课知识交融,组织起来进行学习,总而言之这两周中我学到好多,得益匪浅。 16