数据结构实验7 标识符树与表达式求值

数据结构实验7 标识符树与表达式求值

标识符树与表达式求值 设计 实验类别 班 学 姓 级： 号： 名： 评语： 实验态度：认真（ ） 实验结果：正确（ ） 实验理论：掌握（ ） 操作技能：强（ ） 实验报告：好（ ） 一般（ ） 差（ ） 部分正确（ ）错（ ） 熟悉（ ） 了解（ ） 一般（ 差（ ） 一般（ ） 差（ ） 不懂（ ） 成绩： 指导教师： 批阅时间： 年 月 日 《算法设计与分析 》实验报告 -1- 1、实验内容或题目 （1）定义二叉树的结构如下： struct tree { int data; struct tree *left; struct tree *right; }; typedef struct tree btnode; typedef btnode *bt; // 定义结构体 // 定义一个整型数据域 // 定义左子树指针 // 定义右子树指针 // 树的结构类型 // 定义树结点的指针类型 + * 2 3 6 / 3 （2）把算术表达式 2*3+6/3 的标识符树（见图 7-35）存入一维数组。 （3）求标识符树的前序遍历、中序遍历和后序遍历的序列。 （4）以后序计算标识符树的值。 2、实验目的与要求 （1）掌握二叉树的数组存储方法。 （2）掌握二叉树的非线性特点、递归特点和动态特性。 （3）复习二叉树遍历算法和标识符树的概念。 （4）利用标识符树的后序计算表达式的值（运算只涉及+、-、*、/） 。 标识符树 3、实验步骤与源程序 ⑴ 实验步骤 1、 创建树和指向指针以及表达式二叉树，限定终止条件。 2、 创建新结点内存及内容，应用使表达式二叉树分别进行前序输出、中叙输出、后续输出。表 达式二叉树后序记值，定义两个操作数变量，并对 getvalue 函数作声明，建立终止条件。 3、 运行主程序，创建表达式二叉树，定义输出结果变量。 ⑵ 源代码 #include #include struct tree { char data; struct tree *left; struct tree *right; }; typedef struct tree treenode; typedef treenode *btree; // 树的结构新类型 // 声明树结点指针类型 // 结点数据 // 指向左子树的指针 // 指向右子树的指针 // 树的结构声明 《算法设计与分析 》实验报告 -2- int n; btree createbtree(int *data,int pos) { btree newnode; if (data[pos]==0||pos>n) return NULL; else { newnode=new treenode; newnode->data=data[pos]; newnode->left=createbtree(data,2*pos); // n 计算字符串长度 // 创建表达式二叉树 // 新结点指针 // 终止条件 // 创建新结点内存 // 创建结点内容 // 创建左子树递归调用 newnode->right=createbtree(data,2*pos+1); // 创建右子树递归调用 return newnode; } } void preorder(btree ptr) { if(ptr!=NULL) { printf(" %c",ptr->data); preorder(ptr->left); preorder(ptr->right); } } // 表达式二叉树前序输出 // 终止条件 // 输出结点内容 // 左子树 // 右子树 void inorder(btree ptr) { if (ptr!=NULL) { inorder(ptr->left); // 表达式二叉树中序输出 // 终止条件 // 左子树 《算法设计与分析 》实验报告 -3- printf(" %c",ptr->data); inorder(ptr->right); } } // 输出结点内容 // 右子树 void postorder(btree ptr) { if(ptr!=NULL) { postorder(ptr->left); postorder(ptr->right); printf(" %c",ptr->data); } } // 表达式二叉树后序输出 // 右子树 // 左子树 // 右子树 // 输出结点内容 int cal(btree ptr) { int operand1=0; int operand2=0; int getvalue(int op,int operand1,int operand2); if (ptr->left==NULL && ptr->right==NULL) return ptr->data-48; { operand1=cal(ptr->left); operand2=cal(ptr->right); return getvalue(ptr->data,operand1,operand2); } } // 表达式二叉树后序计值 // 定义操作数变量 1 // 定义操作数变量 2 // 对 getvalue 函数作声明 // 终止条件 // 左子树 // 右子树 int getvalue(int op,int operand1,int operand2) { // 计算二叉树表达式值 《算法设计与分析 》实验报告 -4- switch((char)op) { case'*':return(operand1*operand2); case'/':return(operand1/operand2); case'+':return(operand1+operand2); case'-':return(operand1-operand2); } } void main() { btree root=NULL; int result,k=1; int data[100]={' '}; char ch; // 主程序 // 表达式二叉树指针 // 定义输出结果变量 printf("按前序输入标识符树的结点数据，以回车键表示结束\n"); while((ch=getchar())!='\n') data[k++]=ch; data[k]='\0'; n=k-1; root=createbtree(data,1); printf("\t\n 前序表达式："); preorder(root); printf("\t\n\n 中序表达式："); inorder(root); printf("\t\n\n 后序表达式："); postorder(root); result=cal(root); printf("\t\n\n 表达式结果是：%d\n\n",result); } // 后序输出二叉树 // 计算 // 输出计算结果 // 中序输出二叉树 // 前序输出二叉树 // 创建表达式二叉树 《算法设计与分析 》实验报告 -5- 4、测试数据与实验结果（可以抓图粘贴）