计算机科学与技术专业数据结构课程设计报告

郑州师范学院计算机科学与技术专业数据结构课程设计报告设计题目约瑟夫环班级B15软件工程（）组长组员指导教师完成日期201617成绩目录1需求分析311功能分析312设计平台32概要设计321类LINKLIST322类JOSEPH423类异常处理43详细设计和实现431创建结点NODE432创建双向循环链表533从链表中删除结点64调试与操作说明1041调试情况1042操作说明105设计总结11参考文献12附录121需求分析11功能分析本次选做的课程设计是改进约瑟夫JOSEPH环问题。约瑟夫环问题是一个古老的数学问题，本次课题要求用程序语言的方式解决数学问题。此问题仅使用单循环链表就可以解决此问题。而改进的约瑟夫问题通过运用双向循环链表，同样也能方便地解决。在建立双向循环链表时，因为约瑟夫环的大小由输入决定。为方便操作，我们将每个结点的数据域的值定为生成结点时的顺序号和每个人持有的密码。进行操作时，用一个指针CURRENT指向当前的结点，指针FRONT始终指向头结点。然后建立双向循环链表，因为每个人的密码是通过RAND函数随机生成的，所以指定第一个人的顺序号，找到结点，不断地从链表中删除链结点，直到链表剩下最后一个结点，通过一系列的循环就可以解决改进约瑟夫环问题。1、本演示程序中，利用单向循环链表存储结构模拟约瑟夫问题的进行。程序运行后，首先要求用户指定初始报数上限值，然后读取个人的密码。可设N30。此题所用的循环链表中不需要“头结点”，因此在程序设计中应注意空表和非空表的界限。2、演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令相应的输入数据和运算结果显示在其后。3、程序执行的命令包括1）构造约瑟夫环；2）执行约瑟夫环，并输出出列人的序号以及相应的密码；3）结束。4、测试数据1）M的初始值为20；2）N7，7个人的密码依次为3、1、7、2、4、8、4。3）首先M值为6，正确的出列顺序应为6、1、4、7、2、3、5。12设计平台WINDOWS2000以上操作系统；MICROSOFTVISUALC602概要设计已知N个人（以编号1，2，3N分别表示）围成一圈。从编号为1的人开始报数，数到M的那个人出列；他的下一个人又从1开始报数，数到M的那个人又出列；依此规律重复下去，直到一圈的人全部出列。这个就是约瑟夫环问题的实际场景，有一种是要通过输入N,M,K三个正整数，来求出列的序列。这个问题采用的是典型的循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。PLINKHEAD。解决问题的核心步骤首先建立一个具有N个链结点，无头结点的循环链表。然后确定第1个报数人的位置。最后不断地从链表中删除链结点，直到链表为空。改进的约瑟夫环问题与原问题思路一致，只是不再采用单循环链表存储结构，而采用双向循环链表，而且用一个判断语句来决定报数的方向的顺时针还是逆时针。本课程设计主要采用了类的数据结构，程序中包含了两个类LINKLIST,JOSEPH。为实现上述程序功能，应以单向循环链表表示约瑟夫环。为此，需要两个抽象数据类型单向循环链表和约瑟夫环。1）、单向循环链表的抽象数据类型定义为ADTLIST数据对象DAIAIELEMSET,I1,2,N,N0数据关系R1AI1,AIAI1,AID,I2,N基本操作INITLISTINTPASSWORDDNODELLINKDNODERLINK图31结点DNODE32创建双向循环链表创建一个空双向循环链表，双向循环链表和每个结点包括三个域ELEMENT，LLINK,RLINK其中ELEMENT为元素域，RLINK域为指向后继结点的指针，新增的LLINK域用以指向前驱结点。双向链表也可以带表头结点，并且也可以构成双向循环链表。此时，表头结点的RLINK，LLINK分别指向双向循环链表的头结点或表头结点和尾结点。一个结点的LLINK域的指针指向它左边结点的后部，这并不意味着该结点的LLINK域保存的仍是该左边结点存储块的起始地址。在此处，指针指向某个结点任何部分都是等价的，都是指该存储块的起始位置。图32单表头的双向循环链表每当结点计数到某一结点时，将他的前驱结点接到他的后继结点，然后将他的密码值PASSWORD赋给计数变量，再将此结点删除。如此循环下去，直到最后变为空的单循环链表为止。由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍然是围成一个圆圈的，可以使用循环表，由于退出圆圈的工作对应着表中结RLINKPASSWORDDATAFIRSTLLINK点的删除操作，对于这种删除操作频繁的情况，选用效率较高的链表结构，为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断，链表不带头结点。所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循环链表来描述。设头指针为FRONT，FRONT始终指向头结点，并定义指针CURRENT记录当前的结点。并根据具体情况移动（顺逆时针）。为了记录退出的人的先后顺序，采用一个顺序表进行存储。程序结束后再输出依次退出的人的编号顺序。由于只记录各个结点的DATA值就可以。最后通过函数调用来输出顺序。要解决约瑟夫环问题，首先一点就是必须有一个环，所以第一步我们必须建立一个双向循环链表。而建立一个双向循环链表必须有一个空的双向循环链表，然后运用尾插法建立一个双向循环链表，这样约瑟夫环就创建出来了，接下来就是处理约瑟夫环问题。33从链表中删除结点在双向循环链表中，一个结点的前驱结点地址保存在该结点的LLINK域中，这样可以方便地实现在一个指定结点之前插入一个新结点的操作，也可以方便地删除某个指定结点。函数通过代码QLLINKRLINKQRLINKQRLINKLLINKQLLINKDELETEQ来删除当前的那个结点Q，通过循环来一次次删除当前的结点，直到链表中剩下最后一个结点。具体程序如下INCLUDEINCLUDEINCLUDETYPEDEFSTRUCTNODE/定义单循环链表中节点的结构INTNUM/序列号即个人的编号INTCIPHER/个人所持有的密码STRUCTNODENEXTLINKLISTCLASSYSFHPUBLICLINKLISTCREATINTNLINKLISTSELECT1INTMLINKLISTHEAD/头指针指示有N个结点的单循环链表CREATPROTECTEDLINKLISTSELECTLINKLISTHEAD,INTMPRIVATELINKLISTP/存放人员信息LINKLISTR/临时存放LINKLISTQINTK/建立单循环链表函数/LINKLISTYSFHCREATINTNLINKLISTHEADLINKLISTPPLINKLISTMALLOCSIZEOFLINKLISTHEADPPNUM1PRINTF“随机产生第1个人的密码“PCIPHERRAND10IFPCIPHER0PCIPHERRAND10PRINTF“DN“,PCIPHERRPPNEXTPFORINTK2KNUMK/给每人一个编号PRINTF“随机产生第D个人的密码“,KPCIPHERRAND10IFPCIPHER0PCIPHERRAND10PRINTF“DN“,PCIPHERRNEXTPRPPNEXTHEADRETURNHEAD/决定出列编号/LINKLISTYSFHSELECT1INTMRETURNSELECTHEAD,MLINKLISTYSFHSELECTLINKLISTHEAD,INTMQHEADK1PQNEXT/Q为P的前驱指针,P指向当前报数的人PRINTF“出列的序号依次为“/在HEAD中的第一个结点起循环记数找第M个结点WHILEQPKK1/报一次数IFKM0/所报数等于报数上限值时PRINTF“D“,PNUM/输出该结点的NUM值MPCIPHER/把该结点的CIPHER密码值赋给MQNEXTPNEXT/对应的节点从链表中删除FREEPK0PQNEXTELSEQPPPNEXT/P指向当前报数的人HEADPRETURNHEADVOIDMAININTN,MM0YSFHYPRINTF“输入总人数N“SCANF“D“,YHEADYCREATNPRINTF“随机产生第一次的报数上限值M“MRAND10IFM0MRAND10PRINTF“DN“,MYHEADYSELECT1MPRINTF“DN“,YHEADNUM4调试与操作说明41调试情况这次的课程设计的代码很冗长，所以等有了解题思路后，把代码都写上后难免会有很多错误。当第一次把整个程序写好后运行，出现了很多错误。不过经过一点点的改正，错误也慢慢地变少。这也说明做事要认真，尤其做计算机这方面工作的时候，因为计算机不容许不一点点的错误，有了一点小错误和有一个大错误在计算机看来都是一样的，都不会得不到结果。有些小错误，比如说少了个分号，变量忘了定义，数据溢出等都是些小错误，但也不能松懈。因为要注意的地方很多，经过多次尝试，问题也就自然而然的解决了，而且以后遇到这方面的问题都会觉得比较得心应手。在随机设置每个结点的PASSWORD时也曾是个问题，因为我做的随机函数一直都用不好，要不是每次随到的都是一样的，要么就是每次随到的数都很大，后来通过老师的耐心讲解才得以解决。在调试的过程中，类的优势很明显，能很简单的把问题解决，而不需要使用的其他的一些比较复杂的方法。42操作说明生成界面如图41，42所示图41生成界面图42生成界面当程序运行的时候会出现如上图所示的提示，要求使用者输入程序中所需的输入总人数，使用者只需输入自己所想的总人数，系统便会随机产生每个人对应的密码，同时随机产生第一次的报数上限值。最后系统会给出出列的次序，最后产生的编号便是此次游戏的获胜者。使用者还可按下任意键，进行下一次的游戏。5设计总结通过这次数据结构课程设计，我感受最深的就是对于循环链表的使用，可以说对循环链表有了比以前更进一步的认识，以前只是一知半解的，如果只给个题目自己根本不能把程序完整地编写出来，所以这次课程设计最大的收获就在于对循环链表有了一定的理解，包括其中的一系列操作，如建立一个循环链表，删除链表中的一结点，增加一个结点等。在这次课程设计过程中需要我们一边设计一边探索，这这个过程当中我发现自己在数据结构方面知识掌握不够深入，对一些基本概念不能很好的理解，对一些数据结构不能够熟练的进行上机实现，这是自己比较薄弱。学好基础知识是理论付诸实践的前提，这样理论和实践才能充分地结合起来。在以后的学习中，我还要努力改正，充分利用上机实验的机会提高自己。在程序的输入的时候，因为自己对键盘的不熟练，代码又很多很繁琐，常常会产生放弃的念头，从中我也感受到只有坚持到底，胜利才会出现。在调试程序的时候我也有所体会，虽然约瑟夫环问题不是很难，但调试的时候还是会出现很多错误，因此我们不能认为容易就不认真对待。在以后的学习中，要能不断发现问题，提出问题，解决问题，从不足之处出发，在不断学习中提高自己。参考文献1张乃孝,裘宗燕数据结构C与面向对象的途径北京高等教育出版社，19982周云静数据结构习题解析与上机指导北京冶金工业出版社，20043陈慧南数据结构C语言描述北京人民邮电出版社，20054严蔚敏，吴伟民数据结构北京清华大学出版社，19975ADAMDROZDEK数据结构与算法北京清华大学出版社，20066徐孝凯数据结构实验北京中央广播电视大学出版社，2001附录源程序附下INCLUDEINCLUDEINCLUDEINCLUDEINCLUDEDEFINENULL0TYPEDEFSTRUCTNODEINTM/密码INTN/序号STRUCTNODENEXTNODE,LINKLISTLINKLISTCREATEINTZ/生成循环单链表并返回,Z为总人数INTI,MMLINKLISTH,R,SHNULLPRINTF“请按顺序依次为每个人添加密码“FORI1INISMMMPRINTF“D号的密码D“,I,SMIFHNULL/从链表的第一个节点插入HSRHELSE/链表的其余节点插入RNEXTSRS/R后移/FOR结束RNEXTH/生成循环单链表/RETURNHVOIDSEARCHLINKLISTH,INTM0,INTZ/用循环链表实现报数问题INTCOUNT1/COUNT为累计报数人数计数器INTNUM0/NUM为标记出列人数计数器LINKLISTPRE,PPHPRINTF“出列的顺序为“WHILENUMNEXTWHILECOUNTNEXTPNEXTPRINTF“D“,PNM0PMFREEPPPRENEXTCOUNT1NUM/WHILE结束VOIDCLEANINTSYSTEMCONSTCHARSTRINGINTINQUIRYPRINTF“请问需要清除上一次操作记录吗（1清屏/2不清屏）N“SCANF“D“,IFINQUIRY1SYSTEM“CLS“VOIDTEXTINTM0,Z,I,CHOOSE,K1/K用来阻止第一次进入程序清屏操作LINKLISTHBOOLCHOOSEFLAGFALSEWHILE1IFK1CLEANKWHILECHOOSEFLAGPRINTF“欢迎进入约瑟夫环问题系统N“PRINTF“1输入约瑟夫环数据N“PRINTF“2什么是约瑟夫环N“PRINTF“3退出系统N“PRINTF“N“PRINTF“请输入相应的数字进行选择“SCANF“D“,FORI1I4IIFCHOOSEICHOOSEFLAGTRUEBREAKELSECHOOSEFLAGFAL