棧的課程設計--- 棧的類設計

1、<p>　　計算機科學與技術專業(yè)</p><p>　　《數(shù)據(jù)結構與算法》課程設計報告</p><p>　　題目： 棧的類設計</p><p>　　作者： </p><p>　　指導教師： </p><p>　　2013年1 月1

2、2日</p><p><b>　　摘 要</b></p><p>　　主要實現(xiàn)入棧、出棧、取棧頂三個功能，并調(diào)用這三個個功能的算法（若棧滿追加存儲；否則將數(shù)據(jù)壓入棧。若?？談t提示錯誤；否則刪除棧頂元素。若棧空則提示錯誤，否則提取棧頂。）完成棧的中序遍歷，后序遍歷，以及中序到后序轉(zhuǎn)換的表達式，最后完成后序表達式的計算。</p><p><

3、b>　　目 錄</b></p><p>　　摘要……………………………………2</p><p>　　概述………………………………………………5</p><p>　　二、數(shù)據(jù)結構設計……………………………………8</p><p>　　三、算法設計……………………………………………15</p><p&g

4、t;　　四、源代碼說明…………………………………………</p><p>　　五、結果與分析…………………………………………</p><p><b>　　圖 表 目 錄</b></p><p>　　圖（1）棧…………………………………………………………………5</p><p>　　圖（2）入棧、出棧操作過程……………………

5、…………………………6</p><p>　　圖（3）功能實現(xiàn)…………………………………………………………8</p><p>　　圖（4）入棧流程圖………………………………………………………8</p><p>　　圖（5）出棧流程圖………………………………………………………9</p><p>　　圖（6）鏈棧結構圖………………………………………

6、………………12</p><p>　　圖（7）鏈棧的入棧、出棧………………………………………………13</p><p><b>　　概 述</b></p><p>　　-----描述部分-------</p><p><b>　　棧的概念：</b></p><p>　　

7、棧（stack）是插入和刪除操作限定在表尾進行的線性表。進行插入或刪除操作的一端稱為棧頂，另一端稱為棧底。</p><p>　　棧的邏輯表示為：S =（a1,a2, …,an）</p><p>　　表尾元素an稱為棧頂(top)</p><p>　　表頭元素a1稱為棧底(bottom) </p><p>　　不含元素的空表稱為空棧 </

8、p><p><b>　　棧的基本運算包括：</b></p><p>　　初始化；⑵判?？眨?⑶入棧； ⑷出棧； ⑸ 獲取棧頂；(6)棧中當前元素個數(shù)； (7) 清空棧； </p><p>　　棧的運算特性是：后進先出(Last In First Out--LIFO)或先進后出(First In Last Out--FILO)如圖（1）所示。<

9、/p><p>　　入棧 出棧</p><p><b>　?。▓D1）棧 </b></p><p>　　棧初始化：InitStack(&S) 構造了一個空棧。</p><p>　　清空棧: ClearStack(&s)將s棧置為空棧。</p><p>　

10、　入棧 ： Push(&S，&e) 在棧s的頂部插入新元素e，e成為新的棧頂元素，相當于線形表ListInsert(&L, n+1, e)。</p><p>　　出棧： Pop(&S, &e) 在棧s存在且非空的情況下，返回S棧的棧頂元素，并從s棧中刪除該棧頂元素；否則返回空元素NULL，相當于線性表的ListDelete(&L, i, &e)。&l

11、t;/p><p>　　空棧 1入 棧 2入 棧 2出 棧 1出棧 </p><p>　　2 </p><p>　　1 1 1 </p><p>　　top=-1

12、top=1 top=2 top=1 top=-1 </p><p>　　圖（2）入棧、出棧操作過程</p><p>　　用整形元素top 來指示當前元素位置 。我們可以看到?jīng)]有數(shù)據(jù)時的空棧，此時top =-1，它可以作為判斷空的條件。入棧時加1，出棧時減1，從始至終top的值一直是頂元素的下標，這樣在獲取棧頂?shù)脑?/p>

