约瑟夫环程序设计报告书(共16页).doc

《约瑟夫环程序设计报告书(共16页).doc》由会员分享，可在线阅读，更多相关《约瑟夫环程序设计报告书(共16页).doc（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上附件4：课程设计报告书数 据 结 构课程设计报告 约瑟夫（Joseph）环组别第七组组长组成员成绩 指导教师计算机科学与技术系2014年6月11日摘要约瑟夫环问题是典型的线性表的应用实例，其开发主要包括后台数据库的建立和维护以及前端应用程序的开发两个方面。对于前者要求建立起数据一致性和完整性强、数据安全性好的库。而对于后者则要求应用程序功能完备，易使用等特点。经过分析，我们使用MICROSOFT公司的Microsoft Visual C+6.0开发工具，利用其提供的各种面向对象的开发工具，尤其是数据窗口这一能方便而简洁操作数据库的智能化对象，首先在短时间内建立系统原型

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

3、，进一步加深对链表结构类型及链表操作的理解。通过该课程设计，能运用所学知识，能上机解决一些实际问题，了解并初步掌握设计、实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。 章节安排 摘要、序言. . . . .1一、问题描述1、课程设计目的. . . . . .42、课程设计任务. . . . . .4二、设计过程1、设计思想（数据结构）. . . . .42、设计表示（函数说明）. . . . .53、详细设计（主要算法）. . . . .64、用户手册（使用说明）. . . . .6三、测试报

4、告1、测试用例. . . . . . . .62、测试结果. . . . . . . .63、分析探讨. . . . . . . .7四、总结 . . . . . . . .10五、附录（源程序）. . . . . .10六、参考文献. . . . . . . .16章节安排：一、问题描述1、课程设计目的1.掌握单向循环链表的建立。2.掌握单向循环链表的操作。2、课程设计任务编号是1,2,n的n个人按照顺时针方向围坐一圈,每个人只有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺

5、时针方向的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。请设计一个程序求出出列顺序。1.利用单向循环链表存储结构模拟此过程,按照出列的顺序输出各个人的编号。2.输入数据：建立输入函数处理输入的数据,输入m的初值n,输入每个人的密码,建立单向循环链表。3.输出形式：建立一个输出函数,将正确的出列顺序输出。二、设计过程1、设计思想（数据结构）首先，设计实现 瑟夫环问题的存储结构。由于约瑟夫环本身具有循环性质，考虑 采 用循环链表，为了统一对表中任意节点的操作，循环链表不带头结点。循环链表的结点定义为如下结构类型：struct Lnode /*定义链表*/ int number;int

6、 password; struct Lnode *next; Lnode,*p,*q,*head;其次，建立一个不带头结点的循环链表并由头指针first指示。最后，设计约瑟夫环问题的算法。2、设计表示（函数说明）1、循环链表抽象数据类型定义 struct Lnode /*定义链表*/ int number;int password; struct Lnode *next; Lnode,*p,*q,*head;2、本程序包含一下几个模块 （1） 创建单链表for(i=1;inext=q;p=q; (3) 形成循环链表p-next=head; /*形成循环链表*/（4）主函数模块 int main

7、（）3、详细设计（主要算法）4、用户手册（使用说明）正确的执行完程序后，进去程序显示屏。首先按任意键继续，然后输入初始密码，紧接着输入测试人的数量n，其次依次输入测试人的密码，最后输入报数上限值m，完成后将进行结果的输出。三、测试报告1、测试用例.测试数据：m的初值为20,n=7,7个人的密码依次为3,1,7,2,4,7,4,首先m=6,则正确的输出是什么？2、测试结果3、分析与探讨无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅

8、仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。为了讨论方便，先把问题稍微改变一下，并不影响原意：问题描述：n个人（编号0(n-1)，从0开始报数，报到m-1的退出，剩下的人继续从0开始报数。求胜利者的编号。我们知道第一个人(编号一定是(m-1)%n)出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:kk+1k+2.n-2,n-1,0,1,2,.k-2并且从k开始报0。现在我们把他们的编号做一下转换：k-0k+1-1k+2-2.k-3-n-3k-2-n-2序列1：0,1,2,3n-2,n-1序列2：0,1

9、,2,3k-2,k,n-2,n-1序列3：k,k+1,k+2,k+3,n-2,n-1,1,2,3,k-2,序列4：0,1,2,3,5,6,7,8,n-3,n-2变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！变回去的公式很简单，相信大家都可以推出来：k=m%n;x=x+k=x+m%n;而x+m%n可能大于nx=(x+m%n)%n=(x+m)%n得到x=(x+m)%n如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)

10、的情况-这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是fn.递推公式:f1=0;fi=(fi-1+m)%i;(i1)有了这个公式，我们要做的就是从1-n顺序算出f的数值，最后结果是fn。我们输出fn由于是逐级递推，不需要保存每个，程序也是异常简单：(注意编号是0-n-1)#includeintmain(void)intn,m,i,s=0;printf(NM=);scanf(%d%d,&n,&m);for(i=2;i1k+2-2.n-n-k1-n-k+1.k-1-n-1由上面一组式子可以推出，若知道新产生的n-1个数中某个

