数据结构算法演示系统毕业设计论文.docx

数据结构算法演示系统DataStructureDemonstrationSystem目录目录I摘要VABSTRACTVI前言1第1章绪论21.1.课题研究背景21.2国内计算机辅助教学的现状21.3计算机辅助教学的发展趋势41.4系统建设的目的4本章小结5第2章需求分析62.1功能性需求分析62.1.1系统需求62.1.2识别参与者和用例72.1.3用例的事件流描述92.2非功能性需求分析182. 2.1设计思想182. 2.2可行性分析19本章小结20第3章系统详细设计212.1 系统总体结构图212.2 静态结构模型213. 2.1定义系统对象类213. 2.2定义用户界面类253. 2.3建立类图313. 3动态行为模型31本章小结39第4章系统实现404. 1多线程简介404.1.1线程、多线程概念404.1.2实现多线程的方法404.2动态算法演示模板424.3算法演示的多线程设计434.3.1源代码同步演示的实现444.3.2动画的同步实现454.3.3算法中变量值的同步实现45本章小结45结论46总结与体会47谢辞48参考文献49附录一5055附录二DataStructureDemonstrationSystemABSTRACT,I,issystemtakesQinghuaUniversitypub1.ishinghousepub1.icationC1.anguageversion''DaiaStruc1.urefc1.asamainsource,reasonab1.ychoosespartofa1.gorithmsintheDataStructureandcarriesoninthesystemorganica1.1.ycombinations,formstheoptimizeddynamicdemonstrationsystem.Itmayadaptthereaders'difterentdemandstothea1.gorithmdata-inandcontro1.modestheproccssexecution,anddemonstratesinthea1.gorithmimp1.ementationonthecomputerscreenthedata1.ogica1.organizationeitherthememorystructurechangeconditionorthestackchangeconditioninterecursiona1.gorihnimp1.ementation.WithC#mu1.tithrcad.theDataStructureCAIcanprovidea“treeinone”p1.atform.onwhicha1.gorithmanimation,sourcecodeandvariab1.eva1.uecanbeexecutedandshownsynchronous1.y.Keywords：Datastructures.Dynamicdemonstration,C#.Mu1.thrcad.Synchronous前言数据结构是计.算机专业的核心课程，对各类犯怯的理解则是课程教学的重点和难点,算法动态演示作为辅助教学过程的手段则可以有效帮助学生更快的理解、掌握算法。数据结构对后续课程的学习极其或要。但该课程涉及大地的概念、定义、模型和算法,显得很抽象和深奥。在教学过程中，如果能加以计铝机辅助教学，可.以提高教学效果,所以编写这样的程序不仅有助学习数据结构，同时也大大增强/学生的学习兴趣，提离学生的编程能力。这是因为，一方面利用算法演示系统的生动性和直观性，使教学内容条理化和形象化，降低了对知识理解的难度：另方面，由于演示系统的趣味性和交互性，有利r激发学生浓厚的学习兴趣,使其愿学、乐学.可视化是演示系统应该具备的要求。本系统采用C#多线程技术来实现数据结构.算法的算法动态演示设计，提供及源代码跟踪、变星跟踪、模拟动态效果“三合”的算法演示同步平台。第1章绪论数据结构是计算机专业的核心课程，重点培养学生在对数据分析组织与程序设计算法思想上的综合能力。算法是数据结构的主要内容，也是数据结构教学的点和难点。但在数据结构的教学过程中，使用传统的静态课件或“粉箔+黑板”教学形式很难将算法的执行过程动态地演示出来，影响r教学效果.G数据结构算法动态演示设计是使用专业编程技术实现算法的动态展示，使学生更直观的从算法的设计思想、程序运行描述、程序运行结果同步跟踪展示等全方位的了解算法,使学生能主动积极地学习和掌握应用这些算法.1.I课题研究背景随着现代科学技术的迅猛发展，计尊机技术己渗透到各个领域，成为各行业必不可少的工具，特别是InICrne1.技术的推广和信息裔速公路的建立，使IT产业在市场竞争中越发显示由其独特的优势，步入数字化时代，有巨大的数据信息等待着加工处理和传输，这将现实的许多东西都进入虚拟的世界当中，这都需耍计算机技术的支持司样的，学院的教学手段也在逐步信息化，这使得计算机辅助教学CAI的出现成为一种必然的趋势。90年代以来，随若多媒体和In1.erne1.网络的出现，计算机教仔已步入一个全新的阶段，计算机辅助教学CAI作为一种先进的教学手段正逐步渗透于各类院校的各个学科.E数据结构不仅是大学计算机专业的核心课程之一，也是非计算机专业的主要选修课程之一。该课程涉及大量的概念、数据结构和党法，理论性强又较为抽象，尤其是对算法描述的执行过程的理解是难点和重点。在课堂教学上，大量的算法不可能也无法一一详述,运用计算机辅助教学系统一一G数据结构舞法动态演示系统B可以使教学内容化静为动，调动学生的学习兴趣：变难为易，提高学生学习兴趣：使学生御学于乐，培养学生的学习兴趣,与此同时，利用计算机辅助教学还可以满足学生的学习兴趣。它已成为激发学生兴趣的新方法、新手段。1.2国内计算机辅助教学的现状从上述分析，可以看出系统至少有7个重要的类：顺序表(Sq1.iSt)、链表(Iink1.ist)、二叉树遍历(OEe门Tee)、二叉树线索化(ThreTree)、林夫曼树(HUfFmanCode)、拓扑排序(TopoSon)、内部持序(Sort),接若要确定这些类的属性和方法。1)类sq1.isttransfer(string:str.sq1.ist:&1.):void该函数方法将字符串转化为数组存放。ins_sq1.ist(sq1.ist:&1.char:x.inti):void该操作是顺序表进行插入，以线性表.插入字符和位置作为参数.<1.c1._sq1.ist(sq1.ist:&1.,inti):void该操作是顺序表进行删除,以线性表，删除的位置作为参数。2)类Iink1.is1.crt_!ink1.ist(int:n.Iink1.isi:&1.):void创建一个单链表，以链表元素个数和链表作为参数.insJink1.is1.(1.ink1.isi:&1.,char:x.inti):void该操作是旋表进行插入，以涟表，插入字符和位置作为参数。de1.jink1.ist(sq1.ist:&1.,inti):void该操作是他表进行削除，以徒表，删除的位置作为参数，3)类Orderrreepre-Order(bt:bitree):void该操作是对二叉树进行先序遍历。in-Order(bt:hitree):void该操作是对二叉树进行中序遍历。Post_Ordcr(bt:bitrcc):void该操作是对二叉树进行后序遍历.4)类ThrCTrCCPre_Thre(bi:bitree):void该操作是对二叉树进行先序线索化。in_Thrc(bt:bitrec):void该操作是对二叉树进行中序线索化。PoS1.Thre(bt:bitree):void该操作是对二叉树进行后序线索化。5)类HUfrmanCOdeHUffmanCoding(HIiffmanTrcc&HT,HufTmaneOdC&HC.int*w.i11tn):void该操作用于创建赫夫曼树和孀夫曼树褊码。6)类TopoSortTopOIOgiCa1.SOn(A1.GRAPHG):VOid该操作用于拓扑排序。7)类Sor1.ShcIISorKinta(.intn):void该操作用于希尔排序。QuickSrt(inta11,int1.cft,intright):void该操作用于快速排序。8)类bitreeCrt-Trcc(bt:bitree):void该操作用于创建二叉树。由于每一个算法的演示都要这些操作，因此把它抽象出一个类出来。类名为DCmonStration。9)类Demonstration在确定类Demonstration的屈性和方法时，应考虑如下需求：可以显示C语言编写的核心代码在显示时,应提供C语言编写的核心代码，因此，提供这个功能的操作定义应该如下：ShoWeode(Str:string):void可以显示变动态画面在显示时，应提供动态画面，因此，提供这个功能的操作定义应该如卜.：ShowDemon():void可以显示变量在显示时，应提供变量，因此，提供这个功能的操作定义应该如卜丁ShowB1.(str:string):void可以显示算法设计思想在显示时，应提供算法设计思想，因此,提供这个功能的操作定义应该如下：ShowThink(str:string):void可以返回上一级菜单根据这个需求，定义如下操作：Retuni():void可以重新设置数据根据这个需求，定义如下操作：SCIDa1.a(Str:string):void可以恢纪到演示的开始根据这个需求，定义如下操作：RcStart():void可以暂停正在执行的系统可以将暂仰了的系统继续执行可以跟踪代码可以跟踪变量上述4个需求涉及到C#中线程部分，在定义系统类的时候就不多说了。因为在实现部分(第4章)会详细说明。3. 2.2定义用户界面类用户与系统需要交互，一个用户友好的系统通常采用直观的图形化界面，因此需要定义系统的用户界面类。通过对系统的不断分析和细化，可识别出如下界面类以及类的属性和方法。4)“演示二叉树线索化"的时序图，如图3,9所示:图3.9"演示二叉树线索化”的时序图本章小结本章节主要是进一步对系统的功能性需求分析，将用户的需求逐步转化为代码，从设汁者的角度来设计系统，画出了系统中的静态结构模型和动态行为模型.静态结构模型主要实现了定义系统对象类、定义用户界面类和建立类图。动态行为模型采用时序图来实现.，具体的线程设计如Et2':pub1.icc1.ass/X1.gorithm1.1.iread/JfJf''1.定义线ft.A1.gorithmThread.类成员变域声明处pub1.icAIgorithniThrcadOW构造函数体J类A1.gori1.hmThrCad的构造函数pub1.icvoidRUnOW定义线程体，以实现门定义线程类AIgOri1.hmThread的功能ir11i;Stringsir;fbr(i=0;i<=10;i+)Istr="Stenumber"+i.ToString()+"executed"Thrcad.S1.cep(500);/'1.前线程休W/泞)50OmSI)主程序中建立和启动线程：pub1.icC1.aSSIiiainForm(pub1.icde1.egatevoidDe1.egateSteHints);pub1.icvoidstartA1.gorithmThrcad()(m_a1.go1.i1.hir)Thrcad=ncwThrcad(newThrradStnrt(this.TrcadFunction)创建线程实例m_a1.gotithmThread.Start().,;；动线程，即调用ThreadFunC1.ion线程函数)privatevoidI1.neadFunctionO化值的显示。图-1.1动态"法演示模板4. 3算法演示的多线程设计对一个具体的算法演示子模块，须满足执行、暂停、速度可调、任意时刻更位并能重新执行等第杂切换控制功能.设计A1.gOriIhmThread线程负贡执行链表创建算法，而在主线程（主窗口）中需要同步显示被执行到的源代码行和该行代码中涉及到变址的当前值的获取和显示，这涉及到多线程间的同步和交互的问题。用ManuaIResetEvent类来解决线程的同步和交互控制.具体使用Invoke。、ManiwIResctEvcntxWaiIOnC0、Suspend。、S1.ccp（）,RCSUmC（）等同步、交互技巧可以实现专业的多线程程序,线程之间既解决了同步问题，乂使线程之间的交互十分迅速.下面以创建链表算法的动态演示（见图41）为实例说明它的实现方法其他算法的实现与此相似。有2个线程：主线程算法演示窗体所在的主线程mainFOrm和用户自定义线程AIgorithmThrcad,主线程TnainFOrm主要负责显示算法演示窗体、启动执行自定义线程总结与体会通过这次毕业设计，我对,'春去到死丝方尽.蜡炬成灰泪始干”乂有了更深的认识，好像每次在回里过去的时候，总要感叹一番光阴的流逝.这次的毕业设计是我第一次独立从事这种有相当难度的项目，经历了不少艰辛，但收获同样巨大。和整个项目开发过程同时进行的是我在方安科技从事维修与技术支持的工作，在这个工作学习完成论文的过程中我懂得了许多东西，也培养了独立工作与学习合理安排相厅.调节的能力，树立了对自C1.工作能力的信心，相信会对今后的学习工作生活有巨大而重要的影响.经过几个月的奋战，我的毕业设计终于完成了。通过这次做毕业设计，发现毕业设计不仅是对前面所学知识的种检验，而旦也是对自己能力的种提高：这也让我明白了自己原来知识还比较欠缺,自己要学习的东西还太多：明白了学习是一个长期积盛的过程。在以后的工作、生活中都应该不断的学习，努力提高自匕知识和综合素质。在这次毕业设计中也使我们的同学关系更进步了，同学之间互相帮助，有什么不懂的大家在一起商量，听听不同的看法对我们更好的理解知识，所以在这里非常感谢帮助我的同学。在设计过程中,我通过查阅大量有关资料，与同学交流经验和自学，并向老师请教等方式，使自己学到了不少知识，也经历了不少艰辛，但收获同样巨大。在整个设计中我怪得了许多东西，也培养了我独立工作的能力,树立了对自己工作能力的信心，相信会对今后的学习工作生活有非常重要的影响。而且大大提高J'动手的能力，使我充分体会到了在创造过程中探索的艰难和成功时的喜悦。虽然这个设计做的也不太好，但是在设计过程中所学到的东西是这次毕业设计的最大收获和财富，使我终身受益。参考文献1王吴亮Visua1.C#程序设计教程M.北京：清华大学出版社，2003.2ChriStianNaee1.Bi1.1.Evjen.JayG1.ynn.等.P高级编程MJ.李敏波译.第4版.北京：清华大学出版社,2006.3严蔚械.吴仲民.数据结构M.北京：清华大学出版1GeriSChneiderJaSOnP.Winters.用例分析技术MJ.姚淑珍等译.北京：机械工业出版社，2002.5郑人杰，殷人昆,陶永缶.实用软件工程M北京：清华大学出版6Stan1.eyB.1.ippoiiin.C#PrimerM.北京：中国电力出版,20037刘怀亮，陈荣国,口国华.软件组建技术M.北京：冶金工业出版，20078AddisonBcs1.ey.UM1.Disti1.1.edM.9王宏,曲家庆,黄斌陈琪.基于JRVA的数据结构算法演示系统U1.南吕航空工业学院学报.200610AddisonWes1.ey.M1.ReferenceManua1.'M.11李根强.数据结构（CH版）D0.北京：中国水利水电出版，200512唐策善编著.数据结构-用C诺音描述M.北京：高等教育出版社，199513EHorowitz,SSahni.Fundamenta1.sofDataStructuresM.PitmenPub1.ishing1.imited,1976MJ高期.用JaYa多t程实现数据结构修法动态演示U.北京联合大学学报，2002（2）15计晓云，赵研，狄小蠡,JaVa数据结构和算法M.北京：中国电力出版社。200316RiChardWiener著.罗英伟等译.JaVa数据结构与面向对象编程基础M,北京：人民邮电出版社,200317Wo1.fgangChristian.JavaPrOgra三mingandInteracttechno1.ogiesforundergraduateeducationJ.CoeputerPhysicsCo11unications.200018 PatriCkSmaeehia若施凡.李永伦,谦腕华,徐宇等译.8和.NET2.0实战:平台、谱吉与框架M.北京：人民加电出版社,2008119JC#多线程编程实例实战.ht1.p:/u"w.pc>n1.iuc.Ct1.1.Hc>pceduCIIPo1.der/jc10305168480.h1.u1.20多线程同步.http"expert.CS21再谈WindOWSSf体多战程.microsoft.ComzChinasdnIibrar,dn1.ormsh1.m1.*iufurst1.8162002.asp22浅析.Net下的多线程编程http:211.147.5.I56:700"pub/artic1.e/c1.1.36a26927p1.htm1.1.23jErichGairtna.RichardHe1.nuRa1.phJohnson.JohnVIiSSideS著.李英军，马晓星，察敢，刘建中等译.设计模式：可复用面向对象软件的基础MJ.机械工业出版社,200124JimBeveridge&RobertWiener著.俟捷等译.Iin32多线程程序设计及,华中科技大学出版社，2002附录一Comparedtomu1.ti-threadedoperatingsystem,meansisthatitcanrunaprogramwiththeabi1.ityofdifferentparts;eachpartoftheimp1.ementationwasasathread.Therefore,inthepreparationofapp1.ications.WChaveVCrygooddesigninordertoavoidtheimp1.ementationofthedifferentthreadsofmutua1.interference.Whichwi1.1.he1.pustodesignrobustprocedures,weCanmakeatanytimewhennecessarytoaddthethread.Threadcanbedescribedasamicro-proccss;ithasastartingpointfortheimp1.ementationoftheorderofseriesandadestination.Itisresponsib1.eforthemaintenanceofitsownstack,thestackforexceptionhand1.ing,priorityschedu1.ingandanumberofotherthreadingsystemsrc-inntationoftheinformationneeded.Fromthisconcept,itseemsthereisnothreadwiththeProCexSofdistinction,infact,threadandprocessiscertain1.ydiffcrvni:theprocessofacomp1.eteindependencetohavetheirownmemoryspaceanddata,butthesamethreadwithinaprocessissharedmemoryspaceanddata.Correspondstoaprocessforsomeprocedures,itisbythesamePrOCedUreinwhichanindependentthreadsrunningatthesametimethecomposition.Threadissometinwsrcfccdtoaspara1.1.e1.programrnningon1.ightweightprocesses,threadsare1.ightweightprocessesca1.1.edbecauseitisdependentontheOpCrationandprocessthecontextoftheenvironment,andtheprocessofusingresources.Inaprocess,thethreadsarcpreemptiveschedu1.ingornon-preemptivemode1.Inseizingthenxie1.,theoperatingsystemresponsib1.eforthea1.1.ocationofCPUtimeforeachprocess,oncethecurrentprocessusedtonishthedistributionofCPUtime,thenextoperatingsystemwi1.1.determinetheCPUtimeisoccupiedbyasing1.ethread.I1.iustheoperatingsystemwi1.1.periodica1.1.yinterruptthecurrcn1.threadis11nning.thea1.1.ocationwi1.1.becuptothenextinthequeuewaitingforathread.T1.ierefore,athreadcannotbeanyexc1.usiveCPU.OccupiedbyeachthreadCPUtimedependsontheprocessandtheoperatingsystem.ProCeSSassignedtoeachthreadashortperiodof1.imethatwefee1.a1.1.thethreadsarcexecutedatthesametime.Infact,thesystemtimeforeachprocess,2ms.andthenschedu1.ingotherthreads.Itthesametime,hemaintaineda1.1.thethreadsandcircu1.ation,thedistributionofsma1.1.amountofCPUtimetothethread.Threadswitchingandschedu1.ingissofastthatthefee1.ingisthata1.1.thethreadsareexecutedsimu1.taneous1.y.Whatdocsschedu1.ingmean?Schedu1.ingprocessorstoragemeanstobeimp1.ementedbytheendoftheprocessofCPUtimeforthestateandafuturetime1.oadingthestateoftheprocesstoresumeitsoperation.Inthisway,howevertherearedeficiencies,onethreadatanygiven1.imeinterruptionoftheimp1.ementationofathread.Supposeathreadisad<.u11wntdoeswriteoperation,andanotherthreadinterruptsitsoperation,a1.sotheSa1.nedocumentsdowriteo>eration.Windows95NT,UNIXisusedinsuchawaythreadschedu1.ing.Innon-prccnptivcschedu1.ingmode1.CaChthreadmayneedtooccupymuchtimeCPUtimeCPU.Schedu1.inginthisway,itmaybeavery1.ongexecutiontimemakesa1.1.theotherthreadsneedtothreadCPU"starvingtodeath,"Intheprocessorisid1.e,thatis,whentheprocessdocsnotuseCPU.thesystemcana1.1.owtheprocessoftemporari1.yusingotherCPU.CPUoccupationCPUthreadhasthepowertocontro1.there1.easeofon1.yitsowninitiative,CPU;otherthreadscanusetheCPU.SomeI/OandWindows3.xistheuseofthisschedu1.ingstrategy.Insomeoperatingsysietnsinside,whichwi1.1.usetwoschedu1.ingstrategy.Non-preemptiveschedu1.ingstrategyofrunninginthethreadprioritywhenusedingenera1.,andforhigh-priorityschedu1.ingofthreadsistheuseofpreemptiveSChedUIingstrategy.Ifyouarcunsureaboutthekindofsystemisthatschedu1.ingstrategy,assumingthattheschedu1.ingstrategycannotbeseizedisre1.ative1.ysafetouse.App1.icationinthedesign,webe1.ievethatthosewhooccupyare1.ative1.y1.argenumberofCPUtimeforacertainintenra1.threadwi1.1.re1.easethecontro1.oftheCPU.thistimethesystemwi1.1.checkthequeueofthosewaitinginsidethethreadcurrent1.yrunningwiththesamepriority1.eve1.orhigherprioritythreads,andthreadtousetheseCPU.Ifyoufindsuchasystemofthread,immediate1.ysuspendthecurrent1.yexecutingthreadandactivatethethreadsatisfycertainconditions.IfyoudonotfindtheSa1.neorhigher-prioritythread,thecurrentthreadhasa1.socontinuedtooccupyCPU.Whenthethreadis11nningCPUwou1.d1.iketore1.easecontro1.toa1.owprioritythread,thecuentthreadintos1.eepstatetoa1.1.ow1.ow-prioritythreadsho1.dtheCPU.Inamu1.ti-processorsystem,theoperatingsystemwi1.1.theseindependentthreadsa1.1.ocatedtothedifferentprocessorimp1.ementation,thiswi1.1.great1.yspeeduptheprocessofrunning.Theimp1.ementationoftheefficiencyofthethreadwi1.1.begreat1.yimproved,becausethethreadsoftime-sharingasing1.eprocessorintoadistributedInuIti-PrOCCSSOrimp1.ementation.Thisnw1.ii-processorinthethree-dimensiona1.mode1.ingandgraphicsprocessingisveryusefu1.Doyouneedtomu1.ti-threaded?Wcsentaprintorderrequestingtheprintertoprinttasks,assumingthatthistimeinresponsetothecomputerandtheprinterstoppedworkinga1.so,wou1.ditmeanthatwedothingstostopwaitingforthiss1.owontheprinter?Fortunate1.y,thissituationdocsnotoccur,weworkintheprintercana1.so1.istentomusicordrawing.BecauseWeuseaseparatethreadsoperformthesetasks.Mayyouhavemu1.tip1.eusers'Simu1.1.aneousaccesstoadatabaseorwebserverwassurprisedathowtheywork?Thisisbecauseforeachconnectedtoadatabaseorwebserverusersetupanindependentthreadtomaintainthestatusoftheuser.Ifaprogramismimingacertaindegreeoforder,this1.imeinthiswayprob1.emmayarise,andeven1.eadtotheco1.1.apseoftheentireprocess.Iftheprogramcanbedividedintodifcrentindependenttasks,theuseofmu1.ti-threaded,evenifacertainpartofthetaskfai1.ed,ontheotherwou1.dnotbeaffected,wi1.1.not1.eadtotheco1.1.apseoftheentireprocess.Thereisnodoubtthattheproceduresforhepreparationofmu1.ti-threadedtoo1.makesyouas1.avetodrivetheprocessofnon-mu1.ti-thrcadcd.mu1.ti-threadedbutmaya1.sobecomeaburdenorcostneednotbesma1.1.Iftheimproperuseofitwi1.1.bringmoreofthedisadvantages.Ifaprogramhasa1.otofthreads,thenthethreadisboundtootherprogramscanon1.ytakeup1.essCPUtime;anda1.otofCPUtimeisusedforthreadschedu1.ing;OpCrUIingsystema1.sorequiressufficientmemoryspacetomaintaineachthreadcontextinformation:therefore,a1.argenumberofthreadswi1.1.reducetheefficiencyofsystemoperation.T1.ierefore,iftheuseofnw1.ti-thrcadcd.thenthemu1.ti-threadedprogrammustbedesignedwe1.1.,otherwisethebenefitswi1.1.befar1.essthanthedisadvantages.Theuseofmu1.ti-threadedsoWemustbecarc1.todea1.withthesethreadsofthecreation,schedu1.ingandworkre1.ease.Therearcmanywaystodesignmu1.ti-threadedapp1.ications.Asshowninthebackoftheartic1.e,Iwi1.1.givedetai1.edexamp1.esofprogramming,throughtheseexamp1.es;youwi1.1.beab1.etobe1.terunderstandthemu1.ti-threaded.Threadscanhavedifferentpriorities,forexamp1.es,inourapp1.icationsthere,ordoa1.otofgraphicsrenderingOPerationSatthesametimeioacceptuserinput,iisc1.earheuser'sinputneedstobethefirsttimetorespondto,andRenderingoryouneeda1.otofcomputingtime,thesuspensionisnottheprob1.em,souserswi1.1.needtoenterthethreadofhigh-c1.ass1.eisure,andgraphicsrendering,or1.owpriorityoperationcanbe.Independentofeachot