数据结构课程设计报告约瑟夫环完整版1

PAGEPAGE23**＊*****＊****＊＊***＊实践教学＊***＊＊*******＊****＊兰州理工大学软件职业技术学院2011年春季学期算法与数据结构课程设计题目:约瑟夫环专业班级：姓名:学号：指导教师:成绩:摘要约瑟夫环问题是典型的线性表的应用实例,其开发主要包括后台数据库的建立和维护以及前端应用程序的开发两个方面。对于前者要求建立起数据一致性和完整性强、数据安全性好的库.而对于后者则要求应用程序功能完备,易使用等特点。经过分析，我们使用MICＲＯSOFＴ公司的MicｒosoftＶisuａlＣ+＋６.0开发工具，利用其提供的各种面向对象的开发工具,尤其是数据窗口这一能方便而简洁操纵数据库的智能化对象,首先在短时间内建立系统应用原型，然后,对初始原型系统进行需求迭代,不断修正和改进,直到形成用户满意的可行系统。关键词:单循环链表；ｃ语言;约瑟夫环;序言数据结构是研究数据元素之间的逻辑关系的一门课程，以及数据元素及其关系在计算机中的存储表示和对这些数据所施加的运算.该课程设计的目的是通过课程设计的综合训练,培养分析和编程等实际动手能力，系统掌握数据结构这门课程的主要内容。本次课程设计的内容是用单循环链表模拟约瑟夫环问题,循环链表是一种首尾相接链表，其特点是无须增加存储容量,仅对表的链接方式稍作改变,使表处理更加灵活，约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处,进一步加深对链表结构类型及链表操作的理解.通过该课程设计,能运用所学知识,能上机解决一些实际问题,了解并初步掌握设计、实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以及调试分析,熟练掌握数据结构的选择、设计、实现以及操作方法,为进一步的应用开发打好基础。目录TOC\ｏ”1—３”\ｈ＼z\uＨＹPＥRＬINK＼l”_Toｃ29８072296”摘要PＡＧEREF_Ｔoc298０72296\h１HYPERLＩNK＼l”_Ｔｏｃ２98072297”序言PAＧＥＲEF_Toｃ29807229７＼ｈ2HYＰＥＲLIＮK\l”＿Toc２9807229８”目录PAGＥRＥF_Tｏc2980722９８\h3ＨＹＰEＲLINK\l”_Toｃ29807229９”正文PAGERＥＦ_Toc29807２２99\ｈ４HＹPERLINK\l"_Tｏc298072300"一、问题描述PAGＥＲＥF＿Toc2980７２300\h4ＨYＰERLINK\l”＿Toc2９80７２301"二、逻辑设计PAＧEＲEF＿Toc298072３01\h5ＨYPEＲLＩNK\l”_Ｔｏc２98０72３02”三、详细设计PAＧＥＲEF＿Ｔoc２9807２３02\ｈ７HYＰERLＩNK\l”_Toc298072303”四、程序代码PAＧEREＦ_Toｃ2980７2303\h1３HYPＥRLINＫ\ｌ”＿Ｔoｃ29８0723０4＂五、程序调试与测试PＡGＥREF_Toc29807２304＼h13ＨYPERＬIＮK\l”_Toc２98072３05”设计总结ＰＡGERＥF_Tｏc298072305\h18HYＰERLINK\l”_Ｔoｃ２9８07２306"参考文献PＡＧEＲEF_Ｔｏc298072３０６\h19HYPERLＩNK\l”_Tｏｃ29８0７2307＂致谢ＰAＧERＥF_Ｔｏc2９8072307\ｈ20HＹPEＲＬＩNＫ［２]按要求求解约瑟夫环\n”)； ｐｒintf(”［０］退出\n");ﻩｐｒintf("＊***＊＊*＊＊**＊**＊*****＊**＊**欢迎使用!**＊*＊*＊**＊****＊＊*******＊****＼n＂);｝四、程序代码见附录源程序.五、程序调试与测试1.调用模块时，结点结构的调用与其他模块产生冲突,导致每一行都出现两次错误,加入子函数的声明后错误消失.2.刚开始时曾忽略了一些变量参数的标识”&＂和“＊”，使调试程序时费时不少。今后应重视确定参数的变量和赋值属性的区分和标识。３.本次课程设计采用数据抽象的程序设计方法，将程序划分为三个层次结构：元素节点、单向循环链表,主控制模块.思路较为清晰，实现调用顺利。经过本次实验,使我对数据结构这门课程有了进一步的了解，每一个程序经过需求分析、概要设计、详细设计之后，思路即清晰呈现,程序也很快就出来了,最后经过调试、运行又有新的体验。＜测试用例>这是一个使用循环链表的经典问题。本程序开始运行界面如下:图7约瑟夫环开始运行界面图7约瑟夫环开始运行界面选择1进入约瑟夫环问题阐述.图8约瑟夫环问题阐述图8约瑟夫环问题阐述①选择2,输入下列数据测试：请输入总人数n：7请输入开始上限数ｍ：20；请依次输入每个人的密码：3１７２4８４出队顺序:６147２3５图9约瑟夫环测试1图9约瑟夫环测试1②继续选择2,输入下列数据测试：请输入总人数n:5请输入开始上限数m:３0请依次输入每个人的密码：3456７出队顺序：53１24图10约瑟夫环测试2图10约瑟夫环测试2③继续选择2，输入下列数据测试：请输入总人数ｎ：８请输入开始上限数ｍ：14请依次输入每个人的密码:３45６78910出队顺序：67２８３514图11约瑟夫环测试3图11约瑟夫环测试3测试完成,选择0退出。设计总结我的这次数据结构课程设计的题目是:《约瑟夫环》,通过对该题目的设计,我加深了对数据结构及存储结构的理解,进一步地理解和掌握了课本中所学的各种数据结构,尤其是对单循环链表上基本运算的实现，学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力.通过这次数据结构课程设计，我感受最深的就是对于循环链表的使用,可以说对循环链表有了比以前更进一步的认识，以前只是一知半解的，如果只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解,包括其中的一系列操作，如建立一个循环链表,删除链表中的一个结点，增加一个结点等。在调试程序的时候我也有所体会,虽然约瑟夫环问题不是很难，但调试的时候还是会出现很多错误,因此我们不能认为容易就不认真对待。在以后的学习中,要能不断发现问题，提出问题,解决问题，从不足之处出发,在不断学习中提高自己.两周的课程设计很短暂,但其间的内容是很充实的,在其中我学习到了很多平时书本中无法学到的东西,积累了经验,锻炼了自己分析问题，解决问题的能力，并学会了如何将所学的各课知识融会,组织起来进行学习，总而言之这两周中我学到很多,受益匪浅。参考文献1.严蔚敏，吴伟民。《数据结构(C语言版)》.清华大学出版社.2.严蔚敏，吴伟民.《数据结构题集（C语言版)》。清华大学出版社。3．《ＤＡTASTＲUCTＵREWITHC++》.ＷｉｌliａmForｄ，ＷilｌｉamTｏpp.清华大学出版社(影印版)．４．谭浩强.《ｃ语言程序设计》.清华大学出版社.致谢这次的课程设计，我们两人一个小组去完成我们自己的课程，但是还是得到了来自很多方面的帮助。在此首先要感谢学院提供给我这次实践的机会,让我们有机会贴近现实，感受成功的喜悦；其次要感谢实验机房的老师提供优良的实验设备供我们做课设，正是这种良好的课设环境让我们整个课设过程心情都非常愉快.再次要感谢指导老师们的辛勤指导，每当我们遇到疑难问题时,是他们一次次不厌其烦的解释和悉心的指导,我们才能闯过一个个难关,到达胜利的彼岸,是他们给我们提供了一次宝贵的检验自己机会.最后也要感谢同学们的帮助，有了他们的支持使我遇到任何困难都不是一个人在战斗.感谢所有在我课程设计过程中帮助过我的人!附录源代码：#iｎcｌude<stｄio。h〉／/输入输出函数头文件#include<ｓtdｌiｂ.ｈ＞／／字符串转短整形函数的头文件１0１40219//tｙpedefｓｔrｕctLNodｅ/／定义单循环链表中节点的结构{ ｉnｔnuｍ；／/编号ﻩintpwd;/／pａsswordﻩstrucｔLNode＊next；//指向下一结点的指针}LNoｄｅ;/＊构造结点*/LＮｏｄe*ｃreatｅNode(intｍ_ｎum,inｔm_pwd）{ LNｏｄe*p;ﻩｐ＝(LNode＊)maｌlｏｃ(ｓiｚeｏf（ＬNode));//生成一个结点 p—〉nｕｍ＝m_num;//把实参赋给相应的数据域ﻩp－>ｐwd＝m＿ｐwｄ； p-〉next=NＵLL；//指针域为空ﻩrｅtuｒnｐ;}/**创建循环链表＊＊/voidcｒeatｅLｉsｔ（LNode**ppHead,intn）{/*创建单向循环链表pｐHｅad，人数个数为n，并输入每个人的密码值,若建立失败则生成头结点，让cｕr指向他,若建立成功则插入结点P，cuｒ指向的数据元素为p，后续为”空"的节点，再把P插入循环链表ppHeaｄ中＊/ ｉｎti，m_pｗd;ﻩＬNodｅ＊p,*ｃur;//cuｒ：浮标指针 for（ｉ=１;i〈=n；i＋＋)ﻩ{ ｐrintf(”输入第%d个人的密码:"，i); ｓｃaｎf(”%d”，＆m_pwd);//输入持有密码 ﻩp=crｅａteNode(i，m＿pwｄ）；//调用构造结点函数ﻩ if（*ppHead==ＮULＬ)/／如果头结点为空ﻩﻩ{ﻩﻩﻩ＊pｐHead=cuｒ＝p;//生成头结点,让cｕr指向他ﻩﻩ cur—〉next=*ｐpHead;/／cuｒ的指针域指向自身 }ﻩﻩelsｅ//如果不为空,则插入结点 ﻩ｛ ﻩp—〉next=cuｒ—〉next； ﻩcur—〉nexｔ=p；ﻩ cur=p；//ｃuｒ指向新插入结点ﻩﻩﻩ｝ﻩ｝ prinｔf(”完成创建！＼n");／／提示链表创建完成｝/＊出队处理*/vｏｉdjoｓe（ＬNｏde＊pｐＨeaｄ,ｉｎtm_pwd){／*p指向要删除节点的前一个节点，ppHeaｄ指向要删除的节点，使ｐ=ｐpHeaｄ,ppHead再指向要删除节点的下一个节点，使p和ppHｅad链接,输出p指向节点的编号和密码值，释放pｐHead，如此循环,直至把所有节点都打印和删除为止!＊/ﻩinti，ｊ； LNｏde*p,＊p＿ｄel;/／定义指针变量 fｏr(i=1；p!=pｐHead;ｉ++){ ﻩfｏr(j=１;j<m_pwd;++j）{ﻩﻩ p=ｐpHead；//ｐ赋值为ppHｅａd，p指向要删除结点的前一个结点ﻩﻩﻩppHead＝ppＨeaｄ—>next;/／ppHｅad指向下一个元素 ﻩ} p-〉next=ｐpHeaｄ—〉nｅxt;／/ｐ结点与头结点链接ﻩ i=ppHeaｄ—〉ｐwｄ；/／i赋值为pｐＨｅａd—〉pwd j=ｐpHeａd—〉num；/／ｊ赋值为ｐpHead－〉num，j为要删除的密码值 ﻩｐrｉntf(”第％d个人出列,密码：％d\ｎ”，j,ｉ);ﻩﻩm＿pwｄ=ｐpＨeaｄ—〉ｐwｄ;/／m＿pｗd赋值为ppHｅad-〉ｐwｄ ﻩｆrｅe（ppHｅad)；//释放头结点 ﻩpｐＨead=p—〉nｅxｔ；//ppＨeａd重新赋值给p-〉neｘt,即释放前的ｐpＨead—＞pｗd指针//删除报数结点 } i＝ｐpHｅａd－〉pｗd;//ｉ赋值为ｐpＨead-〉ｐwdﻩj=pｐHｅａd—〉nuｍ；//ｊ赋值为ppHead-〉num pｒiｎtf（"最后一个出列是％d号,密码是:%d＼n",j，i）; fｒeｅ(ppHｅａd)；//释放头结点}voiｄｉｎstruｃtion（）{printｆ（"＊**＊*＊＊******＊**＊＊＊＊＊*＊**＊＊*＊*＊＊*＊*＊****＊**＊*＊**＊＊＊＊＊＊＊＊*****＊**\n”);prｉntf（”约瑟夫环:\n"）;pｒｉｎtf（”编号为1,２,3，4…,n的ｎ个人按顺时针方向围坐一圈，每人持有一个密\n"）；ｐrｉｎtf(”码(正整数).一开始任选一个正整数作为报数的上限值m,从第一个人开始\n");pｒinｔf(”按顺时针方向自1开始顺序报数，报到时停止.报m的人出列，将他的密码\n”);priｎｔf（”m作为新的ｍ值,从他在顺时针方向上的下一人开始重新从１报数，如此下去,＼n”）;printf(”直到所有人全部出列为止。编程打印出列顺序．\n”)；prｉnｔf(＂*＊＊*****＊＊＊*＊**＊****＊＊*＊＊****＊**＊*＊*＊*＊＊**＊****＊＊＊**＊*\n");reｔｕrｎ0;｝voｉdmｅnu(){ pｒiｎtｆ(”＊*****＊**＊****＊＊**＊＊＊*＊＊**约瑟夫环＊*****＊**＊＊＊*＊＊*＊**＊*＊**＊**＊*\n”)； printｆ（”\n")；ﻩpｒｉntｆ（”［１]约瑟夫环问题的阐述\n”)；ﻩｐｒinｔf(”［2］按要求求解约瑟夫环\n＂)； pｒiｎtｆ(”[0]退出＼n");ﻩpｒintf（”＊＊＊****＊＊＊＊＊＊**＊*＊＊***＊**＊欢迎使用!***＊*******＊＊＊****＊*＊*＊*＊***＼n”)；｝/＊主函数模块*/intｍaｉn（){ﻩintn，ｍ,x;ﻩＬNoｄｅ*ppHeaｄ=NＵLL; ｍｅnｕ（); fｏｒ（；；){ printf(”\n请选择要执行的操作：”）; scａnf("％ｄ”,＆x)；ﻩｓｙstｅm（”clｓ”);ﻩswｉtcｈ（x)｛ｃase１：ﻩ priｎtｆ（"＊＊＊＊＊***＊＊＊*＊＊＊****＊*＊**＊＊*＊＊＊＊***＊＊＊*＊＊****＊＊***＊*＊*＊＊**＊＊***＊＊\n”）；ｐrinｔf（"约瑟夫环:\ｎ");prinｔf(”编号为1,２，3，4…,n的