1、 请输入学校名称请输入学校名称毕业论文模板毕业论文模板 数据结构课程设计 实验报告 题 目 猴子选王问题和二叉树求解 学 院 数理与信息工程学院 专 业 计算机科学与技术 目录目录 一、问题描述 4 1.1 问题描述.4 1.1.1 猴子选王问题 4 1.1.2 二叉树问题.4 1.2 基本要求.4 1.2.1 猴子选王问题 .4 1.2.2 二叉树问题.4 二、问题分析 5 2.1 猴子选王问题的分析 .5 2.1.1 需求分析 5 2.1.2 过程分析 6 2.2 二叉树求解问题 .6 2.2.1 需求分析 6 2.2.2 过程分析 7 三、 数据结构描述 .7 3.1 猴子选王问题 .7
2、 3.2 二叉树求解问题.8 四、 算法设计 8 4.1 猴子选王问题 .8 4.1.1 单循环链表解决猴子选王问题.8 4.1.2 顺序结构（数组）解决解决猴子选王问题 11 4.2 二叉树问题的求解 12 五、 详细程序清单 . 13 5.1 猴子选王问题 . 13 5.1.1 单循环链表解决猴子选王问题. 13 5.1.2 顺序结构（数组）解决解决猴子选王问题 16 5.2 二叉树问题的求解 19 六、 程序运行结果 . 19 6.1 猴子选王问题 . 22 6.1.1 单循环链表解决猴子选王问题. 22 6.1.2 顺序结构（数组）解决解决猴子选王问题 23 6.2 二叉树问题的求解
3、24 七、 分析与体会. 24 一、问题描述一、问题描述 1.1 问题描述问题描述 1.1.1 猴子选王问题猴子选王问题 一堆猴子都有编号，编号是 1，2，3 .m ,这群猴子（m 个）按 照 1-m 的顺序围坐一圈，从第 1 开始数，每数到第 n 个，该猴子就要 离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子 为大王。 1.1.2 二叉树问题二叉树问题 已知二叉树 T 中结点的中序和后序遍历序列，编写算法实现构造 满足上述条件的二叉树。 1.2 基本要求基本要求 1.2.1 猴子选王问题猴子选王问题 (1)利用单循环链表作为存储结构模拟此过程； (2)输入数据：输入 m,n,
4、m,n 为整数，nn 输出形式:提示输入 m只猴子,数到的数为 n,输出为大王的猴子为 几号,建立一个函数来实现此功能. 步骤:输入 m、n 后，进行 1n 的报数，每数到 n，则删除该猴 子，直至只剩一只猴子，输出它的编号为猴子王。 2.1.2 过程分析过程分析 假设 m=5，n=3 则过程为： 第一轮：1-2-3 淘汰 3 第二轮：4-5-1 淘汰 1 第三轮：2-4-5 淘汰 5 第四轮：2-4-2 淘汰 2 由此得出:4 为猴子王！ ！ ！ ！ 2.2 二叉树求解问题二叉树求解问题 2.2.1 需求分析需求分析 要求： 输入：某二叉树的中序和后序序列。 输出：求出其先序序列。 步骤：输
5、入后序和中序序列后，判断是否存在树，存在则输出它 的先序序列。 开始 输入中序、后序序列 求出这棵二叉树 先序遍历 结束 输出先序序列 二叉树存在 是 否 2.2.2 过程分析过程分析 假设： 中序为：DBEAFCG 后序为：DEBFGCA 则求出该树： 则它的先序为：ABDECFG 三、三、数据结构描述数据结构描述 3.1 猴子选王问题猴子选王问题 typedef struct Lnode int data; struct Lnode *next; linklist; /单循环链表解决猴子选王问题 3.2 二叉树求解问题二叉树求解问题 struct TreeNode struct TreeN
6、ode* left; struct TreeNode* right; char elem; ; /树的二叉链表存储表示 四、四、算法设计算法设计 4.1 猴子选王问题猴子选王问题 4.1.1 单循环链表解决猴子选王问题单循环链表解决猴子选王问题 算法： int monkeyking(int m,int n) int i,total; linklist *head,*p,*s,*q; head =(linklist *)malloc(sizeof(linklist); p = head; p-data = 1; p-next = p; for (i = 2;i data = i; s -next = p-next; p -next =s ; p = p-next; /初始化链表 p = head; total = m; /保存总节点数 q = head; while (total!=1) for(i=1;inext; /报数过程，p 指向要删除的节点 w
