《数据结构课程设计总结报告猴子选王问题和二叉树求解》由会员分享，可在线阅读，更多相关《数据结构课程设计总结报告猴子选王问题和二叉树求解（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三、 数据结构描述63.1猴子选王问题63.2 二叉树求解问题7四、 算法设计74.1猴子选王
2、问题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二叉树问题的求解22七、 分析与体会23 一、问题描述1.1问题描述 1.1.1 猴子选王问题一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，
3、从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 1.1.2二叉树问题已知二叉树T中结点的中序和后序遍历序列，编写算法实现构造满足上述条件的二叉树。 1.2基本要求 1.2.1猴子选王问题(1)利用单循环链表作为存储结构模拟此过程；(2)输入数据：输入m,n, m,n 为整数，nn输出形式:提示输入m只猴子,数到的数为n,输出为大王的猴子为几号,建立一个函数来实现此功能.步骤:输入m、n后，进行1n的报数，每数到n，则删除该猴子，直至只剩一只猴子，输出它的编号为猴子王。2.1.2过程分析假设m=5，n=3则过程为：第一轮：1-2-3 淘
4、汰3第二轮：4-5-1 淘汰1第三轮：2-4-5 淘汰5第四轮：2-4-2 淘汰2由此得出:4为猴子王！2.2二叉树求解问题2.2.1需求分析要求：输入：某二叉树的中序和后序序列。输出：求出其先序序列。 开始 输入中序、后序序列 求出这棵二叉树 先序遍历 结束 输出先序序列 二叉树存在是否步骤：输入后序和中序序列后，判断是否存在树，存在则输出它的先序序列。2.2.2过程分析 假设： 中序为：DBEAFCG 后序为：DEBFGCA 则求出该树： 则它的先序为：ABDECFG三、 数据结构描述3.1猴子选王问题 typedef struct Lnodeint data;struct Lnode *
5、next;linklist; /单循环链表解决猴子选王问题3.2 二叉树求解问题 struct TreeNodestruct TreeNode* 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
6、 (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-next = p-next ;/删除p节点s = p;p = p-next;free(s);total-;printf(the monkey king is:%dn,p-data);free(p);return 0
7、;4.1.2顺序结构（数组）解决解决猴子选王问题算法： int findMonkeyKing(int m,int n)int a100;int i=1;int count=1;/记录报数的次数int total =m; for(;i=m;i+) /将猴子按从1到m编号 ai-1=i; while(m!=1)if(count elem = *(aftorder + length - 1);printf(%c,node-elem);int rootIndex = 0;for (; rootIndex left = BinaryTree(inorder, aftorder, rootIndex);n
8、ode-right = BinaryTree(inorder + rootIndex + 1, aftorder + rootIndex, length - (rootIndex + 1);return node;五、 详细程序清单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 *)mal
9、loc(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指向要删除的节点/printf(“【%d】”,p-data);while(q-next != p) q = q-next; / q指向p的节点的前驱q-next = p-next ;/删除p节点s = p;p = p-next;free(s);total-;printf(the monkey king is:%dn,p-data);free(p);return 0;void main()int m,n;printf(*WELCOME TO OUR DESIGN*n); printf(* MONKEY *n);printf( - n);printf( / n);printf( C| |D n);printf( - / n);printf( _/ n);printf(*
