猴子选王问题和二叉树求解论文

《数据结构》课程设计实验报告题目猴子选王问题和二叉树求解学院数理与信息工程学院专业计算机科学与技术[请输入学校名称]毕业论文模板目录TOC\o"1-3"\h\u一、问题描述 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为整数，n<m；(3)输出形式：中文提示按照m个猴子，数n个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能。【选做内容】(1)添加在顺序结构上实现的部分；(2)界面设计的优化。1.2.2二叉树问题（1）假设二叉树T的结点值是字符。（2）建立的二叉树以二叉链表的存储结构进行存储（3）输出二叉树的先序遍历序列。二、问题分析2.1猴子选王问题的分析2.1.1需求分析要求：输入数据：输入整数m、n,m>n输出形式:提示输入m只猴子,数到的数为n,输出为大王的猴子为几号,建立一个函数来实现此功能.步骤:输入m、n后，进行1—n的报数，每数到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则求出该树：则它的先序为：ABDECFG数据结构描述3.1猴子选王问题typedefstructLnode{ intdata; structLnode*next;}linklist;//单循环链表解决猴子选王问题3.2二叉树求解问题structTreeNode{ structTreeNode*left; structTreeNode*right; charelem;};//树的二叉链表存储表示算法设计4.1猴子选王问题4.1.1单循环链表解决猴子选王问题算法：intmonkeyking(intm,intn){ inti,total; linklist*head,*p,*s,*q; head=(linklist*)malloc(sizeof(linklist)); p=head; p->data=1; p->next=p; for(i=2;i<=m;i++){ s=(linklist*)malloc(sizeof(linklist)); s->data=i; s->next=p->next; p->next=s; p=p->next; }//初始化链表 p=head; total=m;//保存总节点数 q=head; while(total!=1){ for(i=1;i<n;i++){ p=p->next;//报数过程，p指向要删除的节点 } while(q->next!=p){ q=q->next;//q指向p的节点的前驱 } q->next=p->next;//删除p节点 s=p; p=p->next; free(s); total--; } printf("themonkeykingis:%d\n",p->data); free(p); return0;}4.1.2顺序结构（数组）解决解决猴子选王问题算法：intfindMonkeyKing(intm,intn){ inta[100]; inti=1; intcount=1;//记录报数的次数 inttotal=m;for(;i<=m;i++){//将猴子按从1到m编号 a[i-1]=i;}while(m!=1){ if(count<n){ if(a[i]!=0){ count++; i++;i=i%total; } else i++;i=i%total; } if(count=n){ a[i]=0; m--; i++;i=i%total; count=1; } } returni;}4.2二叉树问题的求解算法：TreeNode*BinaryTree(char*inorder,char*aftorder,intlength){ if(length==0) { returnNULL; } TreeNode*node=newTreeNode; node->elem=*(aftorder+length-1); printf("%c",node->elem); introotIndex=0; for(;rootIndex<length;rootIndex++) { if(inorder[rootIndex]==*(aftorder+length-1)) break; } node->left=BinaryTree(inorder,aftorder,rootIndex); node->right=BinaryTree(inorder+rootIndex+1,aftorder+rootIndex,length-(rootIndex+1)); returnnode;}详细程序清单5.1猴子选王问题5.1.1单循环链表解决猴子选王问题#include<stdio.h>#include<malloc.h>typedefstructLnode{ intdata; structLnode*next;}linklist;intmonkeyking(intm,intn){ inti,total; linklist*head,*p,*s,*q; head=(linklist*)malloc(sizeof(linklist)); p=head; p->data=1; p->next=p; for(i=2;i<=m;i++){ s=(linklist*)malloc(sizeof(linklist)); s->data=i; s->next=p->next; p->next=s; p=p->next; }//初始化链表 p=head; total=m;//保存总节点数 q=head; while(total!=1){ for(i=1;i<n;i++){ p=p->next;//报数过程，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("themonkeykingis:%d\n",p->data); free(p); return0;}voidmain(){ intm,n; printf("********WELCOMETOOURDESIGN********\n");printf("*************MONKEY*************\n"); printf("\n"); printf("/^^\\\n"); printf("C|@@|D\n"); printf("\\--/\n"); printf("\\_____/\n"); printf("**************************************\n"); printf("IKING\n");printf("WANTTHE\n"); printf("TOBE\n"); printf("**************************************\n"); printf("pleaseinputthenumberofmandn(m>n):"); scanf_s("%d%d",&m,&n); monkeyking(m,n); system("pause");}5.1.2顺序结构（数组）解决解决猴子选王问题#include<stdio.h>intfindMonkeyKing(intm,intn){ inta[100]; inti=1; intcount=1;//记录报数的次数 inttotal=m;for(;i<=m;i++){//将猴子按从1到m编号 a[i-1]=i;}while(m!=1){ if(count<n){ if(a[i]!=0){ count++; i++;i=i%total; } else i++;i=i%total; } if(count=n){ a[i]=0; m--; i++;i=i%total; count=1; } } returni;}voidmain(){intm,n; printf("********WELCOMETOOURDESIGN********\n");printf("*************MONKEY*************\n"); printf("\n"); printf("/^^\\\n"); printf("C|@@|D\n"); printf("\\--/\n"); printf("\\_____/\n"); printf("**************************************\n"); printf("IKING\n");printf("WANTTHE\n"); printf("TOBE\n"); printf("**************************************\n");printf("pleaseinputthenumberofmandn(m>n):"); scanf_s("%d%d",&m,&n);printf("themonkeykingis:%d\n",findMonkeyKing(m,n)); system("pause");} 5.2二叉树问题的求解#include<stdio.h>#include<string>#include<malloc.h>typedefstructTreeNode{ structTreeNode*left; structTreeNode*right; charelem;}TreeNode;TreeNode*BinaryTree(char*inorder,char*aftorder,intlength){ if(length==0) { returnNULL; } TreeNode*node; node=(TreeNode*)malloc(sizeof(TreeNode)); node->elem=*(aftorder+length-1); printf("%c",node->elem); introotIndex=0; for(;rootIndex<length;rootIndex++) { if(inorder[rootIndex]==*(aftorder+length-1)) break; } node->left=BinaryTree(inorder,aftorder,rootIndex); node->right=BinaryTree(inorder+rootIndex+1,aftorder+rootIndex,length-(rootIndex+1)); returnnode;}intmain(intargc,char**argv){ char*post="DEBFGCA"; char*mid="DBEAFCG"; intlength=strlen(mid); printf("********WELCOMETOOURDESIGN********\n"); printf("*************BITREE*************\n"); printf("A\n"); printf("/\\\n"); printf("