13、素時直接可以通過取棧頂下標的值 從而得到棧頂。但要注意：為top =-1的情況，因為一個數(shù)組的下標是不可能小于0的。</p><p>　　遍歷：所謂遍歷，是指沿著某條搜索路線，依次對棧中每個數(shù)據(jù)均做一次且僅做一次訪問。</p><p>　　獲取棧頂元素：GetTop(S, &e)在棧s存在且非空情況下，讀棧頂元素，棧不變化。與Pop(&S, &e)的差別在不刪除棧頂

14、元素，相當于線性表的GetElem(L, I, &e)。</p><p>　　中序轉(zhuǎn)后序：中序是我們常用的表達式格式。即數(shù)據(jù)--符號--數(shù)據(jù)或者符號—數(shù)據(jù)—符號—數(shù)據(jù)--符號。我們將一個正規(guī)的計算式壓入棧中，出棧時變成數(shù)據(jù)—數(shù)據(jù)—符號或者數(shù)據(jù)—數(shù)據(jù)--符號--符號—符號的格式。這個過程我們稱為中序轉(zhuǎn)后序。例如：a+b*c-d是一個中序表達式，轉(zhuǎn)后序之后變成了ab+c*d-。</p><

15、p>　　后序表達式：邏輯關系是數(shù)據(jù)在前，符號在后的表達式。例如：abc+-。</p><p>　　------簡單算法分析--------</p><p>　　入棧：初始條件是棧已存在；操作結果是推入棧內(nèi)的新元素e為新的棧頂元素。</p><p>　　出棧：初始條件是棧已存在；操作結果是刪除棧頂元素，并返回棧頂元素。</p><p>　

16、　遍歷： 初始條件是有若干的數(shù)據(jù)存在。操作結果是將所有數(shù)據(jù)依次輸出，得到所有數(shù)據(jù)。</p><p>　　獲取棧頂元素：初始條件是棧已存在且非空；操作結果是得到棧頂元素。</p><p>　　中序轉(zhuǎn)后序：首先有一個中序表達式存在，經(jīng)過邏輯關系的轉(zhuǎn)變變成后序表達式。表達式的值沒有發(fā)生變化，只是表現(xiàn)形式發(fā)生變化而已。</p><p>　　后序表達式：將前序、中序表達式用后

17、序形式表現(xiàn)。 </p><p><b>　　數(shù)據(jù)結構設計</b></p><p><b>　　設計考慮</b></p><p><b>　　圖（3）功能實現(xiàn)</b></p><p><b>　　滿</b></p><p><b

18、>　　沒滿</b></p><p><b>　　圖（4）入棧流程</b></p><p><b>　　Y</b></p><p><b>　　N</b></p><p><b>　　N</b></p><p>&l

19、t;b>　　Y</b></p><p>　　圖（5）出棧流程圖 </p><p>　　獲取棧頂?shù)牧鞒毯统鰲５南嗨啤Ｔ诘谝粋€出來的時候返回其值，次值就是棧頂。</p><p>　　邏輯結果和存儲結構表示</p><p><b>　　入棧</b></p><p>　　入棧操作執(zhí)行前，

20、需判斷棧是否已滿，不滿時將值為elem的新元素添加到棧頂 ，棧的結構發(fā)生變化。</p><p>　　Void Push(Stack &S,DataType elem) </p><p><b>　　{</b></p><p>　　If(!Stack_Full(s)) 若棧不滿就不允許插入</p><p>

21、;<b>　　{</b></p><p><b>　　S.top++；</b></p><p>　　S.elem[S.top]=elem；</p><p><b>　　}</b></p><p><b>　　Else</b></p><

22、p>　　Printf(“棧已滿！可執(zhí)行此操作！”)；</p><p><b>　　} </b></p><p><b>　　出棧</b></p><p>　　出棧操作執(zhí)行前，需判斷棧是否為空，不空時將棧頂元素從棧中取出，棧發(fā)生變化。</p><p>　　DataType Pop（Sta

23、ck &s）</p><p><b>　　{</b></p><p>　　if（！Stack_Empty(S)） 若?？?，不允許執(zhí)行出棧操作</p><p><b>　　{</b></p><p>　　Return S.elem[S.top--]</p><p>

24、;<b>　　}</b></p><p><b>　　Else</b></p><p>　　Printf(“棧已空，不可執(zhí)行此操作！”)；</p><p><b>　　}</b></p><p><b>　　獲取棧頂元素</b></p>&l

