课程设计报告-表达式类型的实现-方锐洲

《课程设计报告-表达式类型的实现-方锐洲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课程设计报告<<数据结构>>课程设计表达式类型的实现学院计算机学院专业计算机科学与技术年级班别2006级01班学号3106006394学生姓名方锐洲辅导教师__吴伟民_______成绩_____________2008年7月3日第35页共35页数据结构课程设计报告~~~~~~~~~~表达式类型的实现~~~~~~~~~~目录：一、需求分析------------------------3二、概要设计-----------------------3-61、数据类型的声明：2、表达式的抽象数据类型定义3、整体设计三

2、、详细设计----------------------7-131、二叉树的存储类型2、顺序栈的存储类型3、表达式的基本操作4、主程序和其他伪码算法5、函数的调用关系四、设计和调试分析-------------------14五、用户手册------------------------14六、测试--------------------------15-18七、课程设计的心得和心得以及问题-----18八、参考文献------------------------19九、附录：程序清单-----------------1

3、9-35第35页共35页数据结构课程设计报告一、需求分析【课程设计要求】【问题的描述】一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式Expression的操作。【基本要求】【一】【必做部分】假设算术表达式Expression内可以含有变量（a-z）,常量（0-9）和二元运算符（+，-，*，/，^（乘幂））。实现以下操作：（1）ReadExpr(E)――以字符序列的形式输入语法正确的前缀表达式并构造表达式E。（2）WriteExpr(E)――用带括号的中缀表达式输出表达式E

4、。（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)【测试数据】1)分别输入0；a;-91;+a*

5、bc;+*5x2*8x;+++*3^*2^x2x6并输出。2)每当输入一个表达式后，对其中的变量赋值，然后对表达式求值。3)还有很多测试的数据，详细请见附上的文件Test.txt。二、概要设计1、数据类型的声明：在这个课程设计中，采用了链表二叉树的存储结构，以及两个顺序栈的辅助存储结构/*头文件以及存储结构*/#include#include#include#include#defineTRUE1#defineFALSE0#defineOK1

6、#defineERROR0#defineOVERFLOW0typedefintStatus;第35页共35页数据结构课程设计报告2、表达式的抽象数据类型定义ADTExpression{数据对象D：D是具有数值的常量C和没有数值的变量V；数据关系：R={<(V或者C)P(V或者C)>

7、V,C∈D,<(V或者C)P(V或者C)>表示由运算符P结合起来的表达式E}基本操作：StatusInput_Expr(&string,flag)操作结果：以字符序列的形式输入语法正确的前缀表达式，保存到字符串string；参数flag表

8、示输出的提示信息是什么，输入成功返回OK，否则，返回ERROR。voidjudge_value(&E,&string,i)初始条件：树E存在，表达式的前缀字符串string存在；操作结果：判断字符string[i]，如果是'0'-'9'常量之间，二叉树结点E存为整型；否则，存为字符型。StatusReadExpr(&E,&exprstring)初始条件：表达式的前缀形式字符串exprstring存在；操作结果：以正确的前缀表示式exprstring并构造表达式E，构造成功，返回OK，否则返回ERROR。StatusP

9、ri_Compare(c1,c2)初始条件：c1和c2是字符；操作结果：如果两个字符是运算符，比较两个运算符的优先级，c1比c2优先，返回OK，否则返回ERROR。voidWriteExpr(&E)初始条件：表达式E存在；操作条件：用带括弧的中缀表达式输入表达式E。voidAssign(&E,V,c,&flag)初始条件：表达式E存在，flag