數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告重言式的判定

山東理工大學(xué)計算機(jī)學(xué)院課程設(shè)計（數(shù)據(jù)結(jié)構(gòu)）班級姓名學(xué)號指導(dǎo)教師二○一一年一月二十日課程設(shè)計任務(wù)書及成績評定課題名稱重言式判定Ⅰ、題目的目的和要求：1、設(shè)計目的鞏固和加深對數(shù)據(jù)結(jié)構(gòu)的理解，通過上機(jī)實(shí)驗(yàn)、調(diào)試程序，加深對課本知識的理解，最終使學(xué)生能夠熟練應(yīng)用數(shù)據(jù)結(jié)構(gòu)的知識寫程序。（1）通過本課程的學(xué)習(xí)，能熟練掌握幾種基本數(shù)據(jù)結(jié)構(gòu)的基本操作。（2）能針對給定題目，選擇相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，分析并設(shè)計算法，進(jìn)而給出問題的正確求解過程并編寫代碼實(shí)現(xiàn)。2、設(shè)計題目要求：問題描述：一個邏輯表達(dá)式如果對于其變元的任意一種取值都為真，則稱為重言式；反之對于其變元的任意一種取值都為假，則為矛盾式；然而，更多的情況下，既非重言式，也非矛盾式。試寫一個程序，通過真值表判別一個邏輯表達(dá)式屬于上述哪一類?；疽螅?1)邏輯表達(dá)式從終端輸入，長度不超過一行。邏輯運(yùn)算符包括“|”，“&”和“~”，分別表示或、與和非，運(yùn)算優(yōu)先程度遞增，但可由括號改變，及括號內(nèi)的運(yùn)算優(yōu)先。邏輯變元為大寫字母。表達(dá)式中任何地方都可以含有多個空格符。(2)若是重言式或矛盾式，可以只顯示“Trueforever”或“Falseforever”，否則顯示”Satisfactible”以及變量名序列，與用戶交互。若用戶對表達(dá)式中變量取定一組值，程序就求出并顯示邏輯表達(dá)式的值。Ⅱ、設(shè)計進(jìn)度及完成情況日期內(nèi)容1.10-1.11選取參考書，查閱有關(guān)文獻(xiàn)資料，完成資料搜集和系統(tǒng)分析工作。1.12~1.14創(chuàng)建相關(guān)數(shù)據(jù)結(jié)構(gòu),錄入源程序。1.17~1.19調(diào)試程序并記錄調(diào)試中的問題，初步完成課程設(shè)計報告。1.20~1.21上交課程設(shè)計報告打印版并進(jìn)行課程設(shè)計答辯，要求每個同學(xué)針對自己的設(shè)計回答指導(dǎo)教師3-4個問題?？己私Y(jié)束后將課程設(shè)計報告和源程序的電子版交班長統(tǒng)一刻光盤上交。Ⅲ、主要參考文獻(xiàn)及資料[1]嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)（C語言版）清華大學(xué)出版社1999[2]嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)題集（C語言版）清華大學(xué)出版社1999[3]譚浩強(qiáng)C語言程序設(shè)計清華大學(xué)出版社[4]與所用編程環(huán)境相配套的C語言或C++相關(guān)的資料Ⅳ、成績評定：設(shè)計成績：（教師填寫）指導(dǎo)老師：（簽字）二○一一年一月二十一日

