重言式判别sjjgkcsj.docx

重言式判别SjjgkCSj数据结果实验报告题目：编制一个重言式判别程序一:需求分析1：一个逻辑表达式如果对于其变元的任一种取值都为真，则称为重言式;反之，如果对于其变元的任一种取值都为假，则称为矛盾式;然而，更多的情况下，既非重言式，也非矛盾式。试写一程序，通过真值表判断一个逻辑表达式属于那一类。2:逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括“I”，和，分别表示或、与和非，运算优先程度递增，但可以有括号改变，即括号内的运算优先。逻辑变元为大写字母。表达式中任何地方都可以含有多个空格符。3:若是重言式或矛盾式，可以只“显示TrUeforever"或"Fa1seforever,否则显示rtSatisfactib1ew以及变量名序列，与用户交互。若用户对表达式中变元取一组值，程序就求出并显示逻辑表达式的值。4:测试数据：(I)(AIA)&(B|B)(A&“A)&C(3) A&B&C&B(4) (AB)(AB)(5) A1B1C1D1EA(6)A&B|A&0,0;1;1,0;1,1.二:概要设计二叉树的抽象数据类型定义如下：ADTBinaryTree数据对象:D是具有相同特性的数据元素的集合。数据关系：若D为空集，称BinaryTree为空二叉树；否则关系R=H:(1)在D中存在唯一的称为根的数据元素root,它在关系H下无前驱；(2)D中其余元素必可分为两个互不相交的子集1和R,每一个子集都是一棵符合本定义的二叉树，并分别为root的左子树和右子树。如果左子树1不空，则必存在一个根结点，它是root的左后继(CrOot,>?H),如果右子树R不空，则必存在一个根结点为root的右后继(<root,>?H)。基本操作P：结构初始化InitBiTree(H);操作结果:构造空二叉树T0CreateBiTree(&T,definition);初始条件:definition给出二叉树T的定义。操作结果：按definition构造二叉树To销毁结构DestroyBiTree(&T);初始条件:二叉树T存在。操作结果:销毁二叉树To引用型操作BiTreeEmpty(T);初始条件:二叉树T存在。操作结果:若T为空二叉树，则返回TRUE,否则返回FA1SE和树相同，创建二叉树的算法取决于它的数据元素之间关系的输入方式。BiTreeDepth(T);初始条件:二叉树T存在。操作结果:返回T的深度。Root(T);初始条件:二叉树T存在。操作结果:返回T的根。Va1ue(T,e);初始条件:二叉树T存在，e是T中某个结点。操作结果:返回e的值。Parent(T,e);初始条件:二叉树T存在，e是T中某个结点。操作结果:若e是T的非根结点，则返回它的双亲，否则返回空。1eftChi1d(T,e);初始条件:二叉树T存在，e操作结果:返回e的左孩子。e);初始条件:二叉树T存在，e操作结果:返回e的右孩子。e);初始条件:二叉树T存在，e操作结果:返回e的左兄弟。是T中某个结点。若e无左孩子,则返回空。RightChi1cKT,是T中某个结点。若e无右孩子，则返回空1eftSib1ing(T,是T中某个结点。若e是其双亲的左孩子或无左兄弟，则返回空。RightSibIin晨T,e);初始条件:二叉树T存在，e是T的结点。操作结果:返回e的右兄弟。若e是其双亲的右孩子或无右兄弟，则返回空。PreOrderTraverse(T,visit();初始条件：二叉树T存在，visit是对结点操作的应用函数。操作结果:先序遍历T,对每个结点调用函数visit一次且仅一次。一旦visit()失败，则操作失败。TnOrderTraverse(T,vsit();初始条件:二叉树T存在，visit是对结点操作的应用函数。操作结果：中序遍历T,对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。PostOrderTraverse(T,visit();初始条件：二叉树T存在，visit是对结点操作的应用函数。操作结果:后序遍历T,对每个结点调用函数visit一次且仅一次。,数据结构上机试验报告,，重言式判别第3页共10页一旦visit()失败，则操作失败。1eve1OrderTraverse(T,visit();初始条件:二叉树T存在，visit是对结点操作的应用函数。操作结果:层序遍历T,对每个结点调用函数visit一次且仅一次。一旦visit()失败，则操作失败。加工型操作C1earBiTree(&T);初始条件:二叉树T存在。操作结果:将二叉树T清为空树。Assign(&T,&e,va1ue);初始条件:二叉树T存在，e是T中某个结点。操作结果:结点e赋值为va1ue0InsertChiId(&T,p,1R,c);初始条件:二叉树T存在，P指向T中某个结点，1R为。或1非空二叉树c与T不相交且右子树为空。操作结果:根据1R为O或1插入C为T中P所指结点的左或右子树。P所指结点原有左或右子树成为c的右子树。De1eteChiId(&T,p,1R);)ADTBinaryTree三:详细设计1：程序如下；#inc1ude<iostream>ttinc1ude<cmath>#inc1ude<stdio.h>usingnamespacestd;charbia100;boo1bianva126;structtw(intdata;tw*1c,*rc;；boo1findkuo(int&i,int&j,boo11c)找配对括号intii=i+1,jj=j1;if(Ic)whi1e(ii<=j)if(biaii=,),)i=ii;if(i!=j)returnfa1se;returntrue;)if(biaii=,(,)findkuo(ii,j,1c);ii+;)e1se(whi1e(i<=jj)(if(biajj=(,)j=jj；if(i!=j)returnfa1se;returntrue;)if(biajj>-),)findkuo(i,jj,!1c);jj;)returntrue;boo1f(tw*&pt,inti,intj)/传进表达式最外层保证无括号intii=i,jj;if(ii<j)存在优先级最低算符，则寻找if(biaii>,A,&&biaii<=,Z,)首元字母为变元ii+;if(biaii=-C)找括号得另一半位置赋值iifindkuo(ii,j,true);/boo1型ture表示ii=j,否则ii!=jii+;)jj=ii+1;whi1e(jj<=j)寻找优先级最低算符if(biajj=C)findkuo(jj,j,true);e1seif(biajj=biaii(biaii=,&&biajj=,)11(biaii=-",M(biajj<,A,biajj>,Z,)ii=jj;jj+；)pt=newtw;pt->data=biaii;if(biaii>=A,&&biaii<=Z,)pt->1c=pt->rC=NU11;e1seif(biaii='')pt->Ic=NU11;jj=ii+1;if(biajj=-CMfindkuo(jj,j,true)f(pt->rc,ii+2,j-1);e1sef(pt->rc,ii÷1,j);)e1seif(biaii>biaii>,)jj=ii-1;if(biajj=,),Mfindkuo(i,jj,fa1se)f(pt->1c,i+1,ii-2);e1sef(pt->1c,i,ii-1);jj=ii+1;if(biajj=-(,Mfindkuo(ii,jj,true)f(pt->rc,ii+2,j-1);e1sef(pt->rc,ii+1,j);)returntrue;)boo1torf(consttw*pt)/bianva126-boo1,(if(pt->data>,A,&&pt->data<=，Z,)returnbianva1pt->data-,A,;e1seif(pt->data=-"')return!torf(pt->rc);e1seif(pt->data=,)return(torf(pt->1c)&&torf(pt->rc);e1sereturn(torf(pt->1c)torf(pt->rc);)intcacu1ate(tw*&pt,charcha,intn,boo1wheone)判别还是求值,/true为判别if(wheone)(intm=pow(2,n),i=0,charn;boo1tof;whi1e(i<m)(charn=i;for(intj=0;j<n;j+)bianva1chaj>A,=(charn%2?fa1se:true);charn=2;endforif(i=0)tof=torf(pt);e1seif(tof!=torf(pt)return-1;i+；/endwhi1eif(tof)return1;e1sereturn0;e1secout<<z,ttinputtheva1ue:,<<end1;COUt<<"tt"inti=0,j;whi1e(i<n)(cin>>j;if(j)bianva1chai+-'A,=true;e1sebianva1chai+-'A,=fa1se;returntorf(pt);)boo1destroytw(tw*pt)if(!pt)returntrue;if(pt->1c)destroytw(pt->1c);if(pt->rc)destroytw(pt>rc);de1etept;)voidzhongyan()charcom;whi1e(system(z,c1s.exe,z),cout<<zz*重言式判别*nn”,cout<<t行重言式判别或者是求值，请输入'y',否则如退出请输入,e,:nt，cin>>com,com!=，e,)if(com!=,e,&&com!=,y,)continue;COUt<<"tt请输入逻辑表达式(注意:格式要正确):ntt”;charcha26,cc;inti=0,j=0,n=0;for(intii=O;ii<26;ii+)bianva1ii=fa1se;getchar();boo1f1a=fa1se;whi1e(scanf(zz%czz,&cc),cc!=*n,)(if(cc!,)(if(!(cc