課程設計---重言式判別

上傳人：奔*** IP屬地：河北更新時間：2024-03-02 格式：doc 頁數(shù)：14 大?。?36.00KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩13頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　計算機科學學院　　課程設計報告　　課程數(shù)據(jù)結構　　題目重言式判別　　年級 &l

2、t;/p>　　專業(yè) 軟件工程　　學生 　　學號 　　指導教師 　　2012年11月7日<b&

3、gt;　　重言式判別　　目的　　鞏固和加深對數(shù)據(jù)結構的理解，通過上機實驗、調試程序，加深對課本知識的理解，最終使學生能夠熟練應用數(shù)據(jù)結構的知識寫程序。　?。?）通過本課程的學習，能熟練掌握幾種基本數(shù)據(jù)結構的基本操作。

4、;　?。?）能針對給定題目，選擇相應的數(shù)據(jù)結構，分析并設計算法，進而給出問題的正確求解過程并編寫代碼實現(xiàn)。　　需求分析　?。?）邏輯表達式從終端輸入，長度不超過一行。邏輯運算符包括“|”，“&”和“~”,　　分別表示或、與和非，運算優(yōu)先程度遞增，但可以有括號改變，即括

5、號內的運算優(yōu)先。邏輯變元為大寫字母。表達式中任何地方都可以含有多個空格符。　?。?）若是重言式或矛盾式，可以只“顯示True forever”或“False forever”，否則顯示“Satisfactible”以及變量名序列，與用戶交互。若用戶對表達式中變元取一組值，程序就求出并顯示邏輯表達式的值。　　（3）測試數(shù)據(jù)：</b&

6、gt;　　①(A|~A)&(B|~B)　?、?A&|~A)&C　?、跘|B|C|D|E|~A　?、蹵&B&C&~B　?、?A|B)&(A

7、|~A)　?、轆&~B|~A&B　　概要設計　　1、數(shù)據(jù)結構的設計 　　//根據(jù)表達式建立的二叉樹的結點定義，由于表達式的求值類似二叉樹的中序遍歷，故我們可以ijiang表達式構造為一個二叉樹;

8、　　typedef struct btdnode{}*bitree;　　//識別表達式使用的堆棧定義,它存放的都是樹的結構，鑒于邏輯符號的優(yōu)先不同，我們需要用到堆棧;　　typedef struct lnode_optr{}sqstack;　　2、算法的設計

9、　　本設計從總體上劃分可分為四個模塊，　　第一個模塊為樹與堆棧的創(chuàng)建。　　void create(bitree &zigen,bitree l,bitree r){}；void creatstack(sqstack &st){}；void creattree(char s[],bitree &am

10、p;tree){}；　　第二個模塊為對樹與堆棧的操作，包括對樹的取值以及堆棧的入棧，出棧操作。　　int value_tree(bitree tree){}；void push(sqstack &st,bitree e){}；　　void pop(sqstack &st,bitree &e

11、){}　　第三個模塊為對表達式的邏輯運算符的判別。　　char youxianji(char lie,char hang){}；void gettop(sqstack &st,bitree &e){}；　　第四個模塊為于用戶的交互。　　void user(

12、){}；　　3、抽象數(shù)據(jù)類型的設計　　根據(jù)所設計的數(shù)據(jù)結構和函數(shù)接口，設計抽象數(shù)據(jù)類型。　　ADT Binary Tree{　　數(shù)據(jù)對象：D是具有相同特性的數(shù)據(jù)元素的集合。　　二叉樹數(shù)據(jù)關系：</b&g

13、t;　　若D為空集，稱BinaryTree 為空二叉樹；　　否則關系 R={H}；　　在D中存在唯一的成為根的數(shù)據(jù)元素root，它在關系H下無前驅；　　D中其余元素必可分為兩個互不相交的子集L和R，每一個子集都是一棵符合本定義的二叉樹，并分別為root的左子樹和右子樹。

14、如果左子樹L不空，則必存在一個根結點，它是root的“左后繼”（<root>∈H）,如果右子樹R不空，則必存在一個根結點為root的“右后繼”（<root>∈H）。　　基本操作P：　　{結構初始化}　　initBi

15、Tree（&T）；　　操作結果：構造二叉樹T。　　CreateBiTree（&T，definition）；　　初始條件：definition給出二叉樹T的定義。　　操作結果：按definition構造二叉樹T。&l

16、t;b>　　{銷毀結構}　　DestroyBiTree（&T）；　　初始條件：二叉樹T存在。　　操作結果：銷毀二叉樹T。　　{引用型操作}　　BiTreeEm

17、pty（T）；　　初始條件：二叉樹T存在。　　操作結果：若二叉樹為空二叉樹，則返回TRUE，否則返回FALSE。　　和數(shù)相同，創(chuàng)建二叉樹的算法取決于它的數(shù)據(jù)元素之間關系的輸入方式。　　Root（T）<p&

18、gt;　　初始條件：二叉樹T存在。　　操作結果：返回T的根。　　Value（T，e）　　初始條件：二叉樹T存在，e是T中某個結點。　　操作結果：返回e的值。　　Parent（T,e）；

19、初始條件：二叉樹T存在，e是T中某個結點。　　操作結果：若e是T的非根結點，則返回它的雙親，否則返回“空”。　　LeftChild（T,e）；　　初始條件：二叉樹T存在，e是T中某個結點。　　操作結果：返回T的左孩子，若e無左孩子，則返回“空”。&

20、lt;p>　　RightChild（T,e）；　　初始條件：二叉樹T存在，e是T中某個結點。　　操作結果：返回T的右孩子，若e無左孩子，則返回“空”。　　}　　堆棧數(shù)據(jù)關系：</p&g

