数据结构实验报告

..课程设计实验报告实验名称：表达式类型的实现编译环境：硬件:PC软件：VS2010问题描述一个表达式和一棵二叉树之间,存在着自然的对应关系。写一个程序,实现基于二叉树表示的算术表达式Expression的操作。基本要求假设算术表达式Expression可以含有变量〔a～z、常量〔0~9和二元运算符〔+,-,*,/,^〔乘幂。实现以下操作。ReadExpr<E>——以字符序列的形式输入语法正确的前缀表示式并构造表达式E。WriteExpr<E>——用带括弧的前缀表示式输出表达式E。Assign<V,c>——实现对变量V的赋值<V=c>,变量的初值为0。Value<E>——对算术表达式E求值。CompoundExpr<P,E1,E2>——构造一个新的复合表达式<E1>P<E2>。选作内容：增加常数合并操作MergeConst<E>-------合并表达式中E的所有常数运算。例如：表达式E=2+2*1-A进行合并常数的操作后,求得E=4-A〔2以表达式的原书写形式输入需求分析1．以字符序列的形式输入语法正确的中缀表示式并构造表达式E。即要根据正确的前缀式建立一棵二叉树T。2．用带括弧的前缀表达式输出表达式E。即要求在前缀遍历二叉树的时候考虑运算符的优先级,在适当的位置输出括弧。3．实现对变量V的赋值〔V＝c,变量的初值为0。那就在中缀遍历二叉树的过程中比较结点的值是否为V,找到V以后将c赋给V。4．对算术表达式E求值。如果表达式中有变量的话,首先提示用户表达式中变量,建议先执行操作3〔实现对变量V赋值,执行完后再回来执行表达式求值这一步骤。表达式求值利用递归,如果某个结点的值为运算符并且它的左右孩子结点的值为数据,那么就把〔左孩子〔运算符〔右孩子的结果赋给该结点。一层一层往上,最后只剩下一个根结点。此时根结点的值就是表达式E的值。5．构造一个新的复合表达式〔E1P〔E2。只要先构造表达式E1的二叉树和E2的二叉树,然后利用P把这两棵二叉树连接起来构成一棵新的二叉树。6．合并表达式E中所有常数运算。此原理类似于对表达式E求值,不同之处只在于该功能只对常数合并。概要设计1.树的抽象数据类型定义:ADTTree{数据对象D:D是具有相同特性的数据元素的集合。数据关系R:若D为空集,则称为空树；若D仅含一个数据元素,则R为空集,否则R={H},H是如下二元关系：在D中存在唯一的称为根的数据元素root,它在关系H下无前驱；若D-{root}≠ф,则存在D-{root}的一个划分D1,D2,…Dm<m>0>,对任意j≠k<1<=j,k<=m>有Dj∩Dk=ф,且对任意的i<1≤i≤m>,唯一存在数据元素Xi∈Di,有<root,Xi>∈H；对应于D-{root}≠ф的划分,H-{<root,Xi>…<root,Xm>}有唯一的一个划分H1,H2…Hm<m>0>,对任意j≠k<1<=j,k<=m>有Dj∩Dk=ф,且对任意的i<1≤i≤m>,Hi是Di上的二元关系,<Di,{Hi}>是一棵符合本定义的树,称为根的root的子树。基本操作:DoubleExpression<char*exp>;功能：算术表达式求值doublecalculate<doubleopnd1,charop,doubleopnd2>;功能：操作数四则运算voidpush<char,char,double,ExpressionCalculateStack*>;功能：入栈doublepop<char,ExpressionCalculateStack*>;功能：出栈voidGetNextNotation<char*notation,char*exp>;功能：读下一个运算符或操作数charGetTypeOfNotation<char*notation>;功能：判定是运算符或是操作数intCompareOpPrior<charop2,charop1>;功能：运算符优先级别比较BTNode*ReadExpr<chars[],inti,intj>功能：读入表达式voidWriteExpr<BTNode*b>功能：/把输入的表达式转换为相应的二叉树,并以前缀表达式的形式输出charSeek<chars[],intk>功能：判断是否有字母输入voidCompoundExpr<charE1[],charE2[],charp>功能：复合表达式voidAssign<chars[],chari,charj>功能：对变量进行复制}流程图：MMian函数对算术表达式求值查找式中的变量Seek以中缀方式输入表达式ReadExpr以前缀方式输出表达式WriteExpr对式中的变量进行复制Assign3菜单65412复合表达式对变量赋值,即执行步骤3NY是否有变量对算术表达式求值查找式中的变量Seek以中缀方式输入表达式ReadExpr以前缀方式输出表达式WriteExpr对式中的变量进行复制Assign3菜单65412复合表达式对变量赋值,即执行步骤3NY是否有变量常数合并常数合并程序清单：头文件〔MyExpression.h#include<stdio.h>#include<malloc.h>#include<string.h>#include<math.h>#include<conio.h>#defineMaxSize100typedefcharElemType;typedefstructnode{ElemTypedata;structnode*lchild;structnode*rchild;}BTNode;#defineMAX_EXP_LEN128/*表达式最大长度*/#defineMAX_NOTATION_NUM32/*一个表达式中的最大算符个数*/#defineMAX_NOTATION_LEN20/*表达式中一个算符的最大字串长度*/#defineNULL0typedefstructstack{/*表达式计算堆栈*/doubleOpdStack[MAX_NOTATION_NUM];/*操作数堆栈*/charOpStack[MAX_NOTATION_NUM];/*运算符堆栈*/intOpdStackTop,/*操作数堆栈顶指针*/OpStackTop;/*运算符堆栈顶指针*/}ExpressionCalculateStack;#defineOPND'D'/*操作数类型标志*/#defineOPTR'R'/*运算符类型标志*/#defineCONTINUE_READ_NEXT_NOTATION'C'/*表达式扫描标志,继续扫描*/#defineSTOP_READ_NEXT_NOTATION'S'/*表达式扫描标志,暂停扫描*//*部分子函数声明如下〔主要是表达式求值函数*/doubleExpression<char*exp>;/*算术表达式求值*/doublecalculate<doubleopnd1,charop,doubleopnd2>;/*操作数四则运算*/voidpush<char,char,double,ExpressionCalculateStack*>;/*入栈*/doublepop<char,ExpressionCalculateStack*>;/*出栈*/voidGetNextNotation<char*notation,char*exp>;/*读下一个运算符或操作数*/charGetTypeOfNotation<char*notation>;/*判定是运算符或是操作数*/intCompareOpPrior<charop2,charop1>;/*运算符优先级别比较*/源代码文件〔MyExpression.c#include"MyExpression.h"#include"stdlib.h"externdoubleExpression<char*oldexp>;externintCompareOpPrior<charop2,charop1>;externcharGetTypeOfNotation<char*notation>;externvoidGetNextNotation<char*notation,char*exp>;externdoublecalculate<doubleopnd1,charop,doubleopnd2>;externdoublepop<chartype,ExpressionCalculateStack*s>;externvoidpush<chartype,charop,doubleopnd,ExpressionCalculateStack*s>;BTNode*ReadExpr<chars[],inti,intj>{BTNode*p;intk,plus=0,posi;if<i==j>{p=<BTNode*>malloc<sizeof<BTNode>>;p->data=s[i];p->lchild=NULL;p->rchild=NULL;returnp;}//以下是i!=j的情况if<i!=j>{for<k=i;k<=j;k++> {if<s[k]=='+'||s[k]=='-'> { plus++; posi=k; }}if<plus==0>{ for<k=i;k<=j;k++> if<s[k]=='*'||s[k]=='/'> { plus++; posi=k; }} p=<BTNode*>malloc<sizeof<BTNode>>; p->data=s[posi]; p->lchild=ReadExpr<s,i,posi-1>; p->rchild=ReadExpr<s,posi+1,j>; returnp; // }}}voidWriteExpr<BTNode*b>//把输入的表达式转换为相应的二叉树,并以前缀表达式的形式输出{ if<b!=NULL> { printf<"%c",b->data>; if<b->lchild!=NULL||b->rchild!=NULL> { printf<"<">; WriteExpr<b->lchild>; if<b->rchild!=NULL> printf<",">; WriteExpr<b->rchild>; printf<">">; } }}charSeek<chars[],intk>//判断是否有字母输入{chara[1]={0};inti;for<i=0;i<=k;i++> if<s[i]>='A'&&s[i]<='Z'||s[i]>='a'&&s[i]<='z'> returna[0]='1';}voidAssign<chars[],chari,charj>{for<intp=0;p<=strlen<s>-1;p++> if<s[p]==i> s[p]=j;}voidCompoundExpr<charE1[],charE2[],charp>//复合表达式{charNewE[MaxSize],q[1];intk=0,i;BTNode*bt1,*bt2,*T;if<p=='+'||p=='-'>//复合函数为+或-是应怎样复合{for<i=0;i<strlen<E1>;i++> NewE[i]=E1[i]; NewE[strlen<E1>]=p; for<k=0;k<strlen<E2>;i++,k++> NewE[i+1]=E2[k]; NewE[i+1]='\0'; printf<"复合后的表达式为：%s\n\n",NewE>;printf<"其对应的二叉树为：">; T=ReadExpr<NewE ,0,strlen<NewE>-1>; WriteExpr<T>; printf<"\n">;}else{printf<"复合的表达式为：">;//复合符号为*或/是应该怎样复合这两个表达式bt1=ReadExpr<E1,0,strlen<E1>-1>;printf<"<">;WriteExpr<bt1>;printf<">">;printf<"%c",p>;bt2=ReadExpr<E2,0,strlen<E2>-1>;printf<"<">;WriteExpr<bt2>;printf<">">;printf<"\n">;}}voidConbination<chars[],intk>//对常数项进行合并{//intFX=0;if<s[k]=='*'>{if<<s[k-1]>='0'&&s[k-1]<='9'>&&<s[k+1]>='0'&&s[k+1]<='9'>>//判断是否为数字{/*FX=s[k-1]*s[k+1];s[k-1]=FX;*/ s[k-1]=<s[k-1]-48>*<s[k+1]-48>+48;for<inti=k;i<strlen<s>;i++> s[i]=s[i+2];}}if<s[k]=='/'>{if<<s[k-1]>='0'&&s[k-1]<='9'>&&<s[k+1]>='0'&&s[k+1]<='9'>>{s[k-1]=<s[k-1]-48>/<s[k+1]-48>+48;for<inti=k;i<strlen<s>;i++> s[i]=s[i+2];}}if<s[k]=='+'>{if<<s[k-1]>='0'&&s[k-1]<='9'>&&<s[k+1]>='0'&&s[k+1]<='9'>>{s[k-1]=<s[k-1]-48>+<s[k+1]-48>+48;for<inti=k;i<strlen<s>;i++> s[i]=s[i+2];}}if<s[k]=='-'>{if<<s[k-1]>='0'&&s[k-1]<='9'>&&<s[k+1]>='0'&&s[k+1]<='9'>>{s[k-1]=<s[k-1]-48>-<s[k+1]-48>+48;for<inti=k;i<strlen<s>;i++> s[i]=s[i+2];}}printf<"常数合并后为：%s",s>; }voidMergeConst<chars[]>//常数合并{inti,j,n;for<i=0;i<strlen<s>;i++>{if<s[i]=='*'||s[i]=='/'> Conbination<s,i>;}for<j=0;j<strlen<s>;j++>{if<s[j]=='+'||s[j]=='-'> Conbination<s,j>;}}voidmain<>{doublefx=0;BTNode*b;inti=0,j=0;chars[MaxSize],yesORno,value,getvalue,GetDigitl=NULL,p,E1[7],E2[3],e1,e2;printf<"\n\n表达式类型实现的使用说明：\n\n">;printf<"表达式暂时还不能进行括号操作,请不要输入括号,\n\n">;printf<"数字的输入只能是一位数〔0-9,字母的输入a-z或A-Z\n\n">;printf<"表达式输入时请按以下形式输入：A-S+D\n\n">;printf<"************************************\n\n">;printf<"1.输入表达式2.输出表达式\n\n">;printf<"3.对变量赋值4.对表达式求值\n\n">;printf<"5.复合表达式6.常数合并\n\n">;printf<"7.返回\n\n">;printf<"************************************\n\n">;printf<"请输入选择〔1-7">;while<<GetDigitl=getchar<>>!='7'>{switch<GetDigitl> {case'1':{printf<"\n\n请以中缀表达式形式输入表达式,例如a+b*c/d\n\n">;printf<"你的输入">;getchar<>;gets<s>;//以中缀表达式形式输入表达式printf<"\n">;printf<"你输入的表达式为:%s\n",s>;b=ReadExpr<s,0,strlen<s>-1>; printf<"\n请输入选择〔1-7\n">; break; } case'2': { printf<"\n对应的二叉树：">; WriteExpr<b>; printf<"\n\n">; printf<"\n请输入选择〔1-7\n">; break; } case'3': {while<<yesORno=Seek<s,strlen<s>-1>>=='1'> { printf<"表示式中有变量！\n">; getchar<>;printf<"需要赋值的变量：">; value=getchar<>; getchar<>; printf<"变量值：">; getvalue=getchar<>; Assign<s,value,getvalue>; } b=ReadExpr<s,0,strlen<s>-1>; printf<"\n对应的二叉树：">;WriteExpr<b>;printf<"\n请输入选择〔1-7\n">; break; } case'4': {yesORno=Seek<s,strlen<s>-1>; if<yesORno=='1'> printf<"表达式中有未知变量,请选择3进行变量赋值\n">; else { fx=Expression<s>;/*表达式求值*/printf<"\n表达式的运算结果为:%f\n",fx>; } printf<"\n请输入选择〔1-7\n">; break; } case'5': { printf<"请从〔+、-、*、/中选择一个作为复合符号\n">; printf<"你的选择是：">; getchar<>; p=getchar<>; printf<"\n">; printf<"请输入要复合的第一个表达式：">; getchar<>; gets<E1>; printf<"\n">; printf<"请输入要复合的第二个表达式:">; gets<E2>; printf<"\n">; CompoundExpr<E1,E2,p>;printf<"\n请输入选择〔1-7\n">; break; } case'6': {MergeConst<s>; printf<"\n请输入选择〔1-7\n">; break; }} }}//一下是表达式求值函数#include"MyExpression.h"doubleExpression<char*oldexp>//表达式计算函数,输入的是表达式字符串{charnotation[MAX_NOTATION_LEN],//存放当前符号扫描读入的符号op1,op2,exp[MAX_EXP_LEN];//存放当前操作表达式charflag=CONTINUE_READ_NEXT_NOTATION;//判别是否继续扫描下去intprior;//存放算符优先级别比较结果:op2<op1:-1op2>op1:1//op2=op1:0doubleopnd1,opnd2;//存放当前用于计算的2个操作数ExpressionCalculateStacks;//定义堆栈ss.OpdStackTop=s.OpStackTop=0;strcpy<exp,oldexp>;//把原表达式复制给当前操作表达式strcat<exp,"#">;//把‘#’接到exp后面,原exp最后面的‘\0’被取消push<OPTR,'#',0.0,&s>;//初始化表达式计算堆栈while<1>{if<flag==CONTINUE_READ_NEXT_NOTATION>GetNextNotation<notation,exp>;else/*有运算结果进操作数栈后*/flag=CONTINUE_READ_NEXT_NOTATION;if<GetTypeOfNotation<notation>==OPND>{opnd2=atof<notation>;push<OPND,NULL,opnd2,&s>;//操作数处理}else//运算符处理{op2=notation[0];op1=<char>pop<OPTR,&s>;//运算符出栈prior=CompareOpPrior<op2,op1>;if<prior<0>//op2<op1{push<OPTR,op1,0.0,&s>;//刚出栈的运算符再次进栈push<OPTR,op2,0.0,&s>;//当前运算符优先级别高,进栈}if<prior>0>//op2>op2{opnd2=pop<OPND,&s>;opnd1=pop<OPND,&s>;opnd2=calculate<opnd1,op1,opnd2>;push<OPND,NULL,opnd2,&s>;flag=STOP_READ_NEXT_NOTATION;///暂停读入下一个表达式符号//使当前运算符与栈顶运算符再作一次比较}if<prior==0>//op2=op1的情况处理{if<op2=='#'>returnpop<OPND,&s>;//结束运算,将运算结果从堆栈中弹出}}}}voidpush<chartype,charop,doubleopnd,ExpressionCalculateStack*s>{if<type==OPND>s->OpdStack[s->OpdStackTop++]=opnd;elses->OpStack[s->OpStackTop++]=op;}doublepop<chartype,ExpressionCalculateStack*s>{if<type==OPND>//是操作数栈returns->OpdStack[--s->OpdStackTop];else//是运算符栈return<double><s->OpStack[--s->OpStackTop]>;}doublecalculate<doubleopnd1,charop,doubleopnd2>{switch<op>{case'+':returnopnd1+opnd2;case'-':returnopnd1-opnd2;case'*':returnopnd1*opnd2;case'/':if<opnd2!=0.0>returnopnd1/opnd2;elsereturn0.0;}return0.0;}voidGetNextNotation<char*notation,char*exp>//读入下一个完整的符号:操作数或运算符{//把一个完整的操作数或运算符保存到notation[]staticinti=0;//变量i为表达式扫描的当前位置,注意其类型intj;chartype,lasttype=GetTypeOfNotation<exp+i>;for<j=0;exp[i]!='\0';j++,i++>{if<exp[i]==''>continue;notation[j]=exp[i];type=GetTypeOfNotation<notation+j>;if<type==OPTR&&lasttype==OPTR>{i++,j++;break;}//第一次读到的就是//运算符if<type==OPTR&&lasttype==OPND>break;//由读到的不是运算符转为读到的是运算符lasttype=type;}notation[j]=NULL;if<notation[0]=='#'>i=0;//表达式扫描完毕}charGetTypeOfNotation<char*notation>//判断一个字符是不是运算符{charopstr[]="+-*/<>#";//运算符集inti;if<notation[0]=='\0'>returnNULL;for<i=0;opstr[i]!='\0';i++>if<notation[0]==opstr[i]>returnOPTR;//'R'即是运算符returnOPND;//'D'即是操作数或小数点或其它如空格等}intCompareOpPrior<charop2,charop1>//2个先后出现的运算符优先级别比较：按P53表3.1//定{charopstr[]="+-*/<>#";inti,j;intpriortable[7][7]=//+-*/<>#{1,1,-1,-1,-1,1,1,1,1,-1,-1,-1,1,1,1,1,1,1,-1,1,1,1,1,1,1,-1,1,1,-1,-1,-1,-1,-1,0,'I',1,1,1,1,'I',1,1,-1,-1,-1,-1,-1,'I',0,};for<i=0;opstr[i]!='\0';i++>i