约瑟夫环问题课程设计说明书.doc

《约瑟夫环问题课程设计说明书.doc》由会员分享，可在线阅读，更多相关《约瑟夫环问题课程设计说明书.doc（33页珍藏版）》请在沃文网上搜索。

1、 目录： 摘 要2前言3课程设计报告正文4一需求分析4二概要设计5三详细设计71各模块关键代码及算法的解释：72函数的调用关系图10四调试分析13五用户使用说明15六测试结果16七源程序（带注释）22总结26参考文献26致谢28附录，带注释的源程序29摘 要当约瑟夫环中某人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍然是围成一个圆圈的，可以使用循环表，由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，选用效率较高的链表结构，为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断，链表不带头结点。所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头结点

2、的循环链表来描述。设头指针为p，并根据具体情况移动。为了记录退出的人的先后顺序，采用一个顺序表进行存储。程序结束后再输出依次退出的人的编号顺序。由于只记录各个结点的number值就可以，所以定义一个整型一维数组。如：int quitn;n为一个根据实际问题定义的一个足够大的整数。 解决问题的核心步骤： 1.建立一个具有n个链结点，无头结点的循环链表 2.确定第1个报数人的位置 3.不断地从链表中删除链结点，直到链表为空前言约瑟夫环（Josephus）问题是由古罗马的史学家约瑟夫（Josephus）提出的，他参加并记录了公元6670年犹太人反抗罗马的起义。约瑟夫作为一个将军，设法守住了裘达伯特城