21、t;　　ADT Stack{　　InitStack(&S) 　　操作結果：構造一個空棧。　　DestroyStack(&S)　　初始條件：棧S存在。　　操作結果：棧S被銷毀。</p

22、>　　GetTop（S,&e）　　初始條件：棧S已存在且非空。　　操作結果：用e返回S的棧頂元素。　　Push（&S，e）　　初始條件：棧S已存在。　　操作結果：插入結點為e的新

23、的棧頂元素。　　Pop（&S，&e）　　初始條件：棧S已存在且非空。　　操作結果：刪除S的棧頂元素，并用e返回其值。　　}　　算法思想：

24、;　　自底向上地根據(jù)運算符地優(yōu)先級來建立分子樹函數(shù);當邏輯表達式讀完后-子根root就是一棵完整的二叉樹。用窮舉法得出所有可能組合，對二叉樹進行先序遍歷，對存放在上面的表達式進行求值。并用兩個棧分別存放運算符和變量，來判別是否為重言式。　　詳細設計　　設計抽象數(shù)據(jù)類型對應的類

25、定義。（如用C實現(xiàn)則沒有這項）　　typedef struct btdnode　　{　　char data;　　struct btdnode *lchild; 　　struct btdnode

26、 *rchild;　　}*bitree;　　//識別表達式使用的堆棧定義,它存放的都是樹的結構;　　typedef struct lnode_optr　　{ &

27、lt;p>　　struct btdnode **base; //棧中的元素都是樹的結點結構；　　struct btdnode **top;　　int stacksize;　　}sqstack;　　設計每個成員函數(shù)；<

28、;/p>　　void creatzuhe(int n){//用于產(chǎn)生變量的各種取值組合;　　int i,num=0,j=0,e;　　int temp[bianliang_max];　　for(i=0;i<N;i++)　　zuhe[i]=0

29、;　　while(n){　　e=n%2;　　num++;　　temp[j++]=e;　　n=n/2

30、;　　}　　j=j-1;　　num=N-num;　　while(j>=0){　　e=temp[j--];

31、　　zuhe[num++]=e;　　}　　}　　//自底向上地根據(jù)運算符地優(yōu)先級來建立分子樹函數(shù);當邏輯表達式讀完后-子根zigen就是一棵完整的二叉樹　　int k=0;//建

32、樹的標志，k＝1表示第一次建立分子樹，要對左右孩子的指針域處理　　void create(bitree &zigen,bitree l,bitree r){　　zigen->lchild=l;　　zigen->rchild=r;//分樹的鏈接<b

33、>　　if(l&&r){　　if(int(l->data)>=65&&int(l->data)<=90){　　l->lchild=NULL;　　l->rchild=NULL;&l

34、t;b>　　}　　if(int(r->data)>=65&&int(r->data)<=90){　　r->lchild=NULL;　　r->rchild=NULL;　　}<

35、;/b>　　}　　}　　//邏輯運算符的優(yōu)先級判別；　　char youxianji(char lie,char hang){　　int i,

36、j;　　char bijiao[7][7]={' ','|','&','~','(',')','#',　　'|','>','<','<','<

37、;','>','>',　　'&','>','>','<','<','>','>',

38、

39、 　　'~','>',

40、9;>','>','<','>','>',　　'(','<','<','<','<','=',' ',　　')

41、','>','>','>',' ','>','>',　　'#','<','<','<','<',' ','='};</p&

42、gt;　　for(i=0;i<7;i++)　　if(bijiao[0][i]==lie)　　break;　　for(j=0;j<7;j++)　　if(bijiao[j][0]==hang)</p

43、>　　break;　　return bijiao[j][i];　　}　　//對操作符棧和變量堆棧的操作；　　void creatstack(sqstack &s

