(数据结构课程实验报告实验5.docVIP

HUNAN UNIVERSITY 课程实习报告 题 目： 四则运算表达式求值 学生姓名 康小雪 学生学号 20090810310 专业班级 计科三班 指导老师 李晓鸿 完 成 日 期 2010-10-24 需求分析 1．该程序可以从通过从键盘输入一个中缀表达式，判断该表达式是否合法，若合法将 其转化为后缀表达式，并计算其结果，否则说明该表达式错误 2．.输入的表达式包含数字和运算符及括号，之间用空格隔开 3．数字可以为整数和小数 4．运算结果保留两位小数 输入输出举例 输入：21+23*（12-6） 输出：21 23 12 6 -*+ 概要设计 在表达式中每个运算符应对应两个操作数，与二叉树中非叶子结点和叶子结点之间的关系刚好相同，于是，本题可采用二叉树来将中缀表达式变为后缀表达式。 最后用堆栈来实现后缀表达式的计算。 抽象数据类型 二叉树 ADT BiTree { 数据对象 D：D是具有相同特性的数据元素集合 数据关系 R： 若D为空集，则R为空集，则称BinaryTree为空二叉树； 若D不为空集，否则R={H}，H是如下二元关系： 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； 若D-{root}≠空集，则存在D-{root}的一个划分{D1,Dr} 且D1∩Dr=空集； 若D1≠空集，则D1中存在唯一元素x1，root，x1∈H,且存在D1shang de guanxi H1=H;ruo Dr≠空集，则Dr中存在唯一的元素，xr，root，xr∈H，且存在Dr上的关系Hr∈H;H={root,x1,root,xr,H1,Hr}; (D1,{H1})是一棵符合本定义的二叉树，称为根的左子树，(Dr，{Hr})是一棵符合本定义的二叉树，称为根的右子树 基本操作P: InitBiTree（T） 操作结果：构造空二叉树T DestroyBiTree（T） 初始条件：二叉树T存在 操作结果：销毁二叉树T CreateBiTree（T，definition） 初始条件：definition给出二叉树T的定义 操作结果：按definition构造二叉树T ClearBiTree（T） 初始条件：二叉树T存在 操作结果：将二叉树T清空为空树 TreeBiEmpty(T) 初始条件：二叉树T存在 操作结果：若二叉树T为空树，则返回TRUE，否则返回FALSE TreeBiDepth（T） 初始条件：二叉树T存在 操作结果：返回二叉树T的深度 Root（T） 初始条件：二叉树T存在 操作结果：返回T的根 Value（T,cur_e） 初始条件：二叉树T存在，cur_e是T中的某个结点 操作结果：返回cur_e的值 Assign（T, cur_e，value） 初始条件：二叉树T存在，cur_e是T中的某个结点 操作结果：结点cur_e赋值为value Parent（T,cur_e） 初始条件：而擦树T存在，cur_e是T中的某个结点 操作结果：若cur_e是非根结点，则返回它的双亲，否则函数值为空 LeftChild（T，cur_e） 初始条件：二叉树T存在，cur_e是T中的某个结点 操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回空 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所指结点的度+1，非空树c与T不相交 操作结果：插入c为T中p指结点的第i棵子树 DeleteChild（T,p,i） 初始条件：树T存在，p指向T中某个结点，1=i=p所值结点的度 操作结果：删除T中p所指结点的第i棵子树 PreOrderTravereseTree（T,Visit()） 初始条件：二叉树T存在