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