数据结构课程实验报告实验5.doc

HUNAN UNIVERSITY

课程实习报告

题 目： 四则运算表达式求值

学生姓名 康小雪
学生学号 20090810310
专业班级 计科三班
指导老师 李晓鸿
完 成 日 期 2010-10—24

一、 需求分析
1．该程序可以从通过从键盘输入一个中缀表达式，判断该表达式是否合法，若合法将
其转化为后缀表达式，并计算其结果，否则说明该表达式错误
2．。输入的表达式包含数字和运算符及括号，之间用空格隔开
3．数字可以为整数和小数
4．运算结果保留两位小数
输入输出举例
输入:21+23*（12-6）
输出：21 23 12 6 —*+
二、 概要设计
在表达式中每个运算符应对应两个操作数,与二叉树中非叶子结点和叶子结点之间的关系刚好相同,于是，本题可采用二叉树来将中缀表达式变为后缀表达式.
最后用堆栈来实现后缀表达式的计算.
抽象数据类型
二叉树
ADT BiTree
{
数据对象 D:D是具有相同特性的数据元素集合
数据关系 R：
若D为空集，则R为空集，则称BinaryTree为空二叉树；
若D不为空集,否则R={H},H是如下二元关系：
（1） 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；
（2） 若D—{root｝≠空集，则存在D-｛root}的一个划分{D1，Dr} 且D1∩Dr=空集；
（3） 若D1≠空集，则D1中存在唯一元素x1，<root，x1〉∈H,且存在D1shang de guanxi H1=H;ruo Dr≠空集，则Dr中存在唯一的元素，xr，<root，xr>∈H，且存在Dr上的关系Hr∈H;H={〈root，x1>，<root，xr>，H1，Hr｝；
（4） （D1，｛H1}）是一棵符合本定义的二叉树，称为根的左子树，（Dr，{Hr｝)是一棵符合本定义的二叉树，称为根的右子树
基本操作P：
InitBiTree(&T)
操作结果：构造空二叉树T
DestroyBiTree（＆T)
初始条件：二叉树T存在
操作结果：销毁二叉树T
CreateBiTree（＆T，definition）
初始条件:definition给出二叉树T的定义
操作结果：按definition构造二叉树T
ClearBiTree(＆T）
初始条件：二叉树T存在
操作结果:将二叉树T清空为空树
TreeBiEmpty（T）
初始条件：二叉树T存在
操作结果：若二叉树T为空树，则返回TRUE，否则返回FALSE
TreeBiDepth（T）
初始条件:二叉树T存在
操作结果：返回二叉树T的深度
Root（T）
初始条件：二叉树T存在
操作结果:返回T的根
Value（T,cur_e）
初始条件:二叉树T存在，cur_e是T中的某个结点
操作结果：返回cur_e的值
Assign（T, cur_e,value）
初始条件:二叉树T存在，cur_e是T中的某个结点
操作结果：结点cur_e赋值为value
Parent（T，cur_e)
初始条件：而擦树T存在，cur_e是T中的某个结点
操作结果:若cur_e是非根结点，则返回它的双亲，否则函数值为空
LeftChild(T，cur_e）
初始条件：二叉树T存在，cur_e是T中的某个结点
操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子,否则返回空
RightChild（&T，＆p，i）
初始条件：二叉树T存在,cur_e是T中的某个结点
操作结果:若cur_e有右兄弟，则返回它的右兄弟，否则函数值为空
LeftSibling（T，e）
初始条件：二叉树T存在，e是T中的某个结点
操作结果：返回e的左兄弟，若e是T的左孩子或无左兄弟，返回空
RightSibling（T,e）
初始条件：二叉树T存在，e是T中的某个结点
操作结果:返回e的右兄弟，若e是T的右孩子或无右兄弟，返回空
InsertChild(＆T，＆p,I，c）
初始条件：二叉树T存在，p指向T中某个结点，1<=i<=p所指结点的度+1，非空树c与T不相交
操作结果：插入c为T中p指结点的第i棵子树
DeleteChild（＆T,＆p，i）
初始条件:树T存在，p指向T中某个结点，1〈=i〈=p所值结点的度
操作结果：删除T中p所指结点的第i棵子树
PreOrderTravereseTree（T，Visit()）
初始条件：二叉树T存在，Visit是对界定操作的应用函数
操作结果:先序遍历T，对每个结点调用函数visit（）一次且仅一次,一旦visit(）失败，则操作失败
InOrderTravereseTree（T，Visit(））
初始条件：二叉树T存在，Visit是对界定操作的应用函数
操作结果：中序遍历T，对每个结点调用函数visit()一次且仅一次，一旦visit()失败，则操作失败
PostOrderTravereseTree（T,Visit（)）
初始条件：二叉树T存在，Visit是对界定操作的应用函数
操作结果：后序遍历T,对每个结点调用函数visit(）一次且仅一次，一旦visit(）失败，则操作失败

}ADT Tree
堆栈
ADT Stack｛
数据对象：D=｛∈ElemType,i=1,2,…，n，n>=0｝
数据关系：R1=｛∈D，i=2，…,n｝
基本操作:
InitStack(＆S）
操作结果:构造一个空栈S
DestroyStack(&S）
初始条件：栈S已存在
操作结果：栈S被销毁
ClearStack（&S）
初始条件：栈S已存在
操作结果:栈S清为空栈
StackEmpty（S）
初始条件：栈S已存在
操作结果:若S为空栈，则返回TRUE，否则FALSE
StackLength（S）
初始条件：栈S已存在
操作结果:返回S元素的个数，即栈的长度
GeTop(S，＆e）
初始条件：栈S已存在且非空
操作结果：用e返回S的栈顶元素
Push（＆S,e）
初始条件：栈S已存在
操作结果:插入元素e为新的栈顶元素
Pop(&S,＆e）
初始条件：栈S已存在且非空
操作结果:删除S的栈顶元素，并返回e
StackTraverse（S，visit（））
初始条件：栈S已存在且非空
操作结果：从栈底到栈顶依次对S的每个元素调用函数visit（)，一旦visit(）失败，则操作失败
}ADT Stack

算法的基本思想
以(A+B）＊(C—D/E）这样一个表达式为列求它的后缀表达式
按照优先级加上括号，得到:(A+B)*（C-（D/E）)
然后从最外层括号开始，依次转化成二叉树
1、根是* ，左子树(A+B)，右子树(C—(D/E))
2、右子树的根- ，右子树的左子树C,右子树的右子树（D/E）
3、（A+B)的根+，左子树A ，右子树B
4、（D/E)的根/ ,左子树D,右子树E
*
+
-
A
/
B
C
D
E
可以画出表达式对应的2叉树,操作数作为叶子节点,操作符作为非叶子节点，如图所示。

再逆序遍历二叉树可得逆波兰表达式为:AB+CDE/-*
利用堆栈的方法计算后缀表达式的值
程序的流程
程序由三个模块组成:
（1）输入模块：在主函数中输入中缀表达式
（2）转换模块：将中缀表达式转换为后缀表达式，并打印
（3）计算模块:生成的后缀表达式用于计算,打印最后结果
三、详细设计
物理数据类型
二叉树
#define Max_TREE_SIZE 100
Typedef TElemType SqBiTree［MAX_TREE_SIZE]；
SqBiTree bt；
堆栈
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
＃define TRUE 1
＃define FALSE 0
#define ERROR 0
#define OVERFLOW -2

typedef float SElemtype；
typedef int Status;
算法的具体步骤
//基本操作的函数原型

//二叉树的存储结构表示
Typedef struct BiTNode｛
TElemType data；
Srtuct BiTNode *lchild,＊rchild;
}BiTNode，＊BiTree；
//基本操作的函数原型说明
Status CreatBiTree(BiTree ＆T）
//按先序次序插入二叉树中结点的值(一个字符）
//构造二叉链表表示二叉树T
Status PreOrderTraverse（BiTreeT,Status (* Visit)（TELemType e)）
//采用二叉链表的存储结构，Visit是对结点操作的应用函数
//先序遍历二叉树，对每个结点调用且仅调用一次Visit函数
//一旦Visit函数失败则操作失败
Status InOrderTraverse（BiTreeT,Status （＊ Visit)(TELemType e））
//采用二叉链表的存储结构，Visit是对结点操作的应用函数
//中序遍历二叉树，对每个结点调用且仅调用一次Visit函数
//一旦Visit函数失败则操作失败
Status PostOrderTraverse（BiTreeT，Status （* Visit）(TELemType e)）
//采用二叉链表的存储结构,Visit是对结点操作的应用函数
//后序遍历二叉树，对每个结点调用且仅调用一次Visit函数
//一旦Visit函数失败则操作失败
//堆栈的存储结构表示
typedef struct
｛
SElemtype ＊ base；
SElemtype ＊ top;
int stacksize；
} SqStack；

Status InitStack（SqStack &S)
{
S。base = (SElemtype *）malloc(STACK_INIT_SIZE＊sizeof(SElemtype）)；
if （! S。base） exit(OVERFLOW）;
S.top = S。base;
S。stacksize = STACK_INIT_SIZE；
return OK;
}

int StackLength（SqStack S)
｛
//获得堆栈元素的个数
//填空
return S。top-S.base；
｝

Status Push(SqStack &S， SElemtype e)
{
//入栈
//填空
S.top++;
*（S。top）=e；
return true；
}

Status Pop(SqStack &S, SElemtype ＆e）
｛
//出栈
//填空
if(S.top<S.base) return false ;
e=*(S。top)；
S。top-—；
return true；

｝

算法的时空分析
遍历所有的结点上限是O(n)，故此算法的增长率上限为O(n)
输入和输出的格式
请输入中缀表达式：//输出
//等待输入
//输出后缀表达式
后缀表达式：
//输出结果
运算结果为:

四、调试分析
略。
五、测试结果
六、用户使用说明（可选)
七、实验心得(可选）
略。

七、附录（可选）

Gcd。c 主程序