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

PAGE PAGE 14 数理与信息工程学院 《数据结构》课程设计 ———————猴子选王问题求解和二叉树的建立 专 业 计算机科学与技术 班 级 指导教师 编写日期 2012 目 录 一、 课程设计的目的………………………………………………3 二、 课程设计的要求………………………………………………3 三、 相关知识………………………………………………………3 四、 问题的分析……………………………………………………3 五、 数据结构的描述………………………………………………4 六、 算法的设计……………………………………………………4 七、 代码实现………………………………………………………6 八、 程序运行成功展示……………………………………………11 九、 心得体会………………………………………………………14 十、 参考资料………………………………………………………14 一、课程设计的目的 课程设计是学生对课程所学知识的综合运用，它与课堂听讲、上机实验、课外练习、自学研究相辅相成，构成一个完整的课程教学体系。《数据结构》是一门实践性强的课程，其中对算法设计和程序编写的掌握尤为重要。学生虽然可以通过与课堂教学同步的上机实验完成相关内容的练习，但却往往局限于一些功能简单、彼此之间关系独立的算法和程序。课程设计是一种综合训练，致力于培养学生全面、灵活的算法设计思想和较高的编程能力，为今后从事计算机开发与应用打下基础。新世纪需要具有丰富科学知识、独立解决实际问题、有创造能力的新型人才，这也是该课程设计的最终目的。 二、课程设计的要求 1、猴子选王问题描述 一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 2、二叉树的建立描述 已知二叉树T中结点的前序和中序遍历序列，编写算法实现构造满足上述条件的二叉树。 3、界面设计模块问题描述 设计一个菜单式界面，让用户可以选择要解决的问题，同时可以退出程序。界面要求简洁明了，大方得体，便于用户的使用，同时，对于用户的错误选择可以进行有效的处理。 三、相关知识 1、猴子选王求解 约瑟夫环（Josephus）问题是由古罗马的史学家约瑟夫（Josephus）提出的，他参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军，设法守住了裘达伯特城达47天之久，在城市沦陷之后，他和40名死硬的将士在附近的一个洞穴中避难。在那里，这些叛乱者表决说“要投降毋宁死”。于是，约瑟夫建议每个人轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签，并且，作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降了罗马。 约瑟夫环问题的具体描述是：设有编号为1，2，……，n的n(n>0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序 2、二叉树的建立 二叉树的存储结构为二叉链表 C语言 二叉树的遍历 四、问题的分析 1、猴子选王问题的分析 通过问题的文字描述可以先把问题简化为一个简单的线性顺序表，然后通过顺序查找来删除所需元素，但是因为该题的需要进行循环计数，因此需要将此线性顺序表改造成为一个循环链表，通过指针将表头和表尾连接起来，再通过指针计数将所需删除的元素导出，最后通过重复操作将元素逐一删除，得到自己最后想要得到的元素，即猴王。 2、二叉树的建立 由于要根据二叉树中结点的中序和后序遍历序列，建立的二叉树以二叉链表的存储结构进行存储，并且输出二叉树的先序遍历序列，所以我们先根据后序遍历序列的最后一个结点是根节点出发，再在中序遍历序列中找个该字符，则左右两边分别为左右子数的字符序列.以这个思想递归调用函数建立起二叉树.然而先序遍历是先遍历根节点再遍历左右字数，我们就编写相关的函数调用即可 五、数据结构描述 typedef struct Lnode{ int data; struct Lnode *next; }linklist;//单链表解决猴子选王时储存结点信息 typedef struct node{ char data; struct node * lch,*rch; }BTNode,*BTree;//树的二叉链表储存表示 六、算法的设计 1、程序功能模块图 猴子选王问题 猴子选王问题 二叉树的建立 结束 用循环链表解决