数据结构课程设计报告约瑟夫环完整版[1]课案

1、*实践教学*兰州理工大学软件职业技术学院2011年春季学期算法与数据结构课程设计题 目： 约瑟夫环专业班级： 姓 名：学 号：指导教师：成 绩：摘要约瑟夫环问题是典型的线性表的应用实例， 其开发主要包括后台数据库的建 立和维护以及前端应用程序的开发两个方面。 对于前者要求建立起数据一致性和 完整性强、 数据安全性好的库。 而对于后者则要求应用程序功能完备， 易使用等 特点。经过分析，我们使用 MICROSOFT 公司的 Microsoft Visual C+6.0 开发工 具，利用其提供的各种面向对象的开发工具， 尤其是数据窗口这一能方便而简洁 操纵数据库的智能化对象， 首先在短时间内建立系统

2、应用原型， 然后，对初始原 型系统进行需求迭代，不断修正和改进，直到形成用户满意的可行系统。关键词： 单循环链表； c 语言；约瑟夫环；23序言数据结构是研究数据元素之间的逻辑关系的一门课程， 以及数据元素及其关 系在计算机中的存储表示和对这些数据所施加的运算。 该课程设计的目的是通过 课程设计的综合训练， 培养分析和编程等实际动手能力， 系统掌握数据结构这门 课程的主要内容。本次课程设计的内容是用单循环链表模拟约瑟夫环问题， 循环链表是一种首 尾相接链表， 其特点是无须增加存储容量， 仅对表的链接方式稍作改变， 使表处 理更加灵活， 约瑟夫环问题就是用单循环链表处理的一个实际应用。 通过这个

3、设 计实例，了解单链表和单循环链表的相同与不同之处， 进一步加深对链表结构类 型及链表操作的理解。通过该课程设计， 能运用所学知识， 能上机解决一些实际问题， 了解并初步 掌握设计、实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以 及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的 应用开发打好基础。目录摘要1序言 2目录 3正文4一、问题描述 4.二、逻辑设计 5.三、详细设计 7.四、程序代码 1.3.五、程序调试与测试 1.3.设计总结 1.8.参考文献 1.9.致谢2.0.附录2.1.这就是第二步的位置, 这时他的密码作为新的m值，即m=4，同时得到的第

4、一个密码为正文一、问题描述约瑟夫环问题描述的是：设编号为 1, 2,，n的n （n0）个人按顺时针 方向围坐一圈，每个人持有一正整数密码。开始时选择一个正整数作为报数上限 m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的 人出圈，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新从 1 报数。如此下去，直到所有人都出圈为止。令 n最大值为100。要求设计一个程 序模拟此过程，求出出圈的编号序列。如下图分析：这是第一个人，他的密码是“ 1 ”，个他输一个m值，如果m=3,则从他开始向下走3 个4； 4号出去向下走4, 到9这儿；（这这一步 完了剩余的为：1,2,3,5

5、,6，7,8,9,0,)这就是第三步的位置，这 时他的密码作为新的 m 值，即m=9，同时得到 的第二个密码为9; 9号 出去向下走9，到0这儿； 继续走就行了（这儿剩余 的就是：1，2，3，5， 6,7,8,0）图1约瑟夫环问图解第二次，1号出列第三步:约瑟夫环原理演示图234567第一步：给第一个人第四步：第三次,第二部：第一次停下的位置，此时6号出列，并将他的值作为新赋初始密码为：20则4号出列f(本图只演示前两步)/8 3r214 1从它开始向下走 20次，到6号位置r最后排序后的密码序列:的m值，即：新的m=8;从7 好开始继续向下走8次，到1号 7 46 1 4 7 2 3 5的位

