表达式类型的实现.doc

*理工大学数据结构课程设计报告题目：表达式类型的实现 院（系）：计算机工程学院 学生姓名: * 班级： 计算111 学号:2011070*起迄日期: 2012.7.82012.7.19 指导教师: * 一、需求分析1.问题描述：本程序通过输入前缀表达式建立一颗二叉树，通过中序遍历建立好的二叉树输出带括号的中缀表达式。然后中序遍历二叉树对表达式中的未知数x进行赋值。通过后序遍历二叉树计算表达式的值。根据两颗二叉树和输入的运算符构造复合表达式。另外，通过中序遍历二叉树对表达式进行化简。 2.基本功能以字符序列的形式输入语法正确的前缀表示式并构成表达式E用带括号的中缀表达式输出表达式E实现对变量x的赋值，变量初始值为0对算术表达式求值构造新的复合表达式（E1）P（E2）对表达式进行化简 3.输入输出本程序运算数的输入输出局限于无符号整型数据，运算符的输入输出包括“+、-、*、/、”二、 概要设计1.设计思路：本程序以字符序列的形式输入语法正确的前缀表达式，在输入表达式的过程中判断输入的字符是运算数还是运算符并将其保存到树节点中相应的位置，表达式输入结束的同时也就构成一颗二叉树。根据建立好的二叉树，可以采用中序遍历二叉树的方法输出正常顺序的表达式。在中序遍历二叉树时，访问存放运算符的结点时要判断其与双亲结点中运算符的优先级关系来判断是否要添加括号。在给表达式中的未知数x赋值时，本程序采用的是中序遍历二叉树的方法，遇到存放x的结点就将数值赋值给其数据域的变量。然后通过后序遍历二叉树的方法就行表达式求值。构造复合表达式可以分别建立两颗二叉树，然后将这两颗二叉树作为新申请的运算符结点的左右孩子结点。在化简表达式时，先判断运算符结点的两个孩子节点是不是运算数结点（不包括x结点）。如果两个孩子节点是运算数结点，就计算出这个子表达式的值并用其代替这个运算符结点。 2.数据结构设计：抽象数据类型二叉树的定义如下：ADT BinaryTree 数据对象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，且存在D1上的关系H1H；若Dr，则Dr中存在唯一的元素Xr，H,且存在Dr上的关系HrH；H=,H1,Hr；（4）（D1，H1）是一颗符合本定义的二叉树，称为根的左子树，（Dr，Hr）是一颗符合本定义的二叉树，称为根的右子树。基本操作：CreatBitTree (BitTree T,BitTree p);操作结果：根据前缀表达式先序构造二叉树。InOrderTraverse(BitTree T)初始条件：二叉树T存在。操作结果：中序遍历二叉树T，输出每个结点的数据域且仅一次。InOrder(BitTree T,int *num);初始条件：二叉树T存在且存在x结点。操作结果：将num赋值给x。PostOrderTraverse(BitTree T);初始条件：二叉树T。操作结果：后序遍历二叉树求表达式的值。ADT BinaryTree3.软件结构设计：BitTree ReadExpr(BitTree T);BitTree WriteExpr(BitTree T)BitTree Assign(BitTree T);BitTree Value(BitTree T);Int main（）Void menu（）void CompoundExpr(BitTree T);void MergeConstruction(BitTree T);退出！三、 详细设计 1. 定义程序中所有用到的数据及其数据结构，及其基本操作的实现；typedef struct BitNodechar data;int opnd;struct BitNode *lchild;struct BitNode *rchild;struct BitNode *parent;BitNode,*BitTree;2主函数和其他函数的伪码算法；(1)主函数：int main()BitTree T=NULL;T=(BitTree )malloc(sizeof(BitNode); if(T=NULL)printf(有错n);elseflag=0;menu(T);return 0;(2) 菜单函数：void menu(BitTree T)int sel=0;doprintf(nn);printf( (1) 以字符序列的形式输入语法正确的前缀表示式并构造表达式 n);printf( (2) 用带括弧的中缀表达式输出表达式 n);printf( (3) 实现对变量x的赋值（x=c）,变量的初值为0 n);printf( (4) 对算术表达式求值 n);printf( (5) 造一个新的复合表达式（E1）P(E2) n);printf( (6) 表达式化简n);printf( (0) 退出 n);printf( 请输入您的选择:);scanf(%d,&sel);printf(%d,sel);system(cls);switch(sel)case 1: T=ReadExpr(T);break;case 2: T=WriteExpr(T);break;case 3: T=Assign(T);break;case 4: T=Value(T);break;case 5: CompoundExpr(T);break;case 6: MergeConstruction(T);break;case 0: printf( 已退出!n);break;while(sel!=0);(3) 构建二叉树函数：BitTree CreatBitTree (BitTree T,BitTree p) char ch;ch=getche();if(In(ch)=0)printf(n表达式有误,请重新输入:n);T = CreatBitTree (T,p);return T;T=(BitTree )malloc(sizeof(BitNode); if(T=NULL)printf(有错n);elseif(In(ch)=2)if(ch=x)xflag=1;assg=0;T-data = ch;T-opnd = 0;elseT-data = N;T-opnd = ch-0;else if(In(ch)=1)T-data = ch;T-opnd = 0;T-parent = p; p=T; if(In(ch)=2) T-lchild = NULL;T-rchild = NULL; else if(In(ch)=3) T-lchild = CreatBitTree(T-lchild ,p );T-rchild = NULL; else T-lchild = CreatBitTree(T-lchild ,p ); T-rchild = CreatBitTree(T-rchild ,p ); return T;(4) 中序遍历二叉树输出带括号中缀表达式的函数：void InOrderTraverse(BitTree T)if(T=NULL)return ;else if(Precede(T-data , T-parent-data )=-1) printf();InOrderTraverse(T-lchild);if(T-data = N)printf(%d,T-opnd);else printf(%c,T-data); InOrderTraverse(T-rchild); printf();elseInOrderTraverse(T-lchild); if(T-data = N)printf(%d,T-opnd);else printf(%c,T-data); InOrderTraverse(T-rchild); (5) 中序遍历二叉树给变量x赋值的函数：void InOrder(BitTree T,int *num)if(T=NULL)return; else if(Precede(T-data , T-parent-data )=-1) printf();InOrder(T-lchild,num); if(T-data = N)printf(%d,T-opnd);else if(T-data = x)T-opnd = *num;printf(%d,T-opnd );else printf(%c,T-data);InOrder(T-rchild,num); printf();elseInOrder(T-lchild,num); if(T-data = N)printf(%d,T-opnd);else if(T-data = x)T-opnd = *num;printf(%d,T-opnd );else printf(%c,T-data);InOrder(T-rchild,num); (6) 后序遍历二叉树求表达式值的函数：void PostOrderTraverse(BitTree T)if(T=NULL)return; else PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild);if(In(T-data )=2)return;else if(In(T-data )=1)T-opnd = calculate(T-lchild -opnd ,T-data ,T-rchild -opnd ); (7) 构造复合表达式的函数：void CompoundExpr(BitTree T)char optr;BitTree T1=NULL,T2=NULL;BitTree p;p=T1;printf(请以字符序列的形式输入语法正确的前缀表示式E1:n);T1=CreatBitTree (T1,p);T1-parent = T1; printf(n二叉树构造成功!n);p=T2;printf(请以字符序列的形式输入语法正确的前缀表示式E2:n);T2=CreatBitTree (T2,p);T2-parent = T2; printf(n二叉树构造成功!n);printf(请输入运算符p:);getchar();scanf(%c,&optr);T-data = optr;T-opnd = 0;T-parent = T;T-lchild = T1;T-rchild = T2;T1-parent = T;T2-parent = T;flag=1;(8) 化简函数表达式的函数：void MergeConstruction(BitTree T)int a=1;printf(化简后表达式为: );while(a=1)a=0;huajian(T,&a);InOrderTraverse(T);printf(n);void huajian(BitTree T,int *a)if(T=NULL)return; else huajian(T-lchild,a); if(In(T-data )=1&T-lchild -data = N&T-rchild -data = N)T-opnd = calculate(T-lchild -opnd ,T-data ,T-rchild -opnd );T-data = N;T-lchild = NULL;T-rchild = NULL;*a=1;huajian(T-rchild,a); 开始3. 主要函数的程序流程图，实现设计中主程序和其他子模块的算法，以流程图的形式表示。输入选项yesCreatBitTree (BitTree T,BitTree p)ReadExpr(T);选项1noInOrderTraverse(BitTree T)yesWriteExpr(BitTree T)选项2noyesInOrder(BitTreeT,int *num)Assign(BitTree T)选项3noyesPostOrderTraverse(BitTree T)Value(BitTree T)选项4noyesCreatBitTree (BitTree T,BitTree p) CompoundExr(BitTree T)选项5noyesHuajian(BitTree T,int *a)MergeConstruction(BitTreeT)选项6noyes选项0no结束4. 画出函数之间的调用关系图。BitTree ReadExpr(BitTree T);CreatBitTree (BitTree T,BitTree p)BitTree WriteExpr(BitTree T)InOrderTraverse(BitTree T)BitTree Assign(BitTree T);InOrder(BitTreeT,int *num)Void menu（）Int main（）BitTree Value(BitTree T);PostOrderTraverse(BitTree T)void CompoundExpr(BitTree T);CreatBitTree (BitTree T,BitTree p) void MergeConstruction(BitTree T);Huajian(BitTree T,int *a)四、 调试分析 1. 实际完成的情况说明（完成的功能，支持的数据类型等）；（1）以字符序列的形式输入正确的前缀表达式。（2）用带括号的中缀表达式输出表达式。（3）实现对变量x的赋值，初始值为0。（4）对算术表达式求值。（5）构造新的复合表达式。（6) 对表达式化简。 2.程序的性能分析，包括时空分析；本程序实现了通过遍历二叉树对表达式的求值，化简等操作。此外，可以增加一些其他的操作或者增加一些其他的运算操作。 3.上机过程中出现的问题及其解决方案；（1） 构建的二叉树为空。解决方案：通过传地址的方式调用二叉树操作函数。（2） 运行程序是无法输入字符。解决方案：用ch=getche();语句接收字符。（3） 使用数学函数时出错。解决方案：添加头文件#include 。4. 程序中可以改进的地方说明；本程序运算数的输入输出局限于无符号整型数据，运算符的输入输出包括“+、-、*、/、”。可以通过改进实现对浮点型数据的计算。另外，可以增加一些其他的运算，例如三角函数，指数函数等等。5. 程序中可以扩充的功能及设计实现假想。程序可以增加对操作符sin，cos，tan，cot，log，ln等运算符的识别，也可以增加对浮点型数据的操作的功能。五、测试结果（1）构建二叉树（2）输出带括号的中缀表达式：（3）对变量x赋值：（4）对算术表达式求值：（5）构造复合表达式：（6）化简表达式：（7）错误提示：六、用户手册第一步：输入选项一，构建二叉树。如下图：第二步：输入前缀表达式：第三步：输入选项二，输出带括号的中缀表达式：第四步：输入选项三，对变量x赋值；第五步：输入选项四，对算术表达式求值：第六步：输入选项六，化简表达式：第七步：输入选项五，构造复