数据结构课程设计表达式类型的实现（难度系数1.2）_毕业论文.doc

数据结构课程设计报告 题目：表达式类型的实现（难度系数：1.2） 学 院 计算机 专 业 计算机科学与技术 年级班别 2015级8班 学 号 3115005210 学生姓名 杨嘉慧 指导教师 李杨 编 号 成 绩 2017 年 1 月 报告： 报告内容： □详细　 □完整　 □基本完整 □不完整 设计方案： □非常合理　 □合理　 □基本合理 □较差 算法实现： □全部实现　 □基本实现　 □部分实现 □实现较差 测试样例： □完备　 □比较完备　 □基本完备 □不完备 文档格式： □规范　 □比较规范　 □基本规范 □不规范 答辩： □理解题目透彻，问题回答流利 □理解题目较透彻，回答问题基本正确 □部分理解题目，部分问题回答正确 □未能完全理解题目，答辩情况较差 总评成绩： □优　　　□良　　　□中　　　□及格　　　□不及格 运行环境：CodeBlocks 完成的题目：表达式类型的实现（难度系数：1.2） 选做的内容：(4)在表达式内增加对三角函数等初等函数的操作。 一、 需求分析【课程设计要求】 【问题的描述】 一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现 基于二叉树表示的算术表达式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 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 typedef int Status; 2、表达式的抽象数据类型定义 基本操作： void judge_str(E,string1) 初始条件：树E存在，表达式的前缀字符串string存在； 操作结果：判断字符string[i]，如果是0-9常量之间，二叉树结点E存为整型；否则，存为字符型。 Status ReadExpr(E,string1) 初始条件：表达式的前缀形式字符串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) 初始条件：表达式E存在，flag为标志是否有赋值过； 操作结果：实现对表达式E中的所有变量V