1、數據結構實驗報告 實驗項U名稱：棧的應用 實驗地點 ZRZ 專業、班 18訟卓1班 指導教師 林仙麗 實驗時間 2020.4.5 一、實驗U的及要求 1. 熟悉棧的基本概念; 2. 掌握棧的順序存儲結構; 3. 掌握棧的應用。 二、實驗設備（環境）及要求 微型計算機： windows操作系統; Microsoft Visual Studio 6.0 集成開發環境。 三. 實驗內容與步驟 1.棧的順序表表示如下: define MaxSize 100 typedef int ElemType： typedef struct ElemType dataMaxSize; int top： SqSta

2、ck; 1）實現順序棧的基本操作； 2）調用棧操作函數實現判別一個算術表達式中的圓括號和方括號配對是否正 確匹配。 運行結果： 1 C:5er$506l60e 如甲 jgVCfflBW)txe -口X Ph；卜兀；;%屮2 ；TyC；Tw 3 Fb：丁岀吃凡2； 八iFMtt的tlH 5. *iK；i rs ; Empty 6打印半防棧収術仃尤4( 詢找 8. , ；reiw 0退出 ；：配建W“！小* 朋卩爪住a山試擰M：-(單獨個住恪、-()”(W號屮供宅ft) 債入i：H靑輸入沖5個進棧的朮U 譏輸入魁執行的作：2 寺訊極(尤賓為：S 輸入耍執廿的作： 圖2:棧的lop()操作 C:Ue

3、 論506l60WopWi阻配建富測迸樣M； ”ona-e空格)、“()”0護格 M附入fi決仃的提i： 1 訕輸入耍進棧的丘農ftfib 5 :?:個養逬FEM尤索5 r,除入2個JJHQ鴿尤4(: 上0(入;R3個疋檢旳尤| 詁W入第4個箜込出用，兀余： T；總入5J5個址棧忙兀*: ZWXejKIjffJKfl : 4 的長燈為J 5 請輸入鑒執計的操作： 2 3 4 5 圖4:棧的size()操作 C AUscts5O6 * GVOskto p 71 u9CB0宇U.exe - X rf. 二 .1.，C；:P-P - . 1L. A ；W：f/i n J .1 打： 5.鳶i -.棧

4、建臺人 仆16汀印棧5所“尤* r :涓八応8J1； I 0 i III W ；K議制dim - “（m f空ft）、（）”併中1誦和和 *入：J行的1知：5 niifK ., 輸X仏行的操T： 圖5:判斷棧是否為空的emplyO操作 C User叭16Dkto p4tCifiBltrHOebugVCfiaWrx;xe i Push兀餐迥人：?.時劉W.S.HTop 3. Pop曲;1科用兀応 二時W%訕側枳肌S滋 5列斯F筋理址乃它鯽tY 6HH、S的棧中所ft尤索 泊吃、切ii找89；兀配0. id 111 川刃I配建a忍試樣Ms “ （單tt 個臨林八-（”（擠號屮AK!恪） 入啖?.棧

5、的1：好：2 5.:.ft足J昇廠也忖y 6.：W|M棧小所有尤索 沁廣1：.棧8小;呱配a 2ili :Pi；（ViJi空 ,-,1 fiSk : 1 sstHtr U W： 5 耳入第1個:門叮土】勺尤lb F2牛劉LMJ尤食： 7 3*進吃為尤素J 出4GH比I勺尤昴 J 5fi5個JI.門尤董* ” A、芟執行 t；!l : 6 r 4 * 2 1 F： ；、iJur 的操作：7 f 窩行的操作：6 r 整執行的樣作：4 為；0 廠、執行的採作：5 棧為*1* 心“入菱機廿的作： 圖7淸空棧中元素的clearO操作 畑 i6We$ktg保Wisansm趴OQugCfimimteg l.

6、Psh兀艮訃人孩V 二F，!河技i!幾袞Top 3.Pop艸川枝飛幾#; 4紂到*山我1皿叮2己5兀冷 n樓覽莎力腳pty 6打山詢棧中折仆尤余 7詒彳巴卩川棧弓 諂入代：的按作：8 W入W；字持中；（ 譏輯入fift行的樣作：3 W輸入WV ?符M仃【0 VCK i/J輸入望怏行的様作：8 WHfcXIJiV nd!：（） W*入快行的操作：8 冷處人ijYrNh）（ 詁城妄眞廿的作：8 詁沁人曲（ 4、5； 圖 stacks; scanf s. push (a);/入棧 printf C%(in, s. topO); /収得棧頂元素輸出 s.p op()；/di 棧 return 0; 請

7、根據以上程序，設il算法如下： 判別一個算術表達式中的圓括號配對是否正確。 （1）問題分析： 首先這個問題類似于洛谷的P1739表達式括號匹配，在括號匹配的問題中, 如果我們只考慮一種括號是否匹配的話，其實可以不用到棧就可以實現這樣的算 法，而這樣的過程其實本質上也是有點類似于棧的思想，我們可以對輸入的左括 號（進行訃數，同時設置一個標記位為0,當檢測到字符弗中的左括號時便 加1,遇到右括號“）時便減1,當遍歷完字符串時，我們判斷一下這個標記 位是否還是為0就可以知道字符串中的括號是否匹配，當然，為了避免字符審最 前面的括號為右括號的情況，我們在遍歷字符吊時可以加上判斷標記為是否小于 0, 旦

8、小于0則證明不匹配，直接退出循環。 而如果表達式中的括號不只有一種，此時用stack棧來完成這樣的算法是非 常好的，我們可以遍歷表達式字符串，遇到左括號（“（、）時, 便將其進行入棧操作，然后遇到右括號（）、.“：r ）時，我們就將 棧頂與遇到的右括號進行匹配，如果配對成功，則彈出棧頂括號，繼續配對，反 之則跳出遍歷。 （2）運行結果: 圖9：棧實現括號匹配的問題（1） 一 , exited 合fter 19.62 seconds vith return value 0 1按任wHfR ；比topve號酥畑聰g - X re 5 exi- after 6.177 seconds ith ret

9、urn value 0 按盤tt軌, 圖10:棧實現括號匹配的問題（2） 3、查閱資料，了解的棧其他應用，并找一應用實例，如表達式求解，要求說明 算法思想并編程實現。 (1)問題分析： 棧在我們生活中的應用十分多，這里我主要集合了括號匹配、進制轉換、行 編輯程序、表達式轉換求解這四種比較常見的實例。 括號匹配在上文已經說明過了其算法實現原理，這里就不再贅述。 進制轉換能用棧的原因主要是我們在對數字進行進制轉換時，最先用算出的 數字為低位，應該最后輸出，所以考慮到棧的先進后出的特性，我們可以將出 來的數字不斷進棧，然后最后將棧頂元素不斷彈出輸出就可以實現進制轉換的原 理,要注意的點就是大于9的數

10、字應該要用大寫字母來表示，需要多加一個判斷。 行編輯程序能用棧的原因主要是利用了棧彈出棧頂元素和能夠清除整個棧的 特點，在我們輸入文本時，我們將一個個字符入棧，同時進行判斷，我們用縛 代表牛前的一個字符無效，這時只要判斷當前字符為時，我們就彈出棧 頂元素然后繼續遍歷，我們用 迢代表 迤前的所有字符無效，這時只要判斷 當前字符為 時，我們就清除整個棧，當輸入完一行文本時，我們將棧輸血 就能得到正確的文本。 將中綴表達式轉換成后綴表達式同時求解是對棧的一個比較綜合的運用，我 們可以將其分成兩個部分：一是將中綴表達式轉換成后綴表達式，二就是對后綴 表達式進行求解，這兩部分都運用到了棧。第一部分首先我

11、們主要是用棧來對表 達式中的運算符號進行一個優先級的處理，這里我們將符號定為優先級最 高，廠 優先級次之，一優先級最低，同時遇到括號時，要對括 號中的運算符號進行特判，然后再將處理完的符號放入字符審中，最后這個字符 吊中存著的就是后綴表達式。第二部分就是我們對這個字符審開始遍歷，同時將 每個字符存入一個棧，當檢測到運算符號時，我們將棧頂的兩個元素彈出，對其 進行運算，就這樣重復直到最后算出結果來。 (2)運行截圖: 0 匹忙 昭怡入輕執行的操作：I 0) 入執行的作：I no PCV 入婁快行件： .；:佝 2. 2. -J -Vl- f. ：0. 4-； :井-zUUi blvtl : 2

12、F 上.卜進制tts 10 /. -i XfiSv換的進 i j 10 10 1/入執行的春作：2 諂輸入快進W的I址制10 i/J輸入荽轉換的進W 2 1010 IflWXetXlr的操作：2 諭輯入空轉換進iMWIiSMtti 10 訥輸入箜轉換的進8 12 入執仃的作：2 說輸入菱轉換進M的|進Mtt； 10 id入轉換的必制：16 入箜執行的你： 圖12:棧實現進制轉換 CAUf506i rtffiMDebu9c- ??；A 二汕小小 3. -J川4 1 計 久出ffr+M: 3 b：lS#ilr#e(s5s) outcha9putchar(*s=*+ 圖13:棧實現行編輯程序 C:Ut

13、ertS06160e 比(劭咖工 g麗VOebugW .IttUg 眼燉 r；-v-l : 4 (3*2=e)/5*4 326*5/4* 0 3 12 * 5 / 4 * 7 15 S / 4 * 34 4 * ，、執汙的ft作：4 2*(3 2*4*9/3-2/2*3 232493/*2-2/*3 ,6324*93/*2-2/*3* ；694*93/*2-2/*3* 36 9 3 / * 2 2 / * 3 * l6 36 3*22/*3* 16 39 2- 2/ + 3 + 16 37 2 / * 3 * 18 * 3 * “ 3 * ，C執行的作: 圖14：棧實現表達式轉換并且求解 四、

14、分析與討論 在這一次的實驗中，我對棧的理解更加深刻了，學會了用棧去實現各種算 法，同時自己也學會了建立起一個順序棧，讓我更加熟悉了棧的原理，掌握了棧 的更多使用技巧，同時也更明白了棧的使用范圍和棧的特性特征。 成績 五、教師評語 簽名: 附源程序淸單: 1. *include *include typedef int ElemType; #define MaxSize 100 typedef struct MyStack ElemType dataMaxSize; int top： SqStack： void InitStack(SqStack* s-top = -1： void Destro

15、yStack(SqStack* int Size(SqStack* s) return(stop + 1); bool IsEmpty(SqStack* s) return(stop = 1); ElemType Pop(SqStack* s-top； return data; void Push(SqStack* else s-top+; sdatastop = s; ElemType Top(SqStack* s) if (IsEmpty(s) printfC此時找為空,無找頂尤素十）; return 0： else return s-datas-top; void Printstack(

16、SqStack* s) int i; for (i = -top; i = 0; i) printf、sdatai): printf(*n*); void ClearStack(SqStack* s) s-top = -1： bool Check(char a, char b) if (a + 1 = b i a + 2 = b) ,7 C：40 ):41：123 ： 125：91 ：93 return true; else return false; int BracketMatch(char* str) SqStack* a; char ch： int flag = 0： InitStac

17、kCa); for (int i = 0; stri ：= 0 ; i卄) switch (stri) case :break; case case case flag = 1; Push (a, stri); break; case case case flag = 1： if (isEmpty(a) printf C*未匹配n); return 0： else ch = Top (a); if (Check(ch, stri) Pop(a); else printf (未匹配n); return 0： if C!flag) printfC字符串中無括號十); return 0： if Ci

18、sEmpty(a) printf C匹配n); else printfC 未匹配 ir); DestroyStack(a); return 0： int mainO SqStack* s： InitStack(s); int i; 5.判斷當前找是否為空Empty 6.打印當前棧中所有元素 printf-l.Push元索進入棧中2得到棧頂元索Top 3. Pop #出棧頂元素n); printf (4.得到肖前棧的長度Size n); 0退出十)； ”(單獨一個空格)、括號中帶空格八n); printf(-7.淸空半前棧8.括號匹配 printf(-括號匹配建議測試樣例：“ do printf

19、C請輸入耍執行的操作: scanf_s switch (i) case 1: int n; ElemType x; printf(請輸入要進棧的元索數雖：); scanf.s(0d, for (int i = 0; i Push(s, X); break; case 2: print玖當前棧頂元索為：%dn-. Top(s); break; case 3： printf (棧頂元索以彈出彈出元索為：喙in, Pop(s); break; case 4: printf C當前棧的長度為5 %dn*, Size(s); break; case 5: if(isEmpty (s) printf C當

20、前棧為空11); else printf(-當前棧不為空n); break; case 6: Printstack(s); break; case 7: ClearStack(s); break; case 8: char str100; getchar0； printf(請輸入括號字符串：”); scanf_s C*%Cn*, BracketMatch(str); break; default: break; while (i != 0); DestroyStack(s); return 0; 2. 只有一種括號模擬棧的做法 Sinclude #include using namespace

21、 std： int mainO string s, a： int cin for top = 0： s; (int i = 0; i s.sizeO; i+) if (top 0) cout *不匹配* endl; return 0： if (si = - C) top+; a top=) if (si = atop) top: if (top = 0) cout *匹配* endl: else cout 不匹配 endl: stack 做法： #include *include *include using namespace std： bool Check(char a, char b)

22、if (a + 1 = b I： a + 2 = b) return true; else return false: int mainO stack s: string a; cin a： for (int i = 0; i a. size() : i+) case case case s. push(ai); break; case case case if (s. empty C) cout 不匹配 endl： return 0： else if (Check(s. top(), ai) s. popO ; break; else cout *不匹配* endl; return 0： b

23、reak; if (s. empty () cout *匹配* endl: else cout *不匹配* endl: 3. Sinclude Sinclude #include #include using namespace std： int BracketMatchO stack s; string a： cin a; for (int i = 0; i a.size(): i+) case case case s. push(ai); break; case case case if (s empty () cout *不匹配* endl： return 0： else if s. t

24、opO + 1 = ai s. topO + 2 = ai) s. popO ; break; else cout 不匹配* endl; return 0： break; if (s. empty () cout *匹配* endl: else cout *不匹配* endl: return 0： void SwitchO int n, m; stack s: cout *請輸入要轉換進制的十進制數：- cin n; cout 請輸入要轉換的進制：； cin m; while (n) if (n % m 10) s. push (n % m + o); else s. push(n % m 1

25、0) + A)； while (!s. empty0) cout s. topO : s pop C); cout endl; void LineEdit() stack s; char ch = getchar (): string a： while (getline(cin, a) for (int 1 = 0： i a. size() ; i+) s pop C); break： case * : while C! s. empty C) s. popO ; break： default: s push(ai); break; stack temp: while C! s. empty C) temp. push(s. topO ); s popO ; while C! temp, empty () cout ternp.topO; temp. popO; cout endl: int Level(char ch) switch (ch) case case return 1: case : case /: return 2: case : return3： -1： case case return 0： default: return void Pri