资源描述：
《数据结构课程实验报告实验5》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、数据结构课程实验指导书HUNANUNIVERSITY课程实习报告题目：四则运算表达式求值学生姓名康小雪学生学号20090810310专业班级计科三班指导老师李晓鸿完成日期2010-10-24－8－数据结构课程实验指导书一、需求分析1．该程序可以从通过从键盘输入一个中缀表达式，判断该表达式是否合法，若合法将其转化为后缀表达式，并计算其结果，否则说明该表达式错误2．.输入的表达式包含数字和运算符及括号，之间用空格隔开3．数字可以为整数和小数4．运算结果保留两位小数输入输出举例输入：21+23*（12-6）输出：2123126-*+
2、二、概要设计在表达式中每个运算符应对应两个操作数，与二叉树中非叶子结点和叶子结点之间的关系刚好相同，于是，本题可采用二叉树来将中缀表达式变为后缀表达式。最后用堆栈来实现后缀表达式的计算。抽象数据类型二叉树ADTBiTree{数据对象D：D是具有相同特性的数据元素集合数据关系R：若D为空集，则R为空集，则称BinaryTree为空二叉树；若D不为空集，否则R={H}，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root}≠空集，则存在D-{root}的一个划分{D1,Dr}
3、且D1∩Dr=空集；（3）若D1≠空集，则D1中存在唯一元素x1，∈H,且存在D1shangdeguanxiH1=H;ruoDr≠空集，则Dr中存在唯一的元素，xr，∈H，且存在Dr上的关系Hr∈H;H={,,H1,Hr};（4）(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树，(Dr，{Hr})是一棵符合本定义的二叉树，称为根的右子树基本操作P:InitBiTree（&T）操作结果：构造空二叉树TDestroyBiTree（&T）初始条件：二叉
4、树T存在操作结果：销毁二叉树TCreateBiTree（&T，definition）初始条件：definition给出二叉树T的定义操作结果：按definition构造二叉树TClearBiTree（&T）初始条件：二叉树T存在操作结果：将二叉树T清空为空树TreeBiEmpty(T)初始条件：二叉树T存在操作结果：若二叉树T为空树，则返回TRUE，否则返回FALSETreeBiDepth（T）－8－数据结构课程实验指导书初始条件：二叉树T存在操作结果：返回二叉树T的深度Root（T）初始条件：二叉树T存在操作结果：返回T的根
5、Value（T,cur_e）初始条件：二叉树T存在，cur_e是T中的某个结点操作结果：返回cur_e的值Assign（T,cur_e，value）初始条件：二叉树T存在，cur_e是T中的某个结点操作结果：结点cur_e赋值为valueParent（T,cur_e）初始条件：而擦树T存在，cur_e是T中的某个结点操作结果：若cur_e是非根结点，则返回它的双亲，否则函数值为空LeftChild（T，cur_e）初始条件：二叉树T存在，cur_e是T中的某个结点操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则
6、返回空RightChild（&T,&p,i）初始条件：二叉树T存在，cur_e是T中的某个结点操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则函数值为空LeftSibling（T,e）初始条件：二叉树T存在，e是T中的某个结点操作结果：返回e的左兄弟，若e是T的左孩子或无左兄弟，返回空RightSibling（T,e）初始条件：二叉树T存在，e是T中的某个结点操作结果：返回e的右兄弟，若e是T的右孩子或无右兄弟，返回空InsertChild（&T,&p,I,c）初始条件：二叉树T存在，p指向T中某个结点，1<=i<=p所
7、指结点的度+1，非空树c与T不相交操作结果：插入c为T中p指结点的第i棵子树DeleteChild（&T,&p,i）初始条件：树T存在，p指向T中某个结点，1<=i<=p所值结点的度操作结果：删除T中p所指结点的第i棵子树PreOrderTravereseTree（T,Visit()）初始条件：二叉树T存在，Visit是对界定操作的应用函数操作结果：先序遍历T，对每个结点调用函数visit（）一次且仅一次，一旦visit()失败，则操作失败InOrderTravereseTree（T,Visit()）初始条件：二叉树T存在，V
8、isit是对界定操作的应用函数操作结果：中序遍历T，对每个结点调用函数visit（）一次且仅一次，一旦visit()失败，则操作失败PostOrderTravereseTree（T,Visit()）初始条件：二叉树T存在，Visit是对界定操作的应用函数－8－数据结构课程实验