6、置图2约瑟夫环原理演示图二、逻辑设计1、循环链表抽象数据类型定义typedef struct LNode/定义单循环链表中节点的结构 int num;/ 编号int pwd;/passwordstruct LNode *n ext;/指向下一结点的指针LNode;2、本程序包含一下几个模块(1)构造结点模块LNode *createNode(i nt m_nu m,i nt m_pwd)LNode *p;p=(LNode *)malloc(sizeof(LNode);/ 生成一个结点p- num=m_num;把实参赋给相应的数据域 p-pwd=m_pwd;p-next=NULL;/ 指针域为空

7、 return p;2) 创建链表模块void createList(LNode *ppHead,int n)3) 出队处理模块void jose(LNode *ppHead,int m_pwd)4) 约瑟夫环说明输出模块void instruction()5) 菜单模块void menu()6) 主函数模块int main() 函数的调用关系图如下：三、详细设计1.主函数图4主函数数据流程图根据流程图，主函数程序如下：int mai n()int n,m,x;LNode *ppHead=NULL;menu();for(;)printf(n请选择要执行的操作：); scan f(%d, &x)

8、;system(cls);switch(x)case 1:printf(* *n); printf( 约瑟夫环 :n);printf( 编号为1,2,3,4,n的n个人按顺时针方向围坐一圈，每人持有一个密 n);printf(码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始n);printf(按顺时针方向自1开始顺序报数，报到m时停止.报m的人出列，将他的密 码 n);printf(m 作为新的 m 值,从他在顺时针方向上的下一人开始重新从1 报数,如此下去,n);printf( 直到所有人全部出列为止 .编程打印出列顺序 .n);printf( * *n);main();

