欢迎来到沃文网! | 帮助中心 分享知识,传播智慧!
沃文网
换一换
首页 沃文网 > 资源分类 > DOCX文档下载
 

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

  • 资源ID:20100       资源大小:181.93KB        全文页数:16页
  • 资源格式: DOCX        下载权限:游客/注册会员/VIP会员    下载费用:10积分 【人民币10元】
快捷注册下载 游客一键下载
会员登录下载
三方登录下载: QQ登录   微博登录  
下载资源需要10积分 【人民币10元】
邮箱/手机:
温馨提示:
支付成功后,系统会自动生成账号(用户名和密码都是您填写的邮箱或者手机号),方便下次登录下载和查询订单;
支付方式: 微信支付    支付宝   
验证码:   换一换

加入VIP,免费下载资源
 
友情提示
2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,既可以正常下载了。
3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰   

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

约瑟夫环问题设计与实现第1页共10页约瑟夫环问题设计与实现摘要约瑟夫问题是由古罗马著名的史学家Josephus提出的问题演变而来,所以通常称为Josephus问题。改进约瑟夫问题的描述是编号为1,2,,n的n个人按顺时针方向围坐一圈,每人有一个密码m(整数),留作其出圈后应报到m后出圈,依次类推,即可求出出列顺序。因此约瑟夫环问题如果采用循环链表则能很好的解决。循环链表的数据结构,就是将一个链表的最后一个节点指针指向第一个结点。出列时,根据密码找到对应的人,打印其编号,将其密码赋值给m后,释放节点,形成新的约瑟夫环,直到所有人出列结束。关键字约瑟夫环;循环链表;出列顺序;释放节点;约瑟夫环问题设计与实现第2页共10页DesignandRealizationoftheJosephringABSTRACTTheJosephproblemistheevolutionproposedbyancientRomefamoushistorianJosephusandcome,sooftenreferredtoastheJosephusproblem.ImprovementofJosephproblemdescriptionisNo.1,2,...N,nindividualsaccordingtoaclockwisedirectionaroundacircle,eachwithapasswordofMinteger,keeptheringshouldbereportedaftertheMring,andsoon,wecancalculatethecolumnorder.SoJosephcircleifusingcircularlinkedlistcanbeverygoodsolution.Circulationlistdatastructure,isthelastofanodeisapointertoalistofthepointstothefirstnode.Out,accordingtothecodetofindthecorrespondingperson,printthenumber,thepasswordisassignedtom,releasethenode,theationofJosephring,untilallthepeopleoutoftheend.KeywordsJosephring;circularlinkedlist;thecolumnorderreleasenodes;目录约瑟夫环问题设计与实现第3页共10页1需求分析„„„„„„„„„„„„„„„„„„„„„„„„11.1课题内容„„„„„„„„„„„„„„„„„„„„„„11.2要求„„„„„„„„„„„„„„„„„„„„„„„„12概要设计„„„„„„„„„„„„„„„„„„„„„„„„„13详细设计„„„„„„„„„„„„„„„„„„„„„„„„„23.1程序中的数据类型„„„„„„„„„„„„„„„„„„23.2函数运行过程详解„„„„„„„„„„„„„„„„„„34设计和调试分析„„„„„„„„„„„„„„„„„„„„„„64.1调试中遇到的问题„„„„„„„„„„„„„„„„„„64.2经验和体会„„„„„„„„„„„„„„„„„„„„„75用户使用说明„„„„„„„„„„„„„„„„„„„„„„„76测试数据和测试结果„„„„„„„„„„„„„„„„„„„„8参考文献„„„„„„„„„„„„„„„„„„„„„„„„„„101需求分析约瑟夫环问题设计与实现第4页共10页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)每个人依序出列打印出列顺序并释放结点模块;约瑟夫环问题设计与实现第5页共10页2.2为了实现上述操作,应以单向循环链表为存储结构。2.3基本操作Data_操作结果构造链表,初始化每个人的相关信息Data_OutPut操作结果释放指向出列的人的结点,并重新报数3详细设计3.1程序中定义的数据类型typedefstructLNode{ElemTypenum;//各人的编号ElemTypedata;//各人的密码structLNode*next;//指向下一个节点的指针}LNode,*LinkList;调用函数Data_创建链表并输入每个人的编号和密码调用函数Data_OutPut按特定的顺序让每个人出列,并释放已出列的节点结束开始执行主函数的内容,开始程序数据next数据next数据next数据next约瑟夫环问题设计与实现第6页共10页程序中定义了一个节点的结构体,每次新分配一个节点内存,即为新增一个人,data为人的密码,num是人的编号。3.2每个函数的过程详解3.2.1voidmain;函数原型voidmain函数源程序voidmain{LinkListLNULL;intm,n30;//m为报数上限,n为人的个数inti0;//常用变量printf\t约瑟夫环问题\n\n;printf请输入m的值(要求m30||ndata;//依次输入每个人的密码R-numi1;//输入每个人的编号PLinkListmallocsizeofLNode;//创建新节点P-nextNULL;QR;R-nextP;//连接新的节点RP;}freeP;//释放无用结点Q-nextL;returnL;//返回循环链表}函数功能及实现先定义结构体指针变量R,P,Q,L,创建一个新节点赋值给指针L,并将L赋值给R,通过for循环再创建n个节点,并录入每个人对应编号,通过scanf函数录入每个人的密码,因为创建了一个节点。并将新创建的节点连到链表尾端,形成一个单链表。最后创建的一个节点是多余的,需要删约瑟夫环问题设计与实现第8页共10页除,所以通过free函数释放最后一个节点。之后将单链表的尾指针指向第一个节点,形成一个单循链表。最后通过return函数返回循环链表,继续执行主函数。3.2.3voidData_OutPutLinkListL,intk,intb;函数原型voidData_OutPutLinkListL,intk,intb;函数原程序voidData_OutPutLinkListL,intk,intb{printf\n出列顺序为\n;LinkListR,P,Q;forinti0;inext;//指针后移}printf第d个出列d\n,i1,R-num;//输出所找人的编号bR-data;//刷新b值,将所找到人的密码赋值给bQ-nextR-next;//将出列人的前一个节点和后一个节点连接形成新环LR-next;freeR;//释放已出列结点}函数功能及实现该函数首先定义了指针变量R,P,Q,L方便对节点的操作。通过for循环以确定所有人都会被出列,在while循环中,b的值最初是给定的报数上限,通过自减操作找到所要出列的那个人,打印其编号,将其密码重新赋值给b,并删除代表该人的节点,并释放该节点,形成一个新的约瑟夫环,约瑟夫环问题设计与实现第9页共10页进行下一次循环,最终所有人出列后完成for循环,打印出列顺序,返回大主函数。4设计和调试分析4.1调试中遇到的问题(1)在用scanf函数给普通变量输入数据时,在变量名前漏写地址运算符。如scanf″%d%d″,x,y;(2)输入数据时的数据形式与要求不符。用scanf函数输入数据时,必须注意要与scanf语句中的对应形式匹配。如scanf″%d,%d″,若按以下形式输入数据24是不合法。数据2和4之间应当有逗号。(3)输入、输出时的数据类型与所用格式说明符不匹配。例如有以下说明语句intx1;chary’a’;则运行时执行语句printf″x%c,y%d\n″,x,y;将给出与原意不符的结果在TURBOC2.0下运行(4)对于复合语句,忘记加花括号。例如i1;a0;whilei<10ai;i;printf″a%d\n″,a;的上限值是数组定义时元素个数减1。(5)对指针的操作要小心谨慎,比如初始化和赋值等问题值得加以注意。4.2经验和体会通过这次数据结构课程设计,我感受最深的就是对于循环链表的使用,可以约瑟夫环问题设计与实现第10页共10页说对循环链表有了比以前更进一步的认识,以前只是一知半解的,如果只给个题目自己根本不能把程序完整地编写出来,所以这次课程设计最大的收获就在于对循环链表有了一定的理解,包括其中的一系列操作,如建立一个循环链表,删除链表中的一个结点,增加一个结点等。在这次课程设计过程中需要我们一边设计一边探索,这这个过程当中我发现自己在数据结构方面知识掌握不够深入,对一些基本概念不能很好的理解,对一些数据结构不能够熟练的进行上机实现,这是自己比较薄弱的。学好基础知识是理论付诸实践的前提,这样理论和实践才能充分地结合起来。在以后的学习中,我还要努力改正,充分利用上机实验的机会提高自己。在程序的输入的时候,因为自己对键盘的不熟练,代码又很多很繁琐,常常会产生放弃的念头,从中我也感受到只有坚持到底,胜利才会出现。在调试程序的时候我也有所体会,虽然约瑟夫环问题不是很难,但调试的时候还是会出现很多错误,因此我们不能认为容易就不认真对待。在以后的学习中,要能不断发现问题,提出问题,解决问题,从不足之处出发,在不断学习中提高自己。5用户使用说明(1)根据正确的提示安装软件。(2)Intel486以上系列、AMDK6以上系列等PC台式机和便携式电脑都可运行。3打开该程序系统,根据提示首先输入初始报数上限和约瑟夫环的人数,然后输入各个人的密码,完成输入后,按回车键即可显示约瑟夫环内各人的出列顺序。6测试数据和测试结果约瑟夫环问题设计与实现第11页共10页(1)进入系统界面系统提示输入m的值,即报数上限,为测试所给数据,将m的值设为20。(2)输入约瑟夫环的人数输入人数后,若输入人数大于30则提示输入错误,重新输入,这里为检测所给数据,设定人数为7。(3)输入7人的密码约瑟夫环问题设计与实现第12页共10页根据题目所给数据,7人的密码依次为3,1,7,2,4,8,4,输入完毕后回车。(4)显示结果测试的出列顺序为6,1,4,7,2,3,5符合题目要求,与算得的结果一致,证明程序正常运行,能够解决一般的约瑟夫环问题。约瑟夫环问题设计与实现第13页共10页参考文献[1]谭浩强.C程序设计第二版.北京清华大学出版社,1999.12[2][美]KennethA.Reek著,徐波译.C和指针.北京;人民邮电出版社2008.4[3]严蔚敏,吴伟民.数据结构.北京清华大学出版社,1997[4][美]HMDeitel,PJDeitel著,薛万鹏等译.C语言程序设计教程.北京机械工业出版社,2000.07约瑟夫环问题设计与实现第14页共10页附录源程序清单/*约瑟夫环问题设计与实现*///函数头文件includestdio.hincludemalloc.hincludestdlib.h//自定义数据类型typedefintStatus;typedefintElemType;//定义节点结构体typedefstructLNode{ElemTypenum;//各人的编号ElemTypedata;//各人的密码structLNode*next;//指向下一个节点的指针}LNode,*LinkList;//函数原型LinkListData_LinkListvoidData_OutPutLinkList//主函数voidmain{LinkListLNULL;intm,n30;//m为报数上限,n为人的个数inti0;//常用变量printf\t约瑟夫环问题\n\n;printf请输入m的值(要求m30||ndata;//依次输入每个人的密码R-numi1;//输入每个人的编号PLinkListmallocsizeofLNode;//创建新节点P-nextNULL;QR;R-nextP;//连接新的节点RP;}freeP;//释放无用结点Q-nextL;returnL;//返回循环链表}//调用数据输出函数voidData_OutPutLinkListL,intk,intb{printf\n出列顺序为\n;LinkListR,P,Q;约瑟夫环问题设计与实现第16页共10页forinti0;inext;//指针后移}printf第d个出列为d\n,i1,R-num;//输出所找人的编号bR-data;//刷新b值,将所找到人的密码赋值给bQ-nextR-next;//将出列人的前一个节点和后一个节点连接形成新环LR-next;freeR;//释放已出列结点}}忽略此处..

注意事项

本文(约瑟夫环数据结构课程设计)为本站会员(星星008)主动上传,沃文网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知沃文网(发送邮件至2622162128@qq.com或直接QQ联系客服),我们立即给予删除!

温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服点击这里,给沃文网发消息,QQ:2622162128 - 联系我们

版权声明:以上文章中所选用的图片及文字来源于网络以及用户投稿,由于未联系到知识产权人或未发现有关知识产权的登记,如有知识产权人并不愿意我们使用,如有侵权请立即联系:2622162128@qq.com ,我们立即下架或删除。

Copyright© 2017-2019 www.wodocx.com ,All Rights Reserved |陕ICP备19002583号-1

陕公网安备 61072602000132号     违法和不良信息举报:0916-4228922