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

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

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

3、与不同之处， 进一步加深对链表结构类型及链表操作的理解。通过该课程设计， 能运用所学知识， 能上机解决一些实际问题， 了解并初步掌握设计、实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。2目录摘要1序言2目录3正文4一、问题描述4二、逻辑设计5三、详细设计7四、程序代码13五、程序调试与测试13设计总结18参考文献19致谢20附录213正文一、问题描述约瑟夫环问题描述的是：设编号为1，2， n 的 n（n>0）个人按顺时针方向围坐一圈， 每个人持有一正整数密码。 开始时选择一个正整数作为报

4、数上限m，从第一个人开始顺时针方向自 1 起顺序报数，报到 m 时停止报数，报 m 的人出圈，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人起重新从 1报数。如此下去，直到所有人都出圈为止。令n 最大值为 100。要求设计一个程序模拟此过程，求出出圈的编号序列。如下图分析：这是第一个人，他的密码是“ 1”，个他输一个 m 值，如果 m=3,则从他开始向下走3个1092345这就是第二步的位置，这时他的密码作为新的 m 值，即 m=4,同时得到的第一个密码为4； 4 号出去向下走4，到 9 这儿；（这这一步完了剩余的为：1,2,3,5,6 ， 7,8,9,0，）8这就是第三步的位置，

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

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

7、urn 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（）函数的调用关系图如下：6主函数调用函数；菜单函数；main()void menu()图 3 约瑟夫环函数调用关系图三、详细设计1. 主函数Case 1：一个简单的输出函数，用于说明约瑟夫环；void instruction()Case 2:建立的约瑟夫环 ,并输出已建

8、立的约瑟夫环：createList(LNode *ppHead,int n)输出该约瑟夫环的每个人的出列顺序 :jose(LNode *ppHead,int m_pwd)Case 0:default : 输入 0，退出 exit(0) ；7Main() 开始选择要执行的操作Menu() 功能菜单约瑟夫功能 2：按要求功能 3：退出系功能 1：环说明求解约瑟夫环统输入总人数n输入开始上线数：m输入每个玩家的密码调用： createList(&ppHead,n);jose(ppHead,m); 函 数 求 解 所 需的密码序列图 4 主函数数据流程图根据流程图，主函数程序如下：intmai

9、n()int n,m,x;LNode *ppHead=NULL;menu();for(;)printf("n 请选择要执行的操作：");scanf("%d",&x);system("cls");switch(x)case 1:printf("* *n");程序运行完，自动返回到功能菜单8printf(" 约瑟夫环 :n");printf("编号为 1,2,3,4,n 的 n 个人按顺时针方向围坐一圈,每人持有一个密n");printf(" 码(正整数 ).一

10、开始任选一个正整数作为报数的上限值m,从第一个人开始n");printf(" 按顺时针方向自1 开始顺序报数 ,报到 m 时停止 .报 m 的人出列，将他的密码 n");printf("m 作为新的 m 值 ,从他在顺时针方向上的下一人开始重新从1 报数 ,如此下去 ,n");printf(" 直到所有人全部出列为止.编程打印出列顺序 .n");printf("* *n");main();break;case 2:printf("n 请输入总人数 n： ");scanf("%

11、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&qu

12、ot;); main();return 0;2. 链表的创建9Main() 函数createList（） ;创建储存玩家密码的循环单链表的方法从主函数中获取玩家信息 n如果 n>0否是退出创建循环单链表，储存各个玩家密码创建链表完成返回主函数 main()图 5 创建链表函数的数据流程图/* 创建单向循环链表 ppHead，人数个数为 n，并输入每个人的密码值，若建立失败则生成头结点，让 cur 指向他，若建立成功则插入结点 P， cur 指向的数据元素为 p,后续为 "空"的节点，再把 P 插入循环链表 ppHead中 */ 根据流程图，创建链表函数程序如下：voi

13、d createList(LNode *ppHead,int n)int i,m_pwd;LNode *p,*cur;/cur: 浮标指针for(i=1;i<=n;i+)printf(" 输入第 %d 个人的密码： ",i);scanf("%d",&m_pwd);/ 输入持有密码p=createNode(i,m_pwd);/调用构造结点函数if(*ppHead=NULL)/ 如果头结点为空*ppHead=cur=p;/生成头结点，让cur 指向他10cur->next=*ppHead;/cur 的指针域指向自身else/如果不为空，则

