数据结构实验报告

1、课程设计实验报告实验名称：表达式类型的实现编译环境：硬件:PC软件：VS2010问题描述 一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式Expression的操作。基本要求假设算术表达式Expression可以含有变量（az）、常量（09）和二元运算符（+，-，*，/，（乘幂）。实现以下操作。（1） ReadExpr(E)以字符序列的形式输入语法正确的前缀表示式并构造表达式E。（2） WriteExpr(E)用带括弧的前缀表示式输出表达式E。（3） Assign(V，c)实现对变量V的赋值(V=c)，变量的初值为0。（4） Value(E)对算术表

2、达式E求值。（5） CompoundExpr(P，E1，E2)构造一个新的复合表达式(E1)P(E2)。选作内容：（1） 增加常数合并操作MergeConst(E)-合并表达式中E的所有常数运算。例如：表达式E=2+2*1-A进行合并常数的操作后，求得E=4-A （2）以表达式的原书写形式输入需求分析1以字符序列的形式输入语法正确的中缀表示式并构造表达式E。即要根据正确的前缀式建立一棵二叉树T。 2用带括弧的前缀表达式输出表达式E。即要求在前缀遍历二叉树的时候考虑运算符的优先级，在适当的位置输出括弧。3实现对变量V的赋值（Vc），变量的初值为0。那就在中缀遍历二叉树的过程中比较结点的值是否为V

3、，找到V以后将c赋给V。4对算术表达式E求值。如果表达式中有变量的话，首先提示用户表达式中变量，建议先执行操作3（实现对变量V赋值），执行完后再回来执行表达式求值这一步骤。表达式求值利用递归，如果某个结点的值为运算符并且它的左右孩子结点的值为数据，那么就把（左孩子）（运算符）（右孩子）的结果赋给该结点。一层一层往上，最后只剩下一个根结点。此时根结点的值就是表达式E的值。5构造一个新的复合表达式（E1）P（E2）。只要先构造表达式E1的二叉树和E2的二叉树，然后利用P把这两棵二叉树连接起来构成一棵新的二叉树。6合并表达式E中所有常数运算。此原理类似于对表达式E求值，不同之处只在于该功能只对常数合

4、并。概要设计1. 树的抽象数据类型定义:ADT Tree数据对象 D: D是具有相同特性的数据元素的集合。数据关系 R: 若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则R=H,H是如下二元关系：(1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2) 若D-root,则存在D-root的一个划分D1,D2,Dm(m>0),对任意jk(1<=j,k<=m)有DjDk = ，且对任意的i(1im),唯一存在数据元素XiDi，有<root,Xi>H；(3) 对应于D-root的划分，H - <root,Xi><roo

5、t,Xm>有唯一的一个划分H1,H2Hm(m>0)，对任意jk(1<=j,k<=m)有DjDk = ，且对任意的i(1im)，Hi是Di上的二元关系，(Di,Hi)是一棵符合本定义的树，称为根的root的子树。基本操作: Double Expression (char *exp);功能： 算术表达式求值 double calculate (double opnd1,char op,double opnd2 ); 功能： 操作数四则运算 void push( char , char, double , ExpressionCalculateStack *); 功能：入栈

6、double pop ( char , ExpressionCalculateStack *); 功能：出栈 void GetNextNotation ( char *notation,char *exp); 功能：读下一个运算符或操作数 char GetTypeOfNotation( char *notation ); 功能：判定是运算符或是操作数int CompareOpPrior(char op2, char op1); 功能：运算符优先级别比较 BTNode *ReadExpr(char s,int i,int j)功能：读入表达式void WriteExpr(BTNode *b) 功

7、能：/把输入的表达式转换为相应的二叉树，并以前缀表达式的形式输出char Seek(char s,int k)功能：判断是否有字母输入void CompoundExpr(char E1,char E2,char p)功能：复合表达式void Assign(char s,char i,char j)功能：对变量进行复制流程图：Mian函数对算术表达式求值查找式中的变量Seek以中缀方式输入表达式ReadExpr以前缀方式输出表达式WriteExpr对式中的变量进行复制Assign3菜单65412复合表达式对变量赋值，即执行步骤3NY是否有变量 常数合并程序清单：头文件（MyExpression.

8、h）#include<stdio.h>#include<malloc.h>#include<string.h>#include<math.h>#include<conio.h>#define MaxSize 100typedef char ElemType;typedef struct node ElemType data; struct node *lchild; struct node *rchild;BTNode;#define MAX_EXP_LEN 128 /* 表达式最大长度 */#define MAX_NOTATION_

9、NUM 32 /* 一个表达式中的最大算符个数 */#define MAX_NOTATION_LEN 20 /* 表达式中一个算符的最大字串长度 */#define NULL 0typedef struct stack /* 表达式计算堆栈 */ double OpdStackMAX_NOTATION_NUM; /* 操作数堆栈 */ char OpStackMAX_NOTATION_NUM; /* 运算符堆栈 */ int OpdStackTop, /* 操作数堆栈顶指针 */ OpStackTop; /* 运算符堆栈顶指针 */ ExpressionCalculateStack;#defi

