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

*******************实践教学*******************兰州理工大学软件职业技术学院2023年春季学期算法与数据结构课程设计 题目：约瑟夫环专业班级：姓名：学号：指导教师：成绩：摘要约瑟夫环问题是典型的线性表的应用实例，其开发重要涉及后台数据库的建立和维护以及前端应用程序的开发两个方面。对于前者规定建立起数据一致性和完整性强、数据安全性好的库。而对于后者则规定应用程序功能完备，易使用等特点。

通过度析，我们使用MICROSOFT公司的MicrosoftVisualC++6.0开发工具，运用其提供的各种面向对象的开发工具，特别是数据窗口这一能方便而简洁操纵数据库的智能化对象，一方面在短时间内建立系统应用原型，然后，对初始原型系统进行需求迭代，不断修正和改善，直到形成用户满意的可行系统。关键词：单循环链表；c语言；约瑟夫环；

序言数据结构是研究数据元素之间的逻辑关系的一门课程，以及数据元素及其关系在计算机中的存储表达和对这些数据所施加的运算。该课程设计的目的是通过课程设计的综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课程的重要内容。本次课程设计的内容是用单循环链表模拟约瑟夫环问题，循环链表是一种首尾相接链表，其特点是无须增长存储容量，仅对表的链接方式稍作改变，使表解决更加灵活，约瑟夫环问题就是用单循环链表解决的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。通过该课程设计，能运用所学知识，能上机解决一些实际问题，了解并初步掌握设计、实现较大程序的完整过程，涉及系统分析、编码设计、系统集成、以及调试分析，纯熟掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。

目录摘要 1序言 2目录 3正文 4一、问题描述 4二、逻辑设计 5三、具体设计 7四、程序代码 13五、程序调试与测试 13设计总结 18参考文献 19致谢 20附录 21