11、数x，那么很显然可以推出x在原数列里的位置，即x=（x+k）%n,由此，我们可以得到一个递推公式f1=1fn=(fn-1+k)%n（n1）如果你认为上式可以推出约瑟夫环问题的解，很不幸，你错了，上面的递推公式中，在某种情况下，fn-1+k会整除n，如n=2，k=3，这时我们修要对上式进行修正，fn=(fn-1+k)%n;if(fn=0)fn=n;问题得解。程序代码如下：#includeintmain()intn,k,s=1;scanf(%d%d,&n,&k);for(inti=2;i=n;i+=1)s=(s+k)%i;if(s=0)s=i;printf(ans=%dn,s);return0;当

12、然，我们还可以用递归方法解决此问题：#includeintmain()intjos(intn,intk);intn,k,s;scanf(%d%d,&n,&k);s=jos(n,k);printf(ans=%dn,s);return0;intjos(intn,intk)intx;if(n=1)x=1;elsex=(jos(n-1,k)+k)%n;if(x=0)x=n;returnx;四、总结我的这次数据结构课程设计的题目是:约瑟夫环,通过对该题目的设计,我加深了对数据结构及存储结构的理解,进一步地理解和掌握了课本中所学的各种数据结构，尤其是对单循环链表上基本运算的实现,学会了如何把学到的知识用于

13、解决实际问题,锻炼了自己动手的能力。 通过这次数据结构课程设计，我感受最深的就是对于循环链表的使用，可以说对循环链表有了比以前更进一步的认识，以前只是一知半解的，如果只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解，包括其中的一系列操作，如建立一个循环链表，删除链表中的一个结点，增加一个结点等。 在调试程序的时候我也有所体会，虽然约瑟夫环问题不是很难，但调试的时候还是会出现很多错误，因此我们不能认为容易就不认真对待。在以后的学习中，要能不断发现问题，提出问题，解决问题，从不足之处出发，在不断学习中提高自己。 两周的课程设计很短暂，但其间的内容

14、是很充实的，在其中我学习到了很多平时书本中无法学到的东西，积累了经验，锻炼了自己分析问题，解决问题的能力，并学会了如何将所学的各课知识融会，组织起来进行学习，总而言之这两周中我学到很多，受益匪浅。五、附录（源程序）#include #include #include#include string.h struct Lnode /*定义链表*/ int number;int password; struct Lnode *next; Lnode,*p,*q,*head; int main(void) system(color 0a);system(title -邦德的荣耀-);printf( n

15、);printf( n);printf( n);printf( n);printf( n);printf( n);printf( n);int n; /n个人 int i; int m; /初始报数上限值int j, k, s, u;char ch;char mima100=007;char input100;printf(-约瑟夫环程序设计-nn);printf(-007倾情奉献-nn);printf( 邦德的荣耀 邦德的荣耀 nn);printf(密码为007n);/system(pause); for(k=0,s=3;k=2;k+,s-)printf(请输入密码：n);gets(inpu

16、t);if(strcmp(mima,input)=0)/比较字符串mima和input的大小，此时相等printf(密码正确!n);break;elseprintf(密码错误，你还有%d次机会n,s-1);while(s=1)return 0;for(u=0;u+)/套上for循环以判断是否继续进行printf(输入测试人的数量 n:); /*输入测试人的数量*/ scanf(%d,&n); loop:if(n=0) /*检验n是否满足要求，如不满足重新输入n值*/ printf(n n是错的!nn); printf(请再次输入 n:); scanf(%d,&n); goto loop; fo

17、r(i=1;inext=q;p=q; printf(请输入第 %d 个人的密码:,i); /*输入每个人所持有的密码值*/ scanf(%d,&(p-password); p-number=i; p-next=head; /*形成循环链表*/ p=head; printf(请输入数字 m:); scanf(%d,&m); printf(密码是:); for (j=1;j=n;j+) /*输出各人的编号*/ for(i=1;inext); m=p-password; printf(%d ,p-number); p-number=p-next-number; /*删除报m的节点*/ p-passw

18、ord=p-next-password; q=p-next; p-next=p-next-next; free(q); getchar(); printf(n是否继续(Y/N):); scanf(%c,&ch); if(ch=y|ch=Y) continue; else break;printf(再见!nn); printf( n);printf( n);printf( n);printf( n);printf( n);printf( n);printf( n); system(pause); return 0;六、参考文献 1严蔚敏，吴伟民.数据结构（C语言版）.清华大学出版社. 2严蔚敏，吴伟民.数据结构题集（C语言版）.清华大学出版社. 3DATA STRUCTURE WITH C+. William Ford,William Topp .清华大学出版社（影印版）. 4谭浩强.c语言程序设计. 清华大学出版社.专心-专注-专业