数据结构课程实验指导书
操作结果：插入元素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
可以画出表达式对应的2叉树，操作数作为叶子节点，操作符作为非叶子节点,如图所示。
+ * - － 11 － A B C / 数据结构课程实验指导书
再逆序遍历二叉树可得逆波兰表达式为：AB+CDE/-* 利用堆栈的方法计算后缀表达式的值
程序的流程
程序由三个模块组成：
（1）输入模块：在主函数中输入中缀表达式 （2）转换模块：将中缀表达式转换为后缀表达式，并打印
（3）计算模块：生成的后缀表达式用于计算，打印最后结果 三、详细设计 物理数据类型 二叉树
－ 12 －
数据结构课程实验指导书
#define Max_TREE_SIZE 100 Typedef
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;
－ 13 －
TElemType
数据结构课程实验指导书
}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)）
－ 14 －
数据结构课程实验指导书
//采用二叉链表的存储结构，Visit是对结点操作的应用函数
//后序遍历二叉树，对每个结点调用且仅调用一次Visit函数
//一旦Visit函数失败则操作失败 //堆栈的存储结构表示 typedef struct {
SElemtype * base; SElemtype * top; int stacksize; } SqStack;
Status InitStack(SqStack &S) { S.base ));
if (! S.base) exit(OVERFLOW); S.top = S.base;
S.stacksize = STACK_INIT_SIZE; return OK;
－ 15 －
= (SElemtype
*)malloc(STACK_INIT_SIZE*sizeof(SElemtype
数据结构课程实验报告-实验5
