數(shù)據(jù)結(jié)構(gòu)報(bào)告—重言式判別(共14頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí)習(xí)報(bào)告題目：重言式判別班級(jí)：計(jì)算機(jī)學(xué)院 姓名：盧魏旭 學(xué)號(hào)： 完成日期：2012年11月一、 需求分析試寫一個(gè)程序，通過(guò)真值表判斷一個(gè)邏輯表達(dá)式屬于哪一類的表達(dá)式基本要求：1） 邏輯表達(dá)式從終端輸入，長(zhǎng)度不超過(guò)一行，邏輯運(yùn)算符包括“|”，“&”和“”，分別表示或，與和非，運(yùn)算優(yōu)先程度遞增，但可以由括號(hào)改變，即括號(hào)內(nèi)的運(yùn)算符優(yōu)先。邏輯變?cè)獮榇髮懽帜福磉_(dá)式中任意地方都可以含有空格符。2） 若是重言式或者矛盾式，可以只顯示“True forever”或者“False forever”，否者顯示“Statisfactible”，與用戶交互，若用戶對(duì)表達(dá)式中變?cè)《?/p>

2、一組值，程序就求出并顯示邏輯表達(dá)式的值。3） 附加要求，可以根據(jù)用戶要求，列出該邏輯表達(dá)式的真值表。測(cè)試數(shù)據(jù)：1) (A|A)&(B|B)2) (A&A)&C3) A|B|C|D|E|A二、 概要設(shè)計(jì)為實(shí)現(xiàn)上述程序功能，以二叉樹的結(jié)構(gòu)來(lái)存儲(chǔ)邏輯表達(dá)式，通過(guò)一個(gè)輔助棧來(lái)完成建樹過(guò)程二叉樹的抽象數(shù)據(jù)類型定義為：ADT Bitree數(shù)據(jù)對(duì)象 D：D是具有相同特性的數(shù)據(jù)元素的集合數(shù)據(jù)關(guān)系 R：基本操作:creatbitree(&B,&S1,&S2,*a)初始條件：樹B，棧S1，S2存在操作結(jié)果:通過(guò)兩個(gè)輔助的棧S1，S2將元素a值建在二叉樹內(nèi)showtr

3、ee(B)初始條件：二叉樹B存在操作結(jié)果：先序遍歷二叉樹，輸出每一個(gè)節(jié)點(diǎn)中的信息（用于檢測(cè)）voluation($B,c,value)初始條件：二叉樹B存在操作結(jié)果：通過(guò)先序遍歷二叉樹，對(duì)樹中變量為c的結(jié)點(diǎn)賦值value excel(B,i,c,v,*x)初始條件：二叉樹存在操作結(jié)果：通過(guò)遞歸的算法在一維數(shù)組v中記錄各個(gè)變量各種賦值情況（所有賦值情況的真值結(jié)果記錄）此外以棧的存儲(chǔ)結(jié)構(gòu)做輔助棧的抽象數(shù)據(jù)類型定義為：ADT Bstack數(shù)據(jù)對(duì)象:D=a|ai<-ElemSet,i=1,2,3n數(shù)據(jù)關(guān)系:R1=<ai-1,ai>|ai-1,ai <-D,i=1,2,3n基本操

4、作：creatstack(&S)操作結(jié)果：建立一個(gè)空棧SPushstack(&S,&B)初始條件：棧S存在操作結(jié)果：將一個(gè)二叉樹的結(jié)點(diǎn)入棧Popstack(&S，&B)初始條件：棧S存在操作結(jié)果：從棧中取出一個(gè)二叉樹的結(jié)點(diǎn)showstack(S)初始條件：棧S存在操作結(jié)果：訪問(wèn)棧內(nèi)結(jié)點(diǎn)，查看元素信息Gettop(S)初始條件：棧S存在操作結(jié)果：返回棧頂元素三、 詳細(xì)設(shè)計(jì)#include<stdio.h>#include<malloc.h>#include<windows.h>#include<math.h>

5、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,Bitr

6、ee &B)S.top-;B=*S.top;Bitree Gettop(Bstack S)return *(S.top-1);int Judge(char c) /判斷字符是運(yùn)算符還是操作符if(c>='A'&&c<='Z'|c>='a'&&c<='z'|c='0'|c='1')return 1;elsereturn 0;char compare(char c1,char c2) /比較兩個(gè)運(yùn)算符的優(yōu)先級(jí)char c='-1&#

7、39;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 '&

8、':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、#39;:c='>'break;case '&':c='>'break;case '':c='>'break;case '(':c='<'break;case ')':c='>'break;case '#':c='>'break; break;case '(':switch(c2) case '|':c='<'break;c

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

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

12、='<'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操作符棧，為運(yùn)算數(shù)棧 建立二叉樹過(guò)程類似于算術(shù)表達(dá)式求值int i=0,len=0,flag=1; char c;Bit

