数据结构报告—重言式判别

1、实习报告题目：重言式判别班级：计算机学院12052313 姓名：卢魏旭 学号：12051521 完成日期：2012年11月一、 需求分析试写一个程序，通过真值表判断一个逻辑表达式属于哪一类的表达式基本要求：1） 逻辑表达式从终端输入，长度不超过一行，逻辑运算符包括“|”，“&”和“”，分别表示或，与和非，运算优先程度递增，但可以由括号改变，即括号内的运算符优先。逻辑变元为大写字母，表达式中任意地方都可以含有空格符。2） 若是重言式或者矛盾式，可以只显示“True forever”或者“False forever”，否者显示“Statisfactible”，与用户交互，若用户对表达式中变

2、元取定一组值，程序就求出并显示逻辑表达式的值。3） 附加要求，可以根据用户要求，列出该逻辑表达式的真值表。测试数据：1) (A|A)&(B|B)2) (A&A)&C3) A|B|C|D|E|A二、 概要设计为实现上述程序功能，以二叉树的结构来存储逻辑表达式，通过一个辅助栈来完成建树过程二叉树的抽象数据类型定义为：ADT Bitree数据对象 D：D是具有相同特性的数据元素的集合数据关系 R：基本操作:creatbitree(&B,&S1,&S2,*a)初始条件：树B，栈S1，S2存在操作结果:通过两个辅助的栈S1，S2将元素a值建在二叉树内sho

3、wtree(B)初始条件：二叉树B存在操作结果：先序遍历二叉树，输出每一个节点中的信息（用于检测）voluation($B,c,value)初始条件：二叉树B存在操作结果：通过先序遍历二叉树，对树中变量为c的结点赋值value excel(B,i,c,v,*x)初始条件：二叉树存在操作结果：通过递归的算法在一维数组v中记录各个变量各种赋值情况（所有赋值情况的真值结果记录）此外以栈的存储结构做辅助栈的抽象数据类型定义为：ADT Bstack数据对象:D=a|ai<-ElemSet,i=1,2,3n数据关系:R1=<ai-1,ai>|ai-1,ai <-D,i=1,2,3n

4、基本操作：creatstack(&S)操作结果：建立一个空栈SPushstack(&S,&B)初始条件：栈S存在操作结果：将一个二叉树的结点入栈Popstack(&S，&B)初始条件：栈S存在操作结果：从栈中取出一个二叉树的结点showstack(S)初始条件：栈S存在操作结果：访问栈内结点，查看元素信息Gettop(S)初始条件：栈S存在操作结果：返回栈顶元素三、 详细设计#include<stdio.h>#include<malloc.h>#include<windows.h>#include<math.h&

