数据结构课程设计总结报告-猴子选王问题和二叉树求解.doc

数据结构课程设计实验报告题 目 猴子选王问题和二叉树求解 学 院 数理与信息工程学院 专 业 计算机科学与技术 班 级 计科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猴子选王问题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的顺序围坐一圈，从第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 淘汰3第二轮：4-5-1 淘汰1第三轮：2-4-5 淘汰5第四轮：2-4-2 淘汰2由此得出:4为猴子王！2.2二叉树求解问题2.2.1需求分析要求：输入：某二叉树的中序和后序序列。输出：求出其先序序列。 开始 输入中序、后序序列 求出这棵二叉树 先序遍历 结束 输出先序序列 二叉树存在是否步骤：输入后序和中序序列后，判断是否存在树，存在则输出它的先序序列。2.2.2过程分析 假设： 中序为：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,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指向要删除的节点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;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);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(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(*n);printf(i kingn); printf( want then);printf( to ben);printf(*n);printf(please input the number of m and n (mn):);scanf_s(%d%d,&m,&n);monkeyking(m,n);system(pause);5.1.2顺序结构（数组）解决解决猴子选王问题#include 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 n):);scanf_s(%d%d,&m,&n); printf(the monkey king is :%dn,findmonkeyking(m,n);system(pause); 5.2二叉树问题的求解#include#include #includetypedef struct treenodestruct treenode* left;struct treenode* right;char elem;treenode;treenode* binarytree(char* inorder, char* aftorder, int length)if (length = 0)return null;treenode* node;node = (treenode*) malloc (sizeof(treenode);node-elem = *(aftorder + length - 1);printf(%c, node-elem);int rootindex = 0;for (; rootindex left = binarytree(inorder, aftorder, rootindex);node-right = binarytree(inorder + rootindex + 1, aftorder + rootindex, length - (rootindex + 1);return node;int main(int argc, char* argv)char* post = debfgca;char* mid = dbeafcg;int length = strlen(mid);printf(*welcome to our design*n);printf(* bitree *n);printf( an);printf( / n);printf( b cn);printf( / / n);printf( d e f gn);printf(*n);printf(中序序列为：);printf(%sn, mid);printf(后序序列为：);printf(%sn, post);printf(先序序列为：);binarytree(mid, post, length);printf(n);system(pause);return 0;程序运行结果六、程序运行结果6.1猴子选王问题6.1.1单循环链表解决猴子选王问题6.1.2顺序结构（数组）解决解决猴子选王问题6.2二叉树问题的求解七、分析与体会短短一周的时间过去了，而我们的课程设计也接近尾声。 这期间，有对自己学过的知识的一个回顾，也有新的知识的补充。当有自己不懂时就翻阅资料，寻求解答；当有疑问的时候，有成员之间的讨论，老师的指导。初拿到该题目时，我们小组感觉无从下手，不知道该用什么样的数据类型，用什么样的储存结构，怎么实现题目中要求的功能。后来，通过从图书馆借的参考书和网上查到的资料，再经过小组成员的分析，思绪渐渐明朗起来，猴子选王问题我们采用单循环链表还有数组方法来实现;二叉树选择二叉树链表来实现。就根据这样的思路编程，我们初步将程序编译调试，