![北工大数据结构上机实验报告3_第1页](http://file3.renrendoc.com/fileroot_temp3/2022-3/10/634a68e8-76b7-43c3-8e3a-6d26977dd22b/634a68e8-76b7-43c3-8e3a-6d26977dd22b1.gif)
![北工大数据结构上机实验报告3_第2页](http://file3.renrendoc.com/fileroot_temp3/2022-3/10/634a68e8-76b7-43c3-8e3a-6d26977dd22b/634a68e8-76b7-43c3-8e3a-6d26977dd22b2.gif)
![北工大数据结构上机实验报告3_第3页](http://file3.renrendoc.com/fileroot_temp3/2022-3/10/634a68e8-76b7-43c3-8e3a-6d26977dd22b/634a68e8-76b7-43c3-8e3a-6d26977dd22b3.gif)
![北工大数据结构上机实验报告3_第4页](http://file3.renrendoc.com/fileroot_temp3/2022-3/10/634a68e8-76b7-43c3-8e3a-6d26977dd22b/634a68e8-76b7-43c3-8e3a-6d26977dd22b4.gif)
![北工大数据结构上机实验报告3_第5页](http://file3.renrendoc.com/fileroot_temp3/2022-3/10/634a68e8-76b7-43c3-8e3a-6d26977dd22b/634a68e8-76b7-43c3-8e3a-6d26977dd22b5.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、上机题三报告 姓名: 学号: 完成日期:2015年5月5日题目:表达式可以用表达式二叉树来表示。对于简单的四则运算表达式,请实现以下功能;(1)对于任意给出的前缀表达式(不带括号)、中缀表达式(可以带括号)或后缀表达式(不带括号),能够在计算机内部构造出一棵表达式二叉树,并且以图示显示出来(字符图或图形的形式)。(2) 对于构造好的内部表达式二叉树,按照用户要求,输出相应的前缀表达式(不带括号)、中缀表达式(可以带括号)或后缀表达式(不带括号).1、 需求分析1. 输入形式、输入值的范围;输入前缀表达式(不带括号)、中缀表达式(可以带括号)或后缀表达式(不带括号)2. 输出形式;表达式二叉树,
2、前缀表达式、中缀表达式和后缀表达式。3. 程序功能;用表达式二叉树表示表达式,并转换为前缀表达式、中缀表达式或后缀表达式。4. 测试数据 正确的输入输出: 错误的输入输出: 2、 概要设计1. ADT定义class TNode/节点类开始2. 主程序流程结束输出各类表达式是是将表达式转换为二叉树表达式是否是否为中缀表达式是否为前缀表达式输入表达式是否为后缀表达式否 3. 各程序模块间的调用关系Main() 删除树打印树求前、中、后缀表达式模块求二叉树表达式模块3、 详细设计1. 实现ADT定义的数据类型class TNode/节点类 public:char oper;/数据域,为简便起见,操作
3、数用单个字符代替TNode *left;TNode *right;int s;int t;/计算树的层数使用TNode()/缺省构造函数 left=right=NULL; oper=0; TNode(char op)/赋值构造函数 left=right=NULL; oper=op;2. 算法描述表达式转化为二叉树void pre2tree(TNode *&p, string str)/前缀表达式生成二叉树 碰到操作数则把其值赋给相应的新申请的二叉树结点,地址压栈;碰到操作符则把其值赋给相应的新申请的二叉树,并从栈中弹出两个地址,分别作为其左指针和右指针,然后再把其地址压栈,最后一个地址
4、即为二叉树的根结点地址。void post2tree(TNode *&p,string str)/后缀表达式生成二叉树 /碰到操作数则把其值赋给相应的新申请的二叉树结点,若栈为空则地址压栈,/碰到操作符则把其值赋给相应的新申请的二叉树结点,取栈顶元素,/若当前元素的左孩子为空则设为其左孩子,/左孩子为满则设为其右孩子,开始那个元素地址为根结点地址,开始时用变量root保存。void in2tree(TNode *&p, string str)/中缀表达式转换成后缀表达式生成二叉树 从中缀表达式中自左至右依次读入各个字符。 如果读入操作数,直接输出到后缀表达式。 如果
5、读入的是运算符,并且运算符栈为空,则将该运算符直接进栈;如果栈不为空, 则比较该运算符和栈顶运算符的优先级。 若该运算符高于栈顶运算符的优先级,则将该运算符直接进栈; 若该运算符低于或等于栈顶运算符的优先级,则将栈中高于或等于该运算符优先级的元 素依次出栈输出到后缀表达式中,然后再将该运算符进栈。 在碰到开括号和栈为空前反复弹出栈中元素 若栈非空栈顶不是左括号且栈顶元素优先级不低于输入运算符时,/将栈顶元素弹出到后缀表达式二叉树表达式转化为表达式 void postOrder(TNode *p) /先序遍
6、历 if(p) postOrder(p->left); postOrder(p->right); cout<<p->oper; void preOrder(TNode *p) /后序遍历 if(p) cout<<p->oper; preOrder(p->left); preOrder(p->right); void inOrder(TNode *p)/中序遍历,同时输出不带冗余括号的中缀表达式 if(p)if(p->left) if(如果当前节点的左子树是运算符,且运算符优先级低于当前运算符,那么左边的表达式要先计算,需要加括号
7、) cout<<"(" inOrder(p->left); cout<<")" else/否则直接输出左子树 inOrder(p->left); cout<<p->oper;/输出当前节点 if(p->right) if(如果当前节点的右子树是运算符,且运算符优先级不高于当前运算符,那么右边的表达式要先计算,需要加括号) cout<<"(" inOrder(p->right); cout<<")" else inOrder(p
8、->right); 4、 程序测试5、 用户使用说明运行程序后,按照提示选择表达式类型(-1:前缀表达式;0:中缀表达式;1:后缀表达式)然后输入相应的表达式,回车后可以得到二叉树表达式及出前缀、中缀、后缀表达式6、 源程序#include <iostream>#include <stack>#include <queue>#include <string>#include<math.h>using namespace std;class TNode/节点类 public:char oper;/数据域,为简便起见,操作数用单个字
9、符代替TNode *left;TNode *right;int s;int t;/计算树的层数使用TNode()/缺省构造函数 left=right=NULL; oper=0; TNode(char op)/赋值构造函数 left=right=NULL; oper=op;bool isOper(char op)/判断是否为运算符char oper='(',')','+','-','*','/',''for(int i=0;i<sizeof(oper);i+) if(op=ope
10、ri) return true; return false;int getOperOrder(char op)/返回运算符op所对应的优先级/ 左括号优先级,加减号为,乘除号为,方幂为,右括号,栈底返回switch(op)case '(': return 1; case '+': case '-':return 2; case '*': case '/':return 3; case '':return 4; default: /定义在栈中的右括号和栈底字符的优先级最低 return 0; void
11、 freeTree(TNode *&p) /递归删除树 if(p->left!=NULL) freeTree(p->left); if(p->right!=NULL) freeTree(p->right); delete(p); void postOrder(TNode *p) /先序遍历 if(p) postOrder(p->left); postOrder(p->right); cout<<p->oper; void preOrder(TNode *p) /后序遍历 if(p) cout<<p->oper; p
12、reOrder(p->left); preOrder(p->right); void inOrder(TNode *p)/中序遍历,同时输出不带冗余括号的中缀表达式 if(p)if(p->left) /如果当前节点的左子树是运算符,且运算符优先级低于当前运算符,/那么左边的表达式要先计算,需要加括号if(isOper(p->left->oper)&& getOperOrder(p->left->oper)<getOperOrder(p->oper) cout<<"(" inOrder(p-&g
13、t;left); cout<<")" else/否则直接输出左子树 inOrder(p->left); cout<<p->oper;/输出当前节点 if(p->right) /如果当前节点的右子树是运算符,且运算符优先级不高于当前运算符,/那么右边的表达式要先计算,需要加括号 if(isOper(p->right->oper)&& getOperOrder(p->right->oper)<=getOperOrder(p->oper) cout<<"("
14、; inOrder(p->right); cout<<")" else inOrder(p->right); void post2tree(TNode *&p,string str)/后缀表达式生成二叉树 /(a)碰到操作数则把其值赋给相应的新申请的二叉树结点,若栈为空则地址压栈,/(b)碰到操作符则把其值赋给相应的新申请的二叉树结点,取栈顶元素,/若当前元素的左孩子为空则设为其左孩子,/左孩子为满则设为其右孩子,开始那个元素地址为根结点地址,开始时用变量root保存。stack <TNode*> nodeStack;/用于保存节
15、点指针的栈 char temp; int i=0; temp=stri+; while(temp!='0') if(temp!='0'&&!isOper(temp)/不是运算符,则进栈 p=new TNode(temp);/以temp为结点值构造二叉树结点 nodeStack.push(p); temp=stri+;/读入下一个 else /如果遇到符号,则弹栈,依次设为右节点和左节点p=new TNode(temp); if(nodeStack.size() p->right=nodeStack.top();/若非空则弹栈并设为结点的右孩
16、子 nodeStack.pop(); if(nodeStack.size() p->left=nodeStack.top();/若非空则弹栈并设为结点的左孩子 nodeStack.pop(); nodeStack.push(p); temp=stri+; void pre2tree(TNode *&p, string str)/前缀表达式生成二叉树/碰到操作数则把其值赋给相应的新申请的二叉树结点,地址压栈;/碰到操作符则把其值赋给相应的新申请的二叉树,并从栈中弹出两个地址,/分别作为其左指针和右指针,然后再把其地址压栈,最后一个地址即为二叉树的根结点地址。stack <TN
17、ode*> nodeStack; char temp; int i=str.size()-1; temp=stri-; while(temp!='0') if(temp!='0'&&!isOper(temp) p=new TNode(temp);/以temp为内容来建立新的结点 nodeStack.push(p); temp=stri-; else p=new TNode(temp); if(nodeStack.size()/栈非空 p->left=nodeStack.top(); /则栈顶指针所指结点设置成当前结点左孩子 nodeS
18、tack.pop(); if(nodeStack.size()/栈非空 p->right=nodeStack.top();/则栈顶指针所指结点设置成当前结点右孩子 nodeStack.pop();/栈顶元素左右孩子指针设置完毕弹出 nodeStack.push(p); temp=stri-; /当栈空且扫描到最后时,树根由P带回void in2tree(TNode *&p, string str)/中缀表达式转换成后缀表达式生成二叉树 stack<char> a; char temp; string Postfixexp="" int i=0; t
19、emp=stri+; while(temp!='0') if(!isOper(temp)/操作数则直接进数据栈 Postfixexp+=temp; temp=stri+; else if(temp='(')/进栈 a.push(temp); temp=stri+; else if(temp=')') while(a.top()!='(')/脱括号 Postfixexp+=a.top(); a.pop();/在碰到开括号和栈为空前反复弹出栈中元素 a.pop(); temp=stri+; else if(temp='+
20、9;|temp='-'|temp='*'|temp='/')/出栈while(!a.empty()&&a.top()!='('&&getOperOrder(a.top()>=getOperOrder(temp)/若栈非空栈顶不是左括号且栈顶元素优先级不低于输入运算符时,/将栈顶元素弹出到后缀表达式中,并且str下标加 Postfixexp+=a.top(); a.pop(); a.push(temp);temp=stri+; /end while(temp!='0') whil
21、e(!a.empty() Postfixexp+=a.top();a.pop(); Postfixexp+='0' /cout<<Postfixexp; post2tree(p,Postfixexp);void count(TNode *p,int &height,int n)/求值函数/求树的高度if(p->left=NULL&&p->right=NULL) if(n>height) height=n; if(p->left!=NULL)count(p->left,height,n+1); if(p->r
22、ight!=NULL) count(p->right,height,n+1);void paint(TNode *p)/打印树 int height=0; int h=0; int i; using std:queue; queue<TNode*> aQueue; count(p,height,1);TNode *pointer=p; TNode *lastpointer; if(pointer) pointer->s=1; pointer->t=1; aQueue.push(pointer); while(!aQueue.empty() lastpointer=
23、pointer; pointer=aQueue.front(); aQueue.pop(); if(pointer->s>h) cout<<endl; h=pointer->s; if(pointer->t=1) for(i=0;i<pow(2,height-pointer->s)-1;i+) cout<<" " else if(lastpointer->s!=pointer->s)for(i=0;i<(pointer->t-1)*(pow(2,height-pointer->s+1)
24、-1)+(pointer->t-1)-1+pow(2,height-pointer->s);i+) cout<<" " else for(i=0;i<(pointer->t-lastpointer->t)*(pow(2,height-pointer->s+1)-1)+(pointer->t-lastpointer->t)-1;i+) cout<<" " cout<<pointer->oper; if(pointer->left!=NULL) pointer->left->s=pointer->s+1; pointer->left->t=pointer-&g
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 七年级数学上册数学 2.6.1 有理数的乘法与除法-有理数的乘法(四大题型)(解析版)
- 北海市实验学校临聘工作人员笔试真题2023
- 2025届新高考生物-命题趋势分析及备考策略-课件
- 沉淀溶解平衡+同步复习题 高二上学期化学人教版(2019)选择性必修1
- 结肠息肉护理评估及诊断课件
- 黄金卷02(参考答案)
- 慢性肾功能不全的中医治疗及护理课件
- 离婚协议书 大纲
- 2024年非离子型纤维素醚项目建议书
- 2024年溶剂绿7项目合作计划书
- 致用英语综合教程第二册-综合英语2--unit-1
- 2018WHO全球指南:手术部位感染的预防(第2版)
- 小儿支气管炎护理查房ppt课件
- 《建筑工程分部、子分部工程、分项工程名称一览表》
- 《六年级上册劳技》PPT课件.ppt
- 80m3重力式无阀滤池图集(共23页)
- 一年级新生家长会PPT课件.ppt
- 防火卷帘的集中做法及详图
- 离退休干部两项待遇落实工作的思考
- 必修1:数据与计算PPT课件
- 自动控制原理课程设计
评论
0/150
提交评论