44、t){　　st.base=(bitree*)malloc(stack_size_normal*sizeof(btdnode));　　if(!st.base) exit(0);　　st.top=st.base;　　st.stacksize=stack_size_normal

45、;　　}　　void push(sqstack &st,bitree e){　　if(st.top-st.base<st.stacksize)　　*st.top++=e;　　el

46、se exit(0);　　}　　void pop(sqstack &st,bitree &e){　　if(st.top==st.base) exit(0);　　e=*--st.top;<p

47、>　　}　　void gettop(sqstack &st,bitree &e){//取運算符棧的棧頂元素進行優(yōu)先級比較　　if(st.top==st.base) exit(0);　　e=*(st.top-1);

48、　　}　　void creattree(char s[],bitree &tree){//重言式的識別函數(shù)；　　sqstack variable; //變量棧;　　sqstack logic; //邏輯運算符棧;

49、　　creatstack(variable);　　creatstack(logic);　　bitree logic_di,variables,logics,e,a,b,theta,kuohao; //定義棧中的元素;　　//theta為最后的二叉樹的根;<p&

50、gt;　　logic_di=(bitree)malloc(sizeof(btdnode));　　if(!logic_di) exit(0);　　logic_di->data='#';　　push(logic,logic_di);　　while(*s

51、!=NULL){ 　　if(int(*s)>=65&&int(*s)<=90){ 　　variables=(bitree)malloc(sizeof(btdnode));　　if(!variables) exit(0);　　vari

52、ables->data=*s;　　push(variable,variables);　　}　　else if(int(*s)>90||int(*s)<65){ 　　gettop(logic,e);//取運算符棧的棧

53、頂元素進行優(yōu)先級比較　　switch(youxianji(*s,e->data)){　　case '<': //棧頂?shù)倪\算符優(yōu)先級低,邏輯運算符進棧　　logics=(bitree)malloc(sizeof(btdnode));　　if(!l

54、ogics) exit(0);　　logics->data=*s;　　push(logic,logics);　　break;　　case '='://脫括號并接受下一個字符;<p&

55、gt;　　pop(logic,kuohao);break;　　case '>':pop(logic,theta);//彈出邏輯運算符　　pop(variable,a);//彈出變量　　b=NULL;　　if(th

56、eta->data!='~')　　pop(variable,b);　　//建樹的函數(shù)調用　　k=k+1;　　create(theta,b,a);<

57、;p>　　push(variable,theta);//將臨時的根作為新的變量壓入變量棧中;　　if(*s!='#'&&*s!=')') {　　logics=(bitree)malloc(sizeof(btdnode));　　if(!logics) exit

58、(0);　　logics->data=*s;　　push(logic,logics);　　}　　else s=s-1;　　break;</p

59、>　　}　　}　　s++;　　}　　tree=theta;<p

60、>　　}　　//根據(jù)變量的取值組合并利用邏輯表達式的性質對樹進行求值 　　int value_tree(bitree tree){　　if(!tree) return 0; //遇到空的結點;　　if(tree->dat

61、a=='('){　　while(tree->data!='(')　　value_tree(tree);　　}　　else if(tree->data!='|'&&am

62、p;tree->data!='&'&&tree->data!='~'&&tree->data!='('&&tree->data!=')')//找到的是變量；　　return zuhe[int(tree->data)-65];

63、　　else if(int(tree->data)<65||int(tree->data)>90) //找到的是運算符;　　switch(tree->data){　　case '|': return(value_tree(tree->lchild)||value_tr

64、ee(tree->rchild));　　case '&': return(value_tree(tree->lchild)&&value_tree(tree->rchild));　　case '~': return(!value_tree(tree->rchild));<

65、;/p>　　}　　}　　//用戶設定變量的一種取值；　　void user()　　{&l

66、t;b>　　int i;　　cout<<"請依次輸入你的變元取值"<<endl;　　for(i=65;i<65+N;i++)　　{　　cout<<

67、char(i)<<" = ";　　cin>>zuhe[i-65];　　}　　}　　設計主函數(shù)

