《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)成果報(bào)告-括號(hào)配對(duì)的程序設(shè)計(jì)與實(shí)現(xiàn)

數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)成果報(bào)告括號(hào)配對(duì)的程序設(shè)計(jì)與實(shí)現(xiàn)學(xué)生學(xué)號(hào)： 學(xué)生姓名： 學(xué) 院： 計(jì)算機(jī)學(xué)院 專(zhuān)業(yè)班級(jí)： 軟件工程1341 專(zhuān)業(yè)課程： 數(shù)據(jù)結(jié)構(gòu)與算法 指導(dǎo)教師： 2014 年 12 月 29 日題 目括號(hào)配對(duì)的程序設(shè)計(jì)與實(shí)現(xiàn)考核項(xiàng)目考核內(nèi)容得分平時(shí)考核（30分）出勤情況、態(tài)度、效率；知識(shí)掌握情況、基本操作技能、知識(shí)應(yīng)用能力、獲取知識(shí)能力系統(tǒng)設(shè)計(jì)（20分）分析系統(tǒng)的功能模塊編程調(diào)試（20分）實(shí)現(xiàn)系統(tǒng)的各個(gè)功能模塊，并完成調(diào)試回答問(wèn)題（15分）回答老師針對(duì)課程設(shè)計(jì)提出的問(wèn)題課程設(shè)計(jì)報(bào)告撰寫(xiě)（10分）嚴(yán)格按照規(guī)范要求完成課程設(shè)計(jì)報(bào)告源代碼（5分）按照規(guī)范要求完成課程設(shè)計(jì)源代碼的排版總 評(píng) 成 績(jī)指導(dǎo)教師評(píng)語(yǔ)： 日期： 年 月 日目 錄1 課程設(shè)計(jì)目標(biāo)與任務(wù)11.1 課程設(shè)計(jì)目標(biāo)11.2 課程設(shè)計(jì)任務(wù)11.3 課程設(shè)計(jì)內(nèi)容12 分析與設(shè)計(jì)22.1 題目分析22.2 存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)32.3 算法描述32.4 程序流程圖42.5 測(cè)試程序說(shuō)明63 程序清單94 測(cè)試124.1 測(cè)試數(shù)據(jù)124.2 測(cè)試結(jié)果分析125 總結(jié)13參考文獻(xiàn)141 課程設(shè)計(jì)目標(biāo)與任務(wù)1.1 課程設(shè)計(jì)目標(biāo)通過(guò)本課程設(shè)計(jì)，使學(xué)生在數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計(jì)與實(shí)現(xiàn)方面得到訓(xùn)練，加深對(duì)數(shù)據(jù)結(jié)構(gòu)基本內(nèi)容的理解和靈活應(yīng)用，同時(shí)，在程序設(shè)計(jì)方法及上機(jī)操作方面受到比較系統(tǒng)嚴(yán)格的訓(xùn)練，培養(yǎng)軟件工作所需要的動(dòng)手能力。1.2 課程設(shè)計(jì)任務(wù)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)是在學(xué)完數(shù)據(jù)結(jié)構(gòu)課程之后的實(shí)踐教學(xué)環(huán)節(jié)。該實(shí)踐教學(xué)是軟件設(shè)計(jì)的綜合訓(xùn)練,包括問(wèn)題分析，總體結(jié)構(gòu)設(shè)計(jì)用戶界面設(shè)計(jì)，程序設(shè)計(jì)基本技能和技巧。要求學(xué)生在設(shè)計(jì)中逐步提高程序設(shè)計(jì)能力培養(yǎng)科學(xué)的軟件工作方法學(xué)生通過(guò)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)各方面得到鍛煉：（1）能根據(jù)實(shí)際問(wèn)題的具體情況結(jié)合數(shù)據(jù)結(jié)構(gòu)課程中的基本理論和基本算法，正確分析出數(shù)據(jù)的邏輯結(jié)構(gòu)，合理地選擇相應(yīng)的存儲(chǔ)結(jié)構(gòu)，并能設(shè)計(jì)出解決問(wèn)題的有效算法；（2）通過(guò)上機(jī)實(shí)習(xí),驗(yàn)證自己設(shè)計(jì)的算法的正確性，學(xué)會(huì)有效利用基本調(diào)試方法，迅速找出程序代碼中的錯(cuò)誤并且修改；（3）培養(yǎng)算法分析能力，分析所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度，進(jìn)一步提高程序設(shè)計(jì)水平；（4）盡可能借助語(yǔ)言環(huán)境實(shí)現(xiàn)圖形顯示功能，以便將抽象的數(shù)據(jù)結(jié)構(gòu)以圖形方式顯示出來(lái)，將復(fù)雜的運(yùn)行過(guò)程以動(dòng)態(tài)方式顯示出來(lái)，獲得算法的直觀感受。1.3 課程設(shè)計(jì)內(nèi)容（1）輸入一個(gè)算術(shù)表達(dá)式，式中包含三種括號(hào)：圓括號(hào)、方括號(hào)和花括號(hào)，這三種括號(hào)可以按任意次序嵌套使用，要求編寫(xiě)程序判斷給定表達(dá)式中的括號(hào)是否正確配對(duì)。（2）最好能借助語(yǔ)言環(huán)境實(shí)現(xiàn)圖形顯示功能，以便將抽象的數(shù)據(jù)結(jié)構(gòu)以圖形方式顯示出來(lái)，將復(fù)雜的運(yùn)行過(guò)程以動(dòng)態(tài)方式顯示出來(lái)；（3）給出若干例程，演示通過(guò)調(diào)用自己所縮寫(xiě)程序來(lái)實(shí)現(xiàn)相關(guān)問(wèn)題的求解。2 分析與設(shè)計(jì)2.1 題目分析假設(shè)表達(dá)式中允許包括三種括號(hào)：圓括號(hào)、方括號(hào)和花括號(hào)，其嵌套的順序隨意，即（()）或()等為正確的格式，()或()或()均為不正確的格式。檢驗(yàn)括號(hào)是否匹配的方法可用“期待的急迫程度”這個(gè)概念來(lái)描述。例如考慮下列括號(hào)序列： ( ) 1 2 3 4 5 6 7 8當(dāng)計(jì)算機(jī)接受了第一個(gè)括號(hào)后，它期待著與其匹配的第八個(gè)括號(hào)的出現(xiàn)，然而等來(lái)的卻是第二個(gè)括號(hào)，此時(shí)第一個(gè)括號(hào)“”只能靠邊，而迫切等待與第二個(gè)括號(hào)相匹配的、第七個(gè)括號(hào)“)”的出現(xiàn)，類(lèi)似地，因等來(lái)的是第三個(gè)括號(hào)“”，其期待匹配的程度較第二個(gè)括號(hào)更急迫，則第二個(gè)括號(hào)也只能靠邊，讓位于第三個(gè)括號(hào)，顯然第二個(gè)括號(hào)的期待急迫性高于第一個(gè)括號(hào)；在接受了第四個(gè)括號(hào)之后，第三個(gè)括號(hào)的期待得到滿足，消解之后，第二個(gè)括號(hào)的期待匹配就成為當(dāng)前最急迫的任務(wù)了，依次類(lèi)推。可見(jiàn)這個(gè)處理過(guò)程恰與棧的特點(diǎn)相吻合。在算術(shù)表達(dá)式中，右括號(hào)和左括號(hào)匹配的次序正好符合后到的括號(hào)要最先被匹配的“后進(jìn)先出”堆棧操作特點(diǎn)。 因此首先建立一個(gè)空的堆棧，依次讀入字符直到文件的末尾。我們可以利用一個(gè)棧結(jié)構(gòu)保存每個(gè)出現(xiàn)的左括號(hào)，當(dāng)遇到右括號(hào)時(shí)，從棧中彈出左括號(hào)，檢驗(yàn)匹配情況。輸入一個(gè)算術(shù)表達(dá)式，式中包含三種括號(hào)：圓括號(hào)、方括號(hào)和花括號(hào)，這三種括號(hào)可以按任意次序嵌套使用，要求編寫(xiě)程序判斷給定表達(dá)式中的括號(hào)是否正確配對(duì)。算術(shù)表達(dá)式中各種括號(hào)的使用規(guī)則為：出現(xiàn)左括號(hào)，必有相應(yīng)的右括號(hào)與之匹配，并且每對(duì)括號(hào)之間可以嵌套，但不能出現(xiàn)交叉情況。否則，括號(hào)匹配不正確，則該算數(shù)表達(dá)式無(wú)效；程序結(jié)束。2.2 存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)本程序用的是順序棧，用地址連續(xù)的存儲(chǔ)空間依次存儲(chǔ)棧在中的元素，并記錄當(dāng)前棧頂數(shù)據(jù)元素的位置，這樣的棧稱為順序棧。同順序表的存儲(chǔ)結(jié)構(gòu)類(lèi)似，順序棧也可以用向量來(lái)實(shí)現(xiàn)。由于入棧和出棧運(yùn)算都是在棧頂進(jìn)行的，而棧底位置是固定不變的，可以將棧底位置設(shè)置在向量的起始處；棧頂位置是隨入棧和出棧操作而變化的，故需要用一個(gè)整型變量TOP來(lái)記錄當(dāng)前棧頂元素在向量中的為何子。類(lèi)似順序表的類(lèi)型定義，順序棧的類(lèi)型可定義如下：typedef struct StackElementType elemStack_Size; int top; SeqStack; 2.3 算法描述首先建立一個(gè)空的堆棧，依次讀入字符直到文件的末尾。在算術(shù)表達(dá)式中，右括號(hào)和左括號(hào)匹配的次序正好符合后到的括號(hào)要最先被匹配的“后進(jìn)先出”堆棧操作特點(diǎn)，因此可以借助一個(gè)堆棧來(lái)進(jìn)行判斷。 括號(hào)匹配共有以下4種情況： （1）括號(hào)匹配不正確左括號(hào)多于右括號(hào)；右括號(hào)多于左括號(hào)；左右括號(hào)配對(duì)次序不正確； （2）左右括號(hào)配對(duì)正確； 具體方法如下：順序掃描算術(shù)表達(dá)式，若該表達(dá)式中無(wú)括號(hào)時(shí)，則為空棧，此時(shí)結(jié)束。當(dāng)遇到3種類(lèi)型括號(hào)的左括號(hào)時(shí)，讓該括號(hào)進(jìn)棧。當(dāng)掃描到某一種類(lèi)型的右括號(hào)時(shí)，比較當(dāng)前棧頂括號(hào)是否與之匹配，若匹配，則退棧繼續(xù)進(jìn)行判斷；若當(dāng)前棧頂括號(hào)與當(dāng)前掃描的括號(hào)不相同，則左、右括號(hào)配對(duì)次序不正確；若字符串當(dāng)前為某種類(lèi)型右括號(hào)而堆棧已空，則右括號(hào)多于左括號(hào)；字符串循環(huán)掃描結(jié)束時(shí)，若堆棧非空，則說(shuō)明左括號(hào)多于右括號(hào)；以上三種情況均為括號(hào)匹配不正確，則輸出不匹配括號(hào)的位置。如果上述三種情況都沒(méi)有出現(xiàn)，則說(shuō)明左、右括號(hào)匹配正確。2.4 程序流程圖運(yùn)行程序，用鍵盤(pán)輸入算是表達(dá)式，判斷讀入的字符是否為括號(hào)，若不是括號(hào)，則不入棧繼續(xù)讀取；若是括號(hào)，則入棧，在判斷該括號(hào)是左還是右括號(hào)，若是左括號(hào)則等待下一個(gè)括號(hào)的讀入，如果讀入的下一個(gè)括號(hào)是右括號(hào)，判斷該右括號(hào)是否與上一個(gè)左括號(hào)匹配，若匹配，則棧頂元素出棧，繼續(xù)讀取，若不匹配，則輸出錯(cuò)誤；如果讀入的下一個(gè)括號(hào)為左括號(hào)，則入棧成為棧頂元素；重復(fù)該步驟。讀取完結(jié)束后，判斷棧是否為空，如果為?？眨瑒t該表達(dá)式書(shū)寫(xiě)正確，括號(hào)完全匹配正確；如果棧非空，則表達(dá)式無(wú)效，括號(hào)匹配不正確。 開(kāi)始輸入讀取下一個(gè)括號(hào)？N左括號(hào)？YN匹配？配？YYY左括號(hào)入棧左括號(hào)出棧N指向下一個(gè)指針棧空？Y不匹配完全匹配N(xiāo)結(jié)束圖2-22.5 測(cè)試程序說(shuō)明一、算法用到的抽象數(shù)據(jù)類(lèi)型定義 1、ADT Stack 數(shù)據(jù)對(duì)象D=ai|aiElemSet,i=1,2n, n0 數(shù)據(jù)關(guān)系R1=|ai-1,aiD,i=2, ,n 約定an端為棧頂a1端為棧底 基本操作： （1） InitStack(&S) 操作結(jié)果構(gòu)造一個(gè)空棧S。 （2） StackEmpty(S) 初始條件棧S已存在。 操作結(jié)果若棧S為空棧則返回TURE否則FALUSE。 （3） StackFull(S) 初始條件棧S已存在。 操作結(jié)果若棧S為滿則返回TURE,否則FALUSE. （4） GetTop(S,&e) 初始條件棧S已存在且非空。 操作結(jié)果用e返回S的棧頂元素。（5） Push(&S,e) 初始條件棧S已存在。 操作結(jié)果插入元素e為新的棧頂元素。 （6） Pop(&S,&e) 初始條件棧S已存在且非空。 操作結(jié)果刪除S的棧頂元素 算法中函數(shù)編號(hào)及功能要求： （1） voidInitStack(SeqStack*S)初始化構(gòu)造一個(gè)空棧S （2） IsEmpty(SeqStack *S)判斷棧S為空棧時(shí)返回值為真反之為假 （3） IsFull(SeqStack *S)判斷棧S為滿棧時(shí)返回值為真反之為假 （4） Push(SeqStack *S,StackElementType x)插入元素x為新的棧頂元素 （5） Pop(SeqStack *S,StackElementType *x)將棧S的棧頂元素彈出放 到x所指的存儲(chǔ)空間中 （6） GetTop(SeqStack *S,StackElementType *x)將棧S的棧頂元素彈出放到x所指的存儲(chǔ)空間中但棧頂指針保持不變 （7） Match(char ch,char str)進(jìn)行括號(hào)的匹配 （8） BracketMatch(char *str) str中為輸入的字符串利用堆棧技術(shù)來(lái)檢查該字符串中的括號(hào)是否匹配二、核心代碼判斷括號(hào)是否匹配：str中為輸入的字符串，利用堆棧技術(shù)來(lái)檢查該字符串中的括號(hào)是否匹配，使用for循環(huán)對(duì)字符串中的字符逐一掃描，用Match判斷兩個(gè)括號(hào)是否匹配，已匹配的左括號(hào)出棧，如果不匹配輸出其結(jié)果結(jié)束；若匹配，則輸出匹配。 void BracketMatch(char *str) SeqStack S; int i; char ch; InitStack(&S); for(i=0; stri!=0; i+) switch(stri) case (: case : case : Push(&S,stri); break; case ): case : case : if(IsEmpty(&S) printf(n右括號(hào)多余!n); return; else GetTop(&S,&ch); if(Match(ch,stri) Pop(&S,&ch); else printf(n對(duì)應(yīng)的左右括號(hào)不同類(lèi)!n); return; /*switch*/ /*for*/ if(IsEmpty(&S) printf(n括號(hào)匹配!n); else printf(n左括號(hào)多余!n); 3 程序清單 #define TRUE 1 #define FALSE 0 #define Stack_Size 50 #define StackElementType char #include stdio.h typedef struct StackElementType elemStack_Size; int top; SeqStack; void InitStack(SeqStack *S) S-top = -1; int IsEmpty(SeqStack *S) return(S-top=-1?TRUE:FALSE); int IsFull(SeqStack *S) return(S-top=Stack_Size-1?TRUE:FALSE); int Push(SeqStack *S,StackElementType x) if(S-top=Stack_Size-1) return(FALSE); S-top+; S-elemS-top = x; return(TRUE); int Pop(SeqStack *S,StackElementType *x) if(S-top = -1) return(FALSE); else *x = S-elemS-top; S-top-; return(TRUE); int GetTop(SeqStack *S,StackElementType *x) if(S-top = -1) return(FALSE); else *x = S-elemS-top; return(TRUE); int Match(char ch,char str) if(ch=( & str=) return TRUE; else if(ch= & str=) return TRUE; else if(ch= & str=) return TRUE; else return FALSE; void BracketMatch(char *str) SeqStack S; int i; char ch; InitStack(&S); for(i=0; stri!=0; i+) switch(stri) case (: case : case : Push(&S,stri); break; case ): case : case : if(IsEmpty(&S) printf(n右括號(hào)多余!n); return; else GetTop(&S,&ch); if(Match(ch,stri) Pop(&S,&ch); else printf(n對(duì)應(yīng)的左右括號(hào)不同類(lèi)!n); return; /*switch*/ /*for*/ if(IsEmpty(&S) printf(n括號(hào)匹配!n); else printf(n左括號(hào)多余!n); void main() char str100; printf( *括號(hào)匹配的檢驗(yàn)*n); printf(n); printf(請(qǐng)輸入算數(shù)表達(dá)式: ); gets(str); BracketMatch(str); printf(謝謝使用!n); 4 測(cè)試4.1 測(cè)試數(shù)據(jù)（1）a*(b+c)*(b-d)=（2）a*(b+c)*(b-d)=4.2 測(cè)試結(jié)果分析輸入的表達(dá)式為：a*(b+c)*(b-d)=，圖4-1為程序運(yùn)行后的表達(dá)式中括號(hào)匹配正確的結(jié)果，表達(dá)式正確；圖4-1 輸入的表達(dá)式為：a*(b+c)*(b-d)=，圖4-2為程序運(yùn)行后的表達(dá)式中括號(hào)的左括號(hào)多余的結(jié)果，即括號(hào)匹配錯(cuò)誤，表達(dá)式有錯(cuò)誤；圖4-2 5 總結(jié)這次課程設(shè)計(jì)是運(yùn)用c語(yǔ)言以及這學(xué)期所學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)完成的。數(shù)據(jù)結(jié)構(gòu)是有某一數(shù)據(jù)元素的集合和該集合中的數(shù)據(jù)元素之間的關(guān)系組成。我做的課題是：編一個(gè)程序判斷括號(hào)是否匹配。通過(guò)這次的編程實(shí)訓(xùn)，讓我受益較多，更進(jìn)一步的了解和掌握順序棧的類(lèi)型定義方法，順序棧的操作和應(yīng)用以及棧先進(jìn)后出操作原則在解決實(shí)際問(wèn)題中的應(yīng)用；也認(rèn)識(shí)到了自己在數(shù)據(jù)結(jié)構(gòu)方面的漏缺之處，同時(shí)也增強(qiáng)了自我學(xué)習(xí)的能力，相信我通過(guò)這次的實(shí)訓(xùn)可以讓我在以后更好的學(xué)習(xí)編程！參考文獻(xiàn)1嚴(yán)蔚敏等.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）清華大學(xué)出版社2朱戰(zhàn)立.數(shù)據(jù)結(jié)構(gòu)-使用C語(yǔ)言（第四版）.電子工業(yè)出版社3吳躍.數(shù)據(jù)結(jié)構(gòu)和算法.機(jī)械工業(yè)出版社4周海英等.數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)（第二版）.國(guó)際工業(yè)出版社#define TRUE 1 #define FALSE 0 #define Stack_Size 50 #define StackElementType char #include stdio.h typedef struct StackElementType elemStack_Size; int top; SeqStack; void InitStack(SeqStack *S) S-top = -1; int IsEmpty(SeqStack *S) return(S-top=-1?TRUE:FALSE); int IsFull(SeqStack *S) return(S-top=Stack_Size-1?TRUE:FALSE); int Push(SeqStack *S,StackElementType x) if(S-top=Stack_Size-1) return(FALSE); S-top+; S-elemS-top = x; return(TRUE); int Pop(SeqStack *S,StackElementType *x) if(S-top = -1) return(FALSE); else *x = S-elemS-top; S-top-; return(TRUE); int GetTop(SeqStack *S,StackE