10、ne OPND 'D' /* 操作数类型标志 */#define OPTR 'R' /* 运算符类型标志 */#define CONTINUE_READ_NEXT_NOTATION 'C' /* 表达式扫描标志，继续扫描 */#define STOP_READ_NEXT_NOTATION 'S' /* 表达式扫描标志，暂停扫描 */* 部分子函数声明如下 （主要是表达式求值函数）*/double Expression(char *exp); /* 算术表达式求值 */double calculate (double opnd1,c

11、har op,double opnd2 ); /* 操作数四则运算 */void push( char , char, double , ExpressionCalculateStack *); /* 入栈 */double pop ( char , ExpressionCalculateStack *); /* 出栈 */void GetNextNotation ( char *notation,char *exp); /* 读下一个运算符或操作数 */char GetTypeOfNotation( char *notation ); /* 判定是运算符或是操作数 */int Compare

12、OpPrior(char op2, char op1); /* 运算符优先级别比较 */源代码文件（MyExpression.c）#include"MyExpression.h"#include"stdlib.h"extern double Expression(char *oldexp) ;extern int CompareOpPrior(char op2, char op1);extern char GetTypeOfNotation( char *notation ) ;extern void GetNextNotation (char *not

13、ation,char *exp);extern double calculate(double opnd1,char op,double opnd2 );extern double pop(char type,ExpressionCalculateStack *s);extern void push(char type, char op,double opnd,ExpressionCalculateStack *s);BTNode *ReadExpr(char s,int i,int j) BTNode *p; int k,plus=0,posi; if(i=j) p=(BTNode *)ma

