課程設(shè)計(jì)---重言式判別

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-02 格式：doc 頁(yè)數(shù)：14 大小：136.00KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

2023年全國(guó)碩士研究生考試考研英語(yǔ)一試題真題（含答案詳解+作文范文）_第1頁(yè)

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

版權(quán)說(shuō)明：本文檔由用戶(hù)提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　計(jì)算機(jī)科學(xué)學(xué)院　　課程設(shè)計(jì)報(bào)告　　課程數(shù)據(jù)結(jié)構(gòu)　　題目重言式判別　　年級(jí) &l

2、t;/p>　　專(zhuān) 業(yè) 軟件工程　　學(xué) 生 　　學(xué) 號(hào) 　　指導(dǎo)教師 　　2012年11月7日<b&

3、gt;　　重言式判別　　目的　　鞏固和加深對(duì)數(shù)據(jù)結(jié)構(gòu)的理解，通過(guò)上機(jī)實(shí)驗(yàn)、調(diào)試程序，加深對(duì)課本知識(shí)的理解，最終使學(xué)生能夠熟練應(yīng)用數(shù)據(jù)結(jié)構(gòu)的知識(shí)寫(xiě)程序。　?。?）通過(guò)本課程的學(xué)習(xí)，能熟練掌握幾種基本數(shù)據(jù)結(jié)構(gòu)的基本操作。

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

5、號(hào)內(nèi)的運(yùn)算優(yōu)先。邏輯變?cè)獮榇髮?xiě)字母。表達(dá)式中任何地方都可以含有多個(gè)空格符。　　（2）若是重言式或矛盾式，可以只“顯示True forever”或“False forever”，否則顯示“Satisfactible”以及變量名序列，與用戶(hù)交互。若用戶(hù)對(duì)表達(dá)式中變?cè)∫唤M值，程序就求出并顯示邏輯表達(dá)式的值。　?。?）測(cè)試數(shù)據(jù)：</b&

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

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

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

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

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

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

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

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

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

15、Tree（&T）；　　操作結(jié)果：構(gòu)造二叉樹(shù)T。　　CreateBiTree（&T，definition）；　　初始條件：definition給出二叉樹(shù)T的定義。　　操作結(jié)果：按definition構(gòu)造二叉樹(shù)T。&l

16、t;b>　　{銷(xiāo)毀結(jié)構(gòu)}　　DestroyBiTree（&T）；　　初始條件：二叉樹(shù)T存在。　　操作結(jié)果：銷(xiāo)毀二叉樹(shù)T。　　{引用型操作}　　BiTreeEm

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

18、gt;　　初始條件：二叉樹(shù)T存在。　　操作結(jié)果：返回T的根。　　Value（T，e）　　初始條件：二叉樹(shù)T存在，e是T中某個(gè)結(jié)點(diǎn)。　　操作結(jié)果：返回e的值。　　Parent（T,e）；

19、初始條件：二叉樹(shù)T存在，e是T中某個(gè)結(jié)點(diǎn)。　　操作結(jié)果：若e是T的非根結(jié)點(diǎn)，則返回它的雙親，否則返回“空”。　　LeftChild（T,e）；　　初始條件：二叉樹(shù)T存在，e是T中某個(gè)結(jié)點(diǎn)。　　操作結(jié)果：返回T的左孩子，若e無(wú)左孩子，則返回“空”。&

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

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

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

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

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

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

26、 *rchild;　　}*bitree;　　//識(shí)別表達(dá)式使用的堆棧定義,它存放的都是樹(shù)的結(jié)構(gòu);　　typedef struct lnode_optr　　{ &

27、lt;p>　　struct btdnode **base; //棧中的元素都是樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)；　　struct btdnode **top;　　int stacksize;　　}sqstack;　　設(shè)計(jì)每個(gè) 成員函數(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ùn)算符地優(yōu)先級(jí)來(lái)建立分子樹(shù)函數(shù);當(dāng)邏輯表達(dá)式讀完后-子根zigen就是一棵完整的二叉樹(shù)　　int k=0;//建

32、樹(shù)的標(biāo)志，k＝1表示第一次建立分子樹(shù)，要對(duì)左右孩子的指針域處理　　void create(bitree &zigen,bitree l,bitree r){　　zigen->lchild=l;　　zigen->rchild=r;//分樹(shù)的鏈接<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ùn)算符的優(yōu)先級(jí)判別；　　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];　　}　　//對(duì)操作符棧和變量堆棧的操作；　　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ùn)算符棧的棧頂元素進(jìn)行優(yōu)先級(jí)比較　　if(st.top==st.base) exit(0);　　e=*(st.top-1);

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

49、　　creatstack(variable);　　creatstack(logic);　　bitree logic_di,variables,logics,e,a,b,theta,kuohao; //定義棧中的元素;　　//theta為最后的二叉樹(shù)的根;<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);//取運(yùn)算符棧的棧

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

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

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

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

57、;p>　　push(variable,theta);//將臨時(shí)的根作為新的變量壓入變量棧中;　　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ù)變量的取值組合并利用邏輯表達(dá)式的性質(zhì)對(duì)樹(shù)進(jìn)行求值 　　int value_tree(bitree tree){　　if(!tree) return 0; //遇到空的結(jié)點(diǎn);　　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) //找到的是運(yùn)算符;　　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>　　}　　}　　//用戶(hù)設(shè)定變量的一種取值；　　void user()　　{&l

66、t;b>　　int i;　　cout<<"請(qǐng)依次輸入你的變?cè)≈?quot;<<endl;　　for(i=65;i<65+N;i++)　　{　　cout<<

67、char(i)<<" = ";　　cin>>zuhe[i-65];　　}　　}　　設(shè)計(jì)主函數(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ù)結(jié)構(gòu)課程設(shè)計(jì)"<<endl;　　cout<<"\t\t\t設(shè)計(jì)題目：重言式判別"<<endl;　　cout<<"\t\t\t班級(jí)：軟工10"<&l

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

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

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

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

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

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<<"邏輯表達(dá)式的值為："<<value_tree(Tree)<<endl;　　}　　cout<<"是否繼續(xù)進(jìn)行運(yùn)算？是

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

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

82、p>　　error C2065: 'exit' : undeclared identifier　　原因是因?yàn)槿鄙倭祟^文件#include<stdlib.h>　　在運(yùn)行過(guò)程中，不能有效地解決（）的優(yōu)先級(jí)問(wèn)題　　解決方法：在對(duì)樹(shù)的遍歷函數(shù)value_tree(b

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

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

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

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

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

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

眾賞文庫(kù)> 全部分類(lèi)> 畢業(yè)設(shè)計(jì)

溫馨提示

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

課程設(shè)計(jì)---重言式判別

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

課程設(shè)計(jì)---重言式判別

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載