树和二叉树——数据结构实验报告.doc

实习报告题目：编写一个实现基于二叉树表示的算术表达式Expression操作程序班级： 姓名： 学号： 完成日期/一、 需求分析算术表达式Expression内可以含有变量（az）、常量（09）和二元算术符（+,-,*,/,（乘幂）。实现以下操作： （1）ReadExpr(E)以字符序列的形式输入语法正确的前缀表达式并构造表达式E。 （2）WriteExpr(E)用带括号的中缀表达式输出表达式E。 （3）Assign(V，c)实现对变量V的赋值（V=c），变量的初值为0。 （4）Value(E)对算术表达式E求值。 （5）CompoundExpr(p,E1,E2)构造一个新的复合表达式（E1）p（E2）。二、 概要设计1、数据类型的声明：在这个课程设计中，采用了链表二叉树的存储结构，以及两个顺序栈的辅助存储结构/*头文件以及存储结构*/#include#include#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW 0typedef int Status;2、表达式的抽象数据类型定义ADT Expression数据对象D：D是具有数值的常量C和没有数值的变量V；数据关系：R=|V,CD, 表示由运算符P结合起来的表达式E基本操作：Status Input_Expr(&string,flag)操作结果：以字符序列的形式输入语法正确的前缀表达式，保存到字符串string； 参数flag表示输出的提示信息是什么，输入成功返回OK，否则，返回ERROR。void judge_value(&E,&string,i)初始条件：树E存在，表达式的前缀字符串string存在；操作结果：判断字符stringi，如果是0-9常量之间，二叉树结点E存为整型；否则，存为字符型。Status ReadExpr(&E,&exprstring)初始条件：表达式的前缀形式字符串exprstring存在；操作结果：以正确的前缀表示式exprstring并构造表达式E，构造成功，返回OK，否则返回ERROR。Status Pri_Compare(c1,c2)初始条件：c1和c2是字符；操作结果：如果两个字符是运算符，比较两个运算符的优先级，c1比c2优先，返回OK，否则返回ERROR。void WriteExpr(&E)初始条件：表达式E存在；操作条件：用带括弧的中缀表达式输入表达式E。void Assign(&E,V,c,&flag)初始条件：表达式E存在，flag为标志是否有赋值过；操作结果：实现对表达式E中的所有变量V的赋值(V=c)。long Operate(opr1,opr,opr2)初始条件：操作数opr1和操作数opr2以及操作运算符opr;操作结果：运算符运算求值，参数opr1,opr2为常量，opr为运算符，根据不同的运算符，实现不同的运算，返回运算结果。Status Check(E)初始条件：表达式E存在；操作结果：检查表达式E是否还存在没有赋值的变量，以便求算数表达式E的值。long Value(E)初始条件：表达式E存在；操作结果：对算术表达式求值，返回求到的结果。void CompoundExpr(P,&E1,E2)初始条件：表达式E1和E2存在；操作条件：构造一个新的复合表达式(E1)P(E2)。Status Read_Inorder_Expr(&string,&pre_expr)操作结果：以表达式的原书写形式输入，表达式的原书写形式字符串string变为字符串pre_expr，后调用reversal_string()函数反转得到前缀表达式pre_expr。得到正确的前缀表达式返回OK，否则，返回ERROR。void MergeConst(&E)操作结果：常数合并操作，合并表达式E中所有常数运算。ADT Expression3、整体设计1、顺序栈的基本操作：对于栈SqStack:Status InitStack(SqStack *S)/* 构造一个空栈S */Status StackEmpty(SqStack S)/* 若栈S为空栈，则返回TRUE，否则返回FALSE */Status Push(SqStack *S,SElemType e)/* 插入元素e为新的栈顶元素 */Status Pop(SqStack *S,SElemType *e) /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */Status GetTop(SqStack S,SElemType *e) /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */对于栈SqStack1:Status InitStack1(SqStack1 *S)/* 构造一个空栈S */Status StackEmpty1(SqStack1 S)/* 若栈S为空栈，则返回TRUE，否则返回FALSE */Status Push1(SqStack1 *S,SElemType1 e)/* 插入元素e为新的栈顶元素 */Status Pop1(SqStack1 *S,SElemType1 *e)/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */Status GetTop1(SqStack1 S,SElemType1 *e) /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */2、主程序模块的整体流程在主函数中，采用多分支程序设计语句switch()使程序产生不同的流向，从而达到实现课程设计的各个要求。void main() printf(n 1 输入正确的前缀表达式);printf(n 2 带括弧的中缀表示式输出);printf(n 3 对变量进行赋值);printf(n 4 对算数表达式求值);printf(n 5 构造一个新的复合表达式);printf(n 0 退出);while(1)switch( )根据不同的选择，调用不同的操作函数，完成各个操作；2、本程序有四个模块，主程序模块，二叉树模块，两个顺序栈模块。四者的调用关系如下：主程序模块中的对于表达式的存储结构调用了二叉树模块，而在构造表达式的二叉树模块中又调用了顺序栈SqStack模块，主程序中在将原表达式形式输入表达式转换为前缀表达式操作中调用了顺序栈SqStack1模块。主程序模块二叉树模块顺序栈SqStack模块顺序栈SqStack1模块三、 详细设计1、二叉树的存储类型/*二叉树结点类型*/typedef enumINT,CHARElemTag;/*INT为整型数据num，CHAR为字符型数据c*/typedef struct TElemTypeElemTag tag;/*INT,CHAR指示是整型还是字符型*/unionint num;/*tag=INT时，为整型*/char c;/*tag=CHAR时，为字符型*/; TElemType;/*二叉树的二叉链表存储表示 */typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; /* 左右孩子指针 */ BiTNode,*BiTree;二叉树的基本操作已经在构造表达式和表达式中的基本操作中根据不同的功能和实际情况修改了，详细见各个函数操作的算法设计。2、顺序栈的存储类型/*栈的顺序存储表示 */#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */#define STACKINCREMENT 2 /* 存储空间分配增量 */*两个顺序栈*/typedef struct SqStack SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */ SElemType *top; /* 栈顶指针 */ int stacksize; /* 当前已分配的存储空间，以元素为单位 */ SqStack; /* 顺序栈SqStack */typedef struct SqStack1 SElemType1 *base; /* 在栈构造之前和销毁之后，base的值为NULL */ SElemType1 *top; /* 栈顶指针 */ int stacksize; /* 当前已分配的存储空间，以元素为单位 */ SqStack1; /* 顺序栈SqStack1 */相关的基本操作见上面的“expression.h文件的整体结构”的说明，详细的算法设计见附录的程序清单。3、表达式的基本操作Status Input_Expr(char *string,int flag);/*以字符序列的形式输入语法正确的前缀表达式，保存到字符串string*/*参数flag=0表示输出的提示信息是请输入正确的前缀表示式：*/*flag=1表示输出的提示信息为请以表达式的原书写形式输入正确表示式：*/void judge_value(BiTree *E,char *string,int i);/*判断字符stringi，如果是0-9常量之间，二叉树结点存为整型；否则，存为字符型*/Status ReadExpr(BiTree *E,char *exprstring);/*以正确的前缀表示式并构造表达式E*/Status Pri_Compare(char c1,char c2);/*如果两个字符是运算符，比较两个运算符的优先级，c1比c2优先，返回OK，否则返回ERROR*/void WriteExpr(BiTree E);/*用带括弧的中缀表达式输入表达式*/void Assign(BiTree *E,char V,int c,int *flag);/*实现对表达式中的所有变量V的赋值(V=c)，参数flag为表示是否赋值过的标志*/long Operate(int opr1,char opr,int opr2);/*运算符运算求值，参数opr1,opr2为常量，opr为运算符，根据不同的运算符，实现不同的运算，返回运算结果*/Status Check(BiTree E);/*检查表达式是否还存在没有赋值的变量，以便求算数表达式的值*/long Value(BiTree E);/*对算术表达式求值*/void CompoundExpr(char P,BiTree *E1,BiTree E2);/*构造一个新的复合表达式*/Status Read_Inorder_Expr(char *string,char *pre_expr);/*以表达式的原书写形式输入，表达式的原书写形式字符串string变为字符串pre_expr，后调用reversal_string()函数反转得到前缀表达式pre_expr*/下面列出部分基本操作的伪码算法，未列出的请见程序清单。其中部分基本操作的伪码算法如下：Status Input_Expr(char *string,int flag)if(flag=0)printf(n请输入正确的前缀表示式：);else printf(n请以表达式的原书写形式输入正确表示式：);flushall();/*清理缓冲区*/gets(string);/*从键盘输入一串字符串作为表达式*/if(strlen(string)=1)/*输入的表达式字符串长度为1*/if(string0=+|string0=-|string0=*|string0=/|string0=)/*输入的表达式只有一个运算符*/ printf(n表达式只有运算符，错误！);return ERROR;else if(string0=0&string0=a&string0=A&string0=0 & stringidata.tag=INT;(*E)-data.num=stringi-48;else if(stringi=1 & stringidata.tag=INT;(*E)-data.num=save_numberstringi;else/*为变量*/(*E)-data.tag=CHAR;(*E)-data.c=stringi;Status ReadExpr(BiTree *E,char *exprstring)SqStack S;int i,len;/*len为表达式的长度*/BiTree p,q;(*E)=(BiTree)malloc(sizeof(BiTNode);/*申请二叉树的根结点的空间*/(*E)-lchild=NULL;(*E)-rchild=NULL;len=strlen(exprstring);/*len赋值为表达式的长度*/if(len=1)/*表达式长度为1时，二叉树只有根结点*/judge_value(E,exprstring,0);/*将exprstring0存入二叉树的结点中*/else judge_value(E,exprstring,0);/*将exprstring0存入二叉树的结点中*/InitStack(&S);/*初始化栈*/q=(*E);Push(&S,q);/*入栈*/Push(&S,q);/*入栈，根结点入栈两次是为判断先序输入的表达式是不是正确的表达式*/for(i=1; ilchild=NULL;p-rchild=NULL;if(exprstringi=+ | exprstringi=- | exprstringi=* | exprstringi=/ | exprstringi=)/*为运算符，运算符入栈，左孩子不空，向左孩子走，否则，如果右孩子不空，向右孩子走*/if(!q-lchild)q-lchild=p;Push(&S,p);q=p;elseq-rchild=p;Push(&S,p);q=p;else/*不是运算符，运算符出栈*/if(!q-lchild)q-lchild=p;Pop(&S,&q);elseq-rchild=p;Pop(&S,&q);if(StackEmpty(S)&i=len)return OK;/*栈空且i=len，说明输入的表达式是正确的*/else/*输入的表达式是错误的*/printf(n输入的表达式有误！);return ERROR;Status Pri_Compare(char c1,char c2)if(c1=|c1=*|c1=-|c1=+|c1=/)&(c2=|c2=*|c2=-|c2=+|c2=/)if(c1=)if(c2!=) return OK;else return ERROR;else if(c1=*|c1=/)if(c2=|c2=*|c2=/) return ERROR;else return OK;else return ERROR;else return ERROR;/*c1和c2不是运算符*/void WriteExpr(BiTree E)if(E)/*树不为空*/*先递归左子树*/if( E-lchild & E-lchild-data.tag=CHAR )/*E的左孩子不为空，且左孩子为字符*/if(Pri_Compare(E-data.c,E-lchild-data.c)/*E-data.c比E-lchild-data.c优先*/printf();WriteExpr(E-lchild);printf();/*带括弧输出左子树*/elseWriteExpr(E-lchild);/*否则，不带括弧输出左子树*/else WriteExpr(E-lchild);/*否则，输出左子树*/if(E-data.tag=INT)/*访问输出根结点的值*/printf(%d,E-data.num);elseprintf(%c,E-data.c);/*后递归右子树*/if(E-rchild&E-rchild-data.tag=CHAR)/*E的右孩子不为空，且右孩子为字符*/if(Pri_Compare(E-data.c,E-rchild-data.c)/*E-data.c比E-rchild-data.c优先*/printf();WriteExpr(E-rchild);printf();/*带括弧输出右子树*/elseWriteExpr(E-rchild);/*否则，不带括弧输出右子树*/elseWriteExpr(E-rchild);/*否则，输出右子树*/void Assign(BiTree *E,char V,int c,int *flag)if(*E)if(*E)-data.tag=CHAR & (*E)-data.c=V)/*如果找到要赋值的变量，赋值*/(*E)-data.tag=INT;(*E)-data.num=c;*flag=1;Assign(&(*E)-lchild),V,c,flag);/*递归左子树*/Assign(&(*E)-rchild),V,c,flag);/*递归左子树*/long power(int x,int exp)/*指数运算函数，底数为x，指数为exp*/long result;int i;for(i=1,result=1;idata.tag=CHAR)/*树不为空*/if(E-data.c!=*&E-data.c!=&E-data.c!=-&E-data.c!=+&E-data.c!=/)printf(n表达式中仍存在没有赋值的变量!);return ERROR;if(Check(E-lchild)/*递归左子树*/Check(E-rchild);/*递归右子树*/long Value(BiTree E)if(E)/*树不为空*/if(!E-lchild & !E-rchild & E-data.tag=INT) return (E-data.num);/*结点的左孩子和右孩子为空，为叶子结点，返回结点的值*/return Operate(Value(E-lchild),E-data.c,Value(E-rchild);/*运算求值，后根遍历的次序对表达式求值，其中参数递归调用了Value()函数求左子树的值和右子树的值*/void CompoundExpr(char P,BiTree *E1,BiTree E2)/*构造一个新的复合表达式=CompoundExpr=*/BiTree E;E=(BiTree)malloc(sizeof(BiTNode);/*申请一个结点存放运算符P*/E-data.tag=CHAR;E-data.c=P;/*申请到的结点值为P*/E-lchild=(*E1);/*结点的左孩子为E1*/E-rchild=E2;/*结点的右孩子为E2*/(*E1)=E;/*(*E1)为根结点*/printf(n表达式E复合成功！其表达式变为: );WriteExpr(E);/*输出复合好的表达式*/Status Read_Inorder_Expr(char *string,char *pre_expr)int i,j,len,char_number=1;/*len表示字符串string的长度，char_number是记录数组save_number的个数*/int number;/*保存大于9的常量*/char c,c1;SqStack1 S;/*栈定义*/InitStack1(&S);/*初始栈*/Push1(&S,#);/*先将字符#入栈，用来表示作为栈的最底一个元素*/len=strlen(string);/*len为字符串string的长度*/c=stringlen-1;/*从字符串的最后一个字符开始向前扫描*/i=len-1;while(!StackEmpty1(S)&i=0)/*栈不为空且i大于等于0*/if(c=()/*字符为(*/Pop1(&S,&c);/*出栈，赋值给c*/while(c!=)/*假如c不为),出栈*/*pre_expr+=c;if(!StackEmpty1(S)&GetTop1(S,&c1)&c1!=#) Pop1(&S,&c);else printf(n输入的表达式有误!);return ERROR;else if(c=)/*字符为)，入栈*/Push1(&S,c);else if(c=0&c=0&c1=0;j+,i-)/*循环扫描string前一个字符，求出常量后赋给number*/number=(c1-48)*power(10,j)+number;/*number为扫描到的常量*/c1=stringi-2;save_numberchar_number=number;/*将number存入到数组save_number中，下标为char_number*/*pre_expr+=char_number+;else if(c=a&c=A&c=0&stringi-1=A&stringi-1=a&stringi-1=0) c=stringi;/*i不小于0，c=stringi循环下一个字符*/else /*否则，将清空栈*/while(!StackEmpty1(S)&GetTop1(S,&c1)&c1!=#)Pop1(&S,&c);*pre_expr+=c;Pop1(&S,&c);/*将#出栈*/*pre_expr=0;/*字符串结束符*/if(i0&StackEmpty1(S)return OK;else return ERROR;void reversal_string(char *exprstring)/*将字符串exprstring反转过来*/int len,i,j;char temp;len=strlen(exprstring);/*len为exprstring的长度*/for(i=0,j=len-1;i输入正确的前缀表达式*/if(Input_Expr(Expr_String,0)if(ReadExpr(&E,Expr_String)flag=1;printf(输入的带括弧的中缀表达式：);WriteExpr(E);getch();break;case 2:/*2 带括弧的中缀表示式输出*/if(flag=1) printf(n带括弧的中缀表达式为：);WriteExpr(E);else printf(n表达式未构造成功！请重新构造表达式！);getch();break;case 3:/*3 对变量进行赋值*/if(flag=1)int Assign_flag=0;printf(n表达式E为:);WriteExpr(E);flushall();/*清理缓冲区*/printf(n请输入要赋值的值:);V=getchar();printf(请输入要将赋值为:);scanf(%d,&c);Assign(&E,V,c,&Assign_flag);if(Assign_flag)printf(n赋值成功！n赋值后的表达式为:);WriteExpr(E);else printf(n表达式里没有%c这个变量！,V);else printf(n表达式未构造成功！请重新构造表达式！);getch();break;case 4:/*4 对算数表达式求值*/if(flag=1)printf(n算数表达式:);WriteExpr(E);if(Check(E) result=Value(E);printf(n求算数表达式的值:t);WriteExpr(E);printf(=%ld,result);else printf(n表达式未构造成功！请重新构造表达式！);getch();break;case 5:/*5 构造一个新的复合表达式*/if(flag=1)printf(n表达式E1为:);WriteExpr(E);printf(n请构造新的表达式E2:);flushall();/*清理缓冲区*/if(Input_Expr(stri