14、插入结点p->next = cur->next;cur->next = p;cur= p;/cur 指向新插入结点printf(" 完成创建！ n"); / 提示链表创建完成3. 出队处理Main() 函数jose()；出队函数从循环链表中按初始密码依次扫描，找出对应的玩家序列输出其持有的密码i=ppHead->pwd;j=ppHead->num;移动浮标指针m_pwd=ppHead->pwd;输出密码后， 删除相应的结点，并释放所占的储存空间free(ppHead); ppHead=p->next;图 6 出队函数的数据流程图出队

15、处理的方法执行完后返回主函数/*p 指向要删除节点的前一个节点，ppHead 指向要删除的节点，使p=ppHead，11ppHead 再指向要删除节点的下一个节点，使 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;j<m_pwd;+j)p=ppHead;/p 赋值为 ppHead，p 指向要删

16、除结点的前一个结点ppHead=ppHead->next;/ppHead指向下一个元素p->next = ppHead->next;/p 结点与头结点链接i=ppHead->pwd;/i 赋值为 ppHead->pwdj=ppHead->num;/j 赋值为 ppHead->num， j 为要删除的密码值printf(" 第%d 个人出列，密码： %dn",j,i);m_pwd=ppHead->pwd;/m_pwd 赋值为 ppHead->pwdfree(ppHead);/释放头结点ppHead=p->next;/

17、ppHead 重新赋值给 p->next,即释放前的 ppHead->pwd 指针 /删除报数结点i=ppHead->pwd;/i 赋值为 ppHead->pwdj=ppHead->num;/j 赋值为 ppHead->numprintf(" 最后一个出列是 %d 号，密码是 :%dn",j,i);free(ppHead);/释放头结点4. 约瑟夫环说明模块void instruction()printf("* *n");printf(" 约瑟夫环 :n");printf("编号为 1,2

18、,3,4,n 的 n 个人按顺时针方向围坐一圈,每人持有一个密 n");printf(" 码(正整数 ).一开始任选一个正整数作为报数的上限值m,从第一个人开始 n");printf(" 按顺时针方向自 1 开始顺序报数 ,报到时停止 .报 m 的人出列， 将他的密码 n");printf("m 作为新的m 值,从他在顺时针方向上的下一人开始重新从1 报数 ,如此下去 ,n");12printf(" 直到所有人全部出列为止.编程打印出列顺序 .n");printf("*n");retu

19、rn 0;5. 菜单模块void menu()printf("*约瑟夫环*n");printf("n");printf("1约瑟夫环问题的阐述n");printf("2按要求求解约瑟夫环n");printf("0退出n");printf("*欢迎使用！*n");四、程序代码见附录源程序。五、程序调试与测试1. 调用模块时，结点结构的调用与其他模块产生冲突，导致每一行都出现两次错误，加入子函数的声明后错误消失。2 . 刚开始时曾忽略了一些变量参数的标识"&&q

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

21、数据测试：请输入总人数 n：7请输入开始上限数m：20；请依次输入每个人的密码：3 1 7 2 4 8 4出队顺序：6147235图 9约瑟夫环测试1继续选择 2，输入下列数据测试：请输入总人数 n：5请输入开始上限数m：30请依次输入每个人的密码：3 4 5 6 7出队顺序：5312415图 10约瑟夫环测试2继续选择 2，输入下列数据测试：请输入总人数 n：8请输入开始上限数m：14请依次输入每个人的密码：3 4 5 6 7 8 9 10出队顺序：6728351416图 11约瑟夫环测试3测试完成，选择0 退出。17设计总结我的这次数据结构课程设计的题目是 :约瑟夫环 ,通过对该题目的设计

22、 , 我加深了对数据结构及存储结构的理解 ,进一步地理解和掌握了课本中所学的各种数据结构，尤其是对单循环链表上基本运算的实现 ,学会了如何把学到的知识用于解决实际问题 ,锻炼了自己动手的能力。通过这次数据结构课程设计， 我感受最深的就是对于循环链表的使用， 可以说对循环链表有了比以前更进一步的认识， 以前只是一知半解的， 如果只给个题目自己根本不能把程序完整地编写出来， 所以这次课程设计最大的收获就在于对循环链表有了一定的理解， 包括其中的一系列操作， 如建立一个循环链表， 删除链表中的一个结点，增加一个结点等。在调试程序的时候我也有所体会， 虽然约瑟夫环问题不是很难， 但调试的时候还是会出现

23、很多错误， 因此我们不能认为容易就不认真对待。 在以后的学习中，要能不断发现问题，提出问题，解决问题，从不足之处出发，在不断学习中提高自己。两周的课程设计很短暂， 但其间的内容是很充实的， 在其中我学习到了很多平时书本中无法学到的东西， 积累了经验， 锻炼了自己分析问题， 解决问题的能力，并学会了如何将所学的各课知识融会， 组织起来进行学习， 总而言之这两周中我学到很多，受益匪浅。18参考文献1严蔚敏，吴伟民 .数据结构（ C 语言版）.清华大学出版社 .2严蔚敏，吴伟民 .数据结构题集（ C 语言版）.清华大学出版社 .3 DATA STRUCTURE WITH C+ . William F

24、ord,William Topp . 清华大学出版社（影印版） .4谭浩强 .c 语言程序设计 . 清华大学出版社 .19致谢这次的课程设计， 我们两人一个小组去完成我们自己的课程， 但是还是得到了来自很多方面的帮助。 在此首先要感谢学院提供给我这次实践的机会， 让我们有机会贴近现实， 感受成功的喜悦； 其次要感谢实验机房的老师提供优良的实验设备供我们做课设， 正是这种良好的课设环境让我们整个课设过程心情都非常愉快。再次要感谢指导老师们的辛勤指导， 每当我们遇到疑难问题时， 是他们一次次不厌其烦的解释和悉心的指导，我们才能闯过一个个难关，到达胜利的彼岸，是他们给我们提供了一次宝贵的检验自己机会

25、。 最后也要感谢同学们的帮助， 有了他们的支持使我遇到任何困难都不是一个人在战斗。 感谢所有在我课程设计过程中帮助过我的人！20附录源代码：#include <stdio.h>/输入输出函数头文件#include <stdlib.h>/字符串转短整形函数的头文件10140219/typedef struct LNode/定义单循环链表中节点的结构int num;/ 编号int pwd;/passwordstruct LNode *next;/ 指向下一结点的指针LNode;/* 构造结点 */LNode *createNode(int m_num,int m_pwd)L

