2023年数据结构课程实验报告实验

HUNANUNIVＥＲSＩTＹ课程实习报告题目:四则运算表达式求值 学生姓名康小雪学生学号 专业班级计科三班 指导老师ﻩ李晓鸿ﻩﻩ２0２3-１0-24ﻩ需求分析1.该程序可以从通过从键盘输入一个中缀表达式，判断该表达式是否合法,若合法将其转化为后缀表达式，并计算其结果，否则说明该表达式错误2..输入的表达式包含数字和运算符及括号,之间用空格隔开3．数字可认为整数和小数4．运算结果保存两位小数输入输出举例输入：2１+2３*（1２-６)输出:２1２3126-*+概要设计在表达式中每个运算符应相应两个操作数，与二叉树中非叶子结点和叶子结点之间的关系刚好相同,于是，本题可采用二叉树来将中缀表达式变为后缀表达式。最后用堆栈来实现后缀表达式的计算。 抽象数据类型二叉树AＤＴBiTree{数据对象D：D是具有相同特性的数据元素集合数据关系R:若D为空集，则R为空集,则称BinaryＴｒｅｅ为空二叉树;若D不为空集,否则R={Ｈ},H是如下二元关系:在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；若D-{root}≠空集，则存在Ｄ－{ｒoｏｔ}的一个划分{Ｄ1,Dｒ}且D1∩Ｄr=空集；若D1≠空集,则Ｄ1中存在唯一元素ｘ１,<rooｔ,x1>∈H，且存在D1ｓhaｎgｄeguanxｉH1＝H;ruoＤr≠空集，则Ｄr中存在唯一的元素,ｘr,＜ｒoot，xr>∈H,且存在Dr上的关系Hr∈H;H={＜rｏot，x1>,<rooｔ,xｒ>,H1，Ｈｒ};(D１,{Ｈ1}）是一棵符合本定义的二叉树,称为根的左子树,(Dr，{Hｒ｝）是一棵符合本定义的二叉树,称为根的右子树基本操作P:ＩnｉtBiＴree(&T）操作结果：构造空二叉树ＴＤeｓtrｏyＢiＴrｅｅ（&T)初始条件：二叉树T存在操作结果:销毁二叉树TＣreａteBｉTrｅe(&T，definitiｏｎ)初始条件:definｉtiｏn给出二叉树T的定义操作结果：按definｉtion构造二叉树ＴCｌearＢiTreｅ（&Ｔ)初始条件:二叉树T存在操作结果：将二叉树T清空为空树TｒeｅBiＥmpty(T)初始条件:二叉树T存在操作结果:若二叉树T为空树,则返回TRUＥ,否则返回FAＬSETreeＢiDepth（T）初始条件:二叉树T存在操作结果:返回二叉树T的深度Ｒoot（T)初始条件:二叉树T存在操作结果:返回T的根Valｕe（T，cur_ｅ）初始条件：二叉树T存在，cur_e是T中的某个结点操作结果:返回ｃuｒ_e的值Assigｎ（T，ｃｕr_e，ｖａｌｕe）初始条件：二叉树T存在，cur_ｅ是T中的某个结点操作结果:结点cur_e赋值为vaｌuePareｎt（T,cur_e)初始条件:而擦树Ｔ存在，cuｒ_ｅ是T中的某个结点操作结果：若cur_e是非根结点,则返回它的双亲，否则函数值为空LeftＣｈild（T，cｕr_e）初始条件：二叉树T存在,ｃur＿e是T中的某个结点操作结果：若cｕr_ｅ是T的非叶子结点，则返回它的最左孩子,否则返回空RighｔChilｄ(&T,＆ｐ,ｉ）初始条件：二叉树T存在,ｃur_ｅ是T中的某个结点操作结果:若cｕr_e有右兄弟,则返回它的右兄弟,否则函数值为空ＬeftＳibｌｉng（T,e）初始条件:二叉树Ｔ存在,e是T中的某个结点操作结果：返回e的左兄弟,若e是Ｔ的左孩子或无左兄弟,返回空ＲigｈtＳibliｎg(T,ｅ)初始条件:二叉树T存在,e是T中的某个结点操作结果:返回e的右兄弟,若ｅ是T的右孩子或无右兄弟,返回空InserｔChilｄ（&T，&p，I,c）初始条件:二叉树T存在,p指向Ｔ中某个结点，１＜=ｉ<＝p所指结点的度+1,非空树c与T不相交操作结果:插入c为T中p指结点的第i棵子树DeｌeteＣhｉld(&T，&p,i）初始条件:树T存在,p指向T中某个结点，1<=i＜＝p所值结点的度操作结果:删除Ｔ中p所指结点的第i棵子树PｒeOrｄｅrTrａvｅreseTｒｅｅ（T，Visit()）初始条件:二叉树Ｔ存在，Visiｔ是对界定操作的应用函数操作结果:先序遍历T，对每个结点调用函数ｖisit(）一次且仅一次，一旦visｉt(）失败，则操作失败ＩnＯｒderTrａvereseTree（T,Viｓiｔ()）初始条件:二叉树T存在,Ｖｉsiｔ是对界定操作的应用函数操作结果：中序遍历T，对每个结点调用函数visit(）一次且仅一次，一旦ｖiｓit()失败，则操作失败PoｓtOrｄerTｒａvｅreseTreｅ(T，Visit()）初始条件：二叉树T存在，Ｖiｓit是对界定操作的应用函数操作结果:后序遍历T,对每个结点调用函数ｖisｉt（）一次且仅一次，一旦viｓit()失败,则操作失败}AＤTTｒｅe堆栈ＡDTStaｃk{数据对象:D＝｛∈ElｅmTypｅ,i＝1,2,…，n,n＞=0}数据关系:R1={∈Ｄ,ｉ＝2,…,ｎ}基本操作：IｎitStａck(＆S)操作结果:构造一个空栈SDeｓtｒoyＳｔack（&S）初始条件:栈S已存在操作结果：栈S被销毁ClearStａｃk（&S）初始条件：栈S已存在操作结果:栈Ｓ清为空栈StackＥmｐty(S）初始条件:栈S已存在操作结果：若Ｓ为空栈，则返回TＲUE,否则FALSEＳｔaｃkLengｔｈ(S)初始条件：栈S已存在操作结果：返回Ｓ元素的个数，即栈的长度GeTop（Ｓ，&e)初始条件:栈Ｓ已存在且非空操作结果:用e返回S的栈顶元素Ｐush（&Ｓ，e)初始条件：栈S已存在操作结果：插入元素ｅ为新的栈顶元素Pｏp（&S,＆e)初始条件：栈S已存在且非空操作结果:删除S的栈顶元素,并返回ｅStacｋTｒavｅrｓe(S,viｓit(））初始条件：栈S已存在且非空操作结果:从栈底到栈顶依次对S的每个元素调用函数visiｔ(),一旦visit(）失败,则操作失败}ＡDＴStａck算法的基本思想以(A+B)*(C－D/Ｅ)这样一个表达式为列求它的后缀表达式按照优先级加上括号,得到：(A+B）*(C－(Ｄ/E))然后从最外层括号开始,依次转化成二叉树1、根是*,左子树（A＋B)，右子树(C-(D/Ｅ)）2、右子树的根-,右子树的左子树C,右子树的右子树（D／Ｅ)３、(A+B)的根+,左子树Ａ,右子树B4、(Ｄ/Ｅ）的根／，左子树D,右子树E*+-A/*+-A/BCDE再逆序遍历二叉树可得逆波兰表达式为：AB+CDE／-*运用堆栈的方法计算后缀表达式的值程序的流程程序由三个模块组成:（１）输入模块:在主函数中输入中缀表达式(2）转换模块:将中缀表达式转换为后缀表达式,并打印(3）计算模块：生成的后缀表达式用于计算，打印最后结果三、具体设计物理数据类型二叉树＃definｅMａx＿ＴREＥ＿ＳIZE1０0TyｐedeｆTElemTｙpeＳｑBiTree[MＡX_TＲEＥ_SIZE];SqBiTrｅeｂt;堆栈#ｄefｉｎeＳTACK_INIT＿ＳIZE１0０#ｄｅｆｉneSＴＡCKINCＲEＭENT10#defineＯK 1#ｄefineTＲUE1#ｄefｉneFALＳＥ0#defｉｎeＥRROR０#ｄefineOVEＲＦLOW-２tyｐeｄeｆfloatSElｅmtｙｐe;tyｐｅdｅfinｔStａtus;算法的具体环节/／基本操作的函数原型／/二叉树的存储结构表达TyｐedeｆｓtｒucｔＢiTNode{ＴEｌeｍTypedａta;SｒtucｔＢiTＮodｅ*lchild,*rchild;}ＢiTNｏde,*BｉTrｅe；//基本操作的函数原型说明StａtｕｓＣreatBiTrｅe(ＢiTrｅe＆T)//按先序顺序插入二叉树中结点的值（一个字符)//构造二叉链表表达二叉树TＳtatusＰｒeＯrderTrａverse（ＢｉTreｅT,Status（*Vｉsiｔ）(TELemTｙpｅe)）/／采用二叉链表的存储结构，Visｉt是对结点操作的应用函数//先序遍历二叉树，对每个结点调用且仅调用一次Vｉｓit函数//一旦Ｖiｓit函数失败则操作失败StatｕsIｎOrderTravｅrse（ＢiＴreeＴ，Staｔus（*Ｖiｓit)(TELemTypee)）//采用二叉链表的存储结构，Vｉｓit是对结点操作的应用函数//中序遍历二叉树，对每个结点调用且仅调用一次Viｓit函数/／一旦Ｖisit函数失败则操作失败StatusPｏsｔOrdｅrTｒaveｒｓe（BiTreeT,Stａtuｓ(*Viｓit）(TELｅmTyｐee)）//采用二叉链表的存储结构,Viｓｉｔ是对结点操作的应用函数//后序遍历二叉树，对每个结点调用且仅调用一次Visit函数／/一旦Visiｔ函数失败则操作失败／/堆栈的存储结构表达tyｐedｅfstruct{ﻩSEleｍｔypｅ*baｓe； SElｅmtｙpｅ*tｏp;ﻩinｔｓtackｓize；}SqStａck；ＳtaｔｕsInitStａck(SｑＳｔack&Ｓ)｛ﻩS.base＝(SＥlｅmtypｅ*)mａlｌｏc（STACK_INＩT＿SＩZE*sizeoｆ(SEleｍｔypｅ))； if(！S.baｓｅ)exｉt(OＶEＲＦLＯW); S.top=S．bａse; S.stackｓizｅ=ＳTACＫ＿ＩＮＩT＿ＳＩZE; rｅtｕrnＯK;｝intStａckＬength(SｑStacｋＳ）{／/获得堆栈元素的个数//填空returｎＳ.ｔop-S．base;}ＳtatusPuｓh(SｑStack&S,SＥｌemtypee){／/入栈//填空S.ｔop＋+;*(Ｓ.top)=ｅ;ｒeｔｕrnｔrue;｝StatusPoｐ(SqSｔack&S,SＥlemtｙpｅ&ｅ）{//出栈//填空 if(S.top＜