1、河南工程學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計成果報告括號匹配算法的設(shè)計與實現(xiàn)學(xué)生學(xué)號： 學(xué)生姓名： 學(xué) 院： 計算機學(xué)院 專業(yè)班級： 軟件工程1342班 專業(yè)課程： 數(shù)據(jù)結(jié)構(gòu)與算法 指導(dǎo)教師： 2014 年 12 月 29 日題 目括號匹配算法的設(shè)計與實現(xiàn)考核項目考核內(nèi)容得分平時考核（30分）出勤情況、態(tài)度、效率；知識掌握情況、基本操作技能、知識應(yīng)用能力、獲取知識能力系統(tǒng)設(shè)計（20分）分析系統(tǒng)的功能模塊編程調(diào)試（20分）實現(xiàn)系統(tǒng)的各個功能模塊，并完成調(diào)試回答問題（15分）回答老師針對課程設(shè)計提出的問題課程設(shè)計報告撰寫（10分）嚴格按照規(guī)范要求完成課程設(shè)計報告源代碼（5分）按照規(guī)范要求完成課程設(shè)計源代碼的

2、排版總 評 成 績指導(dǎo)教師評語： 日期： 年 月 日目 錄1 課程設(shè)計目標(biāo)與任務(wù)11.1 課程設(shè)計目標(biāo)11.2 課程設(shè)計任務(wù)11.3 課程設(shè)計的基本要求12 分析與設(shè)計22.1 括號匹配的概述22.2 存儲結(jié)構(gòu)設(shè)計22.3 算法描述42.4程序流程圖63 程序清單74 測試114.1 測試數(shù)據(jù)114.2 測試結(jié)果分析115 總結(jié)126參考文獻131 課程設(shè)計目標(biāo)與任務(wù)1.1 課程設(shè)計目標(biāo)（1）了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力。（2）初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能。（3）提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的

3、能力。（4）訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。1.2 課程設(shè)計任務(wù) 設(shè)計括號匹配的相關(guān)函數(shù)庫，以便在程序設(shè)計中調(diào)用，要求：（1）輸入一個算術(shù)表達式，式中包含三種括號：圓括號、方括號和花括號，這三種括號可以按任意次序嵌套使用，要求編寫程序判斷給定表達式中的括號是否正確配對。（2）能借助語言環(huán)境實現(xiàn)圖形顯示功能，以便將抽象的數(shù)據(jù)結(jié)構(gòu)以圖形方式顯示出來，將復(fù)雜的運行過程以動態(tài)方式顯示出來。（3）給出若干例程，演示通過調(diào)用自己所縮寫程序來實現(xiàn)相關(guān)問題的求解。1.3 課程設(shè)計的基本要求嚴格按照題意要求，獨立進行設(shè)計，不能隨意更改。若確因條件所限

