数据结构课程设计 约瑟夫（Joseph）环

1、 课程设计说明书 no.14 约瑟夫（joseph）环1.课程设计的目的本次课程设计通过设计一完整的程序，可以掌握数据结构的应用、算法的编写、类c语言的算法转换成c程序并用tc上机调试的基本方法。应用对数据结构理论学习，通过上机实践的方式将理论知识与实践更好的结合起来，巩固所学知识。 数据结构是实践性很强的课程，课程设计是加强学生实践能力的一个有力手段。本次课程设计的目的就是要达到理论与实际的应用相结合学会数据的组织方法，能把现实世界中的实际问题在计算机内部表现出来，能够提高学生的思维能力和专业素质的提高，对学生基本程序设计素质的培养和为以后工作打下了坚实的基础。 本次课程设计是利用利用单向循

2、环链表存储结构解决joseph环问题，编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止，本次课程设计将设计一个程序来求出出列顺序。2.设计方案论证2.1设计思路及方法 为了记录退出的人的先后顺序，采用一个顺序表进行存储。程序结束后再输出依次退出的人的编号顺序。由于只记录各个结点的data值就可以。最后通过函数调用来输出顺序。第一步是定义结构变量结点lin

3、klist，并在该结点下定义结点的元素域:data,password，指针域:llink和rlink。然后建立一个由n个链结点，有表头结点的单向循环链表。并由构造函数对结点赋值，由随机函数rand()产生每个结点的password。由于每个结点的password是由随机函数产生的，也就是每个结点的password是后知的，所以在一开始人为地指定一个结点的顺序，由此结点开始报数。报password个数后，报到的那个结点被删除，它的password被记录下，由它的下一个结点开始逆方向报数如此循环，直到循环链表里只剩下一个结点，那就是问题所求的结果。具体到问题上，还需要创建一个joseph类，由构造

4、函数来初始化，输入所有的人数，也就是表长，然后指定由第几个人开始报数。在joseph类中定义一个getwinner()函数，由它来实现获得最后的胜利者。并在该类中设置一个判断语句来确定先由顺时针报数并淘汰了一个人之后，再按逆时针顺序报数，如此交替进行。创建一个空单向循环链表，单向循环链表和每个结点包括三个域:element，llink,rlink.其中element为元素域，rlink域为指向后继结点的指针，新增的llink域用以指向前驱结点。单向链表带表头结点，并且也可以构成单向循环链表。此时，表头结点的rlink，llink分别指向双向循环链表的头结点(或表头结点)和尾结点。一个结点的ll

5、ink域的指针指向它左边结点的后部，这并不意味着该结点的llink域保存的仍是该左边结点存储块的起始地址。在此处，指针指向某个结点任何部分都是等价的，都是指该存储块的起始位置。每当结点计数到某一结点时，将他的前驱结点接到他的后继结点，然后将他的密码值password赋给计数变量，再将此结点删除。如此循环下去，直到最后变为空的单循环链表为止。由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍然是围成一个圆圈的，可以使用循环表，由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，选用效率较高的链表结构，为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判

6、断，链表不带头结点。所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循环链表来描述。设头指针为front，front始终指向头结点，并定义指针current记录当前的结点。并根据具体情况移动（顺逆时针）。 开始输入m,nm0,n0的整数结束输出pnopnext=p i+ iippassword=m 输出pno(m%n)=0?n:m%n=m2.2系统流程图建立含n个结点的链表且用head指向第一个元素，结点数据域包含password、no、以及指向下一结点的指针 head=p n2删除p所指向结点， n- - 图1.系统流程图2.3算法设计举例（1）利用单向循环链表存储结构模拟此过

7、程，因为循环链表最后一个结点的指针域指向头结点，整个链表形成一人环，刚好和题中的“n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）”内容要求一致，而且，循环链表中任一结点出发均可找到表中其他结点，利用这一优点可较容易地找出报数的人及下一个报数的人，最后按照出列的顺序用一个for语句实现。joseph环的组成成员由密码（password）和序号(no)组成，循环链表的存储结构如下：typedef struct lnode int password; /密码 int no; /序号 struct lnode *next; /下一成员指针member; /组成成员结构体（2）定义结构体类型

8、，其中password为密码，no为序号，将两者均定义为整型，lnode *next为下一成员指针，具体算法如下： typedef struct lnode int password; int no; struct lnode *next; member; typedef int status; （3）主函数模块算法 程序main中调用了createlist_circle函数，创建了循环链表，还调用了outnode函数实现了输出。首先定义人数n，头指针即首员地址和遍历指针均为空，当输入人数小于等于0时，输出“重新输入”字样，如果输入数大于0则创建循环链表，返回头指针。当m小于等于0时也提示重新