68、　　void main(){　　char str[str_max],string[str_max],*pstr;　　int loop=20,choice,i=0,choose,sum;　　bitree Tree;　　while(loop)</p&

69、gt;　　{　　cout<<"\t\t\t****************************"<<endl;　　cout<<"\t\t\t****************************"<<e

70、ndl;　　cout<<"\t\t\t數(shù)據(jù)結構課程設計"<<endl;　　cout<<"\t\t\t設計題目：重言式判別"<<endl;　　cout<<"\t\t\t班級：軟工10"<&l

71、t;endl;　　cout<<"\t\t\t姓名：汪國志"<<endl;　　cout<<"\t\t\t****************************"<<endl;　　pstr=str;</b

72、>　　i=0;　　int SUM=0,l; //用于累加變量的每種組合的邏輯表達式的結果;可以作為邏//輯表達式類別判別的根據(jù)　　cout<<"請輸入邏輯表達式的變量的個數(shù)"<<endl;<p

73、>　　cin>>N;　　sum=int(pow(2,N)); //變量組合的總數(shù);　　cout<<"請輸入邏輯表達式的表達式(或用'|',與用'&'和非用'~')"<<endl;

74、　　cout<<"（取多變量時請按A,B,C字母順序來選?。?quot;<<endl<<endl;;　　cin>>str;　　//重言式的正確讀取;　　for(;*pstr!=NULL;pstr++

75、)　　if(*pstr!=' ') string[i++]=*pstr;　　string[i]='#';　　string[i+1]='\0';　　creattree(string,Tree);//建立重言式的二叉樹;<

76、/p>　　for(loop=0;loop<sum;loop++){　　creatzuhe(loop);//產(chǎn)生變量取值組合;　　SUM+=value_tree(Tree);　　}　　string[i]

77、='\0';　　cout<<endl;　　if(SUM==0) cout<<" False forever"<<endl<<endl;;　　if(SUM==sum) cout<<" True Forever

78、"<<endl<<endl;;　　if (SUM>0&&SUM<sum){　　cout<<" Statisfactible"<<endl;　　cout<<endl;<

79、p>　　user();　　cout<<"邏輯表達式的值為："<<value_tree(Tree)<<endl;　　}　　cout<<"是否繼續(xù)進行運算？是

80、按1/ 否按0:";　　cin>>choice;　　if(choice==0)　　exit(0);　　loop--;

81、;　　}　　}　　調試分析　　在調試過程中出現(xiàn)以下問題：　　error C2065: 'malloc' : undeclared identifier</

82、p>　　error C2065: 'exit' : undeclared identifier　　原因是因為缺少了頭文件#include<stdlib.h>　　在運行過程中，不能有效地解決（）的優(yōu)先級問題　　解決方法：在對樹的遍歷函數(shù)value_tree(b

83、itree tree){}中添加以下語句即可　　if(tree->data=='('){　　while(tree->data!='(')　　value_tree(tree);　　}</

84、p>　　測試結果　　測試數(shù)據(jù)①(A|~A)&(B|~B)　　當A、B取值為0，0；0，1；1，0；1，1；時表達式的值分別為1，1，1，1，為重言式。　　測試數(shù)據(jù)②(A&|~A)&C

85、　　當A、C取值為0，0；0，1；1，0；1，1；時表達式的值分別為0，0，0，0，為矛盾式。　　測試數(shù)據(jù)③A|B|C|D|E|~A　　測試結果為重言式。　　測試數(shù)據(jù)④A&B&C&~B　　測試

86、結果為矛盾式。　　⑤(A|B)&(A|~A)　　測試結果為非重言式和矛盾式。　　測試數(shù)據(jù)⑥A&~B|~A&B　　測試結果為非重言式和矛盾式。　　用戶使用說明</b

87、>　　從以上六個測試用例來看，結果正確。但是程序還有一些有待解決的問題。比如，表達式中沒有解決空格的問題，當有空格存在，就無法繼續(xù)下去。另一個問題是表中顯示的大寫字母和表達式中的大寫字母不對應，只是機械的按照次序。　　但總的來說程序已經(jīng)比較完善，書上的要求也基本符合，并且加入了對矛盾式的判別。<b&g

88、t;　　課設總結　　1，通過本次試驗，更加鞏固了我二叉樹這種數(shù)據(jù)結構的理解，完全掌握了它們的基本操作。　　2，借助單步調試功能和數(shù)據(jù)窗口，可以加快找到程序中的錯誤點，調試能力有大幅度的提高。　　3，通過對出現(xiàn)的錯誤不斷的改正，鞏固了自己的薄弱環(huán)節(jié)，加深了對知識的理解，動手操作能力有了很大的提高

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

課程設計---重言式判別

文檔簡介

溫馨提示

最新文檔

評論

課程設計---重言式判別

文檔簡介

溫馨提示

最新文檔

評論

免費下載