括號匹配算法的設計與實現(xiàn)-數(shù)據(jù)結構課程設計

河南工程學院數(shù)據(jù)結構與算法課程設計成果報告括號匹配算法的設計與實現(xiàn)學生學號： 學生姓名： 學 院： 計算機學院 專業(yè)班級： 軟件工程1341班 專業(yè)課程： 數(shù)據(jù)結構與算法 指導教師： 2014 年 12 月 29 日題 目括號匹配算法的設計與實現(xiàn)考核項目考核內容得分平時考核（30分）出勤情況、態(tài)度、效率；知識掌握情況、基本操作技能、知識應用能力、獲取知識能力系統(tǒng)設計（20分）分析系統(tǒng)的功能模塊編程調試（20分）實現(xiàn)系統(tǒng)的各個功能模塊，并完成調試回答問題（15分）回答老師針對課程設計提出的問題課程設計報告撰寫（10分）嚴格按照規(guī)范要求完成課程設計報告源代碼（5分）按照規(guī)范要求完成課程設計源代碼的排版總 評 成 績指導教師評語： 日期： 年 月 日目 錄1 課程設計目標與任務11.1 課程設計目標11.2 課程設計任務11.3 課程設計的基本要求12 分析與設計22.1 括號匹配的概述22.2 存儲結構設計22.3 算法描述42.4 程序流程圖63 程序清單74 測試104.1 測試數(shù)據(jù)104.2 測試結果分析105 總結116參考文獻121 課程設計目標與任務1.1 課程設計目標（1）了解并掌握數(shù)據(jù)結構與算法的設計方法，具備初步的獨立分析和設計能力。（2）初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技能。（3）提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力。（4）訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應具備的科學的工作方法和作風。1.2 課程設計任務 設計括號匹配的相關函數(shù)庫，以便在程序設計中調用，要求：（1）輸入一個算術表達式，式中包含三種括號：圓括號、方括號和花括號，這三種括號可以按任意次序嵌套使用，要求編寫程序判斷給定表達式中的括號是否正確配對。（2）能借助語言環(huán)境實現(xiàn)圖形顯示功能，以便將抽象的數(shù)據(jù)結構以圖形方式顯示出來，將復雜的運行過程以動態(tài)方式顯示出來。（3）給出若干例程，演示通過調用自己所縮寫程序來實現(xiàn)相關問題的求解。1.3 課程設計的基本要求嚴格按照題意要求，獨立進行設計，不能隨意更改。若確因條件所限，必須要改變課題要求時，應在征得指導教師同意的前提下進行。學生應制定設計工作計劃，認真完成設計的各個環(huán)節(jié)，并在老師的指導下認真組織設計工作，撰寫設計報告，做好設計總結。2 分析與設計2.1 括號匹配的概述假設表達式中允許包含兩種括號：圓括號和方括號，其嵌套的順序隨意，即( ( ) )或 ( ) 等為正確的格式， ( 或 ( ) 或( ( ) 均為不正確的格式。檢驗括號是否匹配的方法可用“期待的急迫程度”這個概念來描述。例如考慮下列括號排序： ( ) 12345678當計算機接受了第一個括號后，它期待著預期匹配的第八個括號的出現(xiàn)，然而等來的確實第二個括號，此時的第一個括號只能暫時等待。第二個括號期待著第七個括號的出現(xiàn)，然而等來的確實第三個括號，第二個括號仍然需要讓先。第三個括號出現(xiàn)之后期待著第四個括號的出現(xiàn)，匹配完成之后第二個括號繼續(xù)開始期待，依此類推，即可完成對括號的匹配。可見這個處理過程恰好和棧的特點相吻合。由此，在算法中設置一個棧，每讀入一個括號，如是右括號，則或者使置于棧頂?shù)淖钇惹械钠诖靡韵?，或者是不合法的情況；若是左括號，則作為一個新的更迫切的期待壓入棧，自然使原有的在棧中的左右未消解的急迫性都降了一級。另外，在算法的開始和結束時，棧都是空的。2.2 存儲結構設計構造一個空棧S， int 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是否為空棧，用于主函數(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 DestoryStack(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 算法描述構造一個算法，用來確定什么樣的情況括號匹配是正確的。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(Please enter a string of parenthesis:);gets(e);if(e0=)|(e0=)|(e0=)printf(括號匹配錯誤); exit(0);for(i=0;ei!=0;i+)/以/0判斷輸入是否結束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;2.4 程序流程圖程序有兩個模塊一個模塊存儲括號配對的正確情況， Comp（）方法用來判斷括號配對的正確情況（詳情參考圖2.4 程序流程圖2）如左右括號多出等。GetCount（）用來判斷括號匹配的錯誤的情況（詳情參考圖2.4 程序流程圖2）。主函數(shù)用來調用這兩個方法。如圖所示：主函數(shù)調用Comp（）調用GetCount（）結束圖2.4 程序流程圖1GetCount（）方法用來判斷輸入的字符串是否為正確的括號匹配序列。通過出棧與進棧的循環(huán)來判定為左括號多余或者是右括號多余。循環(huán)流程圖如下：輸入字符串為左括號？否是為右括號且匹配？左括號進棧是左括號出棧指向下一個字符圖2.4 程序流程圖23 程序清單#include#include#include#include#define STACK_INIT_SIZE 100/存儲空間初始分配量#define STACKINCREMENT 10typedef char Status; typedef char SElemType ;/建立棧的首節(jié)點typedef structSElemType *base; /在棧構造前和銷毀后，base的值為NULLSElemType *top; /棧頂指針int stacksize; /當前已分配的存儲空間，以元素為單位SqStack;/構造一個空棧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(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的棧頂元素，并返回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+ =e;return 1; /若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK，否則返回ERRORStatus 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(Please enter a string of parenthesis:);gets(e);if(e0=)|(e0=)|(e0=)printf(括號匹配錯誤); exit(0);for(i=0;ei!=0;i+)/以/0判斷輸入是否結束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;/主函數(shù)void main()SqStack S;InitStack(S);GetCount(&S);4 測試4.1 測試數(shù)據(jù)（1）左括號多余。（2）右括號多余。（3）匹配正確4.2 測試結果分析（1）錯誤的情況之一是左括號多余，例如 ( )就是一個簡單的左括號多余情況，輸出之后的結果如圖：圖4.2-1 左括號多余（2）錯誤的情況之二是右括號多余，例如( ) 就是一個簡單的右括號多余情況，輸出之后的結果如圖：圖4.2-2 右括號多余（3）匹配正確的有很多種情況。舉例一種 ( ) 就是正確的括號匹配情況，輸出之后的結果如圖：圖4.2-3 括號匹配正確5 總結通過這次的數(shù)據(jù)結構課程設計實驗周,我進一步理解了順序堆棧的構造極其邏輯結構定義，并一定程度上掌握順序堆棧的基本操作算法。書本上對順序堆棧的基本算法介紹的比較詳盡，但由于我對這方面的知識了解真的不深，而且之前C 語言的基礎沒有打好，程序設計過程中遇到不少難題，通過和直到老師、同學們的溝通，并上網查了些資料，問題終于得到一定程度上的解決。 這一次程序設計實驗周中我受益匪淺，掌握到了順序堆棧的基本算法。所學到的知識得到了很好的復習并鞏固。我認識到數(shù)據(jù)結構是實踐很強的一門課程，光是“聽”和“讀”是絕對不夠的，必須加強實踐。6參考文獻1.嚴蔚敏，吳偉民編著，數(shù)據(jù)結構（C語言版），清華大學出版社，2005 2 嚴蔚敏，陳文博編著，數(shù)據(jù)結構及應用算法教程，清華大學出版社，2006 3 李云清，楊慶紅，揭安全編著，數(shù)據(jù)結構（C語言版），人民郵電出版社2006 4 譚浩強，張基溫，唐永炎編著，C語言程序設計教程（第二版）高等教育出版社，2005 5 蘇仕華等編著，數(shù)據(jù)結構課程設計，上海；機械工業(yè)出版社，2004#include#include#include#include#define STACK_INIT_SIZE 100/存儲空間初始分配量#define STACKINCREMENT 10typedef char Status; typedef char SElemType ;/建立棧的首節(jié)點typedef structSElemType *base; /在棧構造前和銷毀后，base的值為NULLSElemType *top; /棧頂指針int stacksize; /當前已分配的存儲空間，以元素為單位SqStack;/構造一個空棧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(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的棧頂元素，并返回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+ =e;return