C语言实现一.二叉树操作-二.用栈实现算术表达式求值--课设报告

沈阳理工大学课程设计专用纸沈阳理工大学目录题目一.二叉树操作（1）二.算术表达式求·························1一、课程设计的目的·······················································1二、课程设计的内容和要求··············································1三、题目一设计过程·······················································2四、题目二设计过程·······················································6五、设计总结······························································17六、参考文献······························································18沈阳理工大学课程设计专用纸No.1沈阳理工大学题目一.二叉树操作（1）二.算术表达式求一、课程设计的目的本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。这次课程设计不但要求学生掌握《数据结构》中的各方面知识，还要求学生具备一定的C语言基础和编程能力。（1）题目一的目的：1、掌握二叉树的概念和性质2、掌握二叉树的存储结构3、掌握二叉树的基本操作（2）题目二的目的：1、掌握栈的顺序存储结构和链式存储结构2、掌握栈的先进后出的特点3、掌握栈的基本运算二、课程设计的内容和要求（1）题目一的内容和要求：1、编写已知二叉树的先序、中序序列，恢复此二叉树的程序2、编写求二叉树深度的程序（2）题目二的内容和要求：1、算术表达式由操作数、运算符和界限符组成。操作数是正整数，运算符为加减乘除，界限符有左右括号和表达式起始2、将一个表达式的中缀形式转化为相应的后缀形式3、依据后缀表达式计算表达式的值沈阳理工大学课程设计专用纸No.2沈阳理工大学三、题目一设计过程1、题目分析现已知一棵二叉树的先序遍历序列和中序遍历序列，依次从先序遍历序列中取结点，由先序序列确定根结点(就是第一个字母)，每次取出一个结点就与中序遍历的序列进行比较，当相等的时候，中序遍历序列就被分成以该结点为根的二叉树子树，该结点左部分为左子树，右部分为右子树，直到取完先序列里的所有结点，则二叉树构造完毕（树用链式存储结构存储），用递归实现！由建好的二叉树，先判断这棵树是否为空，若不为空则找数的左子树，统计它的高度，然后找树的右子树，统计它的高度，比较左子树和右子树的高度，然后返回其中大的那个值加一，则求出数的高度。这里用递归实现！2、算法描述main()（主函数）先构造一颗二叉树，初始化为空，用来存储所构造的二叉树，并输入一棵树的先序序列和中序序列，并统计这个序列的长度。然后调用实现功能的函数。voidCreateBiTree(BiTree*T,char*pre,char*in,intlen)（由先序序列和中序序列构造二叉树）根据前序遍历的特点,知前序序列(pre)的首个元素(pre[0])为根(root),然后在中序序列(in)中查找此根(pre[0]),根据中序遍历特点,知在查找到的根(root)前边的序列为左子树,后边的序列为右子树。设根前边有n个元素，则又有,在前序序列中，紧跟着根(root)的n个元素序列(即pre[1...n])为左子树,在后边的为右子树，而构造左子树问题其实跟构造整个二叉树问题一样，只是此时前序序列为pre[1...n]),中序序列为in[0...n-1],分别为原序列的子串,构造右子树同样。这里用递归实现！intDepth(BiTreeT)（求树的深度）当所给的参数T是NULL时，返回0。说明这个树只有一个叶子节点深度为0，当所给的参数不是NULL时，函数调用自己看看这个参数的左分支是不是NULL，沈阳理工大学课程设计专用纸No.3沈阳理工大学如果不是继续调用自己看看左分支的左分支是不是NULL，直到最后一个的左分支是NULL。然后看与最后一个左分支并列的右分支是不是NULL，不是的话自动调用自己，直到是NULL。同理求出右分支，然后左分支深度和右分支深度比较，返回值大的作为深度。3、源代码#includestdio.h#includemalloc.htypedefstructNode{chardata;structNode*lchild;structNode*rchild;}*BiTree,BitNode;voidInitBitTree(BiTree*T);//初始化一棵树voidCreateBiTree(BiTree*T,char*pre,char*in,intlen);//由先序序列和中序序列构造二叉树intDepth(BiTreeT);//求树的深度voidmain(){BiTreeT;InitBitTree(&T);chara[50],b[50];inti,len=0,j;printf(请输入一棵二叉树的先序序列：);沈阳理工大学课程设计专用纸No.4沈阳理工大学gets(a);printf(请输入一棵二叉树的中序序列：);gets(b);for(i=0;i50;i++){if(a[i]!='\0')len++;elsebreak;}CreateBiTree(&T,a,b,len);j=Depth(T);printf(这棵树的深度是：%d\n,j);}voidInitBitTree(BiTree*T)//初始化一棵树{*T=NULL;}voidCreateBiTree(BiTree*T,char*pre,char*in,intlen)//由先序序列和中序序列构造二叉树{intk;char*temp;if(len=0){*T=NULL;沈阳理工大学课程设计专用纸No.5沈阳理工大学return;}*T=(BitNode*)malloc(sizeof(BitNode));(*T)-data=*pre;for(temp=in;tempin+len;temp++)if(*pre==*temp)break;k=temp-in;CreateBiTree(&((*T)-lchild),pre+1,in,k);//构建左子树CreateBiTree(&((*T)-rchild),pre+1+k,temp+1,len-1-k);//构建右子树}intDepth(BiTreeT)//求树的深度{inth,lh,rh;if(T==NULL)h=0;else{lh=Depth(T-lchild);rh=Depth(T-rchild);if(lh=rh)h=lh+1;elseh=rh+1;}returnh;}沈阳理工大学课程设计专用纸No.6沈阳理工大学4、运行结果先输入一棵树的先序遍历序列和中序遍历序列，然后构造出这颗二叉树，并输出这棵树的深度，结果如图：四、题目二设计过程1、题目分析已知输入一个中缀表达式，利用栈（这里用栈的顺序存储结构）的后进先出性，将一个中缀表达式转换成一个后缀表达式，然后同样利用栈的后进先出性，由后缀表达式求出这个表达式的值，并输出。2、算法描述main()（主函数）沈阳理工大学课程设计专用纸No.7沈阳理工大学在主函数中建立两个数组，一个用来存放中缀表达式，另一个用来存放转换后的后缀表达式，然后调用子函数（其中包括一些栈的基本操作函数），实现函数功能。voidTranslateExpress(chars1[],chars2[])（将中缀表达式转化为后缀表达式）将中缀表达式转换为等价的后缀表达式的过程要使用一个栈放“（”，具体方式如下：（1）从左到右一次扫描中缀表达式的每一个字符，如果是数字字符和圆点“.”则直接将它们写入后缀表达式中。（2）如果遇到的是开括号“（”，则将它们压入一个操作符栈（不需要与栈顶操作符相比较），它表明一个新的计算层次的开始，在遇到和它匹配的闭括号“）”时，将栈中的元素弹出来并放入后缀表达式中，直到栈顶元素为“(”时，将栈顶元素“（”弹出（不需要加入后缀表达式），表明这一层括号内的操作处理完毕。（3）如果遇到的是操作符，则将该操作符和操作符栈顶元素比较：1、当所遇到的操作符的优先级小于或等于栈顶元素的优先级时，则取出栈顶元素放入后缀表式，并弹出该栈顶元素，反复执行直到栈顶元素的优先级小于当前操作符的优先级；2、当所遇到的操作符的优先级大于栈顶元素的优先级的时则将它压入栈中。（4）重复上述步骤直到遇到中缀表达式的结束符标记“#”，弹出栈中的所有元素并放入后缀表达式中，转换结束。floatComputeExpress(chars[])（计算后缀表达式的值）计算后缀表达式的值，将遇到的操作数暂存于一个操作数栈中，凡是遇到操作数，便从栈中pop（弹出）出两个操作数，并将计算结果存于操作数栈中，直到对后缀表达式中最后一个操作数处理完，最后存入栈中的数就是最后后缀表达式的计算结果。3、源代码#includestdio.h#includestring.h#includemalloc.h#includestdlib.h#defineMaxSize50沈阳理工大学课程设计专用纸No.8沈阳理工大学typedefstruct{floatdata[MaxSize];inttop;}OpStack;typedefstruct{chardata[MaxSize];inttop;}SeqStack;voidInitStack(SeqStack*S);//初始化栈intStackEmpty(SeqStackS);//判断栈是否为空intPushStack(SeqStack*S,chare);//进栈intPopStack(SeqStack*S,char*e);//删除栈顶元素intGetTop(SeqStackS,char*e);//取栈顶元素voidTranslateExpress(chars1[],chars2[]);//将中缀表达式转化为后缀表达式floatComputeExpress(chars[]);//计算后缀表达式的值voidmain(){chara[MaxSize],b[MaxSize];floatf;printf(请输入一个算术表达式:);gets(a);printf(中缀表达式为：%s\n,a);TranslateExpress(a,b);沈阳理工大学课程设计专用纸No.9沈阳理工大学printf(后缀表达式为：%s\n,b);f=ComputeExpress(b);printf(计算结果：%f\n,f);}voidInitStack(SeqStack*S)//初始化栈{S-top=0;}intStackEmpty(SeqStackS)//判断栈是否为空{if(S.top==0)return1;elsereturn0;}intPushStack(SeqStack*S,chare)//进栈{if(S-top=MaxSize){printf(栈已满，不能进栈!);return0;}else{S-data[S-top]=e;沈阳理工大学课程设计专用纸No.10沈阳理工大学S-top++;return1;}}intPopStack(SeqStack*S,char*e)//删除栈顶元素{if(S-top==0){printf(栈已空\n);return0;}else{S-top--;*e=S-data[S-top];return1;}}intGetTop(SeqStackS,char*e)//取栈顶元素{if(S.top=0){printf(栈已空);return0;沈阳理工大学课程设计专用纸No.11沈阳理工大学}else{*e=S.data[S