《数据结构课程设计总结报告猴子选王问题和二叉树求解.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计总结报告猴子选王问题和二叉树求解.doc（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
10、= 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);pr
11、intf(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
12、 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
13、*) 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, cha
14、r* 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
15、(mid, post, length);printf(n);system(pause);return 0;程序运行结果六、程序运行结果6.1猴子选王问题6.1.1单循环链表解决猴子选王问题6.1.2顺序结构（数组）解决解决猴子选王问题6.2二叉树问题的求解七、分析与体会短短一周的时间过去了，而我们的课程设计也接近尾声。 这期间，有对自己学过的知识的一个回顾，也有新的知识的补充。当有自己不懂时就翻阅资料，寻求解答；当有疑问的时候，有成员之间的讨论，老师的指导。初拿到该题目时，我们小组感觉无从下手，不知道该用什么样的数据类型，用什么样的储存结构，怎么实现题目中要求的功能。后来，通过从图书馆借的参考
16、书和网上查到的资料，再经过小组成员的分析，思绪渐渐明朗起来，猴子选王问题我们采用单循环链表还有数组方法来实现;二叉树选择二叉树链表来实现。就根据这样的思路编程，我们初步将程序编译调试，过程中有很多问题但是我们组员在不对的调试中，发现问题，解决问题，终于把整个问题都解决了，把整个程序都编出来了。虽然，我们的课程设计已经完成，但是，对数据结构的学习似乎才是开始，以后要学习的还很多很多，前面要走的路还很远很远。而我们也要整装待发，在摸索中前进，在前进中不断摸索，让自己的路走得更远更长！八、参考资料1朱蓉，数据结构实验指导书2严蔚敏，吴伟民，数据结构（C语言版）.北京:清华大学出版社，19973严蔚敏，吴伟民，数据结构题集（C语言版）.北京:清华大学出版社，1997
