c++課程設(shè)計(jì)---棧類的設(shè)計(jì)與使用

1、<p><b>　　報(bào)告編號：</b></p><p><b>　　綜合課程設(shè)計(jì)報(bào)告</b></p><p><b>　　棧類的設(shè)計(jì)與使用</b></p><p><b>　　目 錄</b></p><p><b>　　摘 要1&l

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

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

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

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

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

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

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

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

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

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

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

13、了這次課程設(shè)計(jì)，在工作開始前就畫了流程圖，使得整個系統(tǒng)更加明了化，系統(tǒng)采用三級選擇操作，由用戶進(jìn)行操作選擇不同結(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)封裝的棧，當(dāng)用戶選擇了要測試的結(jié)構(gòu)的棧

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

15、層菜單的流程圖，根據(jù)用戶的選擇，運(yùn)行入棧、出棧等不同的操作。</p><p><b>　　3.2 詳細(xì)設(shè)計(jì)</b></p><p>　　3.2.1 用順序鏈表實(shí)現(xiàn)</p><p>　　根據(jù)需要定義了一個棧類，class SqStack，用以實(shí)現(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 用單鏈表實(shí)現(xiàn)</p><p>　　在單鏈表程序中定義了兩

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

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

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

21、表結(jié)點(diǎn)的操作完成棧的基本功能。</p><p>　　入棧主要是申請一個新的Node大小的空間，申請時通過必要的數(shù)據(jù)完成Node結(jié)點(diǎn)的初始化，申請到的空間的基地址給end->next，然后將end指針指向end->next。最后進(jìn)行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é)點(diǎn)（end指向的結(jié)點(diǎn)）的值賦給e，使e將尾結(jié)點(diǎn)的值帶回。使temp指向尾結(jié)點(diǎn)，然后通過其前趨prio找到尾結(jié)點(diǎn)的前一結(jié)點(diǎn)，調(diào)整end的地址，使指向尾指點(diǎn)的前趨結(jié)點(diǎn)，然后將temp指向的空間(原尾結(jié)點(diǎn)空間)釋放掉。進(jìn)行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)實(shí)現(xiàn)</b></p><p><b>　　圖 4.1</b></p><p>　　圖4.1展現(xiàn)了程序運(yùn)行時的初始畫面，也就是給用戶提供了三種封裝棧的

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

25、隨意選擇一種數(shù)據(jù)類型后所進(jìn)入的畫面，這時用戶可以選擇執(zhí)行哪項(xiàng)基本操作</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ù)，當(dāng)元素全部出棧后，會顯示棧已空</p><p><b>　　圖 4.6 </b></p><p>　　圖4.6展示了獲取棧內(nèi)元素個數(shù)和棧頂元素的過程，當(dāng)棧內(nèi)元素為空時，執(zhí)行上兩步操作時，會提示操作失??！</p><p><b>　　第五章 總結(jié)</b></p><p>　　本次實(shí)

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

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

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

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