數(shù)據(jù)結(jié)構(gòu)-括號匹配課程設(shè)計報告

1、安徽三聯(lián)學(xué)院 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計班級： 計 算 機(jī) 科 學(xué) 與 技 術(shù) 系計算機(jī)科學(xué)與技術(shù)專業(yè)2008級（2）班組別： 第 八 組 組長： 徐 恒 組員：何洋洋、枉林然、魏世捷、王煜、戴文強(qiáng) 完成日期：2010.1.20題目：括號匹配檢驗(yàn)一、問題描述：假設(shè)一個算術(shù)表達(dá)式可以包含3種括號：圓括號“（”和“）”，方括號“”和“”，和花括號“”和“”且這三種括號可按照任意次序嵌套使用（如：（）。設(shè)計一個程序，判別所給定表達(dá)式中所含括號是否匹配。二、 要求：1 將算術(shù)表達(dá)式保存在帶頭結(jié)點(diǎn)的單鏈表中；2 在1中建立的單鏈表上實(shí)現(xiàn)括號匹配問題的求解。三、 解決問題思路：1、 首先建立帶頭結(jié)點(diǎn)的單鏈表，單鏈表

2、的數(shù)據(jù)域存儲字符數(shù)據(jù)，指針域?yàn)榻Y(jié)點(diǎn)型指針。設(shè)立字符型數(shù)組先將算術(shù)表達(dá)式輸入到數(shù)組當(dāng)中，通過插入節(jié)點(diǎn)函數(shù)將數(shù)組中字符全部插入到單鏈中1中。2、 建立單鏈表2,通過switch，case語句將單鏈表1中的括號字符全部插入到單鏈表2中。3、 調(diào)用括號匹配函數(shù)將，單鏈表2的頭節(jié)點(diǎn)調(diào)入函數(shù)當(dāng)中，設(shè)立標(biāo)志位has。當(dāng)has取1時，說明找到一組匹配括號；當(dāng)has取0時，當(dāng)前一組括號不匹配。設(shè)立temp指向當(dāng)前所要判斷節(jié)點(diǎn)，將temp所指節(jié)點(diǎn)的值與temp-next節(jié)點(diǎn)的值相比較，利用匹配括號ASCII值相差1或2，相同則相差0；或不相同差值不為1、2或0。當(dāng)temp與temp-next的差值為1或2時，說明

3、找到一組匹配括號。Temp=temp-next；進(jìn)行新的判斷。當(dāng)temp與temp-next的差值不為1或2時，將temp賦為temp-next；進(jìn)行新一輪的判斷。若temp-next-next與temp-next-next-next匹配時，此時將temp-next-next與temp-next-next-next全部值為空值。且temp-next未找到匹配字符時將temp重新賦為temp->next，進(jìn)行新的判斷。4、 最后，若單鏈表p為空則則說明表達(dá)式中括號匹配；若p不為空，則說明算術(shù)表達(dá)式中括號不匹配。四、 運(yùn)行環(huán)境：1、 編輯主要環(huán)境為microsoft visualC+6.0。

4、2、 調(diào)試運(yùn)行環(huán)境為Turbo C2.0。五、 組員分工情況：1、 何洋洋、汪林然負(fù)責(zé)單鏈表相關(guān)函數(shù)的編寫；2、 王煜、洪小龍負(fù)責(zé)收集相關(guān)材料和參考資料；3、 徐恒、戴文強(qiáng)負(fù)責(zé)整理、編譯和調(diào)試。/六、 遇到的困難及解決問題的辦法：1、 最后在調(diào)試程序時發(fā)現(xiàn)許多錯誤，例如函數(shù)類型不匹配、沒有合適的指針、未定義變量、句法錯誤、函數(shù)聲明錯誤、不合法的指針、有未使用的變量、定義不正確等。先是找同學(xué)幫助，然后自己學(xué)著改錯。慢慢的自己學(xué)會改錯，并找到相關(guān)資料來找出的修改方法。2、 遇到實(shí)在不懂的地方，就找組員和同學(xué)一起討論，找到問題的根本原因，然后加以糾正。七、 源代碼及注釋：括號匹配源程序代碼及注釋#i

5、nclude <stdio.h> /*頭文件*/#include <string.h>#include <stdlib.h>#define LEN 80typedef struct listchar node; /*數(shù)據(jù)域*/struct list *next; /*指針域*/list,*linklist; /*節(jié)點(diǎn)類型*/ void initlist(linklist); /*函數(shù)聲明*/int isempty(linklist);int creatlist_node(linklist,char);Textlist(linklist);void main(

