c++課程設計---棧類的設計與使用

1、<p><b>　　報告編號：</b></p><p><b>　　綜合課程設計報告</b></p><p><b>　　棧類的設計與使用</b></p><p><b>　　目 錄</b></p><p><b>　　摘 要1&l

2、t;/b></p><p>　　第一章 前言2</p><p>　　第二章 需求分析3</p><p>　　第三章 設計研究的主要工作4</p><p>　　3.1 總體設計4</p><p>　　3.2 詳細設計6</p><p>　　3.2.1 用順序鏈表實現(xiàn)6<

3、/p><p>　　3.2.2 用單鏈表實現(xiàn)7</p><p>　　3.2.3 用雙向鏈表實現(xiàn)10</p><p>　　第四章 系統(tǒng)實現(xiàn)13</p><p><b>　　第五章 總結(jié)17</b></p><p><b>　　參考文獻：17</b></p>&

4、lt;p><b>　　棧類的設計與使用</b></p><p><b>　　摘 要</b></p><p>　　本小組在這次課程設計中選擇了“棧類的設計與運用”這個課題，主要目的是要利用C++程序設計語言實現(xiàn)棧類的封裝，使得整個程序可以完成出棧、進棧、獲取棧頂元素、清空棧等一系列基本操作，也可以通過此次實訓鞏固C++和數(shù)據(jù)結(jié)構(gòu)中的很多知識

5、點。在實訓過程中，我們通過分工合作完成了一個個獨立的模塊，并將這些模塊整合起來，完成了這次設計。在設計中，我們考慮了封裝棧的多種形式，采用了順序鏈表、單鏈表、雙向鏈表三種方法實現(xiàn)了棧的封裝，并運用了多層菜單的模式，利用類模板實現(xiàn)了對多種類型數(shù)據(jù)的進、入棧，方便了用戶的選擇，實現(xiàn)了完全用戶操作的目的，整個界面簡潔卻不失全面，層層遞進，可以返回，并在實現(xiàn)出棧、入棧功能的基礎上，可以按照用戶的意愿來控制入棧、出棧的元素個數(shù)，更體現(xiàn)出程序的人性

6、化。通過此次實訓，我們不僅鞏固了專業(yè)課的知識點，而且在平時查閱資料的過程中學到了很多新的知識，收獲頗豐。</p><p>　　關(guān)鍵詞：棧 類的封裝 函數(shù)模板 </p><p><b>　　第一章 前言</b></p><p>　　我們這組所選的課題是“棧的設計與使用”，也就是將棧封裝成一個類，完成棧的一些基本操作，例如入棧、出棧、獲取棧頂

7、元素、獲取棧內(nèi)元素個數(shù)等。</p><p>　　在本學期所學的數(shù)據(jù)結(jié)構(gòu)課程里，我們已經(jīng)學過了關(guān)于棧的一些基本知識，棧是限制在表的一端進行插入和刪除運算的線性表，通常稱插入，刪除的這一端為棧頂，另一端為棧底。棧分為兩種類型，順序棧和鏈式棧。棧的順序存儲結(jié)構(gòu)簡稱為順序棧，它是運算受限的線性表。因此，可用數(shù)組來實現(xiàn)順序棧。棧頂位置是隨著進棧和退棧操作而變化的棧的鏈式存儲結(jié)構(gòu)稱為鏈棧，它的運算是受限的單鏈表，插入和刪除操

8、作僅限制在表頭位置上進行。所以為了能讓用戶可以使用多種方式封裝的棧，我們準備在設計中，采用了三種實現(xiàn)方式：順序鏈表、單鏈表和雙向鏈表，以滿足各種不同的需求。</p><p>　　由于棧結(jié)構(gòu)具有的后進先出的固有特性，使得棧在程序設計中得到廣泛地運用。利用?？梢赃M行數(shù)制轉(zhuǎn)換、文字編輯和表達式計算等很多應用。由此可以看出棧在程序設計中的重要地位，所以我們這一組專門選擇了這一課題，為了讓程序員在編程中多次使用棧且不必考慮

9、入棧、出棧等操作細節(jié)，減少程序員程序設計中的工作量。我們準備用類模板實現(xiàn)棧類的封裝，程序員就在使用棧類新建棧對象時只要傳入數(shù)據(jù)類型就可以方便地對各種類型的數(shù)據(jù)進行入棧、出棧等操作，提高程序員程序設計的效率。</p><p><b>　　第二章 需求分析</b></p><p>　　2.1 完成數(shù)據(jù)元素的入棧</p><p>　　在設計中，我們可

