猴子选王问题求解和二叉树成立课程设计报告

1、数理与信息工程学院数据结构课程设计猴子选王问题求解和二叉树的成立专业运算机科学与技术班级指导教师编写日期2021年6月24日课程设计的目的二、课程设计的要求3三、相关知识3四、问题的分析3五、数据结构的描述4六、算法的设计4七、代码实现6八、程序运行成功展现11九、心得体会14十、参考资料14一、课程设计的目的课程设计是学生对课程所学知识的综合运用，它与课堂听讲、上机实验、课外练习、自学研究相辅相成，组成一个完整的课程教学体系。数据结构是一门实践性强的课程，其中对算法设计和程序编写的把握尤其重要。学生尽管能够通过与课堂教学同步的上机实验完成相关内容的练习，但却往往局限于一些功能简单、彼此之间关

2、系独立的算法和程序。课程设计是一种综合训练，致力于培育学生全面、灵活的算法设计思想和较高的编程能力，为尔后从事运算机开发与应用打下基础。新世纪需要具有丰硕科学知识、独立解决实际问题、有制造能力的新型人材，这也是该课程设计的最终目的。二、课程设计的要求一、猴子选王问题描述一堆猴子都有编号，编号是1,2,3.m,这群猴子(m个)依照1-m的顺序围坐一圈,从第1开始数，每数到第n个，该猴子就要离开此圈，如此依次下来，直到圈中只剩下最后一只猴子，那么该猴子为大王。二、二叉树的成立描述己知二叉树T中结点的前序和中序遍历序列，编写算法实现构造知足上述条件的二叉树。3、界而设计模块问题描述设计一个菜单式界面

3、，让用户能够选择要解决的问题，同时能够退出程序。界而要求简练明了，大方得体，便于用户的利用，同时，关于用户的错误选择能够进行有效的处置。三、相关知识一、猴子选王求解约瑟夫环(Josephus)问题是由古罗马的史学家约瑟夫(Josephus)提出的，他参加并记录了公元66-70年犹太人招架罗马的起义。约瑟夫作为一个将军，设法守住了裘达伯特城达47天之久，在城市.沦陷以后，他和40名死硬的将士在周围的一个洞窟中避难。在那里,这些兵变者表决说“要投降毋宁死工于是，约瑟夫建议每一个人连番杀死他隔壁的人，而那个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签，而且，作为洞窟中的两个幸存者之一，他说服了他

4、原先的捐躯品一路投降了罗马。约瑟夫环问题的具体描述是：设有编号为1,2,，n的n(n0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起从头报数，报到m时停止报数，报m的出圈如此下去，直到所有人全数出圈为止。当任意给定n和m后，设计算法求n个人出圈的顺序二、二叉树的成立二叉树的存储结构为二叉链表C语言二叉树的遍历四、问题的分析一、猴子选王问题的分析通过问题的文字描述能够先把问题简化为一个简单的线性顺序表,然后通过顺序查找来删除所需元素，可是因为该题的需要进行循环计数，因此需要将此线性顺序表改造成为一个循环链表，通过指针将表头和表尾连接起来，再通过指针计数将

5、所需删除的元素导出，最后通过重复操作将元素一一删除，取得自己最后想要取得的元素，即猴王。二、二叉树的成立由于要依照二叉树中结点的中序和后序遍历序列，成立的二叉树以二叉链表的存储结构进行存储，而且输出二叉树的先序遍历序列，因此咱们先依照后序遍历序列的最后一个结点是根节点动身，再在中序遍历序列中找个该字符，那么左右两边别离为左右子数的字符序列.以那个思想递归挪用函数成立起二叉树.但是先序遍历是先遍历根少点再遍历左右字数，咱们就编写相关的函数挪用即可五、数据结构描述typedefstnictLnodeintdata;structLnode*next;Jlinklist;程序功能模块图密 C:wind

6、owssystem32cmd.exernxmWELCOMECOMETOOURSYSTEMmm%1/%1/、xm木木x* n秣x米米米松 _木木木木mx.木木n *米米 糕米米_ 糕木木木木i *,r /T*i*i*y,*T*w TT*i*米 米 % * %* *米米米。,俗4、卜。林1.The monkey King Sleet林X “X ”X。不不不 不 zT不v不zT ?T不不v ”.不v不不v不看v不。不u米 米 米 米 木 出 米J/1/%1% /*L/% 1% 1/% /% 1/% 1/1、f、，俗腕2.Binary ree*f、八，仅 （、i i，t、密 C:windowssyst

7、em32cmd.exe木木林木木x太太林木求x太木木木太太x木本初elcome the monkey king slect太木才木太太太太太才太木木米木木才米米木木木木木木木小组成员：PPT演讲:吕光跃资料搜臭:楼外程序编译:龙秋昌请输入喉子的个数n：QB C:wmdowssystem32cmd.exe米米米*米米%米米米/米米米米米米*米米米米米米WELCOMETHEMONKEYKING3LECT米米*米米米米米米%米米*k米米%米米米米米米%米米%小组成员：叩T演讲:吕光跃资料搜集:楼冰程序编语:龙段昌请输入猴子的个数n：23请输入要从第几个猥子开始报数k：1请输入出局数字m：5出局序列为

8、:510152028142141219616113L18口门917237猴子大王为第22号t、*?. exit*iZ将2.BinaryTree将%1/%11/1/%!1/%1/%1/aL/%1/%1/%1/f、iPIeasechoosethefuncticn：z四C:v.rindowssystem32cmd.exe米比米秫蛛米双糕粒米x米为米米米米x米x米糕糊ELCOMEBINARYTREE就米米*米米米x米糕林米x米九米粒米米米双米米米枕小姐成员：PPT演讲:张琪资料搜集:施芳程序编译:陈孝坚后序是:CBEMGTFJI中序是：CEDBHGJIFA输入任意字符直看先序序列:SB C:windo

9、vzssystem32cmd.exeWELCOMECOMETOOLRSYSTEM1/*L/%/%/1/尔米糕木木*米米米米米米秣 .xm米秣米松n *双 米米腕_ 米米林米x*-A*,A,4，,A.*-A*A，4*-A*-A.X*4.4*.#,A*,A*，4*-A-*A_*_A.卜4、Ca4,f、T、，於/：K：K* 米 米*米-%m、t、c、.ThemonkeyKingSiect：1/%!1/1/T/yi1/!/!/1/1/1.1/1/.1/%1/%! 1/%1%1/%1/03. ex i t 米米1/v 1/%1 %/%1/4、，外4,、（、1/1/-L/1/%1%1/1/%1/1/%1/

10、%y*1*秣2.BinaryTree米*V-L/%1/%11/1/%1/%1.1/gCpleasechoosethefcnction：o白了二叉树是一种重要的数据结构，专门好的编程思想，在学习中有很多作用.通过这次课程设计，理论知识和实践彼此结合才能实现程序,通过查阅资料丰硕了以前所遗漏的知识，同时又加倍充实了以前所遗漏的知识，了解了算法在编程中的重要性，一个好的算法能极大地优化一个程序通过这次的课程设计，我们学到了怎么样从一个实际问题动身，成立模型，找到相应的贮存结构和实现方式，实际运行，反复调试和修改，最终实现功能。在程序设计方式和上机操作等大体技术和科学作风方面受到比较系统和严格的训练，学会数据组织的方式，把现实世界中的实际问题在运算机内部表示出来并用软件解决问题，培育了良好的程序设计技术。十、参