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

数据结构课程实验指导书HUNAN UNIVERSITY课程实习报告题 目： 四则运算表达式求值 学生姓名 康小雪 学生学号 20090810310 专业班级 计科三班 指导老师 李晓鸿 完 成 日 期 2010-10-24 8 一、 需求分析1该程序可以从通过从键盘输入一个中缀表达式，判断该表达式是否合法，若合法将其转化为后缀表达式，并计算其结果，否则说明该表达式错误2.输入的表达式包含数字和运算符及括号，之间用空格隔开3数字可以为整数和小数4运算结果保留两位小数输入输出举例输入：21+23*（12-6）输出：21 23 12 6 -*+二、 概要设计在表达式中每个运算符应对应两个操作数，与二叉树中非叶子结点和叶子结点之间的关系刚好相同，于是，本题可采用二叉树来将中缀表达式变为后缀表达式。最后用堆栈来实现后缀表达式的计算。抽象数据类型二叉树ADT BiTree数据对象 D：D是具有相同特性的数据元素集合数据关系 R：若D为空集，则R为空集，则称BinaryTree为空二叉树；若D不为空集，否则R=H，H是如下二元关系：（1） 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2） 若D-root空集，则存在D-root的一个划分D1,Dr 且D1Dr=空集；（3） 若D1空集，则D1中存在唯一元素x1，H,且存在D1shang de guanxi H1=H;ruo Dr空集，则Dr中存在唯一的元素，xr，H，且存在Dr上的关系HrH;H=,H1,Hr;（4） (D1,H1)是一棵符合本定义的二叉树，称为根的左子树，(Dr，Hr)是一棵符合本定义的二叉树，称为根的右子树基本操作P:InitBiTree（&T）操作结果：构造空二叉树TDestroyBiTree（&T）初始条件：二叉树T存在操作结果：销毁二叉树TCreateBiTree（&T，definition）初始条件：definition给出二叉树T的定义操作结果：按definition构造二叉树TClearBiTree（&T）初始条件：二叉树T存在操作结果：将二叉树T清空为空树TreeBiEmpty(T)初始条件：二叉树T存在操作结果：若二叉树T为空树，则返回TRUE，否则返回FALSETreeBiDepth（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赋值为valueParent（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=0数据关系：R1=D,i=2,n基本操作：InitStack(&S)操作结果：构造一个空栈SDestroyStack（&S）初始条件：栈S已存在操作结果：栈S被销毁ClearStack（&S）初始条件：栈S已存在操作结果：栈S清为空栈StackEmpty（S）初始条件：栈S已存在操作结果：若S为空栈，则返回TRUE,否则FALSEStackLength（S）初始条件：栈S已存在操作结果：返回S元素的个数，即栈的长度GeTop（S,&e）初始条件：栈S已存在且非空操作结果：用e返回S的栈顶元素Push（&S，e）初始条件：栈S已存在操作结果：插入元素e为新的栈顶元素Pop（&S,&e）初始条件：栈S已存在且非空操作结果：删除S的栈顶元素，并返回eStackTraverse（S,visit()）初始条件：栈S已存在且非空操作结果：从栈底到栈顶依次对S的每个元素调用函数visit()，一旦visit()失败，则操作失败ADT Stack算法的基本思想以(A+B)*(C-D/E)这样一个表达式为列求它的后缀表达式按照优先级加上括号，得到：(A+B)*(C-(D/E)然后从最外层括号开始，依次转化成二叉树 1、根是* ，左子树(A+B)，右子树(C-(D/E)2、右子树的根- ，右子树的左子树C，右子树的右子树(D/E)3、(A+B)的根+，左子树A ，右子树B 4、(D/E)的根/ ，左子树D，右子树E*+-A/BCDE可以画出表达式对应的2叉树，操作数作为叶子节点，操作符作为非叶子节点,如图所示。再逆序遍历二叉树可得逆波兰表达式为：AB+CDE/-*利用堆栈的方法计算后缀表达式的值程序的流程程序由三个模块组成：（1）输入模块：在主函数中输入中缀表达式（2）转换模块：将中缀表达式转换为后缀表达式，并打印（3）计算模块：生成的后缀表达式用于计算，打印最后结果三、详细设计物理数据类型二叉树#define Max_TREE_SIZE 100Typedef TElemType SqBiTreeMAX_TREE_SIZE;SqBiTree bt;堆栈#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK1#define TRUE 1#define FALSE 0#define ERROR 0#define OVERFLOW -2typedef float SElemtype;typedef int Status;算法的具体步骤/基本操作的函数原型/二叉树的存储结构表示Typedef struct BiTNodeTElemType data;Srtuct BiTNode *lchild,*rchild;BiTNode,*BiTree;/基本操作的函数原型说明Status CreatBiTree(BiTree &T)/按先序次序插入二叉树中结点的值（一个字符）/构造二叉链表表示二叉树TStatus PreOrderTraverse（BiTreeT,Status (* Visit)(TELemType e)）/采用二叉链表的存储结构，Visit是对结点操作的应用函数/先序遍历二叉树，对每个结点调用且仅调用一次Visit函数/一旦Visit函数失败则操作失败Status InOrderTraverse（BiTreeT,Status (* Visit)(TELemType e)）/采用二叉链表的存储结构，Visit是对结点操作的应用函数/中序遍历二叉树，对每个结点调用且仅调用一次Visit函数/一旦Visit函数失败则操作失败Status PostOrderTraverse（BiTreeT,Status (* Visit)(TELemType e)）/采用二叉链表的存储结构，Visit是对结点操作的应用函数/后序遍历二叉树，对每个结点调用且仅调用一次Visit函数/一旦Visit函数失败则操作失败/堆栈的存储结构表示typedef structSElemtype * base;SElemtype * top;int stacksize; SqStack;Status InitStack(SqStack &S)S.base = (SElemtype *)malloc(STACK_INIT_SIZE*sizeof(SElemtype);if (! S.base) exit(OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;int StackLength(SqStack S) /获得堆栈元素的个数/填空 return S.top-S.base;Status Push(SqStack &S, SElemtype e)/入栈/填空 S.top+; *(S.top)=e; return true;Status Pop(SqStack &S, SElemtype &e)/出栈/填空 if(S.topS.b