26、Node *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 指向的数据元素为 p,后续为 "空"的节点，再把 P 插入循环链表 ppHead

27、 中*/int i,m_pwd;LNode *p,*cur;/cur: 浮标指针for(i=1;i<=n;i+)printf(" 输入第 %d 个人的密码： ",i);scanf("%d",&m_pwd);/ 输入持有密码p=createNode(i,m_pwd);/调用构造结点函数if(*ppHead=NULL)/ 如果头结点为空*ppHead=cur=p;/生成头结点，让cur 指向他cur->next=*ppHead;/cur 的指针域指向自身else/如果不为空，则插入结点21p->next = cur->next

28、;cur->next = p;cur= p;/cur 指向新插入结点printf(" 完成创建！ n"); / 提示链表创建完成/* 出队处理 */void jose(LNode *ppHead,int m_pwd)/*p 指向要删除节点的前一个节点， ppHead 指向要删除的节点，使 p=ppHead， ppHead 再指向要删除节点的下一个节点， 使 p 和 ppHead 链接，输出 p 指向节点的编号和密码值，释放 ppHead，如此循环，直至把所有节点都打印和删除为止！ */ int i,j;LNode *p,*p_del;/ 定义指针变量for(i=1;p

29、!=ppHead;i+)for(j=1;j<m_pwd;+j)p=ppHead;/p 赋值为 ppHead，p 指向要删除结点的前一个结点ppHead=ppHead->next;/ppHead指向下一个元素p->next = ppHead->next;/p 结点与头结点链接i=ppHead->pwd;/i 赋值为 ppHead->pwdj=ppHead->num;/j 赋值为 ppHead->num， j 为要删除的密码值printf(" 第%d 个人出列，密码： %dn",j,i);m_pwd=ppHead->pwd;

30、/m_pwd 赋值为 ppHead->pwdfree(ppHead);/释放头结点ppHead=p->next;/ppHead 重新赋值给p->next,即释放前的ppHead->pwd指针 /删除报数结点i=ppHead->pwd;/i 赋值为 ppHead->pwdj=ppHead->num;/j 赋值为 ppHead->numprintf(" 最后一个出列是 %d 号，密码是 :%dn",j,i);free(ppHead);/释放头结点void instruction()printf("* *n");

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