10、以讓用戶對四種類型的數(shù)據(jù)元素進行入棧操作，int double string char類型，首先，用戶可以選擇某一種類型的數(shù)據(jù)，然后可以自定義入棧元素的個數(shù)并輸入相應數(shù)據(jù)，使元素入棧。</p><p>　　2.2 實現(xiàn)數(shù)據(jù)元素的出棧</p><p>　　出棧時，用戶可以選擇出棧元素的個數(shù)，按照棧的“后入先出”原則，使相應個數(shù)的元素出棧，這時，用戶仍可以繼續(xù)輸入元素出棧的個數(shù)，使剩下

11、的元素依次出棧，如果棧空了，會返回棧已空，無法再對元素進行出棧操作了。</p><p>　　2.3 獲取棧頂元素</p><p>　　當用戶將一批元素入棧后，可以通過菜單上的選項完成獲取棧頂元素的功能，更方便的是，在用戶對元素進行隨意出棧的過程中，也可隨時獲得相應的棧頂元素，當棧為空時，還可返回獲取失敗的信息。</p><p>　　2.4 獲取棧內(nèi)元素個數(shù)</

12、p><p>　　當用戶將一批元素入棧后，可以通過菜單上的選項完成獲取棧內(nèi)元素個數(shù)的功能，而且，在用戶對元素進行隨意出棧的過程中，也可隨時獲得相應的棧內(nèi)元素個數(shù)，當棧為空時，還可返回獲取失敗的信息。</p><p>　　第三章 設計研究的主要工作</p><p><b>　　3.1 總體設計</b></p><p>　　我們?yōu)?/p>

13、了這次課程設計，在工作開始前就畫了流程圖，使得整個系統(tǒng)更加明了化，系統(tǒng)采用三級選擇操作，由用戶進行操作選擇不同結(jié)構(gòu)的棧類、選擇測試的數(shù)據(jù)類型、選擇該數(shù)據(jù)的操作。流程圖如下：</p><p><b>　　圖 3.1.1</b></p><p>　　圖3.1.1流程圖說明了主函數(shù)調(diào)用其他函數(shù)的總體規(guī)劃,根據(jù)用戶的選擇，選擇使用不同結(jié)構(gòu)封裝的棧，當用戶選擇了要測試的結(jié)構(gòu)的棧

14、時，進入第二層選擇。</p><p><b>　　圖 3.1.2</b></p><p>　　圖3.1.2顯示第二級菜單，根據(jù)用戶的選擇，測試不同類型的數(shù)據(jù)。選擇后會進入第三級菜單,即進入圖3.1.3的流程</p><p><b>　　圖 3.1.3</b></p><p>　　圖3.1.3顯示了底

15、層菜單的流程圖，根據(jù)用戶的選擇，運行入棧、出棧等不同的操作。</p><p><b>　　3.2 詳細設計</b></p><p>　　3.2.1 用順序鏈表實現(xiàn)</p><p>　　根據(jù)需要定義了一個棧類，class SqStack，用以實現(xiàn)的功能有：初始化一個棧、數(shù)據(jù)元素的入棧（int Push(T num)）和出棧（int Pop(T &

16、amp;num)）、獲取棧頂元素（int GetTop(T &num)）和棧的長度（int size()）、判斷棧是否為空（int Empty( )）；下圖顯示了棧動態(tài)分配空間和指針指向的變化</p><p><b>　　圖3.2.1.1</b></p><p>　　3.2.2 用單鏈表實現(xiàn)</p><p>　　在單鏈表程序中定義了兩

17、個類，結(jié)點類（class node）和棧類（class stack），可以實現(xiàn)的功能有：初始化一個棧、數(shù)據(jù)元素的入棧（void Push(T e)）和出棧（T Pop( )）、獲取棧頂元素（T GetTop( )）和棧的長度（int Getlength( )）、判斷棧是否為空（bool Empty( )）。在棧類里，定義了一個構(gòu)造函數(shù)stack( )，完成棧的初始化，在這個功能的實現(xiàn)中，利用運算符new給棧的頭指針動態(tài)分配空間hea

18、d=new node<T>，在申請內(nèi)存成功的情況下，利用語句head->next=NULL；</p><p>　　length=0，即可完成棧的初始化。</p><p>　　入棧時，可執(zhí)行以下操作：將待入元素放入待入結(jié)點內(nèi)，然后修改頭指針，使其指向待入結(jié)點，并將待入結(jié)點的指針指向空，這時，即完成一個元素的入棧操作，流程圖和示意圖如下：</p><p&g

19、t;<b>　　圖3.2.2.1</b></p><p><b>　　圖3.2.2.2</b></p><p>　　出棧時，可執(zhí)行以下操作：</p><p>　　修改頭指針的指向，使其指向它所指結(jié)點的下一個結(jié)點，并同時釋放它原先所指的結(jié)點，這樣，即完成一個元素的出棧操作，流程圖和示意圖如下：</p><

20、;p><b>　　圖3.2.2.3</b></p><p><b>　　圖3.2.2.4</b></p><p>　　3.2.3 用雙向鏈表實現(xiàn)</p><p>　　在實現(xiàn)棧封裝中，使用到了兩個類，分別是class Node和class Stack。Node類表示雙向鏈表中單個結(jié)點的結(jié)構(gòu)。Stack類中封裝了對雙向鏈