9、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;case 0:exit(0);default:system(cls);printf(n 您选择的操作有误，请重新选择 .nnn); main();return 0;2. 链表的创建图5创建链表函数的数据流程图/*创建单向循环链表ppHead,

10、人数个数为n,并输入每个人的密码值，若建立失败则生成头结点，让cur指向他，若建立成功则插入结点P，cur指向的数据元素为p,后续为空的节点，再把P插入循环链表ppHead中*/根据流程图，创建链表函数程序如下：void createList(LNode *ppHead,i nt n)int i,m_pwd;LNode *p,*cur;/cur:浮标指针for(i=1;inext=*ppHead;/cur的指针域指向自身 else/如果不为空，贝朋入结点p-n ext = cur-n ext;cur- n ext = p;cur= p;/cur指向新插入结点printf（完成创建！ n）; /

11、提示链表创建完成3. 出队处理图6出队函数的数据流程图/*p指向要删除节点的前一个节点，ppHead指向要删除的节点，使p=ppHead,ppHead再指向要删除节点的下一个节点，使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;jn ext;/ppHead指 向下一个元素p-n ext = ppHead

12、-n ext;/p结点与头结点链接 i=ppHead-pwd;/i 赋值为 ppHead-pwd j=ppHead-num;/j赋值为ppHead-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 pri

13、ntf(最后一个出列是%d号，密码是：dn,j,i);free(ppHead);/释放头结点4. 约瑟夫环说明模块void instruction()printf( *n);printf( 约瑟夫环 ：n);printf( 编号为1,2,3,4,n的n个人按顺时针方向围坐一圈，每人持有一 个密 n);printf(码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始 n);printf( 按顺时针方向自 1 开始顺序报数 ,报到时停止 .报 m 的人出列， 将他的 密码n);printf(m 作为新的 m 值,从他在顺时针方向上的下一人开始重新从1 报数,如此下去 ,n);pr

14、intf（ 直到所有人全部出列为止 .编程打印出列顺序 .n）;printf(f*n);return 0;5. 菜单模块void menu()printf(f*约瑟夫环*n);*printf(n);printf( n);printf(n);printf(n);printf(f*1 约 瑟 夫环问题的阐述2 按 要 求求解约瑟夫环0退出欢迎使用！*n);*四、程序代码见附录源程序。五、程序调试与测试1. 调用模块时，结点结构的调用与其他模块产生冲突，导致每一行都出现 两次错误，加入子函数的声明后错误消失。2 . 刚开始时曾忽略了一些变量参数的标识 & 和“ * ”，使调试程序时费时不 少。今后应

15、重视确定参数的变量和赋值属性的区分和标识。3. 本次课程设计采用数据抽象的程序设计方法，将程序划分为三个层次结 构：元素节点、 单向循环链表， 主控制模块。 思路较为清晰， 实现调用顺利。 经 过本次实验， 使我对数据结构这门课程有了进一步的了解， 每一个程序经过需求 分析、概要设计、详细设计之后，思路即清晰呈现，程序也很快就出来了，最后 经过调试、运行又有新的体验。测试用例这是一个使用循环链表的经典问题。本程序开始运行界面如下:图7约瑟夫环开始运行界面选择1进入约瑟夫环问题阐述。图8约瑟夫环问题阐述选择2,输入下列数据测试：请输入总人数n： 7请输入开始上限数m: 20；请依次输入每个人的密

16、码：3 1 7 2 4 8 4出队顺序：6 1 4 7 2 3 5?:岀岀岀岀岀出 戸人人人人人. Aiiil个个个个个个一 crlj. 6 1 4 7 2 3 m卑丄个人的密码 了入笫玄个人的密码 j入第2个人的密码 了入笫冬个人的密码 ijAffs个人的密码 d入第e个人的密码 痢入第J个人的密码 完成创建!S32417密码是M勺瑟夫坏游戏结束？门约瑟夫坏问题的阐述技要求录解约瑟夫坏0J退出_、.请选择要执行的操作：!=sJ2I2SI图9约瑟夫环测试1码码码码码码岳、 密密密密密密番滴3172454继续选择2,输入下列数据测试：请输入总人数n： 5请输入开始上限数m： 30请依次输入每个人

17、的密码：3 4 5 6 7出队顺序：5 3 1 2 4Jal2sl卜;1个人曲密码?：72今人的密码 个人的密弔马 j入第4个人的密码 趣入第5个人的密码 完成创建！34密码是活码码码码岳、 密密密密胡列列列列 切个个个个一 -5312 出勺瑟夫坏游戏结東？丄约瑟夫坏问题的阐述 技要求乗解约瑟夫坏 酊退出JCNKHJCNNHJCNNHJCNNHJCNNHM：耳 HMM：耳 黑对卬使用 | XX 耳 NKKXNKK 耳 NKHXNKHJCNKHJCNKHJCN请选择要执行的操作：图10约瑟夫环测试2继续选择2,输入下列数据测试：请输入总人数n： 8请输入开始上限数m: 14请依次输入每个人的密码

18、：3 4 5 6 7 8 9 10出队顺序：6 7 2 8 3 5 1 4867834山选51约瑟夫环冋题的阐述 技要求录牌约瑟夫环 町退岀 罔瑟夫坏游戏结束？;K XX JOOXJOOOJ JOOJJOO JCJOXJJO坏耳耳 耳耳 耳耳 耳耳耳為眇曲费费费费费费费n 7 J 勺一 一 IJ*TT hj- IJ*TT hj- IJ*TT hj- IJ*TT hj- 送人人人人人人人人 总刑计汗卅 入入wwwmxw A-i人人人人人A! 洼嗚请兀岀專41.念573密码是汚码码码码码码毋W 密密密密密密密忌 , , , , , , JIHH- 列列列列列列列_於 耳出岀出岀出岀出屮 班人人人人

19、人人Y 川个n琲浄个并于A 6728351em图11约瑟夫环测试3测试完成，选择0退出。设计总结我的这次数据结构课程设计的题目是 :约瑟夫环 ,通过对该题目的设计 , 我加深了对数据结构及存储结构的理解 ,进一步地理解和掌握了课本中所学的各 种数据结构，尤其是对单循环链表上基本运算的实现 ,学会了如何把学到的知识 用于解决实际问题 ,锻炼了自己动手的能力。通过这次数据结构课程设计， 我感受最深的就是对于循环链表的使用， 可以 说对循环链表有了比以前更进一步的认识， 以前只是一知半解的， 如果只给个题 目自己根本不能把程序完整地编写出来， 所以这次课程设计最大的收获就在于对 循环链表有了一定的理

20、解， 包括其中的一系列操作， 如建立一个循环链表， 删除 链表中的一个结点，增加一个结点等。在调试程序的时候我也有所体会， 虽然约瑟夫环问题不是很难， 但调试的时 候还是会出现很多错误， 因此我们不能认为容易就不认真对待。 在以后的学习中， 要能不断发现问题，提出问题，解决问题，从不足之处出发，在不断学习中提高 自己。两周的课程设计很短暂， 但其间的内容是很充实的， 在其中我学习到了很多 平时书本中无法学到的东西， 积累了经验， 锻炼了自己分析问题， 解决问题的能 力，并学会了如何将所学的各课知识融会， 组织起来进行学习， 总而言之这两周 中我学到很多，受益匪浅。参考文献1严蔚敏，吴伟民 .数

21、据结构（ C 语言版）.清华大学出版社 .2严蔚敏，吴伟民 .数据结构题集（ C 语言版）.清华大学出版社 .3DATA STRUCTURE WITH C+ . William Ford,William Topp . 清华大学 出版社（影印版） .4谭浩强 .c 语言程序设计 . 清华大学出版社 .致谢这次的课程设计， 我们两人一个小组去完成我们自己的课程， 但是还是得到 了来自很多方面的帮助。 在此首先要感谢学院提供给我这次实践的机会， 让我们 有机会贴近现实， 感受成功的喜悦； 其次要感谢实验机房的老师提供优良的实验 设备供我们做课设， 正是这种良好的课设环境让我们整个课设过程心情都非常愉

22、 快。再次要感谢指导老师们的辛勤指导， 每当我们遇到疑难问题时， 是他们一次 次不厌其烦的解释和悉心的指导，我们才能闯过一个个难关，到达胜利的彼岸， 是他们给我们提供了一次宝贵的检验自己机会。 最后也要感谢同学们的帮助， 有 了他们的支持使我遇到任何困难都不是一个人在战斗。 感谢所有在我课程设计过 程中帮助过我的人！25附录源代码：#i nclude 输入输出函数头文件#i nclude 字符串转短整形函数的头文件 10140219/typedef struct LNode/定义单循环链表中节点的结构int num;/ 编号int pwd;/passwordstruct LNode *n ex

23、t;/指向下一结点的指针LNode;/*构造结点 */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;/* 创建循环链表 */void createList(LNode *ppHead,int n)/*创建单向循环链表ppHead,人数个数为n,并输入每个人的密码值，若 建立失败则生成头结点，让cur指向他，若建立成功则插入结点P, cur指向

24、的数据元素为p,后续为空的节点，再把P插入循环链表ppHead中*/ 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); /提示链表创建完成/*出队处理 */void jose(LNode *ppHead,int m_pwd)/*p 指向要删除节点的前一个节点， ppHead 指向要删除的节点，使 p=ppHead， ppHead再指向要删

25、除节点的下一个节点，使p和ppHead链接，输出p指向节点 的编号和密码值，释放ppHead,如此循环，直至把所有节点都打印和删除为止！*/int i,j;LNode *p,*p_del;/定义指针变量for(i=1;p!=ppHead;i+)for(j=1;jn ext;/ppHead指 向下一个元素p-n ext = ppHead-n ext;/p结点与头结点链接i=ppHead-pwd;/i 赋值为 ppHead-pwdj=ppHead-num;/j赋值为ppHead-num, j为要删除的密码值 printf(第 %d 个人出列，密码：%dn,j,i);m_pwd=ppHead-pwd

26、;/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);/释放头结点void instruction()printf(* *n);printf( 约瑟夫环 ：n);printf( 编号为1,2,3,4,n的n个人按顺时针方向围坐一圈，每人持有一 个密 n);printf(码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始 n);printf（ 按顺时针方向自 1 开始顺序报数 ,报到时停止 .报 m 的人出列， 将他的 密码 n）;printf（m 作为新的 m