数据结构课程实验报告_实验7优先队列

《数据结构课程实验报告_实验7优先队列》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、HUNANUNIVERSITY课程实习报告题目：逆波兰表达式问题优先队列与堆学生姓名_学生学号_指导老师完成日期2015-5-9逆波兰表达式问题实验背景在工资管理软件屮，不可避免的要用到公式的定义及求值等问题。对于数学表达式的计算，虽然可以直接对表达式进行扫描并按照优先级逐步计算，但也可以将中缀表达式转换为逆波兰表达式，这样更容易处理。基本要求使用二叉树来实现。实现提示利用二叉树后序遍历來实现表达式的转换，同时可以使用实验3的结果來求解后缀表达式的值。输入输出格式：输入：在字符界面上输入一个屮缀表达式，回车表示结束。输出：如果该屮缀表达式正确，那

2、么在字符界而上输出其示缀表达式，其屮示缀表达式中两相邻操作数Z间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。测试用例输入：21+23*(12-6)输出：2123126・*+源代码：#incIude#incIude#includeusingnamespacestd;charstr[100][15];//由于一个数字可能有多个数字组成intsearch_1(intstart,intend)//寻找优先级最小的’+'或'-'{inti,count二0,pos二T;//courrt用来记

3、录括号的数量，pos用来记录优先级最小的'+'或的位置for(i二start;i

4、

5、str[i][0]='-’)&&count=0)//无括号时pos=i;//i记录的是优先级最小的'+'或的位置，也就是没有括号，并且在后面的加减运算}returnpos;}intsearch_2(intstart,intend)//寻找优先级最小的或"/'的位置inti,count二0,pos二

6、T;//count用来记录括号的数量，pos用来记录优先级最小的'+'或‘-‘的位置for(i二start;i〈end;i++){if(str[i][0]二二')')count-一；eIseif(str[i][0]='(')count++;elseif((str[i][0]='*'

7、

8、str[i][0]='/')&&count=0)pos=i;}returnpos;}doubleturn(charc[])//将字符串中的数字转换为浮点型{doubIetemp二0;inti;for(i二0;;i++){if(c[i]!二'')temp=temp

9、*10+c[i]-’O';eIsebreak;}returntemp;}cIassNode{pubIic:chardata[15];Node*IchiId;Node*rchiId;Node0{IchiId=NULL;rchiId二NULL;}}；cIassBintree{pubIic:Node*subroot;Node*creattree(intstart,intend);//建立二叉树voidpostorder(Node*subroot);//后续遍历二叉树doubIecaIcute(Node*subroot);//计算表达式的结果voidde

10、story(Node*subroot);//销毁二叉树，释放空间}；Node*Bintree::creattree(intstart,intend)//用递归的方法来建立二叉树{intpos=-1;Node*root二newNode;if(end-start=1)strcpy(root->data,str[start]);eIse{pos=search_1(start,end);//找优先级最低的加减法if(pos二二T)pos二search_2(start,end);//如果没有的话那就找任先级最低的乘除法if(pos==-1)root二cre

11、attree(start+1,endT);eIse{strcpy(root->data,str[pos]);root->lchiId二creattree(start,pos);root->rchiId二creattree(pos+1,end);}}returnroot;voidBintree::postorder(Node*subroot)//递归的方法后续遍历{if(subroot!=NULL){postorder(subroot->lchiId);postorder(subroot->rchiId);cout«subroot->da}void

12、Bintree::destory(Node*subroot)if(subroot!二NULL)destory(subroot->lchi