14、lloc(sizeof(BTNode); p->data=si; p->lchild=NULL; p->rchild=NULL; return p; /以下是i!=j的情况if(i!=j) for(k=i;k<=j;k+) if(sk='+'|sk='-') plus+; posi=k; if(plus=0) for(k=i;k<=j;k+) if(sk='*'|sk='/') plus+; posi=k; p=(BTNode *)malloc(sizeof(BTNode); p->data=s

15、posi; p->lchild=ReadExpr(s,i,posi-1); p->rchild=ReadExpr(s,posi+1,j); return p;/ void WriteExpr(BTNode *b) /把输入的表达式转换为相应的二叉树，并以前缀表达式的形式输出if(b!=NULL) printf("%c",b->data);if(b->lchild!=NULL|b->rchild!=NULL) printf("("); WriteExpr(b->lchild ); if(b->rchild!=NUL

16、L) printf(","); WriteExpr(b->rchild); printf(")");char Seek(char s,int k)/判断是否有字母输入 char a1=0; int i; for(i=0;i<=k;i+) if(si>='A'&&si<='Z'|si>='a'&&si<='z') return a0='1'void Assign(char s,char i,char j) fo

17、r(int p=0;p<=strlen(s)-1;p+) if(sp=i) sp=j;void CompoundExpr(char E1,char E2,char p)/复合表达式char NewEMaxSize,q1; int k=0,i; BTNode *bt1,*bt2,*T; if(p='+'|p='-')/复合函数为+或-是应怎样复合 for( i=0;i<strlen(E1);i+)NewEi=E1i;NewEstrlen(E1)=p;for( k=0;k<strlen(E2);i+,k+) NewEi+1=E2k; NewEi+1

18、='0'printf("复合后的表达式为：%snn",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(")"

19、;); printf("%c",p); bt2=ReadExpr(E2,0,strlen(E2)-1); printf("("); WriteExpr(bt2); printf(")"); printf("n"); void Conbination(char s,int k)/对常数项进行合并/int FX=0; if(sk='*') if(sk-1>='0'&&sk-1<='9')&&(sk+1>='0

20、9;&&sk+1<='9') /判断是否为数字 /*FX=sk-1*sk+1; sk-1=FX;*/ sk-1=(sk-1-48)*(sk+1-48)+48; for(int i=k;i<strlen(s);i+) si=si+2; if(sk='/') if(sk-1>='0'&&sk-1<='9')&&(sk+1>='0'&&sk+1<='9') sk-1=(sk-1-48)/(sk+1-48)+

21、48; for(int i=k;i<strlen(s);i+) si=si+2; if(sk='+') if(sk-1>='0'&&sk-1<='9')&&(sk+1>='0'&&sk+1<='9') sk-1=(sk-1-48)+(sk+1-48)+48; for(int i=k;i<strlen(s);i+) si=si+2; if(sk='-') if(sk-1>='0'&&

22、;sk-1<='9')&&(sk+1>='0'&&sk+1<='9') sk-1=(sk-1-48)-(sk+1-48)+48; for(int i=k;i<strlen(s);i+) si=si+2; printf("常数合并后为：%s",s);void MergeConst(char s)/常数合并 int i,j,n; for(i=0;i<strlen(s);i+) if(si='*'|si='/') Conbination(s

23、,i); for(j=0;j<strlen(s);j+) if(sj='+'|sj='-') Conbination(s,j); void main()double fx=0; BTNode *b; int i=0,j=0; char sMaxSize, yesORno,value,getvalue,GetDigitl=NULL,p,E17,E23,e1,e2; printf(" nn 表达式类型实现的使用说明：nn"); printf(" 表达式暂时还不能进行括号操作，请不要输入括号，nn"); printf(&q

24、uot; 数字的输入只能是一位数（0-9），字母的输入a-z或A-Znn"); printf(" 表达式输入时请按以下形式输入：A-S+Dnn"); printf("*nn"); printf(" 1.输入表达式 2.输出表达式nn"); printf(" 3.对变量赋值 4.对表达式求值nn"); printf(" 5.复合表达式 6.常数合并nn"); printf(" 7.返回nn"); printf("*nn"); printf(&quo

25、t;请输入选择（1-7）"); while(GetDigitl=getchar()!='7') switch(GetDigitl) case '1': printf("nn请以中缀表达式形式输入表达式，例如a+b*c/dnn"); printf("你的输入");getchar(); gets(s); /以中缀表达式形式输入表达式 printf("n"); printf("你输入的表达式为:%sn",s); b=ReadExpr(s,0,strlen(s)-1);printf

26、("n请输入选择（1-7）n"); break; case '2': printf("n对应的二叉树：");WriteExpr(b);printf("nn");printf("n请输入选择（1-7）n"); break; case '3': while(yesORno=Seek(s,strlen(s)-1)='1')printf("表示式中有变量！n");getchar(); printf("需要赋值的变量："); value=

27、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("表达式中有未知变量

28、，请选择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("请输入要复合的第一个表达式：&q

29、uot;);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"doubl

30、e Expression(char *oldexp) /表达式计算函数，输入的是表达式字符串 char notationMAX_NOTATION_LEN, / 存放当前符号扫描读入的符号 op1,op2, expMAX_EXP_LEN; / 存放当前操作表达式 char flag=CONTINUE_READ_NEXT_NOTATION; /判别是否继续扫描下去 int prior; /存放算符优先级别比较结果: op2<op1 :-1 op2>op1 : 1 /op2=op1 : 0 double opnd1,opnd2; / 存放当前用于计算的2个操作数 ExpressionCa

31、lculateStack s; /定义堆栈s s.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=CON

32、TINUE_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); /刚出栈的运

33、算符再次进栈 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 的情况处理

34、if( op2='#')return pop(OPND,&s) ;/结束运算，将运算结果从堆栈中弹出 void push(char type, char op,double opnd,ExpressionCalculateStack *s) if(type=OPND) s->OpdStacks->OpdStackTop+= opnd; else s->OpStacks->OpStackTop+ = op;double pop(char type,ExpressionCalculateStack *s) if(type=OPND) / 是操作数栈

35、return s->OpdStack-s->OpdStackTop; else / 是运算符栈 return (double) (s->OpStack-s->OpStackTop);double calculate(double opnd1,char op,double opnd2 ) switch(op) case '+': return opnd1+opnd2; case '-': return opnd1-opnd2; case '*': return opnd1*opnd2; case '/': i

36、f( opnd2!=0.0) return opnd1/opnd2; else return 0.0; return 0.0;void GetNextNotation (char *notation,char *exp) / 读入下一个完整的符号:操作数或运算符 / 把一个完整的操作数或运算符保存到notation static int i=0; / 变量i为表达式扫描的当前位置,注意其类型 int j; char type,lasttype = GetTypeOfNotation( exp+i ); for( j=0; expi!='0' ; j+,i+ ) if( expi

37、=' ' )continue; notationj=expi; type=GetTypeOfNotation( notation+j ); if( type=OPTR && lasttype=OPTR ) i+, j+; break; /第一次读到的就是/运算符 if( type=OPTR && lasttype=OPND ) break; /由读到的不是运算符转为读到的是运算符 lasttype=type; notationj=NULL; if( notation0='#') i=0; /表达式扫描完毕 char GetType

38、OfNotation( char *notation ) /判断一个字符是不是运算符 char opstr="+-*/()#" /运算符集 int i; if( notation0='0' ) return NULL; for (i=0; opstri!='0'i+) if( notation0=opstri) return OPTR; /'R' 即是运算符 return OPND; / 'D' 即是操作数或小数点或其它如空格等 int CompareOpPrior(char op2, char op1) /2

39、个先后出现的运算符优先级别比较：按P53表3.1/定 char opstr="+-*/()#" int i,j; int priortable77= / + - * / ( ) # 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; opstri!='0' i+ ) if( op1=opstri ) break; for( j=0; opstrj!='0' j+ ) if( op2=opstrj ) break; return priortableij;测试分析与用户使用步骤：出初始界面如下数据测