25、t;p>　　當棧不為空時，根據(jù)top的位置可直接返回棧頂?shù)闹担瑮２话l(fā)生變化。</p><p>　　DataType GetTop(Stack S)</p><p><b>　　{</b></p><p>　　If(！Stack_Empty(S))</p><p><b>　　}</b><

26、/p><p><b>　　Else</b></p><p>　　Printf(“棧中已經(jīng)沒有元素！”)； </p><p><b>　　知識補充</b></p><p>　　鏈棧：棧的鏈式存儲叫做立案棧，是棧的另一種存儲結構。鏈棧解決了容量很難擴充，數(shù)組很大但存儲的數(shù)據(jù)太少而造成的空間浪費的問題。<

27、;/p><p><b>　　棧的存儲結構：</b></p><p><b>　　top</b></p><p>　　elem </p><p>　　elem </p><p>　　elem <

28、;/p><p>　　圖（6）鏈棧的存儲結構 </p><p>　　圖（6）可以看出，要定義一個棧的結構體，需要有棧頂指針，棧的元素。每次入棧都是在棧頂插入一個結點，top是一個指向棧頂?shù)闹羔?，類似于線性鏈表中的頭結點。棧的初始化就是用頭插法建立一個帶頭結點的鏈表，入棧，出棧操作如圖（4）所示。</p><p><b>　　Node1</b><

29、;/p><p>　　elem top</p><p>　　node1 node3 node1</p><p>　　elem top elem top elem top </p><p>　　node2 node2

30、 node2</p><p>　　J1 ^ J1 ^ J1 ^</p><p>　　(a)初始化 （b）J1入棧 （C）J2入棧 （d）J2出棧</p><p>　　圖（7）鏈棧的入棧、出棧操作</p><p>　　入棧：入棧操作執(zhí)行前，需判斷棧是否已滿，不

31、滿時將值為elem的新元素添加到棧頂 ，棧的結構發(fā)生變化。</p><p>　　VoidPush(Stack &S,DataType elem)</p><p><b>　　{</b></p><p>　　Stack NewNode=(Stack)malloc(sizeof(StackNode))；為新結點分配空間</p>

32、<p>　　NewNode->elem=elem； 為新結點賦值</p><p>　　NewNode->top=S->top； 將新結點插入鏈頭</p><p>　　S->top= NewNode； 棧頂指針指向新結點</p><p><b>　　}</b></p><

33、p>　　出棧：出棧操作執(zhí)行前，需判斷棧是否為空，不空時將棧頂元素從棧中取出，棧發(fā)生變化。</p><p>　　DataType Pop（Stack &S） </p><p><b>　　{</b></p><p>　　if（！Stack_Empty(S)）</p><p><b>　　{<

34、/b></p><p>　　DataType ch=GetTop(S)；</p><p>　　Stack S1=(S->top)->top；</p><p>　　Delete(S->top)；</p><p>　　S->top=S1；</p><p>　　Return ch；</p

35、><p><b>　　}</b></p><p><b>　　Else</b></p><p>　　printf(“棧已空，不可執(zhí)行此操作！”)；</p><p><b>　　}</b></p><p><b>　　獲取棧頂元素</b>

36、</p><p>　　當棧不為空時，根據(jù)top的位置可直接返回棧頂?shù)闹?，棧不發(fā)生變化。</p><p>　　DataType GetTop(Stack S)</p><p><b>　　{</b></p><p>　　If(！Stack_Empty(S))</p><p><b>　　{

37、</b></p><p>　　Return(S->top)->elem；</p><p><b>　　}</b></p><p><b>　　Else</b></p><p>　　Printf(“棧中已經(jīng)沒有元素！”)； </p><p><b&

38、gt;　　}</b></p><p><b>　　三、算法設計</b></p><p><b>　　主要設計思想</b></p><p>　　首先創(chuàng)建一個空棧，在空間允許的情況下，將元素壓入棧中。在棧不為空的情況下，將元素取出。取出第一個數(shù)，并返回第一個數(shù)的值就是棧頂。元素全被取完時，棧就成為空棧。調(diào)用入棧，出