正文一、问题描述约瑟夫环问题描述的是：设编号为1，2，…，n的n（n>0）个人按顺时针方向围坐一圈，每个人持有一正整数密码。开始时选择一个正整数作为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出圈，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新从1报数。如此下去，直到所有人都出圈为止。令n最大值为100。规定设计一个程序模拟此过程，求出出圈的编号序列。如下图分析：11234567890这是第一个人，他的密码是“1”，个他输一个m值，假如m=3,则从他开始向下走3个这就是第二步的位置，这时他的密码作为新的m值，即m=4,同时得到的第一个密码为4；4号出去向下走4，到9这儿；（这这一步完了剩余的为：1,2,3,5,6，，7,8,9,0，）这就是第三步的位置，这时他的密码作为新的m值，即m=9，同时得到的第二个密码为9；9号出去向下走9，到0这儿；继续走就行了（这儿剩余的就是：1，2，3，5，6,7,8,0）图1约瑟夫环问图解33271484约瑟夫环原理演示图1234567第二部：第一次停下的位置，此时6号出列，并将他的值作为新的m值，即：新的m=8；从7好开始继续向下走8次，到1号的位置最后排序后的密码序列：（本图只演示前两步）8第三步：第二次，1号出列第四步：第三次，4号出列3第一步：给第一个人赋初始密码为：20则从它开始向下走20次，到6号位置241746147235图2约瑟夫环原理演示图二、逻辑设计1、循环链表抽象数据类型定义typedefstructLNode//定义单循环链表中节点的结构{ intnum;//编号 intpwd;//password structLNode*next;//指向下一结点的指针}LNode;2、本程序包含一下几个模块（1）构造结点模块LNode*createNode(intm_num,intm_pwd){ LNode*p; p=(LNode*)malloc(sizeof(LNode));//生成一个结点 p->num=m_num;//把实参赋给相应的数据域 p->pwd=m_pwd; p->next=NULL;//指针域为空 returnp;}（2）创建链表模块voidcreateList(LNode*ppHead,intn)（3）出队解决模块voidjose(LNode*ppHead,intm_pwd)（4）约瑟夫环说明输出模块voidinstruction()（5）菜单模块voidmenu()（6）主函数模块intmain（）函数的调用关系图如下：CCase2:建立的约瑟夫环,并输出已建立的约瑟夫环：createList(LNode**ppHead,intn)输出该约瑟夫环的每个人的出列顺序:jose(LNode*ppHead,intm_pwd)图3约瑟夫环函数调用关系图菜单函数；voidmenu()主函数调用函数；main()Case1：一个简朴的输出函数，用于说明约瑟夫环；voidinstruction()Case0:default:输入0，退出exit(0)；三、具体设计主函数MMain()开始Menu()功能菜单功能1：约瑟夫环说明功能2：按规定求解约瑟夫环功能3：退出系统输入总人数n输入开始上线数：m输入每个玩家的密码调用：createList(&ppHead,n);jose(ppHead,m);函数求解所需的密码序列选择要执行的操作程序运营完，自动返回到功能菜单图4主函数数据流程图根据流程图，主函数程序如下：intmain(){ intn,m,x; LNode*ppHead=NULL; menu(); for(;;){ printf("\n请选择要执行的操作："); scanf("%d",&x); system("cls"); switch(x){case1: 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(); break; case2: 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; case0: exit(0); default: system("cls"); printf("\n您选择的操作有误，请重新选择...\n\n\n"); main(); } } return0;}链表的创建否否是createList（）;从主函数中获取玩家信息n假如n>0创建循环单链表，储存各个玩家密码退出创建链表完毕返回主函数main()创建储存玩家密码的循环单链表的方法Main()函数图5创建链表函数的数据流程图/*创建单向循环链表ppHead，人数个数为n，并输入每个人的密码值，若建立失败则生成头结点，让cur指向他，若建立成功则插入结点P，cur指向的数据元素为p,后续为"空"的节点，再把P插入循环链表ppHead中*/根据流程图，创建链表函数程序如下：voidcreateList(LNode**ppHead,intn){ inti,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//假如不为空，则插入结点 { p->next=cur->next; cur->next=p; cur=p;//cur指向新插入结点 } } printf("完毕创建！\n");//提醒链表创建完毕}出队解决MMain()函数从循环链表中按初始密码依次扫描，找出相应的玩家序列输出其持有的密码i=ppHead->pwd; j=ppHead->num;移动浮标指针m_pwd=ppHead->pwd;输出密码后，删除相应的结点，并释放所占的储存空间free(ppHead);ppHead=p->next;执行完后返回主函数jose()；出队函数出队解决的方法图6出队函数的数据流程图/*p指向要删除节点的前一个节点，ppHead指向要删除的节点，使p=ppHead，ppHead再指向要删除节点的下一个节点，使p和ppHead链接，输出p指向节点的编号和密码值，释放ppHead，如此循环，直至把所有节点都打印和删除为止！*/根据流程图，出队函数程序如下：voidjose(LNode*ppHead,intm_pwd){ inti,j; LNode*p,*p_del;//定义指针变量 for(i=1;p!=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->pwd j=ppHead->num;//j赋值为ppHead->num，j为要删除的密码值 printf("第%d个人出列，密码：%d\n",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号，密码是:%d\n",j,i); free(ppHead);//释放头结点}4.约瑟夫环说明模块voidinstruction(){printf("****************************************************************\n");printf("约瑟夫环:\n");printf("编号为1,2,3,4…,n的n个人按顺时针方向围坐一圈,每人持有一个密\n");printf("码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始\n");printf("按顺时针方向自1开始顺序报数,报届时停止.报m的人出列，将他的密码\n");printf("m作为新的m值,从他在顺时针方向上的下一人开始重新从1报数,如此下去,\n");printf("直到所有人所有出列为止.编程打印出列顺序.\n");printf("******************************************************\n");return0;}5.菜单模块voidmenu(){ printf("**************************约瑟夫环*****************************\n"); printf("\n"); printf("[1]约瑟夫环问题的阐述\n"); printf("[2]按规定求解约瑟夫环\n"); printf("[0]退出\n"); printf("**************************欢迎使用！****************************\n");}四、程序代码见附录源程序。五、程序调试与测试1.调用模块时，结点结构的调用与其他模块产生冲突，导致每一行都出现两次错误，加入子函数的声明后错误消失。2.刚开始时曾忽略了一些变量参数的标记"&"和“*”，使调试程序时费时不少。此后应重视拟定参数的变量和赋值属性的区分和标记。3.本次课程设计采用数据抽象的程序设计方法，将程序划分为三个层次结构：元素节点、单向循环链表，主控制模块。思绪较为清楚，实现调用顺利。通过本次实验，使我对数据结构这门课程有了进一步的了解，每一个程序通过需求分析、概要设计、具体设计之后，思绪即清楚呈现，程序也不久就出来了，最后通过调试、运营又有新的体验。<测试用例>这是一个使用循环链表的经典问题。本程序开始运营界面如下：图7约瑟夫环开始运营界面图7约瑟夫环开始运营界面选择1进入约瑟夫环问题阐述。图8约瑟夫环问题阐述图8约瑟夫环问题阐述①选择2，输入下列数据测试：请输入总人数n：7请输入开始上限数m：20；请依次输入每个人的密码：3172484出队顺序：6147235图9约瑟夫环测试1图9约瑟夫环测试1②继续选择2，输入下列数据测试：请输入总人数n：5请输入开始上限数m：30请依次输入每个人的密码：34567出队顺序：53124图10约瑟夫环测试2图10约瑟夫环测试2③继续选择2，输入下列数据测试：请输入总人数n：8请输入开始上限数m：14请依次输入每个人的密码：345678910出队顺序：67283514图11约瑟夫环测试3图11约瑟夫环测试3测试完毕，选择0退出。

