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

《数据结构》课程设计实验报告题目猴子选王问题和二叉树求解学院数理与信息工程学院专业计算机科学与技术[请输入学校名称]毕业论文模板目录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("BC\n"); printf("/\\/\\\n"); printf("DEFG\n"); printf("**************************************\n"); printf("中序序列为："); printf("%s\n",mid); printf("后序序列为："); printf("%s\n",post); printf("先序序列为："); BinaryTree(mid,post,length); printf("\n"); system("pause"); return0;}程序运行结果六、程序运行结果6.1猴子选王问题6.1.1单循环链表解决猴子选王问题6.1.2顺序结构（数组）解决解决猴子选王问题6.2二叉树问题的求解七、分析与体会短短一周的时间过去了，而我们的课程设计也接近尾声。这期间，有对自己学过的知识的一个回顾，也有新的知识的补充。当有自己不懂时就翻阅资料，寻求解答；当有疑问的时候，有成员之间的讨论，老师的指导。初拿到该题目时，我们小组感觉无从下手，不知道该用什么样的数据类型，用什么样的储存结构，怎么实现题目中要求的功能。后来，通过从图书馆借的参考书和网上查到的资料，再经过小组成员的分析，思绪渐渐明朗起来，猴子选王问题我们采用单循环链表还有数组方法来实现;二叉树选择二叉树链表来实现。就根据这样的思路编程，我们初步将程序编译调试，过程中有很多问题但是我们组员在不对的调试中，发现问题，解决问题，终于把整个问题都解决了，把整个程序都编出来了。虽然，我们的课程设计已经完成，但是，对数据结构的学习似乎才是开始，以后要学习的还很多很多，前面要走的路还很远很远。而我们也要整装待发，在摸索中前进，在前进中不断摸索，让自己的路走得更远更长！八、参考资料[1]朱蓉，数据结构实验指导书[2]严蔚敏，吴伟民，数据结构（C语言版）.北京:清华大学出版社，1997[3]严蔚敏，吴伟民，数据结构题集（C语言版）.北京:清华大学出版社，1997目录第一章总论 11.1项目背景 11.1.1项目名称及承办单位 11.1.2承办单位 11.1.3项目建设地点 11.1.4可行性研究报告编制单位 11.2报告编制依据和研究范围 11.2.1报告编制依据 11.2.2研究范围 21.3承办单位概况 21.4项目提出背景及必要性 31.4.1项目提出的背景 31.4.2项目建设的必要性 41.5项目概况 51.5.1建设地点 51.5.2建设规模与产品方案 51.5.3项目投资与效益概况 51.6主要技术经济指标 6第二章市场分析及预测 82.1绿色农产品市场分析及预测 82.1.1生产现状 82.1.2市场前景分析 92.2花卉市场分析及预测 112.2.1产品市场现状 112.2.2市场需求预测 122.2.3产品目标市场分析 132.3中药材产品市场分析及预测 132.3.1产品简介 132.3.2产品分布现状分析 152.3.3市场供求状况分析 162.3.4市场需求预测 17第三章建设规模与产品方案 203.1项目的方向和目标 203.2建设规模 203.3产品方案 213.3.1优质高产粮食作物种植基地 213.3.2无公害蔬菜种植基地 213.3.3中药材种植基地 213.3.4花卉种植基地 21第四章建设场址及建设条件 224.1建设场址现状 224.1.1建设场址现状 224.1.2厂址土地权属类别及占地面积 224.2建设条件 224.2.1气象条件 224.2.2水文及工程地质条件 234.2.4交通运输条件 234.2.5水源及给排水条件 244.2.6电力供应条件 244.2.7通讯条件 244.3其他有利条件 244.3.1农产品资源丰富 244.3.2劳动力资源充沛 254.3.3区位优势明显 25第五章种植基地建设方案 265.1概述 265.1.1种植基地运营模式 265.1.2种植基地生产执行标准 265.23000亩优质高产粮食作物种植基地建设方案 285.2.1品种选择 285.2.2耕作技术 285.2.3种植基地建设内容和产量预期 335.32000亩无公害蔬菜种植基地建设方案 345.3.1概述 345.3.2无公害蔬菜质量标准 345.3.3蔬菜栽培与田间管理 355.3.4种植基地建设内容和产量预期 375.42000亩中药材种植基地建设方案 385.4.1概述 385.4.2GAP基地建设要求 385.4.3选择优良品种 395.4.4金银花栽培与田间管理 395.4.5种植基地建设内容和产量预期 435.52000亩花卉种植基地建设方案 445.5.1概述 445.5.2技术方案 455.5.3种植基地建设内容和产量预期 49第六章田间工程及配套设施建设方案 516.1概述 516.23000亩绿色粮食作物种植基地灌溉方案 516.2.1总体布局 516.2.2设计依据 526.2.3灌溉制度的确定 526.2.4渠道衬砌工程设计 536.32000亩无公害蔬菜种植基地灌溉方案 556.3.1总体布局 556.3.2设计依据 556.3.3主要设计参数 566.3.4灌水器选择与毛管布置方式 566.3.5滴灌灌溉制度拟定 576.3.6支、毛管水头差分配与毛管极限长度确定 586.3.7网统布置与轮灌组划分 596.3.8管网水力计算 606.3.9水泵扬程及选型 646.42000亩中药材种植基地灌溉方案 656.4.1设计依据 656.4.2设计参数 656.4.3喷头选型和布置间距 656.4.4灌溉制度 666.4.5取水工程规划布置 686.4.6管网水力计算 706.4.7机泵选型 726.52000亩花卉种植基地灌溉方案 726.5.1设计依据 726.5.2微灌主要设计参数 726.5.3微灌灌水器选择与毛管布置方式 736.5.4微灌灌溉制度拟定 746.5.5微灌支、毛管水头差分配与毛管极限长度确定 756.5.6微灌网统布置与轮灌组划分 766.5.7微灌管网水力计算 776.5.8水泵扬程及选型 816.6田间道路工程 866.7灌溉工程 866.7.1机井工程 866.7.2提灌站改造 876.8沟道治理工程 896.9田间配套设施 906.9.1仓储工程 906.9.2农业技术培训中心 93第七章节能、节水 967.1研究依据 967.2能耗分析 977.3节能措施 97第八章环境与生态影响分析 988.1环境影响现状分析 988.2生态环境影响分析 988.2.1建设期对生态环境的影响 988.2.2运营期对生态环境的影响 988.3生态环境保护措施 988.3.1采用的依据和标准 988.3.2建设期对环境的保护措施 998.3.3运营期对环境的保护措施 1008.4环境影响评价 100第九章企业组织与劳动定员 1019.1公司体制及组织机构 1019.2劳动定员 1019.3人员来源及培训 1029.3.1人员来源 1029.3.2人员培训 102第十章项目组织管理与实施进度计划 10310.1基本要求 10310.2项目组织 10310.3项目管理 10310.4建设周期计划 104第十一章风险分析 10511.1风险因素 10511.2风险因素分析及风险程度 10511.3防范和降低风险的对策 106第十二章投资估算和资金筹措 10812.1投资估算 10812.1.1投资估算的编制范围 10812.1.2投资估算依据 10812.1.3投资估算方法 10812.2总投资估算 10912.4资金筹措 10912.5资金使用计划 PAGEREF