《表达式类型的实现.doc》由会员分享，可在线阅读，更多相关《表达式类型的实现.doc（25页珍藏版）》请在三一办公上搜索。
1、*理工大学数据结构课程设计报告题目：表达式类型的实现 院（系）：计算机工程学院 学生姓名: * 班级： 计算111 学号:2011070*起迄日期: 2012.7.82012.7.19 指导教师: * 一、需求分析1.问题描述：本程序通过输入前缀表达式建立一颗二叉树，通过中序遍历建立好的二叉树输出带括号的中缀表达式。然后中序遍历二叉树对表达式中的未知数x进行赋值。通过后序遍历二叉树计算表达式的值。根据两颗二叉树和输入的运算符构造复合表达式。另外，通过中序遍历二叉树对表达式进行化简。 2.基本功能以字符序列的形式输入语确的前缀表示式并构成表达式E用带括号的中缀表达式输出表达式E实现对变量x的赋值
2、，变量初始值为0对算术表达式求值构造新的复合表达式（E1）P（E2）对表达式进行化简 3.输入输出本程序运算数的输入输出局限于无符号整型数据，运算符的输入输出包括“+、-、*、/、”二、 概要设计1.设计思路：本程序以字符序列的形式输入语确的前缀表达式，在输入表达式的过程中判断输入的字符是运算数还是运算符并将其保存到树节点中相应的位置，表达式输入结束的同时也就构成一颗二叉树。根据建立好的二叉树，可以采用中序遍历二叉树的法输出正常顺序的表达式。在中序遍历二叉树时，访问存放运算符的结点时要判断其与双亲结点中运算符的优先级关系来判断是否要添加括号。在给表达式中的未知数x赋值时，本程序采用的是中序遍历
3、二叉树的法，遇到存放x的结点就将数值赋值给其数据域的变量。然后通过后序遍历二叉树的法就行表达式求值。构造复合表达式可以分别建立两颗二叉树，然后将这两颗二叉树作为新申请的运算符结点的左右孩子结点。在化简表达式时，先判断运算符结点的两个孩子节点是不是运算数结点（不包括x结点）。如果两个孩子节点是运算数结点，就计算出这个子表达式的值并用其代替这个运算符结点。 2.数据结构设计：抽象数据类型二叉树的定义如下：ADT BinaryTree 数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D=，则R=，称BinaryTree为空二叉树；若D，则R=H，H是如下二元关系：（1）在D中存在唯一的称
4、为根的数据元素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存在。操作结果：中序遍历
5、二叉树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 Compou
6、ndExpr(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(BitNo
7、de); 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);print
8、f( (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);
9、(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(I
10、n(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 InOrderTr
11、averse(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); InOrde
12、rTraverse(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); p
13、rintf();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
14、(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(请
15、以字符序列的形式输入语确的前缀表示式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(化简后表达式为: );
16、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;huajia
17、n(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
18、,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 me
19、nu（）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）对算术表达式求值。（
20、5）构造新的复合表达式。（6) 对表达式化简。 2.程序的性能分析，包括时空分析；本程序实现了通过遍历二叉树对表达式的求值，化简等操作。此外，可以增加一些其他的操作或者增加一些其他的运算操作。 3.上机过程中出现的问题及其解决案；（1） 构建的二叉树为空。解决案：通过传地址的式调用二叉树操作函数。（2） 运行程序是无法输入字符。解决案：用ch=getche();语句接收字符。（3） 使用数学函数时出错。解决案：添加头文件#include 。4. 程序中可以改进的地说明；本程序运算数的输入输出局限于无符号整型数据，运算符的输入输出包括“+、-、*、/、”。可以通过改进实现对浮点型数据的计算。另外
21、，可以增加一些其他的运算，例如三角函数，指数函数等等。5. 程序中可以扩充的功能及设计实现假想。程序可以增加对操作符sin，cos，tan，cot，log，ln等运算符的识别，也可以增加对浮点型数据的操作的功能。五、测试结果（1）构建二叉树（2）输出带括号的中缀表达式：（3）对变量x赋值：（4）对算术表达式求值：（5）构造复合表达式：（6）化简表达式：（7）错误提示：六、用户手册第一步：输入选项一，构建二叉树。如下图：第二步：输入前缀表达式：第三步：输入选项二，输出带括号的中缀表达式：第四步：输入选项三，对变量x赋值；第五步：输入选项四，对算术表达式求值：第六步：输入选项六，化简表达式：第七步
22、：输入选项五，构造复合表达式：七、体会与自我评价 经过两对数据结构课程设计（表达式类型的实现）的研究主要有以下几点感受：首先，数据结构课程设计很好的反映了自己这一学期对数据结构基础知识的掌握情况，让自己清醒的认识到自己的真实水平。不动手不知道，自己亲自动手设计程序时才感觉到知识的不扎实。有的知识虽然已经学过，但是用起来还是感觉有点模糊，这也算是给自己的一个警醒吧。 另外，编写程序时有些自己想要编写的功能用已学的知识不能实现，这样就要去上网或查阅课外书来学习一些其他的知识，我感觉这样很好。这样不仅会拓宽自己的知识面，还会提高自己的自学能力。同时，宿舍里的同学集体讨论如去实现各种功能，各自发表看法
23、彼此交流也是一种学习的过程。最深刻的感受就是编写程序过程中的酸甜苦辣。刚开始构思时漏洞百出，程序出错。但是令人高兴的是通过不断的调试程序，不断的出错，然后不断的修改，从这过程中学到了一些调试程序的技巧。虽然有些语句没有语法错误，但是如果语句顺序不对也会提示错误 ，例如error C2143: syntax error : missing ; before typeerror C2275: FILE : illegal use of this type as an expression等错误提示。经过痛苦又快乐的调试过程之后，当自己自如的运行着程序时成就感十足啊！顿时感觉之前付出的一切值了，实在是值了。总之，我感觉数据结构课程设计的重要性不比数据结构课堂差。课程设计提高了我们的动手能力，我们能将课本上的死知识灵活地应用到生活当中，还有就是能够感受到十足的成就感，增加学习专业课的兴趣。另外，不得不感*老师的指导!