4、，必須要改變課題要求時，應(yīng)在征得指導(dǎo)教師同意的前提下進行。學(xué)生應(yīng)制定設(shè)計工作計劃，認真完成設(shè)計的各個環(huán)節(jié)，并在老師的指導(dǎo)下認真組織設(shè)計工作，撰寫設(shè)計報告，做好設(shè)計總結(jié)。2 分析與設(shè)計2.1 括號匹配的概述假設(shè)表達式中允許包含兩種括號：圓括號和方括號，其嵌套的順序隨意，即( ( ) )或 ( ) 等為正確的格式， ( 或 ( ) 或( ( ) 均為不正確的格式。檢驗括號是否匹配的方法可用“期待的急迫程度”這個概念來描述。例如考慮下列括號排序： ( ) 12345678當(dāng)計算機接受了第一個括號后，它期待著預(yù)期匹配的第八個括號的出現(xiàn)，然而等來的確實第二個括號，此時的第一個括號只能暫時等待。第二個括號

5、期待著第七個括號的出現(xiàn)，然而等來的確實第三個括號，第二個括號仍然需要讓先。第三個括號出現(xiàn)之后期待著第四個括號的出現(xiàn)，匹配完成之后第二個括號繼續(xù)開始期待，依此類推，即可完成對括號的匹配。可見這個處理過程恰好和棧的特點相吻合。由此，在算法中設(shè)置一個棧，每讀入一個括號，如是右括號，則或者使置于棧頂?shù)淖钇惹械钠诖靡韵?，或者是不合法的情況；若是左括號，則作為一個新的更迫切的期待壓入棧，自然使原有的在棧中的左右未消解的急迫性都降了一級。另外，在算法的開始和結(jié)束時，棧都是空的。2.2 存儲結(jié)構(gòu)設(shè)計構(gòu)造一個空棧S， int InitStack(SqStack &S)S.base=(SElemType *

6、)malloc(sizeof(SElemType);if(!S.base)exit(0); /存儲分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;return 1;判斷構(gòu)造的若棧S是否為空棧，用于主函數(shù)中對于括號出棧是否為空作為判斷。若為空則返回TRUE，否則返回FALSEint StackEmpty(SqStack S)if(S.base=S.top)return 1;else return 0;將棧清空，以用來進棧void ClearStack(SqStack &S)S.base=NULL;S.top=S.base;棧的銷毀void Destory

7、Stack(SqStack *&S)if(StackEmpty(*S)!=1)ClearStack(*S);free(S); 若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERRORint GetTop(SqStack S,SElemType &e)if(S.top=S.base)return 0;e=*(S.top-1);return 1;2.3 算法描述構(gòu)造一個算法，用來確定什么樣的情況括號匹配是正確的。int Comp(char a,char b)if(a=(&b!=)|(a=&b!=)|(a=&b!=)return 0;else return 1;事先夠想出括號匹配錯誤的情況，

8、并加以分析，只有三種，做括號多出，右括號多出或者括號紊亂。分析出來錯誤的情況并輸出。Status GetCount(SqStack *S)char eSTACK_INIT_SIZE;char e1;int i=0;InitStack(*S);printf(Please enter a string of parenthesis:);gets(e);if(e0=)|(e0=)|(e0=)printf(括號匹配錯誤); exit(0);for(i=0;ei!=0;i+)/以/0判斷輸入是否結(jié)束switch(ei)case (:case :case :Push(*S,ei);break; case

9、):case :case : GetTop(*S,e1); if(GetTop(*S,e1)=0) printf(右括號多余); exit(0); if(Comp(e1,ei)=1) Pop(*S,e1); /S-top-; else printf(括號匹配錯誤n); exit(0);if(S-top!=S-base)printf(左括號多余n);else printf(括號匹配正確n);return 0;2.4程序流程圖匹配左括號入棧左括號出棧指向下一個指針棧空?完全匹配錯誤位置結(jié)束左括號開始輸入括號？程序開始后先判斷是否為括號，如果是括號，再判斷是左括號還是右，如果左，則入棧，如果右括號則

10、進行匹配，只向下一個指針；否則棧空；再判斷是否匹配，結(jié)束。如圖2-4： N Y Y N N Y N圖2-4 程序流程圖3 程序清單#include#include#include#include#define STACK_INIT_SIZE 100/存儲空間初始分配量#define STACKINCREMENT 10typedef char Status; typedef char SElemType ;/建立棧的首節(jié)點typedef structSElemType *base; /在棧構(gòu)造前和銷毀后，base的值為NULLSElemType *top; /棧頂指針int stacksize;

11、 /當(dāng)前已分配的存儲空間，以元素為單位SqStack;/構(gòu)造一個空棧Sint InitStack(SqStack &S)S.base=(SElemType * )malloc(sizeof(SElemType);if(!S.base)exit(0); /存儲分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;return 1;/若棧S為空棧，則返回TRUE，否則返回FALSEint StackEmpty(SqStack S)if(S.base=S.top)return 1;else return 0;/把S置為空棧void ClearStack(SqSta

12、ck &S)S.base=NULL;S.top=S.base; /銷毀棧S，S不在存在void DestoryStack(SqStack *&S)if(StackEmpty(*S)!=1)ClearStack(*S);free(S); /返回S的元素個數(shù)，即棧的長度int StackLength(SqStack S)return S.stacksize;/若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERRORint GetTop(SqStack S,SElemType &e)if(S.top=S.base)return 0;e=*(S.top-1);return 1;/插入元素e為新

13、的棧頂元素Status Push(SqStack &S,SElemType &e)if(S.top-S.base=S.stacksize)/判斷是否棧滿，是則追加存儲空間S.base=(SElemType * )realloc(S.base,(S.stacksize+STACKINCREMENT) * sizeof(SElemType);if(!S.base)exit(0);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+ =e;return 1; /若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK，否則返回ERRO

14、RStatus Pop(SqStack &S,SElemType &e)if(StackEmpty(S)=1)return 0;elsee=*-S.top;return 1;/括號匹配int Comp(char a,char b)if(a=(&b!=)|(a=&b!=)|(a=&b!=)return 0;else return 1;Status GetCount(SqStack *S)char eSTACK_INIT_SIZE;char e1;int i=0;InitStack(*S);printf(請輸入一串括號：);gets(e);if(e0=)|(e0=)|(e0=)printf(括號匹

15、配錯誤); exit(0);for(i=0;ei!=0;i+)/以/0判斷輸入是否結(jié)束switch(ei)case (:case :case :Push(*S,ei);break;case ):case :case : GetTop(*S,e1); if(GetTop(*S,e1)=0) printf(右括號多余); exit(0); if(Comp(e1,ei)=1) Pop(*S,e1); /S-top-; else printf(括號匹配錯誤n); exit(0);if(S-top!=S-base)printf(左括號多余n);else printf(括號匹配正確n);return 0;

16、/主函數(shù)void main()SqStack S;InitStack(S);GetCount(&S);4 測試4.1 測試數(shù)據(jù)（1）左括號多余。（2）右括號多余。（3）匹配正確4.2 測試結(jié)果分析當(dāng)輸如（）時，輸出結(jié)果將會是：左括號多余。如圖4.2-1：圖4.2-1 左括號多余當(dāng)輸如（）時，輸出結(jié)果將會是：右括號多余。如圖4.2-2：圖4.2-2 右括號多余當(dāng)輸如（）時，輸出結(jié)果將會是：括號匹配正確。如圖4.2-3：圖4.2-3 括號匹配正確5 總結(jié)通過這次課程的學(xué)習(xí)，我越發(fā)覺得數(shù)據(jù)結(jié)構(gòu)的重要性。這次課程設(shè)計是運用 c 語言以及這學(xué)期所學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)的只是完成的。數(shù)據(jù)結(jié)構(gòu)是有某一數(shù)據(jù)元素的集合

17、和該集合中的數(shù)據(jù)元素之間的關(guān)系組成。此 次數(shù)據(jù)結(jié)構(gòu)實驗，我做的是判別括號配對。我深刻得體會到了設(shè)計程序的困 難,設(shè)計程序是一個全盤思維的過程.在進行源程序的編寫前,一定要對程序怎樣 運行,程序的原理有一個大致的了解,只有這樣,在編寫時才能做到縱觀全局,不會 只局限于某一個特定的模塊,但是,這正是我們初學(xué)者最容易犯的錯誤.開始，急于 求成，沒有仔細考慮就直接寫程序，結(jié)果出現(xiàn)好多錯誤，由于沒有一個明確的邏 輯思維，沒有認真的分析實驗而導(dǎo)致的。后來，靜下心來慢慢思考，終于寫出了，但在程序編寫過程中仍有不足，調(diào)試能力仍有欠缺，程序還有很的改善空間。6參考文獻1.嚴蔚敏，吳偉民編著，數(shù)據(jù)結(jié)構(gòu)（C語言版）

18、，清華大學(xué)出版社，2005 2 嚴蔚敏，陳文博編著，數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程，清華大學(xué)出版社，2006 3 李云清，楊慶紅，揭安全編著，數(shù)據(jù)結(jié)構(gòu)（C語言版），人民郵電出版社2006 4、譚浩強，張基溫，唐永炎編著，C語言程序設(shè)計教程（第二版）高等教育出版社，2005 5 蘇仕華等編著，數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，上海；機械工業(yè)出版社，2004#include#include#include#include#define STACK_INIT_SIZE 100/存儲空間初始分配量#define STACKINCREMENT 10typedef char Status; typedef char SElemT

19、ype ;/建立棧的首節(jié)點typedef structSElemType *base; /在棧構(gòu)造前和銷毀后，base的值為NULLSElemType *top; /棧頂指針int stacksize; /當(dāng)前已分配的存儲空間，以元素為單位SqStack;/構(gòu)造一個空棧Sint InitStack(SqStack &S)S.base=(SElemType * )malloc(sizeof(SElemType);if(!S.base)exit(0); /存儲分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;return 1;/若棧S為空棧，則返回TRUE，

20、否則返回FALSEint StackEmpty(SqStack S)if(S.base=S.top)return 1;else return 0;/把S置為空棧void ClearStack(SqStack &S)S.base=NULL;S.top=S.base; /銷毀棧S，S不在存在void DestoryStack(SqStack *&S)if(StackEmpty(*S)!=1)ClearStack(*S);free(S); /返回S的元素個數(shù)，即棧的長度int StackLength(SqStack S)return S.stacksize;/若棧不空，則用e返回S的棧頂元素，并返回

21、OK；否則返回ERRORint GetTop(SqStack S,SElemType &e)if(S.top=S.base)return 0;e=*(S.top-1);return 1;/插入元素e為新的棧頂元素Status Push(SqStack &S,SElemType &e)if(S.top-S.base=S.stacksize)/判斷是否棧滿，是則追加存儲空間S.base=(SElemType * )realloc(S.base,(S.stacksize+STACKINCREMENT) * sizeof(SElemType);if(!S.base)exit(0);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top