树和二叉树数据结构实验报告 2.docx
- 文档编号:9203489
- 上传时间:2023-05-17
- 格式:DOCX
- 页数:34
- 大小:275.90KB
树和二叉树数据结构实验报告 2.docx
《树和二叉树数据结构实验报告 2.docx》由会员分享,可在线阅读,更多相关《树和二叉树数据结构实验报告 2.docx(34页珍藏版)》请在冰点文库上搜索。
树和二叉树数据结构实验报告2
实习报告
题目:
编写一个实现基于二叉树表示的算术表达式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
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineOVERFLOW0
typedefintStatus;
2、表达式的抽象数据类型定义
ADTExpression{
数据对象D:
D是具有数值的常量C和没有数值的变量V;
数据关系:
R={<(V或者C)P(V或者C)>|V,C∈D,<(V或者C)P(V或者C)>表示由运算符P结合起来的表达式E}
基本操作:
StatusInput_Expr(&string,flag)
操作结果:
以字符序列的形式输入语法正确的前缀表达式,保存到字符串string;参数flag表示输出的提示信息是什么,输入成功返回OK,否则,返回ERROR。
voidjudge_value(&E,&string,i)
初始条件:
树E存在,表达式的前缀字符串string存在;
操作结果:
判断字符string[i],如果是'0'-'9'常量之间,二叉树结点E存为整型;否则,存为字符型。
StatusReadExpr(&E,&exprstring)
初始条件:
表达式的前缀形式字符串exprstring存在;
操作结果:
以正确的前缀表示式exprstring并构造表达式E,构造成功,返回OK,否则返回ERROR。
StatusPri_Compare(c1,c2)
初始条件:
c1和c2是字符;
操作结果:
如果两个字符是运算符,比较两个运算符的优先级,c1比c2优先,返回OK,否则返回ERROR。
voidWriteExpr(&E)
初始条件:
表达式E存在;
操作条件:
用带括弧的中缀表达式输入表达式E。
voidAssign(&E,V,c,&flag)
初始条件:
表达式E存在,flag为标志是否有赋值过;
操作结果:
实现对表达式E中的所有变量V的赋值(V=c)。
longOperate(opr1,opr,opr2)
初始条件:
操作数opr1和操作数opr2以及操作运算符opr;
操作结果:
运算符运算求值,参数opr1,opr2为常量,opr为运算符,根据不同的运算符,实现不同的运算,返回运算结果。
StatusCheck(E)
初始条件:
表达式E存在;
操作结果:
检查表达式E是否还存在没有赋值的变量,以便求算数表达式E的值。
longValue(E)
初始条件:
表达式E存在;
操作结果:
对算术表达式求值,返回求到的结果。
voidCompoundExpr(P,&E1,E2)
初始条件:
表达式E1和E2存在;
操作条件:
构造一个新的复合表达式(E1)P(E2)。
StatusRead_Inorder_Expr(&string,&pre_expr)
操作结果:
以表达式的原书写形式输入,表达式的原书写形式字符串string变为字符串pre_expr,后调用reversal_string()函数反转得到前缀表达式pre_expr。
得到正确的前缀表达式返回OK,否则,返回ERROR。
voidMergeConst(&E)
操作结果:
常数合并操作,合并表达式E中所有常数运算。
}ADTExpression
3、整体设计
1、顺序栈的基本操作:
对于栈SqStack:
StatusInitStack(SqStack*S)/*构造一个空栈S*/
StatusStackEmpty(SqStackS)/*若栈S为空栈,则返回TRUE,否则返回FALSE*/
StatusPush(SqStack*S,SElemTypee)/*插入元素e为新的栈顶元素*/
StatusPop(SqStack*S,SElemType*e)/*若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR*/
StatusGetTop(SqStackS,SElemType*e)/*若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR*/
对于栈SqStack1:
StatusInitStack1(SqStack1*S)/*构造一个空栈S*/
StatusStackEmpty1(SqStack1S)/*若栈S为空栈,则返回TRUE,否则返回FALSE*/
StatusPush1(SqStack1*S,SElemType1e)/*插入元素e为新的栈顶元素*/
StatusPop1(SqStack1*S,SElemType1*e)/*若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR*/
StatusGetTop1(SqStack1S,SElemType1*e)/*若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR*/
2、主程序模块的整体流程
在主函数中,采用多分支程序设计语句switch()使程序产生不同的流向,从而达到实现课程设计的各个要求。
voidmain()
{
printf("\n1>>>输入正确的前缀表达式");
printf("\n2>>>带括弧的中缀表示式输出");
printf("\n3>>>对变量进行赋值");
printf("\n4>>>对算数表达式求值");
printf("\n5>>>构造一个新的复合表达式");
printf("\n0>>>退出");
while
(1)
{
switch()
{
根据不同的选择,调用不同的操作函数,完成各个操作;
}
}
}
2、本程序有四个模块,主程序模块,二叉树模块,两个顺序栈模块。
四者的调用关系如下:
主程序模块中的对于表达式的存储结构调用了二叉树模块,而在构造表达式的二叉树模块中又调用了顺序栈SqStack模块,主程序中在将原表达式形式输入表达式转换为前缀表达式操作中调用了顺序栈SqStack1模块。
三、详细设计
1、二叉树的存储类型
/*二叉树结点类型*/
typedefenum{INT,CHAR}ElemTag;/*INT为整型数据num,CHAR为字符型数据c*/
typedefstructTElemType
{
ElemTagtag;/*{INT,CHAR}指示是整型还是字符型*/
union
{
intnum;/*tag=INT时,为整型*/
charc;/*tag=CHAR时,为字符型*/
};
}TElemType;
/*二叉树的二叉链表存储表示*/
typedefstructBiTNode
{
TElemTypedata;
structBiTNode*lchild,*rchild;/*左右孩子指针*/
}BiTNode,*BiTree;
二叉树的基本操作已经在构造表达式和表达式中的基本操作中根据不同的功能和实际情况修改了,详细见各个函数操作的算法设计。
2、顺序栈的存储类型
/*栈的顺序存储表示*/
#defineSTACK_INIT_SIZE10/*存储空间初始分配量*/
#defineSTACKINCREMENT2/*存储空间分配增量*/
/*两个顺序栈*/
typedefstructSqStack
{
SElemType*base;/*在栈构造之前和销毁之后,base的值为NULL*/
SElemType*top;/*栈顶指针*/
intstacksize;/*当前已分配的存储空间,以元素为单位*/
}SqStack;/*顺序栈SqStack*/
typedefstructSqStack1
{
SElemType1*base;/*在栈构造之前和销毁之后,base的值为NULL*/
SElemType1*top;/*栈顶指针*/
intstacksize;/*当前已分配的存储空间,以元素为单位*/
}SqStack1;/*顺序栈SqStack1*/
相关的基本操作见上面的“expression.h文件的整体结构”的说明,详细的算法设计见附录的程序清单。
3、表达式的基本操作
StatusInput_Expr(char*string,intflag);
/*以字符序列的形式输入语法正确的前缀表达式,保存到字符串string*/
/*参数flag=0表示输出的提示信息是"请输入正确的前缀表示式:
"*/
/*flag=1表示输出的提示信息为"请以表达式的原书写形式输入正确表示式:
"*/
voidjudge_value(BiTree*E,char*string,inti);
/*判断字符string[i],如果是'0'-'9'常量之间,二叉树结点存为整型;否则,存为字符型*/
StatusReadExpr(BiTree*E,char*exprstring);
/*以正确的前缀表示式并构造表达式E*/
StatusPri_Compare(charc1,charc2);
/*如果两个字符是运算符,比较两个运算符的优先级,c1比c2优先,返回OK,否则返回ERROR*/
voidWriteExpr(BiTreeE);
/*用带括弧的中缀表达式输入表达式*/
voidAssign(BiTree*E,charV,intc,int*flag);
/*实现对表达式中的所有变量V的赋值(V=c),参数flag为表示是否赋值过的标志*/
longOperate(intopr1,charopr,intopr2);
/*运算符运算求值,参数opr1,opr2为常量,opr为运算符,根据不同的运算符,实现不同的运算,返回运算结果*/
StatusCheck(BiTreeE);
/*检查表达式是否还存在没有赋值的变量,以便求算数表达式的值*/
longValue(BiTreeE);
/*对算术表达式求值*/
voidCompoundExpr(charP,BiTree*E1,BiTreeE2);
/*构造一个新的复合表达式*/
StatusRead_Inorder_Expr(char*string,char*pre_expr);
/*以表达式的原书写形式输入,表达式的原书写形式字符串string变为字符串pre_expr,后调用reversal_string()函数反转得到前缀表达式pre_expr*/
下面列出部分基本操作的伪码算法,未列出的请见程序清单。
其中部分基本操作的伪码算法如下:
StatusInput_Expr(char*string,intflag)
{
if(flag==0)printf("\n请输入正确的前缀表示式:
");
elseprintf("\n请以表达式的原书写形式输入正确表示式:
");
flushall();/*清理缓冲区*/
gets(string);/*从键盘输入一串字符串作为表达式*/
if(strlen(string)==1)/*输入的表达式字符串长度为1*/
{
if(string[0]=='+'||string[0]=='-'||string[0]=='*'||string[0]=='/'||string[0]=='^')/*输入的表达式只有一个运算符*/
{
printf("\n表达式只有运算符,错误!
");
returnERROR;
}
elseif((string[0]>='0'&&string[0]<'9')||(string[0]>='a'&&string[0]<='z')||(string[0]>='A'&&string[0]<='Z'))/*输入的表达式只有一个数字或字符*/
{
printf("\n表达式只有一个字符!
");
returnOK;
}
else
{
printf("\n输入的字符不是运算符也不是变量常量,错误!
");
returnERROR;
}
}
returnOK;
}
voidjudge_value(BiTree*E,char*string,inti)
{
if(string[i]>='0'&&string[i]<='9')/*为常量*/
{
(*E)->data.tag=INT;
(*E)->data.num=string[i]-48;
}
elseif(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];
}
}
StatusReadExpr(BiTree*E,char*exprstring)
{
SqStackS;
inti,len;/*len为表达式的长度*/
BiTreep,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;i StackEmpty(S);i++) { p=(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; } } else/*不是运算符,运算符出栈*/ { if(! q->lchild) { q->lchild=p; Pop(&S,&q); } else { q->rchild=p; Pop(&S,&q); } } } if(StackEmpty(S)&&i>=len) { returnOK;/*栈空且i>=len,说明输入的表达式是正确的*/ } else/*输入的表达式是错误的*/ { printf("\n输入的表达式有误! "); returnERROR; } } } StatusPri_Compare(charc1,charc2) { if((c1=='^'||c1=='*'||c1=='-'||c1=='+'||c1=='/')&&(c2=='^'||c2=='*'||c2=='-'||c2=='+'||c2=='/')) { if(c1=='^') { if(c2! ='^')returnOK; elsereturnERROR; } elseif(c1=='*'||c1=='/') { if(c2=='^'||c2=='*'||c2=='/') returnERROR; else returnOK; } else returnERROR; } else returnERROR;/*c1和c2不是运算符*/ } voidWriteExpr(BiTreeE) { 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",E->data.num); } else { printf("%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(")"); }/*带括弧输出右子树*/ else { WriteExpr(E->rchild); }/*否则,不带括弧输出右子树*/ } else { WriteExpr(E->rchild); }/*否则,输出右子树*/ } } voidAssign(BiTree*E,charV,intc,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);/*递归左子树*/ } } longpower(intx,intexp)/*指数运算函数,底数为x,指数为exp*/ { longresult; inti; for(i=1,result=1;i<=exp;i++) result*=x; returnresult; } longOperate(intopr1,charopr,intopr2) { longresult; switch(opr) { case'+': result=opr1+opr2; returnresult; break; case'-': result=opr1-opr2; returnresult; break; case'*': result=opr1*opr2; returnresult; break; case'/': result=opr1/opr2; returnresult; break; case'^': result=power(opr1,opr2); returnresult; break; default: break; } } StatusCheck(BiTreeE) { if(E&&E->data.tag==CHAR)/*树不为空*/ { if(E->data.c! ='*'&&E->data.c! ='^'&&E->data.c! ='-'&&E->data.c! ='+'&&E->data.c! ='/') { printf("\n表达式中仍存在没有赋值的变量! "); returnER
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 树和二叉树数据结构实验报告 二叉 数据结构 实验 报告