设计总结我的这次数据结构课程设计的题目是:《约瑟夫环》,通过对该题目的设计,我加深了对数据结构及存储结构的理解,进一步地理解和掌握了课本中所学的各种数据结构，特别是对单循环链表上基本运算的实现,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。通过这次数据结构课程设计，我感受最深的就是对于循环链表的使用，可以说对循环链表有了比以前更进一步的结识，以前只是一知半解的，假如只给个题目自己主线不能把程序完整地编写出来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解，涉及其中的一系列操作，如建立一个循环链表，删除链表中的一个结点，增长一个结点等。在调试程序的时候我也有所体会，虽然约瑟夫环问题不是很难，但调试的时候还是会出现很多错误，因此我们不能认为容易就不认真对待。在以后的学习中，要能不断发现问题，提出问题，解决问题，从局限性之处出发，在不断学习中提高自己。两周的课程设计很短暂，但其间的内容是很充实的，在其中我学习到了很多平时书本中无法学到的东西，积累了经验，锻炼了自己分析问题，解决问题的能力，并学会了如何将所学的各课知识融会，组织起来进行学习，总而言之这两周中我学到很多，受益匪浅。

参考文献1．严蔚敏，吴伟民.《数据结构（C语言版）》.清华大学出版社.2．严蔚敏，吴伟民.《数据结构题集（C语言版）》.清华大学出版社.3．《DATASTRUCTUREWITHC++》.WilliamFord,WilliamTopp.清华大学出版社（影印版）.4．谭浩强.《c语言程序设计》.清华大学出版社.

致谢这次的课程设计，我们两人一个小组去完毕我们自己的课程，但是还是得到了来自很多方面的帮助。在此一方面要感谢学院提供应我这次实践的机会，让我们有机会贴近现实，感受成功的喜悦；另一方面要感谢实验机房的老师提供优良的实验设备供我们做课设，正是这种良好的课设环境让我们整个课设过程心情都非常快乐。再次要感谢指导老师们的辛勤指导，每当我们碰到疑难问题时，是他们一次次不厌其烦的解释和悉心的指导，我们才干闯过一个个难关，到达胜利的彼岸，是他们给我们提供了一次宝贵的检查自己机会。最后也要感谢同学们的帮助，有了他们的支持使我碰到任何困难都不是一个人在战斗。感谢所有在我课程设计过程中帮助过我的人！

附录源代码：#include<stdio.h>//输入输出函数头文献#include<stdlib.h>//字符串转短整形函数的头文献10140219//typedefstructLNode//定义单循环链表中节点的结构{ intnum;//编号 intpwd;//password structLNode*next;//指向下一结点的指针}LNode;/*构造结点*/LNode*createNode(intm_num,intm_pwd){ LNode*p; p=(LNode*)malloc(sizeof(LNode));//生成一个结点 p->num=m_num;//把实参赋给相应的数据域 p->pwd=m_pwd; p->next=NULL;//指针域为空 returnp;}/**创建循环链表**/voidcreateList(LNode**ppHead,intn){/*创建单向循环链表ppHead，人数个数为n，并输入每个人的密码值，若建立失败则生成头结点，让cur指向他，若建立成功则插入结点P，cur指向的数据元素为p,后续为"空"的节点，再把P插入循环链表ppHead中*/ inti,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//假如不为空，则插入结点 { p->next=cur->next; cur->next=p; cur=p;//cur指向新插入结点 } } printf("完毕创建！\n");//提醒链表创建完毕}/*出队解决*/voidjose(LNode*ppHead,intm_pwd){/*p指向要删除节点的前一个节点，ppHead指向要删除的节点，使p=ppHead，ppHead再指向要删除节点的下一个节点，使p和ppHead链接，输出p指向节点的编号和密码值，释放ppHead，如此循环，直至把所有节点都打印和删除为止！*/ inti,j; LNode*p,*p_del;//定义指针变量 for(i=1;p!=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->pwd j=ppHead->num;//j赋值为ppHead->num，j为要删除的密码值 printf("第%d个人出列，密码：%d\n",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号，密码是:%d\n",j,i); free(ppHead);//释放头结点}voidinstruction(){printf("****************************************************************\n");printf("约瑟夫环:\n");printf("编号为1,2,3,4…,n的n个人按顺时针方向围坐一圈,每人持有一个密\n");printf("码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始\n");printf("按顺时针方向自1开始顺序报数,报届时停止.报m的人出列，将他的密码\n");printf("m作为新的m值,从他在顺时针方向上的下一人开始重新从1报数,如此下去,\n");printf("直到所有人所有出列为止.编程打印出列顺序.\n");printf("******************************************************\n");return0;}voidmenu(){ printf("**************************约瑟夫环*****************************\n"); printf("\n"); printf("[1]约瑟夫环问题的阐述\n"); printf("[2]按规定求解约瑟夫环\n"); printf("[0]退出