1、数据结构课程设计数据结构课程设计 题目一：表达式类型的实现题目一：表达式类型的实现 题目二：图的遍历题目二：图的遍历 表达式类型的实现表达式类型的实现 一、需求分析一、需求分析 1.1.【问题的描述】【问题的描述】 一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于 二叉树表示的算术表达式 Expression 的操作。 2.【基本要求】【基本要求】 【必做部分】【必做部分】 假设算术表达式 Expression 内可以含有变量（a-z） ，常量（0-9）和二元运算符 （+，-，*，/，（乘幂） ） 。实现以下操作： 1) ReadExpr(E)以字符序列的形式输入语法正确
2、的前缀表达式并构造表达 式 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) 进 行 合 并 常 数 的 操 作 后
3、 ， 求 得 E=(5-a)*(b+12) 3) 增加对求偏导数的运算 Diff（E，V）求表达式 E 对 V 的导数 4) 在表达式内增加对三角函数等初等函数的操作。 3.3.【测试数据】【测试数据】 1）分别输入 0；a;-91;+a*bc;+*5x2*8x;+*3*2x2x6 并输出。 2）每当输入一个表达式后，对其中的变量赋值，然后对表达式求值 二、二、概要设计概要设计 1 1、数据类型的声明：、数据类型的声明： 在这个课程设计中，采用了链表二叉树的存储结构，以及两个顺序栈的辅助存储 结构 /*/*头文件以及存储结构头文件以及存储结构*/*/ #include #include #in
4、clude #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW 0 typedef int Status; 2 2、表达式的抽象数据类型定义、表达式的抽象数据类型定义 ADT ExpressionADT Expression 数据对象 D：D 是具有数值的常量 C 和没有数值的变量 V； 数据关系：R=|V,CD, 表示由运算符 P 结合起来的表达式 E 基本操作： Status Input_Expr(Status Input_Expr( 操作结果：运算符运算求值，参数 op
5、r1,opr2 为常量，opr 为运算符， 根据不同的运算符，实现不同的运算，返回运算结果。 Status Check(E)Status Check(E) 初始条件：表达式 E 存在； 操作结果：检查表达式 E 是否还存在没有赋值的变量，以便求算数表达 式 E 的值。 long Value(E)long Value(E) 初始条件：表达式 E 存在； 操作结果：对算术表达式求值，返回求到的结果。 void CompoundExpr(P,void CompoundExpr(P, printf(“n*“); printf(“n 1 输入正确的前缀表达式“); printf(“n 2 带括弧的中缀表
6、示式输出“); printf(“n 3 对变量进行赋值“); printf(“n 4 对算数表达式求值“); printf(“n 5 构造一个新的复合表达式“); printf(“n 6 以表达式的原书写形式输入“); printf(“n 7 合并表达式中所有常数运算“); printf(“n 0 退出“); printf(“n*“); printf(“n 请输入你的选择“); choice=getche(); return choice; 在主函数中，采用多分支程序设计语句 switch()使程序产生不同的流向， 从而达到实现课程设计的各个要求。 void main() while(1) 清屏； switch(主菜单) 根据不同的选择，调用不同的操作函数，完成各个操作； 2 2、本程