目錄第一章概述……………1第二章系統(tǒng)分析………2第三章概要設(shè)計………3第四章詳細(xì)設(shè)計………6第五章運(yùn)行與測試……………………13第六章總結(jié)與心得……………………15參考文獻(xiàn)………………16第一章概述課程設(shè)計是實(shí)踐性教學(xué)中的一個重要環(huán)節(jié)，它以某一課程為基礎(chǔ)，可以涉及和課程相關(guān)的各個方面，是一門獨(dú)立于課程之外的特殊課程。課程設(shè)計是讓同學(xué)們對所學(xué)的課程更全面的學(xué)習(xí)和應(yīng)用，理解和掌握課程的相關(guān)知識?！稊?shù)據(jù)結(jié)構(gòu)》是一門重要的專業(yè)基礎(chǔ)課，是計算機(jī)理論和應(yīng)用的核心基礎(chǔ)課程。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，要求學(xué)生在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計及其實(shí)現(xiàn)等方面，加深對課程基本內(nèi)容的理解。同時，在程序設(shè)計方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。選擇題目：問題描述1、一個邏輯表達(dá)式如果對于其變元的任意一種取值都為真，則稱為重言式；反之對于其變元的任意一種取值都為假，則為矛盾式；然而，更多的情況下，既非重言式，也非矛盾式。試寫一個程序，通過真值表判別一個邏輯表達(dá)式屬于上述哪一類?；疽螅海?）邏輯表達(dá)式從終端輸入，長度不超過一行。邏輯運(yùn)算符包括“|”，“&”和“~”，分別表示或、與和非，運(yùn)算優(yōu)先程度遞增，但可由括號改變，及括號內(nèi)的運(yùn)算優(yōu)先。邏輯變元為大寫字母。表達(dá)式中任何地方都可以含有多個空格符。（2）若是重言式或矛盾式，可以只顯示“Trueforever”或“Falseforever”，否則顯示“Satisfactible”以及變量名序列，與用戶交互。若用戶對表達(dá)式中變量取定一組值，程序就求出并顯示邏輯表達(dá)式的值。（3）本程序先使用棧將邏輯表達(dá)式的變量進(jìn)行儲存，然后將棧中的元素作為二叉樹的結(jié)點(diǎn)結(jié)構(gòu)，然后根據(jù)優(yōu)先級讀取表達(dá)式建立二叉樹，并通過逐個判斷根實(shí)現(xiàn)對重言式的判別。第二章系統(tǒng)分析1、邏輯表達(dá)式從終端輸入，長度不超過一行。邏輯運(yùn)算符包括“|”，“&”和“~”，分別表示或、與和非，運(yùn)算優(yōu)先程度遞增，但可由括號改變，及括號內(nèi)的運(yùn)算優(yōu)先。邏輯變元為大寫字母。表達(dá)式中任何地方都可以含有多個空格符。2、若是重言式或矛盾式，可以只顯示“Trueforever”或“Falseforever”，否則顯示”Satisfactible”以及變量名序列，與用戶交互。若用戶對表達(dá)式中變量取定一組值，程序就求出并顯示邏輯表達(dá)式的值。3、本程序先使用棧將邏輯表達(dá)式的變量進(jìn)行儲存，然后將棧中的元素作為二叉樹的結(jié)點(diǎn)結(jié)構(gòu)，然后根據(jù)優(yōu)先級讀取表達(dá)式建立二叉樹，并通過逐個判斷根實(shí)現(xiàn)對重言式的判別。4、識別邏輯表達(dá)式的符號形式并建立二叉樹可以有兩種策略：自底向上的算符優(yōu)先法和自頂向下的分割，先序遍歷建立二叉樹的方法。5、可設(shè)表達(dá)式中邏輯變量數(shù)不超過20。真值的產(chǎn)生可通過在一維數(shù)組上維護(hù)一個“軟計數(shù)器”實(shí)現(xiàn)；用遞歸算法實(shí)現(xiàn)更簡單。6、程序執(zhí)行時的命令：本程序?yàn)榱耸褂脮r的方便，采用菜單式的方式來完成程序的演示，幾乎不用輸入什么特殊的命令，只需按提示輸入選者即可。（要注意輸入時格式，否者可能會引起一些錯誤）第三章概要設(shè)計為實(shí)現(xiàn)上述程序功能，需要兩個抽象數(shù)據(jù)類型，如下：（1）//根據(jù)表達(dá)式建立的二叉樹的結(jié)點(diǎn)定義；typedefstructbtdnode{chardata;structbtdnode*lchild;structbtdnode*rchild;}*bitree;//對操作符棧和變量堆棧的操作；voidcreatstack(sqstack&st){st.base=(bitree*)malloc(stack_size_normal*sizeof(btdnode));if(!st.base)exit(0);st.top=st.base;st.stacksize=stack_size_normal;}voidpush(sqstack&st,bitreee){if(st.top-st.base<st.stacksize)*st.top++=e;elseexit(0);}voidpop(sqstack&st,bitree&e){if(st.top==st.base)exit(0);e=*--st.top;}voidgettop(sqstack&st,bitree&e){if(st.top==st.base)exit(0);e=*(st.top-1);}(2)//識別表達(dá)式使用的堆棧定義,它存放的都是樹的結(jié)構(gòu);typedefstructlnode_optr{structbtdnode**base;//棧中的元素都是樹的結(jié)點(diǎn)結(jié)構(gòu)；structbtdnode**top;intstacksize;}sqstack;//自底向上地根據(jù)運(yùn)算符地優(yōu)先級來建立分子樹函數(shù)；當(dāng)邏輯表達(dá)式讀完后-子根zigen就是一顆完整的二叉樹Intk=0;//建樹的標(biāo)志，k=1表示第一次建立分子樹，要對左右孩子的指針域處理Voidcreat(bitree&zigen,bitreel,bitreer){Zigen->lchild=1;Zigen->rchild=r;//分?jǐn)?shù)的連接If(l&&r){If(int(l->data)>=65&&int(l->data)<=90){l->lchild=NULL;l->rchild=NULL;}If(int(r->data)>=65&&int(r->data)<=90){r->lchild=NULL;r->rchild=NULL;}}}（1）主程序模塊Voidmain(){初始化While{接受命令處理命令}If(choice==0)退出}（2）對棧的操作模塊。（3）二叉樹的建立模塊，采用自底向上根據(jù)運(yùn)算符地優(yōu)先級來建立子樹函數(shù)，讀取邏輯表達(dá)式。（4）邏輯運(yùn)算符的優(yōu)先級判別模塊。（5）重言式的識別函數(shù)模塊。（6）求值模塊。3．各個模塊之間的調(diào)用關(guān)系具體如下圖：第四章詳細(xì)設(shè)計#include<stdlib.h>#include<stdio.h>#include<iostream.h>#include<string.h>#include<math.h>#definestack_size_normal100#definebianliang_max20#definestr_max60intzuhe[bianliang_max];//變量的取值組合數(shù)組定義;intN;//變量個數(shù);//根據(jù)表達(dá)式建立的二叉樹的結(jié)點(diǎn)定義;typedefstructbtdnode{chardata;structbtdnode*lchild;structbtdnode*rchild;}*bitree;//識別表達(dá)式使用的堆棧定義,它存放的都是樹的結(jié)構(gòu);typedefstructlnode_optr{structbtdnode**base;//棧中的元素都是樹的結(jié)點(diǎn)結(jié)構(gòu)；structbtdnode**top;intstacksize;}sqstack;//用于產(chǎn)生變量的各種取值組合;voidcreatzuhe(intn){inti,j=0,e,num=0;inttemp[bianliang_max];for(i=0;i<N;i++)zuhe[i]=0;while(n){e=n%2;num++;temp[j++]=e;n=n/2;}j=j-1;num=N-num;while(j>=0){e=temp[j--];zuhe[num++]=e;}}//自底向上地根據(jù)運(yùn)算符地優(yōu)先級來建立分子樹函數(shù);當(dāng)邏輯表達(dá)式讀完后-子根zigen就是一棵完整的二叉樹intk=0;//建樹的標(biāo)志，k＝1表示第一次建立分子樹，要對左右孩子的指針域處理voidcreate(bitree&zigen,bitreel,bitreer){zigen->lchild=l;zigen->rchild=r;//分樹的鏈接if(l&&r){if(int(l->data)>=65&&int(l->data)<=90){l->lchild=NULL;l->rchild=NULL;}if(int(r->data)>=65&&int(r->data)<=90){r->lchild=NULL;r->rchild=NULL;}}}//邏輯運(yùn)算符的優(yōu)先級判別；charyouxianji(charlie,charhang){inti,j;charbijiao[7][7]={'','|','&','~','(',')','#','|','>','<','<','<','>','>','&','>','>','<','<','>','>','~','>','>','>','<','>','>','(','<','<','<','<','=','',')','>','>','>','','>','>','#','<','<','<','<','','='};for(i=0;i<7;i++)if(bijiao[0][i]==lie)break;for(j=0;j<7;j++)if(bijiao[j][0]==hang)break;returnbijiao[j][i];}//對操作符棧和變量堆棧的操作；voidcreatstack(sqstack&st){st.base=(bitree*)malloc(stack_size_normal*sizeof(btdnode));if(!st.base)exit(0);st.top=st.base;st.stacksize=stack_size_normal;}voidpush(sqstack&st,bitreee){if(st.top-st.base<st.stacksize)*st.top++=e;elseexit(0);}voidpop(sqstack&st,bitree&e){if(st.top==st.base)exit(0);e=*--st.top;}voidgettop(sqstack&st,bitree&e){if(st.top==st.base)exit(0);e=*(st.top-1);}//重言式識別函數(shù)；voidcreattree(chars[],bitree&tree){sqstackvariable;//變量棧;sqstacklogic;//邏輯運(yùn)算符棧;creatstack(variable);creatstack(logic);bitreelogic_di,variables,logics,e,a,b,theta,kuohao;//定義棧中的元素;//theta為最后的二叉樹的根;logic_di=(bitree)malloc(sizeof(btdnode));if(!logic_di)exit(0);logic_di->data='#';push(logic,logic_di);while(*s!=NULL){if(int(*s)>64&&int(*s)<91){variables=(bitree)malloc(sizeof(btdnode));if(!variables)exit(0);variables->data=*s;push(variable,variables);}elseif(int(*s)>90||int(*s)<65){gettop(logic,e);//取運(yùn)算符棧的棧頂元素進(jìn)行優(yōu)先級比較switch(youxianji(*s,e->data)){case'<'://棧頂?shù)倪\(yùn)算符優(yōu)先級低,邏輯運(yùn)算符進(jìn)棧logics=(bitree)malloc(sizeof(btdnode));if(!logics)exit(0);logics->data=*s;push(logic,logics);break;case'='://脫括號并接受下一個字符;pop(logic,kuohao);break;case'>':pop(logic,theta);//彈出邏輯運(yùn)算符pop(variable,a);//彈出變量b=NULL;if(theta->data!='~')pop(variable,b);//建樹的函數(shù)調(diào)用k=k+1;create(theta,b,a);push(variable,theta);//將臨時的根作為新的變量壓入變量棧中;if(*s!='#'&&*s!=')'){logics=(bitree)malloc(sizeof(btdnode));if(!logics)exit(0);logics->data=*s;push(logic,logics);}elses=s-1;break;}}s++;}tree=theta;}//根據(jù)變量的取值組合并利用邏輯表達(dá)式的性質(zhì)對樹進(jìn)行求值intvalue_tree(bitreetree){if(!tree)return0;//遇到空的結(jié)點(diǎn);elseif(tree->data!='|'&&tree->data!='&'&&tree->data!='~')//找到的是變量A,B,C；returnzuhe[int(tree->data)-65];elseif(int(tree->data)<65||int(tree->data)>90)//找到的是運(yùn)算符switch(tree->data){case'|':return(value_tree(tree->lchild)||value_tree(tree->rchild));case'&':return(value_tree(tree->lchild)&&value_tree(tree->rchild));case'~':return(!value_tree(tree->rchild));}}//用戶設(shè)定變量的一種取值；voiduser(){inti;cout<<"請依次輸入你的變元取值"<<endl;for(i=65;i<65+N;i++){cout<<char(i)<<"=";cin>>zuhe[i-65];}}intmain(){charstr[str_max],*pstr,string[str_max];inti=0,choose,sum,loop=20,choice;bitreeTree;while(loop){pstr=str;i=0;intSUM=0,l;//用于累加變量的每種組合的邏輯表達(dá)式的結(jié)果;可以作為邏輯表達(dá)式類別判別的根據(jù)cout<<"請輸入邏輯表達(dá)式的變量的個數(shù)"<<endl;cin>>N;sum=int(pow(2,N));//變量組合的總數(shù);cout<<"請輸入邏輯表達(dá)式的表達(dá)式，請以大寫形式輸入（或用‘|’與用‘&’非用‘~’"<<endl;cin>>str;//重言式的正確讀??；for(;(*pstr)!=NULL;pstr++)if(*pstr!='')string[i++]=*pstr;string[i]='#';string[i+1]='\0';cout<<"**********請選擇你要的操作**********"<<endl;cout<<"**********1邏輯表達(dá)式的判別（不顯示各種取值組合的結(jié)果）**********"<<endl;cout<<"**********2邏輯表達(dá)式的判別（并顯示各種取值組合的結(jié)果）**********"<<endl;cout<<"**********3邏輯表達(dá)式的求值（根據(jù)用戶的取值）**********"<<endl;cout<<"請選擇你要的操作：";cin>>choose;switch(choose){case1://對變量的不同組合依次調(diào)用重言式二叉樹的求值函數(shù);并判別重言式的類別;creattree(string,Tree);//建立重言式的二叉樹;for(loop=0;loop<sum;loop++){creatzuhe(loop);//產(chǎn)生變量取值組合SUM+=value_tree(Tree);}string[i]='\0';if(SUM==0)cout<<"邏輯表達(dá)式:"<<string<<"Falseforever"<<endl;if(SUM==sum)cout<<"邏輯表達(dá)式:"<<string<<"Trueforever"<<endl;if(SUM>0&&SUM<sum)cout<<"邏輯表達(dá)式:"<<string<<"Satisfactible"<<endl;break;case2:creattree(string,Tree);//建立重言式的二叉樹;cout<<"邏輯表達(dá)式變量組合的預(yù)算結(jié)果"<<endl;cout<<"------------------------------------"<<endl;printf("|");for(l=65;l<65+N;l++)printf("%-4c",l);printf("邏輯表達(dá)式的值");printf("|\n");cout<<"-------------------------------------"<<endl;for(loop=0;loop<sum;loop++){creatzuhe(loop);//產(chǎn)生變量取值組合;SUM+=value_tree(Tree);printf("|");for(inth=0;h<N;h++)printf("%-4d",zuhe[h]);printf("%8d",value_tree(Tree));printf("|\n");cout<<"-------------------------------------"<<endl;}string[i]='\0';if(SUM==0)cout<<"邏輯表達(dá)式:"<<string<<"Falseforever"<<endl;elseif(SUM==sum)cout<<"邏輯表達(dá)式:"<<string<<"Trueforever"<<endl;elsecout<<"邏輯表達(dá)式:"<<string<<"Statisfactible"<<endl;break;case3:creattree(string,Tree);user();cout<<"邏輯表達(dá)式的值為:"<<value_tree(Tree)<<endl;break;}cout<<"是否繼續(xù)進(jìn)行運(yùn)算？是按1/否按0:";cin>>choice;if(choice==0)exit(0);loop--;}}第五章運(yùn)行與測試一、調(diào)試分析（1）提示運(yùn)行有誤，漏掉標(biāo)點(diǎn)，打錯字符，關(guān)鍵字使用不當(dāng)?shù)?，對各種語法的不熟練。盡量的掌握數(shù)據(jù)結(jié)構(gòu)中學(xué)到的知識體系，咨詢老師，注意自己的無謂的失誤，（2）在邏輯符號的優(yōu)先級判別處出現(xiàn)失誤，導(dǎo)