《约瑟夫环问题课程设计报告》由会员分享，可在线阅读，更多相关《约瑟夫环问题课程设计报告（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
