《数据结构课程设计总结报告-猴子选王问题和二叉树求解》由会员分享，可在线阅读，更多相关《数据结构课程设计总结报告-猴子选王问题和二叉树求解（26页珍藏版）》请在金锄头文库上搜索。
1、请输入学校名称毕业论文模板数据结构课程设计实验报告题 目 猴子选王问题和二叉树求解 学 院 数理与信息工程学院 专 业 计算机科学与技术 班 级 计科 132 学 号 学生姓名 指导教师 编写日期 2015.6.25 目录一、问题描述 .21.1 问题描述 .21.1.1 猴子选王问题 .21.1.2 二叉树问题 .31.2 基本要求 .31.2.1 猴子选王问题 .31.2.2 二叉树问题 .3二、问题分析 .32.1 猴子选王问题的分析 .32.1.1 需求分析 .32.1.2 过程分析 .42.2 二叉树求解问题 .52.2.1 需求分析 .52.2.2 过程分析 .5三、 数据结构描述
2、 .63.1 猴子选王问题 .63.2 二叉树求解问题 .7四、 算法设计 .74.1 猴子选王问题 .74.1.1 单循环链表解决猴子选王问题 .74.1.2 顺序结构（数组）解决解决猴子选王问题 .104.2 二叉树问题的求解 .11五、 详细程序清单 .125.1 猴子选王问题 .125.1.1 单循环链表解决猴子选王问题 .125.1.2 顺序结构（数组）解决解决猴子选王问题 .155.2 二叉树问题的求解 .18六、 程序运行结果 .206.1 猴子选王问题 .206.1.1 单循环链表解决猴子选王问题 .206.1.2 顺序结构（数组）解决解决猴子选王问题 .216.2 二叉树问题
3、的求解 .22七、 分析与体会 .23 一、问题描述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, m,n 为整数，nn输出形式:提示输入 m 只猴子,数到的数为 n,输出为大王
4、的猴子为几号,建立一个函数来实现此功能.步骤:输入 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 需求分析要求：输入：某二叉树的中序和后序序列。输出：求出其先序序列。步骤：输入后序和中序序列后，判断是否存在树，存在则输出它的先序序列。开始输入中序、后序序列求出这棵二叉树先序遍历结束输出先序序列二叉树存在是否2.2.2 过程分析
5、假设：中序为：DBEAFCG后序为：DEBFGCA则求出该树：则它的先序为：ABDECFG3、数据结构描述3.1 猴子选王问题typedef struct Lnodeint data;struct Lnode *next;linklist; /单循环链表解决猴子选王问题3.2 二叉树求解问题struct TreeNodestruct TreeNode* left;struct TreeNode* right;char elem; /树的二叉链表存储表示4、算法设计4.1 猴子选王问题4.1.1 单循环链表解决猴子选王问题算法：int monkeyking(int m,int n)int i,t
6、otal;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 指向要删除的节点while(q-next != p)q = q-next; / q 指向 p 的节点的前驱q
7、-next = p-next ;/删除 p 节点s = p;p = p-next;free(s);total-;printf(the monkey king is:%dn,p-data);free(p);return 0;4.1.2 顺序结构（数组）解决解决猴子选王问题算法：int findMonkeyKing(int m,int n)int a100;int i=1;int count=1;/记录报数的次数int total =m;for(;ielem = *(aftorder + length - 1);printf(%c,node-elem);int rootIndex = 0;for
8、(; rootIndex left = BinaryTree(inorder, aftorder, rootIndex);node-right = BinaryTree(inorder + rootIndex + 1, aftorder + rootIndex, length - (rootIndex + 1);return node;5、详细程序清单5.1 猴子选王问题5.1.1 单循环链表解决猴子选王问题#include#includetypedef struct Lnodeint data;struct Lnode *next;linklist;int monkeyking(int m,int n)int i,total;linklist *head,*p,*s,*q;head =(linklist *)malloc(size
