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

《算法设计与分析》实验报告-1-1、实验目的（1）掌握二叉树的数组存储方法。（2）掌握二叉树的非线性特点、递归特点和动态特性。（3）复习二叉树遍历算法和标识符树的概念。（4）利用标识符树的后序计算表达式的值（运算只涉及+、-、*、/）。2、实验内容（1）定义二叉树的结构如下：structtree//定义结构体{intdata;//定义一个整型数据域structtree*left;//定义左子树指针structtree*right;//定义右子树指针};typedefstructtreebtnode;//树的结构类型typedefbtnode*bt;//定义树结点的指针类型（2）把算术表达式2*3+6/3的标识符树（见图7-35）存入一维数组。（3）求标识符树的前序遍历、中序遍历和后序遍历的序列。（4）以后序计算标识符树的值。3、实验要求（1)用C（C++）语言完成算法设计和程序设计。（2)上机调试通过实验程序。（3)输入数据，检验程序运行结果。（4)给出具体的算法分析，包括时间复杂度和空间复杂度等。（5)撰写实验报告（把输入实验数据及运行结果用抓图的形式粘贴到实验报告上）。4、实验步骤与源程序⑴实验步骤先从具体的问题中抽象出适当的数学模型，然后设计出相应的算法，其中，需要设计一个主函数来实现菜单的输出，设计另外五个函数来求分别实现新建，先序遍历输出，中序遍历输出，后序遍历输出，表达式求值，最后，串接函数，并调试程序，多次调试后，发现没有问题，得出实验结果，并截图。⑵源代码#includestdlib.h#includestdio.hstructtree//树的结构声明{chardata;//结点数据structtree*left;//指向左子树的指针structtree*right;//指向右子树的指针};typedefstructtreetreenode;//树的结构新类型+*/2363标识符树《算法设计与分析》实验报告-2-typedeftreenode*btree;//声明树结点指针类型intn;//n计算字符串长度btreecreatebtree(int*data,intpos)//创建表达式二叉树{btreenewnode;//新结点指针if(data[pos]==0||posn)//终止条件returnNULL;else{newnode=newtreenode;//创建新结点内存newnode-data=data[pos];//创建结点内容newnode-left=createbtree(data,2*pos);//创建左子树递归调用newnode-right=createbtree(data,2*pos+1);//创建右子树递归调用returnnewnode;}}voidpreorder(btreeptr)//表达式二叉树前序输出{if(ptr!=NULL)//终止条件{printf(%c,ptr-data);//输出结点内容preorder(ptr-left);//左子树preorder(ptr-right);//右子树}}voidinorder(btreeptr)//表达式二叉树中序输出{if(ptr!=NULL)//终止条件{inorder(ptr-left);//左子树《算法设计与分析》实验报告-3-printf(%c,ptr-data);//输出结点内容inorder(ptr-right);//右子树}}voidpostorder(btreeptr)//表达式二叉树后序输出{if(ptr!=NULL)//右子树{postorder(ptr-left);//左子树postorder(ptr-right);//右子树printf(%c,ptr-data);//输出结点内容}}intcal(btreeptr)//表达式二叉树后序计值{intoperand1=0;//定义操作数变量1intoperand2=0;//定义操作数变量2intgetvalue(intop,intoperand1,intoperand2);//对getvalue函数作声明if(ptr-left==NULL&&ptr-right==NULL)//终止条件returnptr-data-48;{operand1=cal(ptr-left);//左子树operand2=cal(ptr-right);//右子树returngetvalue(ptr-data,operand1,operand2);}}intgetvalue(intop,intoperand1,intoperand2)//计算二叉树表达式值{switch((char)op){case'*':return(operand1*operand2);《算法设计与分析》实验报告-4-case'/':return(operand1/operand2);case'+':return(operand1+operand2);case'-':return(operand1-operand2);}}voidmain()//主程序{btreeroot=NULL;//表达式二叉树指针intresult,k=1;//定义输出结果变量intdata[100]={''};charch;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、测试数据与实验结果（可以抓图粘贴）《算法设计与分析》实验报告-5-6、结果分析与实验体会本次实验是书中的范例程序，经过自己的改写，从而实现要求。先做简单的输出，一步步的再做其它格式的设置。在实验的过程中，我加深了对标识符树各种操作的理解，而且由于对操作的不熟悉，在运行程序的时候，我输入操作数的顺序不正确，而导致实验结果显示的不正确。后来，多次调试，终于得到了正确的结果。