數據結構報告—重言式判別

1、實習報告題目：重言式判別班級：計算機學院12052313 姓名：盧魏旭 學號：12051521 完成日期：2012年11月一、 需求分析試寫一個程序，通過真值表判斷一個邏輯表達式屬于哪一類的表達式基本要求：1） 邏輯表達式從終端輸入，長度不超過一行，邏輯運算符包括“|”，“&”和“”，分別表示或，與和非，運算優(yōu)先程度遞增，但可以由括號改變，即括號內的運算符優(yōu)先。邏輯變元為大寫字母，表達式中任意地方都可以含有空格符。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存在操作結果：先序遍歷二叉樹，輸出每一個節(jié)點中的信息（用于檢測）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) /比較兩個運算符的優(yōu)先級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、;執(zhí)行D“<”:n ");Pushstack(S1,b);i+;break;case '=':printf("執(zhí)行D“=”: n");if(c!='#')Popstack(S1,b);i+;break;elsebreak;case '>':printf("執(zhí)行D“>”: n"); /如果棧頂運算符優(yōu)先級高，則先建立二叉樹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) /表達式輸入無誤則繼續(xù)進行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()依靠兩個工作棧實現的，形式類似于算術表達式的求值，不過這里是建樹，存放變量的結點作為葉子結點，存放運算符的結點作為根結點，這是自底向上的算符優(yōu)先法，第二個難點在于對所有的變量的所有情況賦值，這里采用了簡單的遞歸算法，這個算法我自己做的時候花了很長時間來想，excel()遞歸時候，對每個變量有0和1兩種賦值情況，每當遞歸到最頂層時，調用caculate()算法計算一次真值，然后將值存放到函數攜帶的一維數組中去。2、 本程序中最核心的算法應該是caculate()算法，采用的是后序遍歷的方法，通過根節(jié)點的運算符結合左右孩子結點中變量所攜帶的value值計算真值，并將結果寫入到根結點里去，最終一