数据结构优秀课程设计优质报告.docVIP

一、需求分析【课程设计要求】

【问题描述】

一个表示式和一棵二叉树之间，存在着自然对应关系。写一个程序，实现基于二叉树表示算术表示式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）以表示式原书写形式输入，支持大于0正整数常量；

（2）增加常数合并操作MergeConst(E)——合并表示式E中全部常数运算。比如，对表示式E=(2+3-a)*(b+3*4)进行合并常数操作后，求得E=(5-a)*(b+12)

(3)增加对求偏导数运算Diff（E，V）——求表示式E对V导数

(4)在表示式内增加对三角函数等初等函数操作。

【测试数据】

(1)分别输入0；a;-91;+a*bc;+*5x2*8x;+++*3^*2^x2x6并输出。

（2）每当输入一个表示式后，对其中变量赋值，然后对表示式求值

二、【整体算法思想】

一个表示式和一棵二叉树之间存在一一对应关系。本程序我关键用前缀表示式建树，中序遍历并合适加括号实现中缀输出。具体操作即对树程序进行处理，再输出。

三、【概要设计】

1、数据类型申明：

在这个课程设计中，采取了链表二叉树存放结构，和两个次序栈辅助存放结构

/*头文件和存放结构*/

#includestdio.h

#includeconio.h

#includestdlib.h

#includestring.h

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

操作结果：以表示式原书写