13、ree b1;b1=(Bitree)malloc(sizeof(BiTnode);b1->data='#'b1->value=0;b1->lchild=NULL;b1->rchild=NULL;Pushstack(S1,b1); /先在運(yùn)算符棧里存放一個(gè)data值為“#”的結(jié)點(diǎn)做標(biāo)記while(ai)len+;i+;i=0;c=a0;while(c!='#'|Gettop(S1)->data!='#')c=ai;if(c=' ') /若有空格，直接忽略掉i+;continue;if(i>=len

14、)c='#'Bitree b;b=(Bitree)malloc(sizeof(BiTnode); 建立一個(gè)樹的結(jié)點(diǎn)b->data=c;b->value=0;b->lchild=NULL;b->rchild=NULL;if(Judge(c)Pushstack(S2,b); /若是操作數(shù)的結(jié)點(diǎn)則進(jìn)棧i+;continue;elsechar c1=compare(Gettop(S1)->data,c);if(c1='-1')flag=0;break;switch(c1)case '<':printf("執(zhí)行

15、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ùn)算符優(yōu)先級(jí)高，則先建立二叉樹char c2=Gettop(S1)->data;Bitree a0,a1; /先取一個(gè)運(yùn)算符和一個(gè)操作數(shù)，將操作數(shù)連接在運(yùn)算符的右孩子上Popstack(S1,

16、a0);Popstack(S2,a1);a0->rchild=a1;if(c2!='') /如果不是“”運(yùn)算符，再取一個(gè)結(jié)點(diǎn)連接在運(yùn)算符結(jié)點(diǎn)的左孩子上Bitree a2;Popstack(S2,a2);a0->lchild=a2;Pushstack(S2,a0);elsePushstack(S2,a0);if(flag) /表達(dá)式輸入無(wú)誤則繼續(xù)進(jìn)行B=Gettop(S2);return 1;elsereturn 0;void caculate(Bitree B) /采用后序遍歷判斷邏輯表達(dá)式的真值if(B)caculate(B->lchild);caculat

17、e(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;br

18、eak;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(B-&

19、gt;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) /采用遞歸算法為所有的變量賦值，用數(shù)組v記錄下每一種變量復(fù)制后邏輯表達(dá)式的真值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);el

20、secaculate(B);v*x=B->value;(*x)-;int search(char *a,char *ch) /查找表達(dá)式中的變量，放入ch數(shù)組中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(int

21、*v) /根據(jù)所有賦值情況，判斷邏輯表達(dá)式是哪種類型的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("是否自行為表達(dá)式賦值以計(jì)算真值?(Y/N)n");cha

22、r 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("賦值有誤！請(qǐng)重新輸入：");scanf("%d",&x);voluation(b,chk,x);k+;caculate(b);printf("表達(dá)式? ")

23、;show(a);printf(" 的真值為%dn",b->value);void change(int *b,int x,int sum) /將十進(jìn)制轉(zhuǎn)換為二進(jìn)制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"

24、;);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);char a

25、100,ch10;/a記錄表達(dá)式,ch記錄變量值for(int k=0;k<10;k+)/初始化變量數(shù)組chk='0'for(int m=0;m<200;m+)/初始化真值表數(shù)組v2m=-1;v1m=-1;gets(a);/輸入表達(dá)式j(luò)=search(a,ch);/獲取所有變量的個(gè)數(shù)yn=pow(2,(double)j)-1;/要賦值的次數(shù)flag=creatBiTree(b,S1,S2,a);/根據(jù)表達(dá)式建立二叉樹if(flag)excel(b,0,ch,v1,&n);/計(jì)算所有變量賦值的真值switch(Judge2(v1)case 'T'

26、;:printf("表達(dá)式為永真式n");break;case 'F':printf("表達(dá)式為永假式n");break;case 'O':printf("表達(dá)式為不確定式n");selfvoluation(b,ch,a);break;elseprintf("表達(dá)式輸入有誤n");TrueExcel(a,ch,j,v2,v1);system("PAUSE");四、 調(diào)試分析1、 本程序?qū)崿F(xiàn)了邏輯表達(dá)式的求值，判斷，以及真值表的輸出，程序的難點(diǎn)在于邏輯表達(dá)式的二叉樹

27、建立，以及其判斷，二叉樹的建立creatbitree()依靠?jī)蓚€(gè)工作棧實(shí)現(xiàn)的，形式類似于算術(shù)表達(dá)式的求值，不過(guò)這里是建樹，存放變量的結(jié)點(diǎn)作為葉子結(jié)點(diǎn)，存放運(yùn)算符的結(jié)點(diǎn)作為根結(jié)點(diǎn)，這是自底向上的算符優(yōu)先法，第二個(gè)難點(diǎn)在于對(duì)所有的變量的所有情況賦值，這里采用了簡(jiǎn)單的遞歸算法，這個(gè)算法我自己做的時(shí)候花了很長(zhǎng)時(shí)間來(lái)想，excel()遞歸時(shí)候，對(duì)每個(gè)變量有0和1兩種賦值情況，每當(dāng)遞歸到最頂層時(shí)，調(diào)用caculate()算法計(jì)算一次真值，然后將值存放到函數(shù)攜帶的一維數(shù)組中去。2、 本程序中最核心的算法應(yīng)該是caculate()算法，采用的是后序遍歷的方法，通過(guò)根節(jié)點(diǎn)的運(yùn)算符結(jié)合左右孩子結(jié)點(diǎn)中變量所攜帶的value值計(jì)算真值，并將結(jié)果寫入到根結(jié)點(diǎn)里去，最終一棵樹的真值將會(huì)存