5、gt;typedef struct BiTnodechar data;int value;struct BiTnode *lchild,*rchild;*Bitree;typedef struct BstackBitree *top;Bitree *base;void creatstack(Bstack &S)S.base=(Bitree*)malloc(sizeof(BiTnode);S.top=S.base;void Pushstack(Bstack &S,Bitree &B)*S.top=B;S.top+;void Popstack(Bstack &S,B

6、itree &B)S.top-;B=*S.top;Bitree Gettop(Bstack S)return *(S.top-1);int Judge(char c) /判断字符是运算符还是操作符if(c>='A'&&c<='Z'|c>='a'&&c<='z'|c='0'|c='1')return 1;elsereturn 0;char compare(char c1,char c2) /比较两个运算符的优先级char c='-

7、1'switch(c1)case '|':switch(c2) case '|':c='>'break;case '&':c='<'break;case '':c='<'break;case '(':c='<'break;case ')':c='>'break;case '#':c='>'break; break;case '&a

8、mp;':switch(c2) case '|':c='>'break;case '&':c='>'break;case '':c='<'break;case '(':c='<'break;case ')':c='>'break;case '#':c='>'break; break;case '':switch(c2) case '

9、;|':c='>'break;case '&':c='>'break;case '':c='>'break;case '(':c='<'break;case ')':c='>'break;case '#':c='>'break; break;case '(':switch(c2) case '|':c='<'brea

10、k;case '&':c='<'break;case '':c='<'break;case '(':c='<'break;case ')':c='='break; break;case ')':switch(c2) case '|':c='>'break;case '&':c='>'break;case '':c='&g

11、t;'break;case '(':c='>'break;case ')':c='>'break;case '#':c='>'break; break;case '#':switch(c2) case '|':c='<'break;case '&':c='<'break;case '':c='<'break;case '('

12、;:c='<'break;case '#':c='='break; break;return c;void showstack(Bstack S)while(S.base!=S.top)S.top-;printf("%cn",(*S.top)->data);int creatBiTree(Bitree &B,Bstack &S1,Bstack &S2,char *a) /S1为a操作符栈，为运算数栈 建立二叉树过程类似于算术表达式求值int i=0,len=0,flag=1; char c;

13、Bitree b1;b1=(Bitree)malloc(sizeof(BiTnode);b1->data='#'b1->value=0;b1->lchild=NULL;b1->rchild=NULL;Pushstack(S1,b1); /先在运算符栈里存放一个data值为“#”的结点做标记while(ai)len+;i+;i=0;c=a0;while(c!='#'|Gettop(S1)->data!='#')c=ai;if(c=' ') /若有空格，直接忽略掉i+;continue;if(i>=

14、len)c='#'Bitree b;b=(Bitree)malloc(sizeof(BiTnode); 建立一个树的结点b->data=c;b->value=0;b->lchild=NULL;b->rchild=NULL;if(Judge(c)Pushstack(S2,b); /若是操作数的结点则进栈i+;continue;elsechar c1=compare(Gettop(S1)->data,c);if(c1='-1')flag=0;break;switch(c1)case '<':printf("

15、;执行D“<”:n ");Pushstack(S1,b);i+;break;case '=':printf("执行D“=”: n");if(c!='#')Popstack(S1,b);i+;break;elsebreak;case '>':printf("执行D“>”: n"); /如果栈顶运算符优先级高，则先建立二叉树char c2=Gettop(S1)->data;Bitree a0,a1; /先取一个运算符和一个操作数，将操作数连接在运算符的右孩子上Popstack(

16、S1,a0);Popstack(S2,a1);a0->rchild=a1;if(c2!='') /如果不是“”运算符，再取一个结点连接在运算符结点的左孩子上Bitree a2;Popstack(S2,a2);a0->lchild=a2;Pushstack(S2,a0);elsePushstack(S2,a0);if(flag) /表达式输入无误则继续进行B=Gettop(S2);return 1;elsereturn 0;void caculate(Bitree B) /采用后序遍历判断逻辑表达式的真值if(B)caculate(B->lchild);cacu

17、late(B->rchild);switch(B->data)case '|':B->value=B->lchild->value|B->rchild->value;break;case '&':B->value=B->lchild->value&&B->rchild->value;break;case '':B->value=!B->rchild->value;break;case '0':B->value=0

18、;break;case '1':B->value=1;break;void showtree(Bitree B) /先序遍历二叉树if(B)printf("%c ",B->data);showtree(B->lchild);showtree(B->rchild);void voluation(Bitree B,char c,int value)/采用先序遍历为二叉树的变量赋值if(B)if(B->data=c)B->value=value;voluation(B->lchild,c,value);voluation(

19、B->rchild,c,value);void show(char *a)int i=0;while(ai)if(ai=' ')i+;continue;printf("%c",ai);i+;void excel(Bitree B,int i,char *c,int v,int *x) /采用递归算法为所有的变量赋值，用数组v记录下每一种变量复制后逻辑表达式的真值if(ci!='0')voluation(B,ci,0);i+;excel(B,i,c,v,x);i-;voluation(B,ci,1);i+;excel(B,i,c,v,x)

20、;elsecaculate(B);v*x=B->value;(*x)-;int search(char *a,char *ch) /查找表达式中的变量，放入ch数组中int i=0,k=0,flag=1;while(ai) if(ai>='A'&&ai<='Z')int j=0;while(chj!='0')if(chj=ai)flag=0;break;j+;if(flag)chk=ai;k+;i+;flag=1;/printf("%d n",k);return k;char Judge2(i

21、nt *v) /根据所有赋值情况，判断逻辑表达式是哪种类型的int i=0,flag1=0,flag2=0,flag3=0;while(vi!=-1)if(vi=0)flag1=1;if(vi=1)flag2=1;if(flag1&&flag2)return 'O'i+;if(flag1)return 'F'if(flag2)return 'T'void selfvoluation(Bitree b,char ch,char a) /用户自行赋值printf("是否自行为表达式赋值以计算真值?(Y/N)n");

22、char c;c=getchar();if(c='Y'|c='y')int k=0,x; while(chk!='0')printf("为%c赋值：êo%c=",chk,chk);scanf("%d",&x);while(x!=0&&x!=1)printf("赋值有误！请重新输入：");scanf("%d",&x);voluation(b,chk,x);k+;caculate(b);printf("表达式? &quo

23、t;);show(a);printf(" 的真值为%dn",b->value);void change(int *b,int x,int sum) /将十进制转换为二进制while(x!=0)bsum=(x%2);x=x/2;sum-;void TrueExcel(char *a,char *ch,int j,int *v2,int *v1) /输出真值表int i=0;while(chi!='0')printf("%c ",chi);i+;printf("|");show(a);printf("n&q

24、uot;);for(int l=0,m=pow(2,(double)j)-1;l<pow(2,(double)j);l+,m-)change(v2,l,j-1);for(int k=0;k<j;k+)if(v2k=-1)printf("0 ");elseprintf("%d ",v2k);printf("| %dn",v1m);void main()int j=0,i=0,n,v1200,v2200,flag=0;Bitree b;Bstack S1,S2;creatstack(S1);creatstack(S2);cha

25、r a100,ch10;/a记录表达式,ch记录变量值for(int k=0;k<10;k+)/初始化变量数组chk='0'for(int m=0;m<200;m+)/初始化真值表数组v2m=-1;v1m=-1;gets(a);/输入表达式j=search(a,ch);/获取所有变量的个数yn=pow(2,(double)j)-1;/要赋值的次数flag=creatBiTree(b,S1,S2,a);/根据表达式建立二叉树if(flag)excel(b,0,ch,v1,&n);/计算所有变量赋值的真值switch(Judge2(v1)case 'T&

26、#39;:printf("表达式为永真式n");break;case 'F':printf("表达式为永假式n");break;case 'O':printf("表达式为不确定式n");selfvoluation(b,ch,a);break;elseprintf("表达式输入有误n");TrueExcel(a,ch,j,v2,v1);system("PAUSE");四、 调试分析1、 本程序实现了逻辑表达式的求值，判断，以及真值表的输出，程序的难点在于逻辑表达式的

27、二叉树建立，以及其判断，二叉树的建立creatbitree()依靠两个工作栈实现的，形式类似于算术表达式的求值，不过这里是建树，存放变量的结点作为叶子结点，存放运算符的结点作为根结点，这是自底向上的算符优先法，第二个难点在于对所有的变量的所有情况赋值，这里采用了简单的递归算法，这个算法我自己做的时候花了很长时间来想，excel()递归时候，对每个变量有0和1两种赋值情况，每当递归到最顶层时，调用caculate()算法计算一次真值，然后将值存放到函数携带的一维数组中去。2、 本程序中最核心的算法应该是caculate()算法，采用的是后序遍历的方法，通过根节点的运算符结合左右孩子结点中变量所携带的value值计算真值，并将结果写入到根结点里去，最终一