实习报告。
题目：编写一个实现基于二叉树表示的算术表达式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、数据类型的声明：
在这个课程设计中，采用了链表二叉树的存储结构，以及两个顺序栈的辅助存储结构。
*头文件以及存储结构*/
#include<>
#include<>
#include<>
#include<>
#define true 1
#define false 0
#define ok 1
#define error 0
#define overflow 0
typedef int status;
2、表达式的抽象数据类型定义。
adt expression
基本操作：status input_expr(&string,flag)
操作结果：以字符序列的形式输入语法正确的前缀表达式，保存到字符串string； 参数flag表示输出的提示信息是什么，输入成功返回ok，否则，返回error。
void judge_value(&e,&string,i)
初始条件：树e存在，表达式的前缀字符串string存在；
操作结果：判断字符string[i]，如果是'0'-'9'常量之间，二叉树结点e存为整型；否则，存为字符型。
status readexpr(&e,&exprstring)
初始条件：表达式的前缀形式字符串exprstring存在；
操作结果：以正确的前缀表示式exprstring并构造表达式e，构造成功，返回ok，否则返回error。
status pri_compare(c1,c2)
初始条件：c1和c2是字符；
操作结果：如果两个字符是运算符，比较两个运算符的优先级，c1比c2优先，返回ok，否则返回error。
void writeexpr(&e)
初始条件：表达式e存在；
操作条件：用带括弧的中缀表达式输入表达式e。
void assign(&e,v,c,&flag)
初始条件：表达式e存在，flag为标志是否有赋值过；
操作结果：实现对表达式e中的所有变量v的赋值(v=c)。
long operate(opr1,opr,opr2)
初始条件：操作数opr1和操作数opr2以及操作运算符opr;
操作结果：运算符运算求值，参数opr1,opr2为常量，opr为运算符，根据不同的运算符，实现不同的运算，返回运算结果。
status check(e)
初始条件：表达式e存在；
操作结果：检查表达式e是否还存在没有赋值的变量，以便求算数表达式e的值。
long value(e)
初始条件：表达式e存在；
操作结果：对算术表达式求值，返回求到的结果。
void compoundexpr(p,&e1,e2)
初始条件：表达式e1和e2存在；
操作条件：构造一个新的复合表达式(e1)p(e2)。
status read_inorder_expr(&string,&pre_expr)
操作结果：以表达式的原书写形式输入，表达式的原书写形式字符串string变为字符串pre_expr，后调用reversal_string()函数反转得到前缀表达式pre_expr。得到正确的前缀表达式返回ok，否则，返回error。
void mergeconst(&e)
操作结果：常数合并操作，合并表达式e中所有常数运算。
adt expression
3、整体设计。
1、顺序栈的基本操作：
对于栈sqstack:
status initstack(sqstack *s) /构造一个空栈s */
status stackempty(sqstack s) /若栈s为空栈，则返回true，否则返回false */
status push(sqstack *s,selemtype e) /插入元素e为新的栈顶元素 */
status pop(sqstack *s,selemtype *e) /若栈不空，则删除s的栈顶元素，用e返回其值，并返回ok；否则返回error */
status gettop(sqstack s,selemtype *e) /若栈不空，则用e返回s的栈顶元素，并返回ok；否则返回error */
对于栈sqstack1:
status initstack1(sqstack1 *s) /构造一个空栈s */
status stackempty1(sqstack1 s) /若栈s为空栈，则返回true，否则返回false */
status push1(sqstack1 *s,selemtype1 e) /插入元素e为新的栈顶元素 */
status pop1(sqstack1 *s,selemtype1 *e) /若栈不空，则删除s的栈顶元素，用e返回其值，并返回ok；否则返回error */
status gettop1(sqstack1 s,selemtype1 *e) /若栈不空，则用e返回s的栈顶元素，并返回ok；否则返回error */
2、主程序模块的整体流程。
在主函数中，采用多分支程序设计语句switch()使程序产生不同的流向，从而达到实现课程设计的各个要求。
void main()
printf(" 1 >>输入正确的前缀表达式");
printf(" 2 >>带括弧的中缀表示式输出");
printf(" 3 >>对变量进行赋值");
printf(" 4 >>对算数表达式求值");
printf(" 5 >>构造一个新的复合表达式");
printf(" 0 >>退出");
while(1)
2、本程序有四个模块，主程序模块，二叉树模块，两个顺序栈模块。四者的调用关系如下：
主程序模块中的对于表达式的存储结构调用了二叉树模块，而在构造表达式的二叉树模块中又调用了顺序栈sqstack模块，主程序中在将原表达式形式输入表达式转换为前缀表达式操作中调用了顺序栈sqstack1模块。
三、 详细设计。
1、二叉树的存储类型。
*二叉树结点类型*/
typedef enumelemtag;/*int为整型数据num，char为字符型数据c*/
typedef struct telemtype
指示是整型还是字符型*/
union telemtype;
/*二叉树的二叉链表存储表示 */
typedef struct bitnode
bitnode,*bitree;
二叉树的基本操作已经在构造表达式和表达式中的基本操作中根据不同的功能和实际情况修改了，详细见各个函数操作的算法设计。
2、顺序栈的存储类型。
*栈的顺序存储表示 */
#define stack_init_size 10 /*存储空间初始分配量 */
#define stackincrement 2 /*存储空间分配增量 */
*两个顺序栈*/
typedef struct sqstack
sqstack; /顺序栈sqstack */
typedef struct sqstack1
sqstack1; /顺序栈sqstack1 */
相关的基本操作见上面的“文件的整体结构”的说明，详细的算法设计见附录的程序清单。
3、表达式的基本操作。
status input_expr(char *string,int flag);
*以字符序列的形式输入语法正确的前缀表达式，保存到字符串string*/
*参数flag=0表示输出的提示信息是"请输入正确的前缀表示式："*
*flag=1表示输出的提示信息为"请以表达式的原书写形式输入正确表示式："*
void judge_value(bitree *e,char *string,int i);
*判断字符string[i]，如果是'0'-'9'常量之间，二叉树结点存为整型；否则，存为字符型*/
status readexpr(bitree *e,char *exprstring);
*以正确的前缀表示式并构造表达式e*/
数据结构实验 二叉树的操作
实验题目 二叉树的操作 实验者信息 班级 13007102，姓名庞文正，学号 1300710226 实验完成的时间 3 00 一 实验目的。1,掌握二叉树链表的结构和二叉树的建立过程。2,掌握队列的先进先出的运算原则在解决实际问题中的应用。3,进一步掌握指针变量 指针数组 动态变量的含义。4,掌握递...
数据结构实验报告实验三二叉树的建立与遍历
昆明理工大学信息工程与自动化学院学生实验报告。201 201 学年第一学期 课程名称 数据结构开课实验室年月日。一。实验内容 二叉树的建立与遍历，其中遍历有前序遍历，中序遍历和后序遍历。以及二叉树中序线索化及线索化遍历。二。实验目的 学会二叉树二叉链表非线性存储结构上实现的各种算法。三。主要程序 分...