约瑟夫环数据结构课程设计.docx
《约瑟夫环数据结构课程设计.docx》由会员分享，可在线阅读，更多相关《约瑟夫环数据结构课程设计.docx（16页珍藏版）》请在冰点文库上搜索。
约瑟夫环数据结构课程设计
约瑟夫环问题设计与实现
摘要
约瑟夫问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。
改进约瑟夫问题的描述是：
编号为1，2，…，n的n个人按顺时针方向围坐一圈,每人有一个密码m（整数），留作其出圈后应报到m后出圈，依次类推，即可求出出列顺序。
因此约瑟夫环问题如果采用循环链表则能很好的解决。
循环链表的数据结构，就是将一个链表的最后一个节点指针指向第一个结点。
出列时，根据密码找到对应的人，打印其编号，将其密码赋值给m后，释放节点，形成新的约瑟夫环，直到所有人出列结束。
关键字：
约瑟夫环；循环链表；出列顺序；释放节点；
DesignandRealizationoftheJosephring
ABSTRACT
TheJosephproblemistheevolutionproposedbyancientRomefamoushistorianJosephusandcome,sooftenreferredtoastheJosephusproblem.ImprovementofJosephproblemdescriptionis:
No.1,2,...N,nindividualsaccordingtoaclockwisedirectionaroundacircle,eachwithapasswordofM（integer）,keeptheringshouldbereportedaftertheMring,andsoon,wecancalculatethecolumnorder.SoJosephcircleifusingcircularlinkedlistcanbeverygoodsolution.Circulationlistdatastructure,isthelastofanodeisapointertoalistofthepointstothefirstnode.Out,accordingtothecodetofindthecorrespondingperson,printthenumber,thepasswordisassignedtom,releasethenode,theformationofJosephring,untilallthepeopleoutoftheend.
Keywords:
Josephring;circularlinkedlist;thecolumnorderreleasenodes;
1需求分析………………………………………………………………1
1.1课题内容…………………………………………………………1
1.2要求………………………………………………………………1
2概要设计…………………………………………………………………1
3详细设计…………………………………………………………………2
3.1程序中的数据类型………………………………………………2
3.2函数运行过程详解………………………………………………3
4设计和调试分析…………………………………………………………6
4.1调试中遇到的问题………………………………………………6
4.2经验和体会………………………………………………………7
5用户使用说明……………………………………………………………7
6测试数据和测试结果……………………………………………………8
参考文献……………………………………………………………………10
1需求分析
1.1课题内容：
（1）本演示程序中，人数n应为任意的，首先应输入一个值赋给初始报数上限m，程序应能自动保存出列人的序号和将出列的人所持的密码赋给m，再次作为报数上限，如此循环，直至所有人都出列为止。
（2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据（即每个人所持的密码），每个人的序号由程序自动分配。
（3）程序执行的命令包括：
（1）构造链表；
（2）输入数据；（3）执行报数，储存出列人的序号，删除出列人的信息以及把出列人的密码赋给m；（4）结束。
（4）测试数据
n＝7，7个人的密码依次为：
3，1，7，2，4，8，4，首先m值为6，则这正确的出列顺序为6，1，4，7，2，3，5。
1.2要求：
（1）源程序要有适当的注释，使程序容易阅读；
（2）函数功能要划分好（结构化程序设计）；
（3）可以增加新功能模块；
（4）要提供程序测试方案，程序一定要经得起测试，也要能运行起来，不能运行的程序是没有价值的。
2概要设计
该系统采用C语言开发，主要方法是选择合适的程序结构，灵活使用三种程序设计基本结构、函数等编写程序。
2．1本程序包含三个模块，对应关系图为：
（1）主程序模块；
（2）构造链表并输入每个人信息模块；
（3）每个人依序出列打印出列顺序并释放结点模块；
2.2为了实现上述操作，应以单向循环链表为存储结构。
2.3基本操作：
Data_InPut（）
操作结果：
构造链表，初始化每个人的相关信息
Data_OutPut（）
操作结果：
释放指向出列的人的结点，并重新报数
3详细设计
3.1程序中定义的数据类型
typedefstructLNode{
ElemTypenum;//各人的编号
ElemTypedata;//各人的密码
structLNode*next;//指向下一个节点的指针
}LNode,*LinkList;
程序中定义了一个节点的结构体，每次新分配一个节点内存，即为新增一个人，data为人的密码，num是人的编号。
3.2每个函数的过程详解
3.2.1voidmain（）；
函数原型：
voidmain（）
函数源程序：
voidmain（）
{
LinkListL=NULL;
intm,n=30;//m为报数上限，n为人的个数
inti=0;//常用变量
printf（"\t约瑟夫环问题\n\n"）;
printf（"请输入m的值（要求m<=30）：
"）;
scanf（"%d",&m）;//将m重新赋值
printf（"请输入人数n:
"）;
scanf（"%d",&n）;//确定人的个数，即n得值
while（n>30||n<0）//人数异常处理
{
printf（"请输入小于30的正整数：
"）;
scanf（"%d",&n）;
}
printf（"\n"）;//换行
//调用数据录入函数
Data_InPut（L,n）;
//调用数据输出函数
Data_OutPut（L,n,m）;
}
函数功能及实现：
此为主函数，先输入m和n的值，即确定初始上限m和人数n，并对人数进行防出错处理，之后调用函数Data_InPut（L,n）对n个人编号和输入对应密码，再调用函数Data_OutPut（L,n,m）按照要求对各个人依次出列，打印相关信息到屏幕上。
3.2.2LinkListData_InPut（LinkList&L,intk）;
函数原型：
LinkListData_InPut（LinkList&L,intk）;
函数源程序：
LinkListData_InPut（LinkList&L,intk）
{
LinkListR,P,Q;
L=（LinkList）malloc（sizeof（LNode））;//创建一个节点
R=L;
for（inti=0;i{
scanf（"%d",&R->data）;//依次输入每个人的密码
R->num=i+1;//输入每个人的编号
P=（LinkList）malloc（sizeof（LNode））;//创建新节点
P->next=NULL;
Q=R;
R->next=P;//连接新的节点
R=P;
}
free（P）;//释放无用结点
Q->next=L;
return（L）;//返回循环链表
}
函数功能及实现：
先定义结构体指针变量R，P，Q，L，创建一个新节点赋值给指针L，并将L赋值给R，通过for循环再创建n个节点，并录入每个人对应编号，通过scanf函数录入每个人的密码，因为创建了一个节点。
并将新创建的节点连到链表尾端，形成一个单链表。
最后创建的一个节点是多余的，需要删除，所以通过free函数释放最后一个节点。
之后将单链表的尾指针指向第一个节点，形成一个单循链表。
最后通过return函数返回循环链表，继续执行主函数。
3.2.3voidData_OutPut（LinkList&L,intk,intb）；
函数原型：
voidData_OutPut（LinkList&L,intk,intb）；
函数原程序：
voidData_OutPut（LinkList&L,intk,intb）
{
printf（"\n出列顺序为:
\n"）;
LinkListR,P,Q;
for（inti=0;i{
R=L;
while（--b）//通过while循环找到密码做指向的那个人
{
Q=R;//加入Q方便寻找出列的人的上一个节点
R=R->next;//指针后移
}
printf（"第%d个出列%d\n",i+1,R->num）;//输出所找人的编号
b=R->data;//刷新b值，将所找到人的密码赋值给b
Q->next=R->next;//将出列人的前一个节点和后一个节点连接形成新环
L=R->next;
free（R）;//释放已出列结点
}
函数功能及实现：
该函数首先定义了指针变量R，P，Q，L方便对节点的操作。
通过for循环以确定所有人都会被出列，在while循环中，b的值最初是给定的报数上限，通过自减操作找到所要出列的那个人，打印其编号，将其密码重新赋值给b，并删除代表该人的节点，并释放该节点，形成一个新的约瑟夫环，进行下一次循环，最终所有人出列后完成for循环，打印出列顺序，返回大主函数。
4设计和调试分析
4.1调试中遇到的问题
（1）在用scanf函数给普通变量输入数据时，在变量名前漏写地址运算符&。
如:
scanf（″％d％d″, x, y）;
（2）输入数据时的数据形式与要求不符。
用scanf函数输入数据时，必须注意要与scanf语句中的对应形式匹配。
如：
scanf（″％d,％d″,&x, &y）;
若按以下形式输入数据：
2 4
是不合法。
数据2和4之间应当有逗号。
（3）输入、输出时的数据类型与所用格式说明符不匹配。
例如有以下说明语句：
int x=1; char y=’a’;
则运行时执行语句
printf（″x=％c, y=％d＼n″, x, y）;
将给出与原意不符的结果：
（在TURBO C 2.0 下运行）
（4）对于复合语句，忘记加花括号。
例如：
i=1; a=0;
while （i＜=10）
a+=i; i++;
printf（″a=％d＼n″,a）;的上限值是数组定义时元素个数减1。
（5）对指针的操作要小心谨慎，比如初始化和赋值等问题值得加以注意。
4.2经验和体会
通过这次数据结构课程设计，我感受最深的就是对于循环链表的使用，可以说对循环链表有了比以前更进一步的认识，以前只是一知半解的，如果只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解，包括其中的一系列操作，如建立一个循环链表，删除链表中的一个结点，增加一个结点等。
在这次课程设计过程中需要我们一边设计一边探索，这这个过程当中我发现自己在数据结构方面知识掌握不够深入，对一些基本概念不能很好的理解，对一些数据结构不能够熟练的进行上机实现，这是自己比较薄弱的。
学好基础知识是理论付诸实践的前提，这样理论和实践才能充分地结合起来。
在以后的学习中，我还要努力改正，充分利用上机实验的机会提高自己。
在程序的输入的时候，因为自己对键盘的不熟练，代码又很多很繁琐，常常会产生放弃的念头，从中我也感受到只有坚持到底，胜利才会出现。
在调试程序的时候我也有所体会，虽然约瑟夫环问题不是很难，但调试的时候还是会出现很多错误，因此我们不能认为容易就不认真对待。
在以后的学习中，要能不断发现问题，提出问题，解决问题，从不足之处出发，在不断学习中提高自己。
5用户使用说明
（1）根据正确的提示安装软件。
（2）Intel486以上系列、AMDK6以上系列等PC台式机和便携式电脑都可运行。
（3）打开该程序系统，根据提示首先输入初始报数上限和约瑟夫环的人数，然后输入各个人的密码，完成输入后，按回车键即可显示约瑟夫环内各人的出列顺序。
6测试数据和测试结果
（1）进入系统界面
系统提示输入m的值，即报数上限，为测试所给数据，将m的值设为20。
（2）输入约瑟夫环的人数
输入人数后，若输入人数大于30则提示输入错误，重新输入，这里为检测所给数据，设定人数为7。
（3）输入7人的密码
根据题目所给数据，7人的密码依次为3，1，7，2，4，8，4，输入完毕后回车。
（4）显示结果
测试的出列顺序为6，1，4，7，2，3，5符合题目要求，与算得的结果一致，证明程序正常运行，能够解决一般的约瑟夫环问题。
参考文献
[1]谭浩强.C程序设计（第二版）.北京：
清华大学出版社，1999.12
[2][美]KennethA.Reek著，徐波译.C和指针.北京；人民邮电出版社2008.4
[3]严蔚敏，吴伟民．数据结构．北京：
清华大学出版社，1997
[4][美]HMDeitel，PJDeitel著，薛万鹏等译.C语言程序设计教程.北京：
机械工业出版社，2000.07
附录源程序清单
/*约瑟夫环问题设计与实现*/
//函数头文件
#include"stdio.h"
#include"malloc.h"
#include"stdlib.h"
//自定义数据类型
typedefintStatus;
typedefintElemType;
//定义节点结构体
typedefstructLNode{
ElemTypenum;//各人的编号
ElemTypedata;//各人的密码
structLNode*next;//指向下一个节点的指针
}LNode,*LinkList;
//函数原型
LinkListData_InPut（LinkList&L,intk）;
voidData_OutPut（LinkList&L,intk,intb）;
//主函数
voidmain（）
{
LinkListL=NULL;
intm,n=30;//m为报数上限，n为人的个数
inti=0;//常用变量
printf（"\t约瑟夫环问题\n\n"）;
printf（"请输入m的值（要求m<=30）：
"）;
scanf（"%d",&m）;//将m重新赋值
printf（"请输入人数n:
"）;
scanf（"%d",&n）;//确定人的个数，即n得值
while（n>30||n<0）//人数异常处理
{
printf（"请输入小于30的正整数：
"）;
scanf（"%d",&n）;
}
printf（"\n"）;//换行
//调用数据录入函数
Data_InPut（L,n）;
//调用数据输出函数
Data_OutPut（L,n,m）;
}
//数据输入函数
LinkListData_InPut（LinkList&L,intk）
{
LinkListR,P,Q;
L=（LinkList）malloc（sizeof（LNode））;//创建一个节点
R=L;
for（inti=0;i{
printf（"请输入第%d个人的密码:
\t",i+1）;
scanf（"%d",&R->data）;//依次输入每个人的密码
R->num=i+1;//输入每个人的编号
P=（LinkList）malloc（sizeof（LNode））;//创建新节点
P->next=NULL;
Q=R;
R->next=P;//连接新的节点
R=P;
}
free（P）;//释放无用结点
Q->next=L;
return（L）;//返回循环链表
}
//调用数据输出函数
voidData_OutPut（LinkList&L,intk,intb）
{
printf（"\n出列顺序为:
\n"）;
LinkListR,P,Q;
for（inti=0;i{
R=L;
while（--b）//通过while循环找到密码做指向的那个人
{
Q=R;//加入Q方便寻找出列的人的上一个节点
R=R->next;//指针后移
}
printf（"第%d个出列为：
%d\n",i+1,R->num）;//输出所找人的编号
b=R->data;//刷新b值，将所找到人的密码赋值给b
Q->next=R->next;//将出列人的前一个节点和后一个节点连接形成新环
L=R->next;
free（R）;//释放已出列结点
}
}
忽略此处..
升级会员 