数据结构实验报告-图

数据结构实验报告-图数据结构实验报告-图全文共9页，当前为第1页。数据结构实验报告图数据结构实验报告-图全文共9页，当前为第1页。

问题描述：;四则运算表达式求值，将四则运算表达式用中缀表达式;一、需求分析：;1、本程序是利用二叉树后序遍历来实现表达式的转换;2、输入输出格式：;输入格式：在字符界面上输入一个中缀表达式，回车表;请输入表达式：;输入一个中缀表达式;输出格式：如果该中缀表达式正确，那么在字符界面上;式，其中后缀表达式中两相邻操作数之间利用空格隔开;果不正确，在字符界面上输出

问题描述：

四则运算表达式求值，将四则运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。

一、需求分析：

1、本程序是利用二叉树后序遍历来实现表达式的转换，同时可以使用实验三的结果来求解后缀表达式的值。

2、输入输出格式：

输入格式：在字符界面上输入一个中缀表达式，回车表示结束。

请输入表达式：

输入一个中缀表达式

输出格式：如果该中缀表达式正确，那么在字符界面上数据结构实验报告-图全文共9页，当前为第2页。输出其后缀表达

式，其中后缀表达式中两相邻操作数之间利用空格隔开;如

果不正确，在字符界面上输出表达式错误提示。

逆波兰表达式为：

3、测试用例

输入：21+23*(12-6)

输出：2123126-*+输出逆波兰表达式运算结果为：输出运算后的结果

二、概要设计：

抽象数据类型

二叉树类BiTree

算法的基本思想

根据题目要求，利用栈计算，和二叉树存储，来计算表达式

该算法的基本思想是：

先利用栈进行计算，然后用二叉树进行存储，和实验三算法一样来计算逆波兰表达式的值

程序的流程

程序由三个模块组成：

(1)输入模块：输入一个运算式

(2)计算模块：利用栈进行表达式的计算，二叉树来存数据结构实验报告-图全文共9页，当前为第3页。储。(3)输出模块：屏幕上显示出后缀表达式和运算结果。

三、详细设计

物理数据类型

程序含有两个类，其中栈不再赘述，另一个类为二叉树classBiTree包含私有成员structBiTreeNode，根节点BiTreeNode*T;索引index;intnumber_of_point优先级比较函数xxpare(chara,charb);生成树的函数voidInorderCreate(BiTreeNode*&T,charstr,intstart,intend);判断数字函数boolIsNumber(chara);求值函数doubleOperate(BiTreeNode*T);还有显示后缀表达式的函数voiddisplay(BiTreeNode*T);而公有成员函数则是对私有函数的重载，为方便使用，因为函数中普遍使用了递归的算法。

算法的时空分析

此算法利用栈和二叉树来实现，故次算法的的时间复杂度为(N)。

输入和输出的格式

输入格式：请输入表达式：

输入一个中缀表达式//回车

输出格式：逆波兰表达式为：

输出逆波兰表达式

运算结果为：输出运算后的结果

数据结构实验报告-图全文共9页，当前为第4页。四、调试分析

略。

五、测试结果

本实验的测试结果截图如下：

六、用户使用说明(可选)

1、本程序的运行环境为windows操作系统，执行文件为2、运行程序时

提示输入表达式

本程序可以将中缀表达式转换为后缀表达式后在计算出运算式的结果。提示：请输入表达式：

输出

提示：逆波兰表达式为：

运算结果：

七、实验心得(可选)

本次实验过程比较复杂，由于书上的知识掌握的还不是很牢靠，所以现在实验做起来有点儿吃力。本实验主要是通过与同学的讨论和课后查阅资料来完成的，虽然有些地方还不是很懂，但基本上能完成此次实验的内容。而且通过本次实验，加深了对二叉树算法的了解。

附录(实验代码)：

#include

#include

数据结构实验报告-图全文共9页，当前为第5页。#include

#include

#include

#include

#defineSTACK_INIT_SIZE100

#defineDATA_SIZE10

#defineSTACKINCREMENT10

#defineOK1

#defineTRUE1

#defineFALSE0

#defineERROR0

#defineOVERFLOW-2

usingnamespacestd;

typedeffloatSElemtype;

typedefintStatus;

typedefchar*TElemType;

typedefstructBiTNode{

TElemTypedata;

intlen;//data字符串中字符的个数

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;

typedefstruct

数据结构实验报告-图全文共9页，当前为第6页。{

SElemtype*base;

SElemtype*top;

intstacksize;

}SqStack;

StatusIsDigital(charch)

{if(ch>='0'&&chdata=(char*)malloc(DATA_SIZE*sizeof(char));

while(IsDigital(c))

{T->data=c;

i++;}

T->len=i;

T->lchild=T->rchild=NULL;

(T);

returni;

}

voidCrtSubTree(stack&PTR,charc)

{BiTNode*T;

T=(BiTNode*)malloc(sizeof(BiTNode));

T->data=(char*)malloc(DATA_SIZE*sizeof(char));

T->data=c;

T->len=1;

数据结构实验报告-图全文共9页，当前为第7页。T->rchild=;//先右子树，否则运算次序反了

;

T->lchild=;

;

(T);

}

charsymbol={{'>','>',''},//符号优先级

{'>','>',''},

{'>','>','>','>','>'},

{'>','>','>','>','>'},

{'<','<','<','<','='}};

intsym2num(chars)//返回符号对应优先级矩阵位置{switch(s)

{

case'+':return0;break;

case'-':return1;break;

case'*':return2;break;

case'/':return3;break;

case'#':return4;break;

}

}

charPrecede(chara,charb)//返回符号优先级

数据结构实验报告-图全文共9页，当前为第8页。{return(symbol);}

voidCrtExptree(BiTree&T,charexp)

{//根据字符串exp的内容构建表达式树T

stackPTR;//存放表达式树中的节点指针

stackOPTR;//存放操作符

charop;

inti=0;

('#');

op=;

while(!((exp=='#')&&(=='#')))//与

{

if(IsDigital(exp))

{//建立叶子节点并入栈PTR

i+=CrtNode(PTR,&exp);

}

elseif(exp=='')

i++;

else{

switch(exp)

{

case'(':{

(exp);

数据结构实验报告-图全文共9页，当前为第9页。i++;

break;}

case')':{

op=;;

while(op!='('){

CrtSubTree(PTR,op);

op=;;

}//en