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

实习报告

题目：编写一个实现基于二叉树表示的算术表达式Expression操作程序 班级： 姓名： 学号： 完成日期// 一、 需求分析

算术表达式Expression内可以含有变量（a～z）、常量（0～9）和二元算术符（+,-,*,/,∧（乘幂））。实现以下操作：

（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 0 typedef int Status;

2、表达式的抽象数据类型定义 ADT Expression{

数据对象D：D是具有数值的常量C和没有数值的变量V；

数据关系：R={<(V或者C)P(V或者C)>|V,C∈D, <(V或者C)P(V或者C)>表示由运算符P结合起来的表达式E} 基本操作：

Status Input_Expr(&string,flag)

操作结果：以字符序列的形式输入语法正确的前缀表达式，保存到字符串string； 参数flag表示输出的提示信息是什么，输入成功返回OK，否则，返回ERROR。

void judge_value(&E,&string,i)

初始条件：树E存在，表达式的前缀字符串string存在；

。 1欢迎下载

精品文档

操作结果：判断字符string[i]，如果是'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 Expression

3、整体设计

1、顺序栈的基本操作：

对于栈SqStack:

Status InitStack(SqStack *S) Status StackEmpty(SqStack S)

/* 构造一个空栈S */

/* 若栈S为空栈，则返回TRUE，否则返回FALSE */

。 2欢迎下载

精品文档

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模块。

。 3欢迎下载

精品文档

主程序模块 二叉树模块 顺序栈SqStack1模块 顺序栈SqStack模块

三、 详细设计

1、二叉树的存储类型

/*二叉树结点类型*/

typedef enum{INT,CHAR}ElemTag;/*INT为整型数据num，CHAR为字符型数据c*/ typedef struct TElemType {

ElemTag tag;/*{INT,CHAR}指示是整型还是字符型*/ union {

int 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

。 4欢迎下载

精品文档

{

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);

/*判断字符string[i]，如果是'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);/*从键盘输入一串字符串作为表达式*/

。 5欢迎下载

精品文档

if(strlen(string)==1)/*输入的表达式字符串长度为1*/ {

if(string[0]=='+'||string[0]=='-'||string[0]=='*'||string[0]=='/'||string[0]=='^')/*输入的表达式只有一个运算符*/ {

printf(\"\\n表达式只有运算符，错误！\"); return ERROR; } else

if((string[0]>='0'&&string[0]<'9')||(string[0]>='a'&&string[0]<='z')||(string[0]>='A'&&string[0]<='Z'))/*输入的表达式只有一个数字或字符*/ {

printf(\"\\n表达式只有一个字符！\"); return OK; } else {

printf(\"\\n输入的字符不是运算符也不是变量常量，错误！\"); return ERROR; } }

return OK; }

void judge_value(BiTree *E,char *string,int i) {

if(string[i]>='0' && string[i]<='9')/*为常量*/ {

(*E)->data.tag=INT;

(*E)->data.num=string[i]-48; }

else if(string[i]>=1 && string[i]<=20)/*为常量，常量存于数组save_number中*/

{

(*E)->data.tag=INT;

(*E)->data.num=save_number[string[i]]; }

else/*为变量*/ {

(*E)->data.tag=CHAR; (*E)->data.c=string[i]; } }

。 6欢迎下载

精品文档

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);/*将exprstring[0]存入二叉树的结点中*/ } else {

judge_value(E,exprstring,0);/*将exprstring[0]存入二叉树的结点中*/ InitStack(&S);/*初始化栈*/ q=(*E);

Push(&S,q);/*入栈*/

Push(&S,q);/*入栈，根结点入栈两次是为判断先序输入的表达式是不是正确的表达式*/

for(i=1; ip=(BiTree)malloc(sizeof(BiTNode));

judge_value(&p,exprstring,i);/*将exprstring[i]存入二叉树的结点中*/ p->lchild=NULL; p->rchild=NULL;

if(exprstring[i]=='+' || exprstring[i]=='-' || exprstring[i]=='*' || exprstring[i]=='/' || exprstring[i]=='^')

{/*为运算符，运算符入栈，左孩子不空，向左孩子走，否则，如果右孩子不空，向右孩子走*/

if(!q->lchild) {

q->lchild=p; Push(&S,p); q=p; }

else {

q->rchild=p; Push(&S,p); q=p; } }

。 7欢迎下载

精品文档

else/*不是运算符，运算符出栈*/ {

if(!q->lchild) {

q->lchild=p; Pop(&S,&q); }

else {

q->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;

。 8欢迎下载

精品文档

} 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(\")\"); }/*带括弧输出左子树*/ else {

WriteExpr(E->lchild);/*否则，不带括弧输出左子树*/ } } else {

WriteExpr(E->lchild); }/*否则，输出左子树*/

if(E->data.tag==INT)/*访问输出根结点的值*/ {

printf(\"%d\ } else {

printf(\"%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);

。 9欢迎下载

精品文档

printf(\")\"); }/*带括弧输出右子树*/ else {

WriteExpr(E->rchild); }/*否则，不带括弧输出右子树*/ } else {

WriteExpr(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;i<=exp;i++) result*=x; return result; }

long Operate(int opr1,char opr,int opr2) {

long result; switch(opr) {

case '+':

result=opr1+opr2; return result;

。

10欢迎下载

精品文档

break; case '-':

result=opr1-opr2; return result; break; case '*':

result=opr1*opr2; return result; break; case '/':

result=opr1/opr2; return result; break; case '^':

result=power(opr1,opr2); return result; break; default: break; } }

Status Check(BiTree E) {

if(E&&E->data.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); /*结点的左孩子和右孩子为空，为叶子结点，返回结点的值*/

。

11欢迎下载

精品文档

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=string[len-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输入的表达式有误!\");

。

12欢迎下载

精品文档

return ERROR; } } }

else if(c==')')/*字符为')'，入栈*/ {

Push1(&S,c); }

else if(c>='0'&&c<='9')/*字符为'0'-'9'之间，循环扫描string前一个字符，后确定常量的大小*/ {

number=c-48;/*number为第一个常量字符的ASCII码-48*/

for(c1=string[i-1],j=1;(c1>='0'&&c1<='9')&&i>=0;j++,i--)/*循环扫描string前一个字符，求出常量后赋给number*/ {

number=(c1-48)*power(10,j)+number;/*number为扫描到的常量*/ c1=string[i-2]; }

save_number[char_number]=number;/*将number存入到数组save_number中，下标为char_number*/

*pre_expr++=char_number++; }

else if((c>='a'&&c<='z')||(c>='A'&&c<='Z'))/*字符为'a'-'z'或'A'-'Z'之间的变量*/

{/*string下一个字符不能为常量或变量，否则，出错*/

if((string[i-1]>='0'&&string[i-1]<='9')||(string[i-1]>='A'&&string[i-1]<='Z')||(string[i-1]>='a'&&string[i-1]<='z')) {

printf(\"\\n输入的表达式有误！\"); return ERROR; }

else

*pre_expr++=c; }

else if(c=='*'||c=='/')/*字符为运算符'*'或'/'*/ {

while(GetTop1(S,&c1)&&(c1=='^'))/*将c与栈顶的字符c1比较优先级*/ {

Pop1(&S,&c1); *pre_expr++=c1;

}/*如果c1比c优先，出栈*/ Push1(&S,c);/*入栈字符c*/ }

。

13欢迎下载

精品文档

else if(c=='+'||c=='-')/*字符为运算符'+'或'-'*/ {

while(GetTop1(S,&c1)&&(c1=='^'||c1=='*'||c1=='/'))/*将c与栈顶的字符c1比较优先级*/ {

Pop1(&S,&c1); *pre_expr++=c1;

}/*如果c1比c优先，出栈*/ Push1(&S,c);/*入栈运算符c*/ }

else if(c=='^')/*字符为运算符'^'*/ {

Push1(&S,c);/*入栈运算符'^'*/ } else {

printf(\"\\n输入的表达式有误！\"); return ERROR;

}/*其他字符，错误，返回ERROR*/ i--;/*下一个字符*/ if(i>=0)

c=string[i];/*i不小于0，c=string[i]循环下一个字符*/ else /*否则，将清空栈*/

while(!StackEmpty1(S)&&GetTop1(S,&c1)&&c1!='#') {

Pop1(&S,&c); *pre_expr++=c; } }

Pop1(&S,&c);/*将'#'出栈*/

*pre_expr='\\0';/*字符串结束符*/ if(i<0&&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;itemp=exprstring[i];

exprstring[i]=exprstring[j]; exprstring[j]=temp;

。

14欢迎下载

精品文档

} }

4、主程序和其他伪码算法

void main() {

BiTree E,E1;/*两个表达式E和E1*/

int flag=0;/*表达式E构造标志，为0表示未构造，为1表示已构造*/ long result;/*保存算数表达式运算结果*/ char V,P; int c;

char string[30]; char choice;

printf(\"\\n\============表达式类型的实现=============\"); printf(\"\\n\ 1:输入正确的前缀表达式\"); printf(\"\\n\ 2:输出带括弧的中缀表示式\"); printf(\"\\n\ 3:对变量进行赋值\"); printf(\"\\n\ 4:对算数表达式求值\");

printf(\"\\n\ 5:构造一个新的复合表达式\"); printf(\"\\n\ 0:退出\");

printf(\"\\n\=========================================\"); while(1) {

printf(\"\\n\请输入你的选择: \"); choice=getche(); switch(choice) {

case '1':/*1 >>>输入正确的前缀表达式*/ 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 {

。

15欢迎下载

精品文档

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\

Assign(&E,V,c,&Assign_flag); if(Assign_flag) {

printf(\"\\n赋值成功！\\n赋值后的表达式为:\"); WriteExpr(E); }

else printf(\"\\n表达式里没有%c这个变量！\ }

else printf(\"\\n表达式未构造成功！请重新构造表达式！\"); getch(); break;

case '4':/*4 >>>对算数表达式求值*/ if(flag==1) {

printf(\"\\n算数表达式:\"); WriteExpr(E); if(Check(E)) {

result=Value(E);

printf(\"\\n求算数表达式的值:\\"); WriteExpr(E);

printf(\"=%ld\ } }

else printf(\"\\n表达式未构造成功！请重新构造表达式！\"); getch(); break;

case '5':/*5 >>>构造一个新的复合表达式*/ if(flag==1)

。

16欢迎下载

精品文档

{

printf(\"\\n表达式E1为:\"); WriteExpr(E);

printf(\"\\n请构造新的表达式E2:\"); flushall();/*清理缓冲区*/ if(Input_Expr(string,1)) {

if(Read_Inorder_Expr(string,Expr_String)) {

reversal_string(Expr_String); if(ReadExpr(&E1,Expr_String)) {

flag=1;printf(\"\\n表达式E1构造成功！\");WriteExpr(E1);

printf(\"\\n请输入要构造新的复合表达式的操作运算符:\");

P=getchar();

while(P!='*'&&P!='/'&&P!='+'&&P!='-'&&P!='^') {

flushall();/*清理缓冲区*/

printf(\"\\n输入的操作运算符有误！请重新输入.\");

P=getchar(); }

CompoundExpr(P,&E,E1); }

else printf(\"\\n复合新的表达式失败！请按任意键返回主菜单！\");

} } }

else printf(\"\\n表达式未构造成功！请重新构造表达式！\"); getch(); break;

case '0':/*0 >>>退出*/

printf(\"\\n请按任意键退出！\"); getch(); exit(0); default :

printf(\"\\n输入有误！请按任意键回到主菜单重新选择！\"); getch(); break; } }

。

17欢迎下载

精品文档

}

5、函数的调用关系

除了主函数main()外，其他各个函数相对于其它函数来说是的，函数的使用都由主函数main()调用使用的，可以简单的说，各个函数都是主函数下的从函数。

四、 调试分析

1、在起初设计上，针对前缀表达式的要求构造表达式E，常量的范围限定在0-9之间，后在这个构造表达式的架构上逐个逐个实现对表达式上的操作；后扩展到以表达式的原书写形式输入，整体架构是不变的，只是增加一些细节的处理功能。这样的设计从开始到最后都处于可扩展的模块化设计。

2、在对各个功能操作的实现上，时间复杂度大多数是O(n)，空间上增加了辅助栈，空间复杂度为O(n+s)。而在以原表达式形式输入操作上，实际上是对字符串的操作，将一串原表达式字符串处理为前缀表达式字符串而已，算法时间复杂度取决于输入的字符串的长度n，即O(n)，空间复杂度为O(2n+s)。整体的算法设计没有什么可取之处，对于减少时间复杂度和空间复杂度上没有什么细细考虑。

3、在调试的过程中，花费时间最为多的是对输入错误表达式的出错处理，更改增加的代码几乎都是为了出错处理.

五、 用户手册

1、本程序的运行环境为DOS操作系统，执行文件为：tree.exe； 2、进入演示程序后首先出现一个主菜单，主菜单界面如下：

3、之后输入你的选择，进入你所要进行的操作中。

六、 测试结果 1

。

18欢迎下载

、

精品文档

2

、

。

19欢迎下载

精品文档

3、

4、

5、

。

20欢迎下载

精品文档

5、

。

21欢迎下载

精品文档

6、

七、 附录

源程序文件名清单： #include #include #include #include

。

22欢迎下载