9、输入，把head 附给q ，寻找出列成员，化简m值，k从1到m-1指向出列成员，然后修改m,删除链表的出列成员，成员数自减。具体算法如下：status main() int n,m; member *head=null,*q=null; while (n=0) printf (n must be positive, please enter again:n); if(!createlist_circle(&head,n) return overflow; while (m=2) int k; m=(m%n=0)?n:m%n; for (k=1;inext; m=p-password; outn

10、ode(&q); n-; return ok; 3.设结果与分析3.1需求与分析约瑟夫环问题是一个古老的数学问题，本次课题要求用程序语言的方式解决数学问题。此问题仅使用单循环链表就可以很方便解决此问题在建立单向循环链表时，因为约瑟夫环的大小由输入决定。为方便操作，我们将每个结点的数据域的值定为生成结点时的顺序号和每个人持有的密码。进行操作时，用一个指针current指向当前的结点，指针front始终指向头结点。然后建立双向循环链表，因为每个人的密码是通过rand()函数随机生成的，所以指定第一个人的顺序号，找到结点，不断地从链表中删除链结点，直到链表剩下最后一个结点，通过一系列的循环就可以解决

11、改进约瑟夫环问题。3.2调试过程与分析这次的课程设计的代码很冗长，所以等有了解题思路后，把代码都写上后难免会有很多错误。当第一次把整个程序写好后运行，出现了很多错误。不过经过一点点的改正，错误也慢慢地变少。这也说明做事要认真，尤其做计算机这方面工作的时候，因为计算机不容许不一点点的错误，有了一点小错误和有一个大错误在计算机看来都是一样的，都不会得不到结果。有些小错误，比如说少了个分号，变量忘了定义，数据溢出等都是些小错误，但也不能松懈。因为要注意的地方很多，经过多次尝试，问题也就自然而然的解决了，而且以后遇到这方面的问题都会觉得比较得心应手。在随机设置每个结点的password时也曾是个问题，

12、因为我做的随机函数一直都用不好，要不是每次随到的都是一样的，要么就是每次随到的数都很大，后来通过老师的耐心讲解才得以解决。在调试的过程中，类的优势很明显，能很简单的把问题解决，而不需要使用的其他的一些比较复杂的方法。3.3运行结果3.3.1运行程序结果 在visuar c+中运行该程序并进行调试，然后能够正确输出。 图2.程序运行图3.3.2检测程序的可行性 （1）测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4。图3.输入数据结果图（2）测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4。运行并输出结果。 图4.运行结果图（3）输

13、入数据：建立输入处理输入数据，输入m的初值为6，输入每个人的密码，建立单循环链表，输出正确的序列。图5.运行结果图当程序运行的时候会出现如上图所示的提示，要求使用者输入程序中所需的输入总人数，使用者只需输入自己所想的总人数，系统便会随机产生每个人对应的密码，同时随机产生第一次的报数上限值。最后系统会给出出列的次序，最后产生的编号便是此次游戏的获胜者。使用者还可按下任意键，进行下一次的游戏。4.设计体会为期一周的课程设计快结束了，通过这次数据结构课程设计，我感受最深的就是对于循环链表的使用，可以说对循环链表有了比以前更进一步的认识，以前只是一知半解的，如果只给个题目自己根本不能把程序完整地编写出

14、来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解，包括其中的一系列操作，如建立一个循环链表，删除链表中的一个结点，增加一个结点等。在这次课程设计过程中需要我们一边设计一边探索，这这个过程当中我发现自己在数据结构方面知识掌握不够深入，对一些基本概念不能很好的理解，对一些数据结构不能够熟练的进行上机实现，这是自己比较薄弱的。学好基础知识是理论付诸实践的前提，这样理论和实践才能充分地结合起来。在以后的学习中，我还要努力改正，充分利用上机实验的机会提高自己。在程序的输入的时候，因为自己对键盘的不熟练，代码又很多很繁琐，常常会产生放弃的念头，从中我也感受到只有坚持到底，胜利才会出现。课程设计

15、是培养我们综合运用所学知识，发现、提出、分析和解决实际问题，锻炼实践能力的重要环节,是对我们实际工作能力的具体训练和考察过程.在调试程序的时候我也有所体会，虽然约瑟夫环问题不是很难，但调试的时候还是会出现很多错误，因此我们不能认为容易就不认真对待。在以后的学习中，要能不断发现问题，提出问题，解决问题，从不足之处出发，在不断学习中提高自己。4. 参考文献1严蔚敏，吴伟民.数据结构（c语言版）m.北京：清华大学出版社，2007.4：144-1492苏仕华.数据结构与算分析m.安徽：中国科学技术大学出版社，2004.1：94-983朱若愚.数据结构m.北京:电子邮电出版社,2006.1:41-654

16、徐孝凯.数据结构简明教程.北京:清华大学出版社,2006.4:102-1155耿国华.数据结构-c语言描述m北京:高等教育出版社,2005.1:182-1876孙辉吴,润秀语.c言程序设计教程m北京:北京邮电出版社,2004.10:166-1727许秀林,董杨琴.程序设计基础教程（c语言与数据结构）m北京:中国电力出版社,2005.9:250-2568王曙燕.c语言课程设计m北京:科学出版社,2005.2:159-165附录：源代码typedef struct lnode int password; /密码 int no; /序号 struct lnode *next; /下一成员指针memb

17、er; /组成成员结构体typedef int status;#define overflow -2 #define ok 1 #define error 0#include #include status createlist_circle(member *,int);status deletenode(member *);status main() int n,m; member *head=null,*p=null; /头指针即首成员地址，遍历指针p printf (请输入人数:n); scanf (%d,&n); /总成员数 while (n=0) printf (n must be

18、positive, please enter again:n); scanf (%d,&n); if(!createlist_circle(&head,n) /创建循环链表，返回头指针head return overflow; printf (请输入m的值:n); scanf (%d,&m); /初始值m while (m=2) /寻找出列成员 int i; m=(m%n=0)?n:m%n; /化简m值 for (i=1;inext; /p指向出列成员 printf (%dn,p-no); /输出出列成员序号 m=p-password; /修改m deletenode(&p); /删除链表中的出列成员 n-; /成员数自减 printf (%dn,p-no); /输出最后一个成员序号 return ok;status createlist_circle(member *p_head,int n)