21、表結(jié)點的操作完成棧的基本功能。</p><p>　　入棧主要是申請一個新的Node大小的空間，申請時通過必要的數(shù)據(jù)完成Node結(jié)點的初始化，申請到的空間的基地址給end->next，然后將end指針指向end->next。最后進行l(wèi)en+1操作，記錄下棧中元素個數(shù)。</p><p><b>　　圖3.2.3.1</b></p><p&g

22、t;<b>　　圖3.2.3.2</b></p><p>　　出棧時，將尾結(jié)點（end指向的結(jié)點）的值賦給e，使e將尾結(jié)點的值帶回。使temp指向尾結(jié)點，然后通過其前趨prio找到尾結(jié)點的前一結(jié)點，調(diào)整end的地址，使指向尾指點的前趨結(jié)點，然后將temp指向的空間(原尾結(jié)點空間)釋放掉。進行l(wèi)en-1操作，記錄下棧中元素個數(shù)。</p><p><b>　　圖

23、3.2.3.3</b></p><p><b>　　圖3.2.3.</b></p><p><b>　　第四章 系統(tǒng)實現(xiàn)</b></p><p><b>　　圖 4.1</b></p><p>　　圖4.1展現(xiàn)了程序運行時的初始畫面，也就是給用戶提供了三種封裝棧的

24、方式，用戶可以自行選擇</p><p><b>　　圖 4.2</b></p><p>　　圖4.2展示了用戶隨意進入一種實現(xiàn)方法后的畫面，在這級菜單上，用戶可以選擇所要用的數(shù)據(jù)元素的類型，程序提供了五種</p><p><b>　　圖 4. 3</b></p><p>　　圖4.3展示的是用戶

25、隨意選擇一種數(shù)據(jù)類型后所進入的畫面，這時用戶可以選擇執(zhí)行哪項基本操作</p><p><b>　　圖 4.4</b></p><p>　　圖4.4展示的是執(zhí)行入棧的過程</p><p><b>　　圖 4.5</b></p><p>　　圖4.5展示了數(shù)據(jù)出棧的過程，此時，用戶可按自己意愿選擇

26、出棧的元素個數(shù)，當元素全部出棧后，會顯示棧已空</p><p><b>　　圖 4.6 </b></p><p>　　圖4.6展示了獲取棧內(nèi)元素個數(shù)和棧頂元素的過程，當棧內(nèi)元素為空時，執(zhí)行上兩步操作時，會提示操作失??！</p><p><b>　　第五章 總結(jié)</b></p><p>　　本次實

27、驗，我們小組運用了3種方法來實現(xiàn)棧類的設計，分別為：順序鏈表法、單鏈表法、雙向鏈表法。在實驗初，我們小組僅僅只實現(xiàn)了數(shù)據(jù)元素簡單的一次性入棧、出棧等操作，操作過程不具有人機交互的智能性，不能決定出入棧元素的個數(shù)，而且僅僅包含兩種數(shù)據(jù)類型：int、char，所含數(shù)據(jù)類型過少，程序不夠茁壯。在實驗中經(jīng)授課老師的指導，我們對程序進行了修改。使其更具有人機交互的能力，具有多層面的選擇提示，基本上能滿足多種數(shù)據(jù)類型的輸入輸出方式。</p&g

28、t;<p>　　本小組所設計的內(nèi)容，具有以下優(yōu)點：</p><p>　　對棧封裝后，可以便于用戶的多次使用；</p><p>　　多種類型數(shù)據(jù)元素的設置和類模板的使用，使用戶的操作更具全面化與簡便化；</p><p>　　多級菜單的設置，讓人機交互的好處得到了充分展示；</p><p>　　用戶在定義所要操作的元素個數(shù)時更具人性

29、化。</p><p>　　但由于我們的知識還不是很充分，所以整個程序還有著不足之處，比如：</p><p>　　通過此次實訓，我們鍛煉了自己的動手能力，鞏固了本學期在C++和數(shù)據(jù)結(jié)構(gòu)課程里所學的知識點，更在整個過程中加強了團隊配合的能力。最后謝謝老師的指導，謝謝各位組員的努力！</p><p><b>　　參考文獻：</b></p>

30、<p>　　[1] 《數(shù)據(jù)結(jié)構(gòu)（C語言版）》 嚴蔚敏 吳偉民 北京：清華大學出版社 2009年9月</p><p>　　[2] 《C++面向?qū)ο蟪绦蛟O計》譚浩強 北京：清華大學出版社 2006年1月</p><p>　　[3] 《C++面向?qū)ο蟪绦蛟O計題解與上機指導》譚浩強 北京：清華大學出版社 2006年1月</p><p>　　[4] 《數(shù)