39、棧，獲取棧頂?shù)脑?，將中序表達式進行入棧，出棧的操作，得到后序表達式。</p><p><b>　　入棧的偽碼描述：</b></p><p>　　1 if (stack full) </p><p>　　1 success = false </p><p><b>　　2 else </b>

40、</p><p>　　1 allocate (newPtr) </p><p>　　2 newPtr->data = data </p><p>　　3 newPtr->next = stack.top </p><p>　　4 stack.top = newPtr </p><p>　　5 st

41、ack.count = stack.count + 1 </p><p>　　6 success = true </p><p>　　3 end if </p><p>　　4 return success </p><p>　　end pushStack </p><p><b>　　出棧的偽碼描述

42、：</b></p><p>　　1 if（stack empty）</p><p>　　1 seccess=false</p><p><b>　　2 else</b></p><p>　　1 dltPtr=stack.top</p><p>　　2 dataOut=sta

43、ck.top->data</p><p>　　3 stack.top= stack.top->next</p><p>　　4 stack.count= stack.count -1</p><p>　　5 recycle (dltPtr)</p><p>　　6 success=ture</p>&

44、lt;p><b>　　3end if </b></p><p>　　4return success</p><p>　　end popStack</p><p>　　獲取棧頂?shù)膫未a描述：</p><p>　　1 if (stack empty) </p><p>　　1 succes

45、s = false </p><p><b>　　2 else </b></p><p>　　1 dataOut = stack.top->data </p><p>　　2 success = true </p><p>　　3 end if </p><p>　　4 ret

46、urn success </p><p>　　end stackTop </p><p><b>　　源代碼及說明</b></p><p>　　本節(jié)列出源程序清單。如果太長，可列出最關鍵的程序片段并加以解釋，完整的源代碼在附錄里或附軟盤（光盤）。</p><p><b>　　結果與討論</b>&l

47、t;/p><p>　　本節(jié)給出程序運行結果并進行分析、得出相關的結論和下一版本的改進建議。本次實驗，我們小組運用了順序棧的方法來實現(xiàn)棧的設計，在實驗初我們緊實現(xiàn)了入棧，出棧，獲取棧頂?shù)炔僮?，操作過程不具備人機交互的智能性，程序相對簡單。在實驗過程中經(jīng)老師指導，我們對程序進行了修改，使功能更加豐富，增加了工作界面，具有多層次的選擇提示，基本上能滿足多種數(shù)據(jù)的輸入和輸出。</p><p>　　設計

48、的內(nèi)容具有以下優(yōu)點：</p><p>　　1：有可視化的可供選擇的界面。</p><p>　　2：操作簡便和簡單。</p><p><b>　　3：功能齊全</b></p><p>　　4：用戶可自定義數(shù)據(jù)個數(shù)</p><p>　　同時設計存在如下不足：</p><p>　

49、　1：代碼使用c語言而不是更高級的語言。</p><p><b>　　2：界面還不夠美觀</b></p><p>　　通過此次實驗，我們很好的鞏固了數(shù)據(jù)結構與算法的知識。對棧的了解進一步加深。同時培養(yǎng)了我們得合作精神和解決問題的能力。對我們來說是一次深刻的社會體驗。</p><p><b>　　附 錄</b>&l

50、t;/p><p><b>　　參 考 文 獻</b></p><p>　　[1]《數(shù)據(jù)結構與程序設計（c++語言描述）》Robert L.Kruse</p><p>　　Alexander J.Ryba</p><p>　　[2]《C++面向?qū)ο蟪绦蛟O計》譚浩強 北京：清華大學出版社2009年9月</p>&

51、lt;p>　　[3]《數(shù)據(jù)結構與算法（c++版）實驗和課程設計教程》 唐寧九 游洪躍 朱宏 孫界平 主編</p><p>　　[4]《數(shù)據(jù)結構教程上機實驗指導》 李春堡 北京：清華大學出版社 2005年7月</p><p><b>　　致 謝</b></p><p>　　在本次課程設計的算法設計和編碼過程中得到了老師