约瑟夫环课程设计(数据结构)

计算机学院网络工程专业数据结构课程设计题目：排序系统设计（约瑟夫环问题）班级：网工10101班姓名：房鸿朝学号201017030127同组人姓名：罗源起迄日期:2010年12月26日课程设计地点:E3-A513指导教师：徐晓蓉评阅意见：成绩评定：评阅人：日期：完成日期：2011年12月摘要：功能：设编号为1，2，3，……，n的n(n0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。目录1需求分析........................................................21.1功能分析21.2设计平台22概要设计........................................................22.1创建循环单链表create()22.2输出查找search()32.3异常处理及屏幕清理clean()33程序设计主要流程.................................................43.1程序实现流程图44调试与操作说明...................................................44.1调试情况44.2操作说明5总结............................................................7致谢...........................................................8附录............................................................9参考文献.......................................错误!未定义书签。==1==1．需求分析1.1功能分析本次选做的课程设计是改进约瑟夫(Joseph)环问题。我选择了和罗源两个人来完成本次课程设计的作业。约瑟夫环问题是一个古老的数学问题，本次课题要求用程序语言的方式解决数学问题。此问题仅使用单循环链表就可以解决此问题。在建立单向循环链表时，因为约瑟夫环的大小由输入决定。为方便操作，我们将每个结点的数据域的值定为生成结点时的顺序号和每个人持有的密码。进行操作时，用一个指针r指向当前的结点，指针H指向头结点。然后建立单向循环链表，因为每个人的密码是通过scanf()函数输入随机生成的，所以指定第一个人的顺序号，找到结点，不断地从链表中删除链结点，直到链表剩下最后一个结点，通过一系列的循环就可以解决改进约瑟夫环问题。1.2设计平台Windows2007操作系统；MicrosoftVisualC++6.0；2．概要设计已知n个人（以编号1，2，3...n分别表示）围成一圈。从编号为1的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到一圈的人全部出列。这个就是约瑟夫环问题的实际场景，有一种是要通过输入n,m,k三个正整数，来求出列的序列。这个问题采用的是典型的循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。r-next=H。解决问题的核心步骤：首先建立一个具有n个链结点，无头结点的循环链表。然后确定第1个报数人的位置。最后不断地从链表中删除链结点，直到链表为空。本课程设计主要采用了结构体，程序中包含了两个只要函数：create（）；search（）；2.1创建循环单链表create（）dtypeefstructNode定义一个结构体，m为密码，n为序号（总人数）。==2==定义H=NULL创建一个没有头结点的单向循环链表，并采for(i=1;i=z;i++)随机输入密码，在每次输入密码后，自动生成新的链表存储空间s=(Linklist)malloc(sizeof(Node));当前指针r后移，并释放r的值。直到r-=H时创建单向循环链表成功，并返回H的值作为总人数。单项循环链表示意图：每当结点计数到某一结点时，将他的前驱结点接到他的后继结点，然后将他的密码值password赋给计数变量，再将此结点删除。如此循环下去，直到最后变为空的单循环链表为止。2.2输出查找search（）用循环链表实现报数问题,利用count累计报数人数，num为标记出列人数计数器。当随机输入初始密码m0时即从第一个人报起，到第m时取出m并显示，在释放该指针指向m的值，从删除位的下一个人开始报起，按该人的密码为m实现对总个链表的输出，指针没报数一次则后移一个节点。实现代码：pre-next=p-next;printf(%d,p-n);m0=p-m;free(p);p=pre-next;2.3异常处理及屏幕清理clean()system(cls);对上次输入的及运行结果是否进行屏幕清理工作。使程序运行界面不至于太过混乱，也可以将第二次的实验结果和先前的实验结果进行比较从而可以发现程序是否出现运行错误，便于检查和修改。………==3==3.程序设计主要流程3.1程序实现流程图（图3-1）图3-1程序实现流程图4．调试与操作说明4.1调试情况这次的课程设计的代码很冗长，所以等有了解题思路后，把代码都写上后难免会有很多错误。当第一次把整个程序写好后运行，出现了很多错误。如赋值语句H=NULL没有定义，从而形成带空头结点的单链表，以及在操作r指针后移找出m时，没对r当时的值进行释放从而导致下个输出出现错误。不过经过一点点的改正，错误也慢慢地变少。这也说明做事要认真，尤其做计算机这方面工作的时候，因为计算机不容许不一点点的错误，有了一点小错误和有一个大错误在计算机看来都是一样的，都不会得不到结果。有些小错误，比如说少了个分号，变量忘了定义，数据溢出等都是些小错误，但也不能松懈。因为要注意的地方很多，经过多次尝试，问题也就自然而然的解决了，而且以后遇到这方面的问题都会觉得比较得心应手。在调试的过程中，结构体的优势很明显，能很简单的把问题解决，而不需要使用的其他的一些比较复杂的方法。==4==主菜单1.输入约瑟夫环2.显示约瑟夫环问题的描述3.结束界面是否执行清屏（1=Y，2=N）？1.清屏进入2.不清屏进入4.2操作说明生成界面如图4-1，4-2，4-3,4-4,4-5所示；图4-1主菜单图4-2输入约瑟夫环==5==当程序运行的时候会出现如上图所示的提示，要求使用者输入程序中所需的输入总人数，使用者只需输入自己所想的总人数，便可以随机输入每个人对应的密码。最后系统会给出出列的次序。使用者还可进行选择是否记录上次数据，进行下一次的操作。图4-3显示约瑟夫环问题图4-4退出程序==6==图4-5当输入人数超过最大数总结为期一周的课程设计快结束了，通过这次数据结构课程设计，我感受最深的就是对于循环链表的使用，可以说对循环链表有了比以前更进一步的认识，以前只是一知半解的，如果只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解，包括其中的一系列操作，如建立一个循环链表，删除链表中的一个结点，增加一个结点等。在这次课程设计过程中需要我们一边设计一边探索，这这个过程当中我发现自己在数据结构方面知识掌握不够深入，对一些基本概念不能很好的理解，对一些数据结构不能够熟练的进行上机实现，这是自己比较薄弱的。学好基础知识是理论付诸实践的前提，这样理论和实践才能充分地结合起来。在以后的学习中，我还要努力改正，充分利用上机实验的机会提高自己。在程序的输入的时候，因为自己对键盘的不熟练，代码又很多很繁琐，常常会产生放弃的念头，从中我也=7==感受到只有坚持到底，胜利才会出现。在调试程序的时候我也有所体会，虽然约瑟夫环问题不是很难，但调试的时候还是会出现很多错误，因此我们不能认为容易就不认真对待。在以后的学习中，要能不断发现问题，提出问题，解决问题，从不足之处出发，在不断学习中提高自己。致谢这次的课程设计，我们两人一个小组去完成我们自己的课程.，让我们有机会贴近现实，感受成功的喜悦；其次要感谢实验机房的老师提供优良的实验设备供我们做实验，正是这种良好的实验环境让我们整个实验过程心情都非常愉快。再次要感谢指导老师们的辛勤指导，每当我们遇到疑难问题时，是他们一次次不厌其烦的解释和悉心的指导，我们才能闯过一个个难关，到达胜利的彼岸，是他们给我们提供了一次宝贵的检验自己机会。只有在真正实战的时候才会发现书到用时方恨少的真谛。有时感觉自己那么一次次举手请教，可问题又那么幼稚简单。老师是那么的耐心与不厌其烦，直到我们点头说懂得的时候老师才离开。。最后也要感谢同学们的帮助，感谢所有在我课程设计过程中帮助过我的人！==8==附录#includestdio.h#includemalloc.h#includeconio.h#includestdlib.h#includectime#defineNULL0typedefstructNode{intm;//密码intn;//序号structNode*next;}Node,*Linklist;Linklistcreate(intz)//生成循环单链表并返回,z为总人数{inti,mm;LinklistH,r,s;H=NULL;printf(Outputthecode:);for(i=1;i=z;i++){printf(\ninputcipher=);scanf(%d,&mm);s=(Linklist)malloc(sizeof(Node));s-n=i;s-m=mm;printf(%d号的密码%d,i,s-m);if(H==NULL)//从链表的第一个节点插入{H=s;r=H;}else//链表的其余节点插入{r-next=s;r=s;//r后移}}//for结束r-next=H;/*生成循环单链表*/==9==returnH;}voidsearch(LinklistH,intm0,intz)//用循环链表实现报数问题{intcount=1;//count为累计报数人数计数器intnum=0;//num为标记出列人数计数器Linklistpre,p;p=H;printf(出列的顺序为:);while(numz){do{count++;pre=p;p=p-next;}while(countm0);pre-next=p-next;printf(%d,p-n);m0=p-m;free(p);p=pre-next;count=1;num++;}//while结束}voidclean(){intsystem(constchar*string);intinquiry;printf(请问需要清除上一次操作记录吗（1.清屏/2.不清屏）...?\n);scanf(%d,&inquiry);if(inquiry==1)system(cls);}voidtext(){intm0,z,i,choose,k=1;//k用来阻止第一次进入程序清屏操作LinklistH;boolchooseFlag=false;while(1){==10==if(k!=1)clean();k++;while(!chooseFlag){printf(……………………欢迎进入约瑟夫环问题系统……………………\n);printf(*1.输入约瑟夫环数据*\n);printf(*2.什么是约瑟夫环*\n);printf(*3.退出系统*\n);printf(........................................................\n);printf(请输入相应的数字进行选择:);sc