数据结构-实验7-标识符树与表达式求值(共5页).doc

《数据结构-实验7-标识符树与表达式求值(共5页).doc》由会员分享，可在线阅读，更多相关《数据结构-实验7-标识符树与表达式求值(共5页).doc（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上1、 实验目的（1）掌握二叉树的数组存储方法。（2）掌握二叉树的非线性特点、递归特点和动态特性。（3）复习二叉树遍历算法和标识符树的概念。（4）利用标识符树的后序计算表达式的值（运算只涉及+、-、*、/）。2、 实验内容（1）定义二叉树的结构如下：struct tree / 定义结构体 int data; / 定义一个整型数据域 struct tree *left; / 定义左子树指针 struct tree *right; / 定义右子树指针;typedef struct tree btnode; / 树的结构类型+*/2363 标识符树typedef btnode

2、 *bt; / 定义树结点的指针类型（2）把算术表达式2*3+6/3的标识符树（见图7-35）存入一维数组。（3）求标识符树的前序遍历、中序遍历和后序遍历的序列。（4）以后序计算标识符树的值。3、 实验要求（1) 用C（C+）语言完成算法设计和程序设计。（2) 上机调试通过实验程序。（3) 输入数据，检验程序运行结果。（4) 给出具体的算法分析，包括时间复杂度和空间复杂度等。（5) 撰写实验报告（把输入实验数据及运行结果用抓图的形式粘贴到实验报告上）。4、 实验步骤与源程序 实验步骤先从具体的问题中抽象出适当的数学模型，然后设计出相应的算法，其中，需要设计一个主函数来实现菜单的输出，设计另外五

3、个函数来求分别实现新建，先序遍历输出，中序遍历输出，后序遍历输出，表达式求值，最后，串接函数，并调试程序，多次调试后，发现没有问题，得出实验结果，并截图。 源代码#include#includestruct tree / 树的结构声明char data; / 结点数据 struct tree *left; / 指向左子树的指针 struct tree *right; / 指向右子树的指针;typedef struct tree treenode; / 树的结构新类型typedef treenode *btree; / 声明树结点指针类型int n; / n计算字符串长度btree create

4、btree(int *data,int pos) / 创建表达式二叉树 btree newnode; / 新结点指针 if (datapos=0|posn) / 终止条件 return NULL; else newnode=new treenode; / 创建新结点内存 newnode-data=datapos; / 创建结点内容 newnode-left=createbtree(data,2*pos); / 创建左子树递归调用 newnode-right=createbtree(data,2*pos+1); / 创建右子树递归调用return newnode;void preorder(bt

5、ree ptr) / 表达式二叉树前序输出 if(ptr!=NULL) / 终止条件 printf( %c,ptr-data); / 输出结点内容 preorder(ptr-left); / 左子树 preorder(ptr-right); / 右子树 void inorder(btree ptr) / 表达式二叉树中序输出 if (ptr!=NULL) / 终止条件 inorder(ptr-left); / 左子树 printf( %c,ptr-data); / 输出结点内容 inorder(ptr-right); / 右子树 void postorder(btree ptr) / 表达式二

6、叉树后序输出 if(ptr!=NULL) / 右子树 postorder(ptr-left); / 左子树 postorder(ptr-right); / 右子树 printf( %c,ptr-data); / 输出结点内容 int cal(btree ptr) / 表达式二叉树后序计值 int operand1=0; / 定义操作数变量1 int operand2=0; / 定义操作数变量2 int getvalue(int op,int operand1,int operand2); / 对getvalue函数作声明 if (ptr-left=NULL & ptr-right=NULL)

7、/ 终止条件 return ptr-data-48; operand1=cal(ptr-left); / 左子树 operand2=cal(ptr-right); / 右子树 return getvalue(ptr-data,operand1,operand2); int getvalue(int op,int operand1,int operand2) / 计算二叉树表达式值 switch(char)op) case*:return(operand1*operand2); case/:return(operand1/operand2); case+:return(operand1+oper

8、and2); case-:return(operand1-operand2); void main() / 主程序 btree root=NULL; / 表达式二叉树指针 int result,k=1; / 定义输出结果变量 int data100= ; char ch; printf(按层次输入标识符树的结点数据，以回车键表示结束n); while(ch=getchar()!=n) datak+=ch; datak=0; n=k-1; root=createbtree(data,1); / 创建表达式二叉树 printf(tn 前序表达式：); preorder(root); / 前序输出二

9、叉树 printf(tnn 中序表达式：); inorder(root); / 中序输出二叉树 printf(tnn 后序表达式：); postorder(root); / 后序输出二叉树 result=cal(root); / 计算 printf(tnn 表达式结果是：%dnn,result); / 输出计算结果5、 测试数据与实验结果（可以抓图粘贴）6、 结果分析与实验体会本次实验是书中的范例程序，经过自己的改写，从而实现要求。先做简单的输出，一步步的再做其它格式的设置。在实验的过程中，我加深了对标识符树各种操作的理解，而且由于对操作的不熟悉，在运行程序的时候，我输入操作数的顺序不正确，而导致实验结果显示的不正确。后来，多次调试，终于得到了正确的结果。专心-专注-专业