數(shù)據(jù)結構棧學習教案

1、會計學1數(shù)據(jù)結構數(shù)據(jù)結構(sh j ji u)棧棧第一頁，共30頁。2第1頁/共30頁第二頁，共30頁。3邏輯(lu j)結構分析(fnx) 運算實現(xiàn)（算法） 運算定義 存儲結構數(shù)據(jù)結構的組成第2頁/共30頁第三頁，共30頁。4 an an-1 a1入棧(PUSH) 出棧(POP) 棧頂(top)棧底(bottom)邏輯結構(jigu)和運算a1 a2 an 特性：后進先出 ( LIFO )-Last in First out a1a2anana2a1第3頁/共30頁第四頁，共30頁。5運算(yn sun)定義第4頁/共30頁第五頁，共30頁。6 ;運算描述(mio sh)部分數(shù)據(jù)描述部分類的

2、名稱類的框架第5頁/共30頁第六頁，共30頁。7棧的C+類描述(mio sh)： class stack stack(); 棧的數(shù)據(jù)成員 ;棧的運算(1)初始化 ：設置棧為空。 (2)判斷棧為空： 若為空，則返回TRUE，否則返回FALSE. (3)判斷棧為滿： 若為滿，則返回TRUE，否則返回FALSE. (4)取棧頂元素：取出棧頂元素。 條件：棧不空。 否則，應能明確給出標識，以便程序的處理。(5)入棧：將元素入棧，即放到棧頂。 如果棧滿，怎樣處理？ (6)出棧：刪除當前棧頂?shù)脑亍?如因為?？斩荒苓M行，應怎樣處理？ 采用C+的構造函數(shù)第6頁/共30頁第七頁，共30頁。8棧的C+類描述：

3、class stack stack(); Bool empty() Bool full() 棧的數(shù)據(jù)(shj)成員;棧的運算(1)初始化 ：設置棧為空。 (2)判斷棧為空： 若為空，則返回TRUE，否則返回FALSE. (3)判斷棧為滿： 若為滿，則返回TRUE，否則返回FALSE. (4)取棧頂元素：取出棧頂元素。 條件：棧不空。 否則，應能明確給出標識，以便程序的處理。(5)入棧：將元素入棧，即放到棧頂。 如果棧滿，怎樣處理？ (6)出棧：刪除當前棧頂?shù)脑亍?如因為?？斩荒苓M行，應怎樣處理？判斷為空的函數(shù)判斷為滿的函數(shù)const;const;第7頁/共30頁第八頁，共30頁。9第8頁/

4、共30頁第九頁，共30頁。10由上述討論可得到其他幾個函數(shù)的功能描述(mio sh)：（4)取棧頂元素的運算功能描述(mio sh)： 如果棧不空，則取出棧頂元素到參數(shù)x中，然后返回success。 否則，返回downflow。 對應的運算函數(shù)為： error_code get_top(elementtype &x) const;(5)入棧的運算功能描述(mio sh)： 如果棧不滿，則將元素入棧，并返回success。 否則，返回overflow。 對應的運算函數(shù)為： error_code push(const elementtype x); 第9頁/共30頁第十頁，共30頁。11第

5、10頁/共30頁第十一頁，共30頁。12第11頁/共30頁第十二頁，共30頁。13棧的存儲(cn ch)結構a1a2an01n-1maxlenndatacount順序棧存儲結構第12頁/共30頁第十三頁，共30頁。14這是起什么(shn me)作用的？作用是什么？第13頁/共30頁第十四頁，共30頁。15a1a2an01n-1maxlenndatacount第14頁/共30頁第十五頁，共30頁。16a1a2an01n-1maxlenndatacount第15頁/共30頁第十六頁，共30頁。17a1a2an01n-1maxlenndatacount第16頁/共30頁第十七頁，共30頁。18a1a

6、2an01n-1maxlenndatacount第17頁/共30頁第十八頁，共30頁。19a1a2an01n-1maxlenndatacount第18頁/共30頁第十九頁，共30頁。20n符運算n結果壓入數(shù)字棧；n轉(zhuǎn)向2）第19頁/共30頁第二十頁，共30頁。21#12+5*(2+3)*6/2-4# 開始時，指向第一個位置，準備(zhnbi)讀入，此時的兩個棧均為空。CurrentS=# #12+5*(2+3)*6/2-4# CurrentS=12 由于#是第一個算符，因而自動進棧。讀到操作數(shù)（12）自動進棧。12#第20頁/共30頁第二十一頁，共30頁。22棧頂算符#比當前(dngqin)運

7、算符優(yōu)先級低，故算符要入棧#12+5*(2+3)*6/2-4# #12+#12+5*(2+3)*6/2-4# CurrentS= 依次(yc)讀入5、（、2和后，棧頂算符（比當前算符優(yōu)先級低，故要入棧+#12CurrentS= 52X(3+第21頁/共30頁第二十二頁，共30頁。23#12+5*(2+3)*6/2-4# CurrentS= ) (X+#512棧頂算符比當前(dngqin)運算符）優(yōu)先級高，故要執(zhí)行其運算2+3并入棧#12+5*(2+3)*6/2-4# CurrentS= ) X+#512棧頂算符（與當前運算符）相對應，故要出棧，一同(ytng)釋放32+5(第22頁/共30頁第

8、二十三頁，共30頁。24#12+5*(2+3)*6/2-4# CurrentS=X +#12棧頂算符比當前運算(yn sun)符優(yōu)先運算(yn sun)，故要執(zhí)行運算(yn sun)5*5并入棧#12+5*(2+3)*6/2-4# CurrentS=X +#12棧頂算符比當前(dngqin)運算符優(yōu)先級低，故要入棧X5525X6第23頁/共30頁第二十四頁，共30頁。25#12+5*(2+3)*6/2-4# CurrentS=/ +#12棧頂算符比當前運算符/優(yōu)先運算，故要執(zhí)行(zhxng)運算25*6并入棧#12+5*(2+3)*6/2-4# CurrentS=- +#12棧頂算符/比當前運算(yn sun)符優(yōu)先級高，故要執(zhí)行/運算(yn sun)150/2并入棧X625/1502#12+5*(2+3)*6/2-4# CurrentS=- #12棧頂算符比當前運算符優(yōu)先，故執(zhí)行運算12+75并入棧75+第24頁/共30頁第二十五頁，共30頁。26#12+5*(2+3)*6/2-4# CurrentS=# #87棧頂算符比當前運算符優(yōu)先級高，故要執(zhí)行(zhxng)運算87-4并入棧#12+5*(2+3)*6/2-4# CurrentS=# #83棧頂算符與當前運算符相對(xin