6、) /*主函數(shù)*/char testLEN; int i;list a,b; linklist p,q=&b; /*設(shè)立P為list結(jié)點(diǎn)指針*/p=&a; /*使P指向頭結(jié)點(diǎn)a*/initlist(p); /*使p為第一個節(jié)點(diǎn)*/ printf("Pliease input the expression:n");scanf("%80s",test);for(i=0;i<LEN;i+) creatlist_node(q,testi); /*將數(shù)組中算術(shù)表達(dá)式存入單鏈表q中*/for(i=0;i<LEN;i+,q=q->ne

7、xt)switch(q->node)case '':case '':case '':case '':case '(':case ')':creatlist_node(p,q->node);/*將q中括號插入單鏈表p中*/break;default : continue; /*若節(jié)點(diǎn)中字符不為括號則進(jìn)入下一次循環(huán)*/ Testlist(p); /*調(diào)用判斷括號匹配函數(shù),用P鏈表作為實(shí)參*/if(isempty(p) /*判斷P是否為空，p為空則表達(dá)式中括號匹配*/printf("

8、Truen"); printf("the kuo hao in expression is pipein"); else /*P不為空，則表達(dá)式中括號不匹配*/printf("Falsen"); printf("the kuo hao in expression is not pipein"); void initlist(linklist aplist) /*構(gòu)造頭結(jié)點(diǎn)函數(shù)*/struct list *next;aplist->next=NULL;aplist->node='0'int isem

9、pty(linklist aplist) /*判斷頭結(jié)點(diǎn)是否為空函數(shù)*/linklist next;return aplist->next=NULL?1:0; /*頭結(jié)點(diǎn)不為空側(cè)返回0*/int creatlist_node(linklist aplist,char a) /*插入字符節(jié)點(diǎn)函數(shù)*/ /*建立list型anode節(jié)點(diǎn)，將字符a插入*/linklist bplist=aplist,anode; /*設(shè)立bplist作為中間變量用于添加節(jié)點(diǎn)*/while(bplist->next)bplist=bplist->next;anode=(linklist)malloc(

10、sizeof(list); /*構(gòu)造一個list型節(jié)點(diǎn)并分配空間 */if(!anode)exit(-1);anode->node=a;anode->next=NULL;bplist->next=anode;return 0;int Testlist(linklist aplist) /*判斷算術(shù)表達(dá)式中括號是否匹配函數(shù)*/linklist temp; /*設(shè)立list型節(jié)點(diǎn)temp作為臨時變量*/int has=1; /*作為標(biāo)志,當(dāng)一對括號匹配時，則has置為0，否則置為1*/if(isempty(aplist) /*P為空則返回0*/return 0;while(has

11、) linklist next; /*設(shè)立next為linklist型變量，用于指向新的節(jié)點(diǎn)*/has=0;temp=aplist; /*使temp指向第一個節(jié)點(diǎn)*/while(temp->next) /*若第2個節(jié)點(diǎn)不為空，進(jìn)入while循環(huán)*/if(temp->next->next) /*若第3個節(jié)點(diǎn)不為空，繼續(xù)判斷*/ if(temp->next->next->node-temp->next->node=1)|(temp->next->next->node-temp->next->node=2)/*若第3個節(jié)點(diǎn)

12、字符值減去第2個節(jié)點(diǎn)字符值為1或2則條件成立進(jìn)入if語句*/temp->next=temp->next->next->next; /*將節(jié)點(diǎn)1賦值為節(jié)點(diǎn)3*/has=1; /*標(biāo)志has重置為1*/elsetemp=temp->next;/*若第3個節(jié)點(diǎn)字符值減去第2個節(jié)點(diǎn)字符值為0則將temp置為下一個節(jié)點(diǎn)*/else temp=temp->next; /*若第三個節(jié)點(diǎn)為空則將temp置為下一個節(jié)點(diǎn)*/if(!has) /*判斷has的值若為1則退出內(nèi)while循環(huán)*/break;return 0; /*當(dāng)has值為0時則函數(shù)返回0*/八、 運(yùn)行結(jié)果：運(yùn)行結(jié)果如下：1、 輸入表達(dá)式2x+6y-3y+2z*4z+(45-2x)*13-32結(jié)果如下：2、 輸入表達(dá)式2x+2y+2z-(2x-3y)*5+43*5z-32*12結(jié)果如下：3、 輸入表達(dá)式結(jié)果如下：4、 輸入表達(dá)式純括號類型如：則輸出結(jié)果為錯誤，與實(shí)際狀況不符。九、 討論部分：1、 在單鏈表之后，從數(shù)組中提取字符輸入到單鏈表中時，無法正確輸進(jìn)去，后來找同學(xué)查看，發(fā)現(xiàn)指針有些錯誤。經(jīng)過修改之后，可將字符成功插入到單鏈表中。經(jīng)過討論后得知指針未正確指向頭結(jié)