数据结构实验报告.doc

数据结构实验报告.doc数据结构实验报告
数据结构实验报告
1 / 19
数据结构实验报告
课程设计实验报告
实验名称： 表达式类型的实现
编译环境： 硬件 :PC 软件： VS2010
问题描述
一个表达式和一棵二叉树之间， 存在着自然的对应关系。 写一个程序， 实现基于二叉树表示的算术表达式 Expression 的操作。
基本要求
假设算术表达式 Expression 可以含有变量 （ a～z）、常量（ 0~9）和二元运算符 （ +，- ，
* ， / ， ^（乘幂））。实现以下操作。
（ 1） ReadExpr(E) ——以字符序列的形式输入语法正确的前缀表示式并构造表达式
（ 2） WriteExpr(E) ——用带括弧的前缀表示式输出表达式 E。
（ 3） Assign(V ， c) ——实现对变量 V 的赋值 (V=c) ，变量的初值为 0。
（ 4） Value(E) ——对算术表达式 E 求值。

E。
数据结构实验报告
数据结构实验报告
19 / 19
数据结构实验报告
5） CompoundExpr(P， E1， E2)——构造一个新的复合表达式 (E1)P(E2) 。
选作内容：
数据结构实验报告
数据结构实验报告
19 / 19
数据结构实验报告
（ 1） 增加常数合并操作 MergeConst(E)------- 合并表达式中
如：
表达式 E=2+2*1-A 进行合并常数的操作后，求得 E=4-A
（ 2）以表达式的原书写形式输入

E 的所有常数运算。 例
数据结构实验报告
数据结构实验报告
19 / 19
数据结构实验报告
需求分析
1．以字符序列的形式输入语法正确的中缀表示式并构造表达式
E。即要根据正确的前缀式建立一
棵二叉树 T。
2．用带括弧的前缀表达式输出表达式E。即要求在前缀遍历二叉树的时候考虑运算符的优先级，
在适当的位置输出括弧。
3．实现对变量
V 的赋值（ V＝ c），变量的初值为 0。那就在中缀遍历二叉树的过程中比较结点的
值是否为 V，找到 V以后将 c 赋给 V。
4．对算术表达式
E 求值。如果表达式中有变量的话，首先提示用户表达式中变量，建议先执行
操作 3（实现对变量 V 赋值），执行完后再回来执行表达式求值这一步骤。表达式求值利用递归，
如果某个结点的值为运算符并且它的左右孩子结点的值为数据，
那么就把（左孩子）（运算符）（右
孩子）的结果赋给该结点。
一层一层往上，最后只剩下一个根结点。此时根结点的值就是表达式
E 的值。
5．构造一个新的复合表达式（ E1） P（E2）。只要先构造表达式
E1 的二叉树和 E2 的二叉树，然
后利用 P 把这两棵二叉树连接起来构成一棵新的二叉树。
6．合并表达式
E 中所有常数运算。此原理类似于对表达式
E 求值，不同之处只在于该功能只对
常数合并。
数据结构实验报告
数据结构实验报告
19 / 19
数据结构实验报告
概要设计
树的抽象数据类型定义 : ADT Tree{
数据结构实验报告
数据结构实验报告
6 / 19
数据结构实验报告
数据对象
数据关系

D: D 是具有相同特性的数据元素的集合。
R: 若 D为空集，则称为空树；若 D仅含一个数据元素， 则 R为空集，否则 R={H},H
是如下二元关系：
(1) 在 D中存在唯一的称为根的数据元素 root ，它在关系 H 下无前驱；
(2) 若 D-{root} ≠ф , 则存在 D-{root} 的一个划分 D1,D2, Dm(m>0),对任意
j ≠ k(1<=j,k<=m) 有 Dj ∩Dk = ф，且对任意的 i(1 ≤ i ≤ m), 唯一存在数据
元素 Xi ∈ Di ，有 <root,Xi> ∈ H；
(3) 对应于 D-{root} ≠ф 的划分， H - {<root,Xi> <root,Xm>} 有唯一的一
个划分 H1,H2 Hm(m>0)，对任意 j ≠ k(1<=j,k<=m) 有 Dj ∩Dk = ф，且对
任意的 i(1 ≤ i ≤ m)， Hi 是 Di 上的二元关系， (Di,{Hi}) 是一棵符合本定
义的树，称为根的 root 的子树。
数据结构实验报