3、达47天之久，在城市沦陷之后，他和40名死硬的将士在附近的一个洞穴中避难。在那里，这些叛乱者表决说“要投降毋宁死”。于是，约瑟夫建议每个人轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签，并且，作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降了罗马。 约瑟夫环问题的具体描述是：设有编号为1，2，n的n(n0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。课程设计报告正文一需求分析1输入的形式和输入值

4、的范围本程序中，输入人数n(n小于等于30)和初始密码m（m大于等于1），然后给每个人输入所持有的密码key，均限定为正整数。用单循环链表模拟约瑟夫环，从队头开始从1报数，报到m的人出列，再把此人的密码赋给m，继续下一轮的报数，直到所有的人出列。结果出来后再选择输入一数字，输入1继续新一轮的游戏，输入0结束，退出此游戏。演示程序以用户和计算机对话方式进行，根据提示信息由用户从键盘输入数据，输入的形式为一个以“回车符”为结束标志的正整数。2输出的形式在计算机终端上显示提示信息之后，有用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在其后。运行后输出的结果是约瑟夫环的相关信息

5、和经过报数后出队的人的序列号及相关信息。程序执行的命令包括：（1）输入人数和初始密码 （2）输入所有人的密码 （3）显示输入的所有人的编号及相应的密码（4）输出出列密码及编号 （5）结束 即：（1）构造单循环链表；（2）输出循环链表的信息；（3）按照出列的顺序输出各人的编号3程序功能 提供用户从键盘输入，Joseph约瑟夫环的必要数据，并从屏幕显示出列顺序。4测试数据（1）n=7 ,m=20（常规数据）, 7个人的密码依次为3，1，7，2，4，8，4，正确的输出序列为6，1，4，7，2，3，5.（2）n=5，m=6（常规数据），5个人的密码依次为2，5，4，6，7，正确的输出序列为1,3,4,

6、2,5。（3）n=31, m=3（错误数据），“这个人数太大了，请重新输入”。（4）n=0, m=3（错误数据），“这个约瑟夫环里没有人！”。（5）n=1, m=4,（边缘数据），正确的输出序列为1。（6）n=3, m=1,（边缘数据），正确的输出序列为1，3，2。第一组为常规数据，中间两组为错误数据，后面两组为边缘数据。5设计思路及方案用单循环链表来模拟约瑟夫环，结点信息包括编号、密码、指向下一个结点的指针，用三大主要的函数来实现功能，包括创建链表的函数、输出链表信息的函数、删除结点也就是出队的函数、主函数等函数。二概要设计1抽象数据类型的定义为实现上述功能，应以有序单向循环链表表示约瑟夫环

7、。为此，需要有一个抽象数据类型。该抽象数据类型的定义为：ADT LinkList数据对象：D= ai | ai termset,i=1,2,n,n=0，termset中每个元素包含编号，密码，和一个指向下一节点的指针数据关系：R1= | ai-1, ai D , i=2,n基本操作：LinkList EvaluList(int n);/对单向循环链表进行尾插入赋值int size(LinkList L);/求链表的节点个数Status ScanList(LinkList L);/遍历单向循环链表Status Joseph(LinkList &L,int m);/约瑟夫环的实现此抽象数据类型中的

8、一些常量如下：#define TRUE 1#define FALSE 0#define OK 1typedef int Status;typedef double ElemType;单向循环链表中节点的定义如下所示：typedef struct LNodeint number;int data;struct LNode *next;LNode, *LinkList;2主程序的流程void main() 初始化； 输入数据； 执行功能；显示结果；3模块的设计及介绍（1）主程序模块 Void main（）初始化；do 接受命令；处理命令；while（“命令”=“退出”）；（2）创建链表模块 Sta

9、tic void creatlist（行参）初始化；For接受命令；处理命令 （3）输出链表信息模块static void PrntList(参数)定义变量并初始化；输出命令； （4）删除结点也就是出队模块static void StatGame(参数)定义变量并初始化； While 开始报数； 输出结果；4各程序模块之间的层次(调用)关系。本程序包含以下模块：（1）主程序模块：（2）各功能模块实现顺序表的各项功能。各模块的调用关系：主程序 各功能模块三详细设计1各模块关键代码及算法的解释：（1） 主函数模块代码circularlist pHead=NULL;int main(void) in

10、t n, m， iflag=1while(iflag=1)printf(请输入总人数n=); scanf(%d,&n); printf(n再请输入初始报数上限m=); scanf(%d,&m)； CreatList(&pHead,n); printf(n输出所有人的信息如下:n);PrntList(pHead); printf(n按照出列顺序输出每个人的编号:n); StatGame(&pHead, m); printf(n约瑟夫环的游戏完成!n); printf(输入1开始建环做游戏，输入0退出该游戏，请选择!);scanf(%d,&i); return 0;程序解释：该主函数用一个循环语句

11、，来执行其它的函数的功能。从键盘输入总人数和初始的报数上限，再调用创建链表的函数建环，后输出单循环链表的信息，再调用StatGame（）函数，报到上限的那个结点从表中删除既出队，然后再选择输入一个数确定是否继续游戏，输入1继续，输入0退出。（2） 创建单循环链表函数模块代码static void CreatList(circularlist * ppHead, const int n) int i,ikey; Node *pNew, *pCur; for(i=1;inext=*ppHead; else pNew-next=pCur-next; pCur-next=pNew; pCur=pNew

12、; 程序解释：用一个for循环来给链表的每个结点分配空间，并从键盘输入每人所持有的密码，如果头结点的值为空，使其指向新生成的一个结点，新结点的next指针指向头结点，如果不是，则当前结点的next的值赋给新结点的next，然后当前结点的next值指向新结点，再当前结点的指针指向新结点，实现链表的建立。（3）删除结点函数代码static void StatGame(circularlist * ppHead, int ikey) int iCounter, iFlag=1; Node *pPrv, *pCur, *pDel; pPrv=pCur=*ppHead; while(iFlag) ! *

13、/ for(iCounter=1;iCounternext; if(pPrv=pCur) iFlag=0; pDel=pCur; Prv-next=pCur-next; pCur=pCur-next; ikey=pDel-key; printf(第 %d个人出列, 所持有密码是: %dn, pDel-id,pDel-key); free(pDel); ppHead=NULL; 程序解释：设立一个标签，值为1执行循环语句，值为0跳出循环。循环语句里的for循环实现报数功能，也就是结点移动的功能，移动ikey个结点，再删除第ikey个结点，并把该结点的密码值赋给ikey，再从该结点的下一个结点移动

14、，重复上面的过程，结点全都删除后使标签的值为0，结束while循环，游戏结束。开始2函数的调用关系图定义各种变量2.1主程序流程图输出界面假输入参与人数和密码判断是否满足人数上限结束假a=1？真while语句输出密码输出出列顺序调用PrntList ();开始进行约瑟夫环的操作初始化单链表调用CreaList ();构造单链表真2.2创建单循环链表函数流程图开始i=n?输入每人所持有的密码创建结点结束是否2.3删除结点函数（出队函数）程序流程图iflag=1icounter=ikey从1开始报数,报m结束报m的人出列prv=pru开始真真假假假真iflag=0结束2.4子程序流程图假retur

15、n TRUEif(!pHead)真输入一数值引用指针*pHeadEmptyList（）return FALSE四调试分析1.调试过程中遇到的问题及解决方法及对设计与实现的回顾讨论和分析程序的编写和调试基本正常。遇到的问题有：指针的指向的边界问题。当执行输入人数时，输入0程序出现了意想不到的错误，所以再重新设计时加入了对空节点的处理。在链表节点的设计上，最初是仅包含密码和指针，但是后来考虑到链表节点删除时会带来一系列的编号变化，编号难以确定，所以节点设计上又加了一个编号。在单向链表的赋值操作时，原本是以一个不变的L作为头结点，但是这种赋值方法带来了诸多变量设计的问题，所以将L为节点，赋值完成后，

16、再让L指向头结点。程序原本是没有求节点个数的函数，但是在约瑟夫环的实现函数中，节点的个数时时影响着结果的判断，所以加入了该函数。2.算法的时空分析在空间复杂度方面第一种算法可以增加一存储出列序列的数据组，需要辅助空间，而且与问题的规模Maxsize有关。第二种算法也可直接对约瑟夫环进行求解，结果仍然存储在环中，好处是没有增加额外的空间。在时间复杂度方面，第一种算法可以从中可以看到，报数m的时间极短,问题在出列时,由于用顺序表做删除操作,平均移动大约表中一半的元素,影响效率.但是,两者都存在二重循环,算法中语句重复执行次数的数量级没有发生变化,即时间复杂度O相同。与这两种算法不同的是，动态链表实

17、现的算法中，不需要预先分配足够大的存储空间，没有太大的辅助空间的要求，远小于问题规模Maxsize，即绝小于第一种算法的辅助空间，而接近第二种算法。另外，删除结点操作极其方便，比第二种算法移动元素的少。不过，三者时间复杂度O均相同。对同一问题，可以有不同的算法。但仍可以进一步优化。例如时间问题，密码可采用对剩余节点取余来减少遍历次数。3.经验和体会通过这次的课程设计的综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课程的主要内容，我们对数据结构有了更深的理解。与以往不同的是我们自己选定一个研究问题，对其进行详尽的分析思考，最终解决。我们选择的课程设计的内容是用单循环链表模拟约瑟夫环

18、游戏，循环链表是一种首尾相接链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活，约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。在此期间遇到了很多困难。如：当程序大体完成时，却又在调试过程中发现出列次序总是错误的，才想到第一次指向时应该让变化的指针指向尾节点，这样可以减少当密码为1时程序的设计量。此次课程设计收获相当多，我们不仅对VC软件更加熟悉，而且学会了能运用所学知识分析和解决一些实际问题。了解并初步掌握设计、实现较大程序的完整过程，包括系统分析、编码设计、系统集成、

19、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。本实验采用数据抽象的与模块化程序设计方法。思路清晰，实现时调试顺利，各模块具有很好的可重用性，得到了一次良好的程序设计训练。同时在和队友的不断完善中，许多困难都得到了解决，从这点我们也认识到团队中合作的重要性。相信我们以后会做得更优秀。五用户使用说明1如何使用你编写的程序首先根据提示输入初始密码和人数，再输入每个人的密码。最后输入1或0，选择继续或结束。2每一步的操作步骤示例：进入演示程序后即显示文本方式的用户界面; 欢迎您进入约瑟夫环运行界面 请按照提示执行程序 设计者:刘左彩 先请输入人数n(n小于等

20、于30)和初始密码m(m大于等于1)，再请输入每个人的密码。显示出出列顺序。最后输入1，继续测试。输入0，结束。如：请输入人数n(n小于等于30)7和初始密人数：20 输入1个人的密码：3输入2个人的密码：1输入3个人的密码：7输入4个人的密码：2输入5个人的密码：4 输入6个人的密码：8 输入7个人的密码：4 后会出现7个人的密码为：3 1 7 2 4 8 4 和出列顺序6 1 4 7 2 3 5。输入1之后的界面：继续测试数据输入0之后的界面：结束六测试结果1程序调试，正确2点击运行，进入“约瑟夫环”运行初界面3. 输入总人数之后的界面4输入初始密码后的界面：5.输入所有人所持有的密码后的

21、界面（继续新一轮的游戏，结束后的界面）输入所规定范围内的数值。（第一组，常规数据）14第14页 共 33 页6.输入1之后的界面： 7.输入0之后的界面：8第二次测试，输入所规定范围内的数值（第二组，常规数据）。运行结果如下：9当输入的人数值超过范围时，系统会输出“这个人数太大了，请重新输入”，（第三组，错误数据）运行如下： 10当输入的人数为0时，系统会输出“这个约瑟夫环里没有人”。（第四组，错误数据）程序运行的界面如下：11当输入的人数为1时（第五组，边缘数据）运行界面如下：12当输入的密码为1时（第六组，边缘数值），运行界面如下：七源程序（带注释）#include #include #d

22、efine MAX_NODE_NUM 30 #define TRUE 1U #define FALSE 0U typedef struct NodeType int id; /* 编号 */ int cipher; /* 密码 */ struct NodeType *next; NodeType; /* 创建单向循环链表 */ static void CreaList(NodeType *, const int); /* 运行约瑟夫环问题 */ static void StatGame(NodeType *, int); /* 打印循环链表 */ static void PrntList(co

23、nst NodeType *); /* 得到一个结点 */ static NodeType *GetNode(const int, const int); /* 测试链表是否为空, 空为TRUE，非空为FALSE */ static unsigned EmptyList(const NodeType *); int main(void) int n, m; int iflag=1; NodeType *pHead=NULL; printf(n); printf( 欢迎您进入约瑟夫环运行界面 n); printf( 请按照提示执行程序 n); printf( n);printf( 设计者:刘左彩

24、 n); printf(n); while(iflag=1) printf(请输入人数n(n小于等于%d):,MAX_NODE_NUM); scanf(%d,&n); printf(和初始密码 m:); scanf(%d,&m); if(nMAX_NODE_NUM) printf(这个人数太大了，请重新输入n); continue; CreaList(&pHead,n); printf(n-下列为每个人的密码-n); PrntList(pHead); printf(n-出列顺序-n); StatGame(&pHead, m); printf(n约瑟夫环问题解决了!n); printf(nn是否

25、继续游戏?输入1继续，输入0退出，请选择!n); scanf(%d,&iflag); return 0; static void CreaList(NodeType *ppHead, const int n) int i,iCipher; NodeType *pNew, *pCur; for(i=1;inext=*ppHead; else pNew-next=pCur-next; pCur-next=pNew; pCur=pNew; printf(完成了约瑟夫环的定义n); static void StatGame(NodeType *ppHead, int iCipher) int iCou

26、nter, iFlag=1; NodeType *pPrv, *pCur, *pDel; pPrv=pCur=*ppHead; /* 将pPrv初始为指向尾结点，为删除作好准备 */ while(pPrv-next!=*ppHead) pPrv=pPrv-next; while(iFlag) /* 开始搞了! */ /* 这里是记数，无非是移动iCipher-1趟指针! */ for(iCounter=1;iCounternext; if(pPrv=pCur) /* 是否为最后一个结点了 */ iFlag=0; pDel=pCur; /* 删除pCur指向的结点，即有人出列 */ pPrv-n

27、ext=pCur-next; pCur=pCur-next; iCipher=pDel-cipher; printf(第 %d 人出列, 他的密码: %dn, pDel-id, /* 这个编号标识出列的顺序 */ pDel-cipher); free(pDel); *ppHead=NULL; /* 没人了！为了安全就给个空值 */ static void PrntList(const NodeType *pHead) const NodeType *pCur=pHead; if (EmptyList(pHead) return; do printf(第 %d 个人, 密码为: %dn,pCur

28、-id,pCur-cipher); pCur=pCur-next; while (pCur!=pHead); static NodeType *GetNode(const int iId,const int iCipher) NodeType *pNew; pNew=(NodeType *)malloc(sizeof(NodeType); if(!pNew) printf(error,the memory is not enough!n); exit(-1); pNew-id=iId; pNew-cipher=iCipher; pNew-next=NULL; return pNew; stat

29、ic unsigned EmptyList(const NodeType *pHead) if(!pHead) printf(这个约瑟夫环里没有人!n); return TRUE; return FALSE; 总结通过三周的课程设计之后，培养了我们选用参考书，查阅手册及文献资料的能力，培养独立思考，深入研究，分析问题、解决问题的能力，提高综合运用本课程所学知识的能力，还对设计的基本过程的设计方法、步骤、思路、有一定的了解与认识，并对存储结构，比如线形表、链表、循环链表、树、图等存储结构，特别是对单循环链表理解的更深。也使我认识到数据结构这门课程是计算机程序设计的重要理论技术基础，在我们计算机专

30、业的学习中占据着十分重要的地位。同时也使我知道，要学好这门课程，仅学习书本上的知识是不够的，还要有较强的实践能力。因为我们学习知识就是为了实践。而只有多实践，多编写程序，才能更好的理解与掌握书本上的东西。本次课程设计的主题是用单循环链表来模拟约瑟夫环游戏，由于刚开始对循环链表的理解不够，也没理请约瑟夫环的基本思路，做起来有点难，但通过反复的修改，最终还是能够理解。我学到了很多的东西，通过实际编译系统的分析设计、编程调试，也掌握了一些工程设计方法。现在也能够按要求编写课程设计报告书，能正确阐述设计和实验结果，正确绘制程序框图。课程设计是把我们所学的理论知识进行系统的总结并应用于实践的良好机会，有

31、利于加强我们用知识理论来分析实际问题的能力，进而加强了我们对知识认识的实践度，巩固了我们的理论知识，深化了对知识的认识，并为走向社会打下一个良好的基础。在这次课程设计中我遇到许多问题和麻烦。比如，表建成之后，不能输出表中的信息，说明指针的值没传成功，经过把链表的头指针转为二级指针，传值成功。在程序调试过程中，也得到很多同学的帮助，给我及时指出错误，提出许多宝贵意见。参考文献1 数据结构（C语言版），北京：清华大学出版社2 数据结构课程设计，北京：机械工业出版社3 C语言程序设计教程，上海：高等教育出版社.致谢从选择课程设计题目，到课程设计规划，查找相关资料，设计模型，具体实施，结束论文，整个大

32、致的流程中，我的指导老师都给予了我耐心的指导，非常感谢梁一鑫老师给我的悉心指导，让我顺利地完成了课设论文，当然，也感谢同学们的大力帮助之情，使我学到了许多新的知识，同时也更懂得了一些做学问的道理，这是一笔宝贵的财富。附录，带注释的源程序#include #include #define MAX_NODE_NUM 30 #define TRUE 1U #define FALSE 0U typedef struct NodeType int id; /* 编号 */ int cipher; /* 密码 */ struct NodeType *next; NodeType; /* 创建单向循环链表

33、*/ static void CreaList(NodeType *, const int); /* 运行约瑟夫环问题 */ static void StatGame(NodeType *, int); /* 打印循环链表 */ static void PrntList(const NodeType *); /* 得到一个结点 */ static NodeType *GetNode(const int, const int); /* 测试链表是否为空, 空为TRUE，非空为FALSE */ static unsigned EmptyList(const NodeType *); int main(void) int n, m; int iflag=1; NodeType *pHead=NULL; printf(n); printf( 欢迎您进入约瑟夫环运行界面 n); printf( 请按照提示执行程序 n); printf( n);printf( 设计者:刘左彩 n); printf(n); while(iflag=1) printf(请输入人数n(n小于等于%d):,MAX_NODE_NUM); scanf(%d,&n); printf(和初始密码 m:); scanf(%d,&m); if(nMAX_NODE_NUM) p