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

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

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

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

7、元素、獲取棧內(nèi)元素個(gè)數(shù)等。</p><p>　　在本學(xué)期所學(xué)的數(shù)據(jù)結(jié)構(gòu)課程里，我們已經(jīng)學(xué)過(guò)了關(guān)于棧的一些基本知識(shí)，棧是限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入，刪除的這一端為棧頂，另一端為棧底。棧分為兩種類(lèi)型，順序棧和鏈?zhǔn)綏?。棧的順序存?chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序棧，它是運(yùn)算受限的線性表。因此，可用數(shù)組來(lái)實(shí)現(xiàn)順序棧。棧頂位置是隨著進(jìn)棧和退棧操作而變化的棧的鏈?zhǔn)酱鎯?chǔ)結(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ì)中的重要地位，所以我們這一組專門(mén)選擇了這一課題，為了讓程序員在編程中多次使用棧且不必考慮

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

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

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

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

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

14、時(shí)，進(jìn)入第二層選擇。</p><p><b>　　圖 3.1.2</b></p><p>　　圖3.1.2顯示第二級(jí)菜單，根據(jù)用戶的選擇，測(cè)試不同類(lèi)型的數(shù)據(jù)。選擇后會(huì)進(jìn)入第三級(jí)菜單,即進(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ù)需要定義了一個(gè)棧類(lèi)，class SqStack，用以實(shí)現(xiàn)的功能有：初始化一個(gè)棧、數(shù)據(jù)元素的入棧（int Push(T num)）和出棧（int Pop(T &

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

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

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

19、t;<b>　　圖3.2.2.1</b></p><p><b>　　圖3.2.2.2</b></p><p>　　出棧時(shí)，可執(zhí)行以下操作：</p><p>　　修改頭指針的指向，使其指向它所指結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，并同時(shí)釋放它原先所指的結(jié)點(diǎn)，這樣，即完成一個(gè)元素的出棧操作，流程圖和示意圖如下：</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)棧封裝中，使用到了兩個(gè)類(lèi)，分別是class Node和class Stack。Node類(lèi)表示雙向鏈表中單個(gè)結(jié)點(diǎn)的結(jié)構(gòu)。Stack類(lèi)中封裝了對(duì)雙向鏈

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

22、t;<b>　　圖3.2.3.2</b></p><p>　　出棧時(shí)，將尾結(jié)點(diǎn)（end指向的結(jié)點(diǎn)）的值賦給e，使e將尾結(jié)點(diǎn)的值帶回。使temp指向尾結(jié)點(diǎn)，然后通過(guò)其前趨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操作，記錄下棧中元素個(gè)數(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)行時(shí)的初始畫(huà)面，也就是給用戶提供了三種封裝棧的

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

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

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

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

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

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

30、<p>　　[1] 《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》 嚴(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ù)