数据结构课程设计报告VIP专享VIP免费

- - 1 一、需求分析【课程设计要求】 【问题的描述】 一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式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、数据类型的声明： 在这个课程设计中，采用了链表二叉树的存储结构，以及两个顺 序栈 的辅 助存储结构 /*头 文 件 以及存储结构*/ #include - - 2 #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 表示输出的提示信息是什么，输入成功返...