數(shù)據(jù)結(jié)構(gòu)課件第3章棧和隊(duì)列

1、第三章第三章 棧和隊(duì)列棧和隊(duì)列【課前思考】【課前思考】1. 什么是線性結(jié)構(gòu)？ 2. 你見(jiàn)過(guò)餐館中一疊一疊的盤子嗎？如果它們是按1,2,n 的次序往上疊的，那么使用時(shí)候的次序應(yīng)是什么樣的？ 3. 在日常生活中，為了維持正常的社會(huì)秩序而出現(xiàn)的常見(jiàn)現(xiàn)象是什么？ 第三章第三章 棧和隊(duì)列棧和隊(duì)列 棧和隊(duì)列與線性表相比，是限定性的線性表結(jié)構(gòu)。 棧的特點(diǎn)：棧必須按“后進(jìn)先出”的規(guī)則進(jìn)行操作隊(duì)列特點(diǎn)：必須按“先進(jìn)先出”的規(guī)則進(jìn)行操作。 插 入 刪 除線性表： Insert (L ,i ,x)Delete (L , i) (1in+1) (1in)棧：Insert (L, n+1 ,x) Delete (L ,

2、 n)隊(duì)列：Insert (L, n+1 ,x) Delete (L ,1) 1. 從“數(shù)據(jù)結(jié)構(gòu)”的角度看，它們都是線性結(jié)構(gòu) 即數(shù)據(jù)元素之間的關(guān)系相同。2. 它們是完全不同的數(shù)據(jù)類型。 除了它們各自的基本操作集不同外， 主要區(qū)別是對(duì)插入和刪除操作的“限定”。如：線性表允許在表內(nèi)任一位置進(jìn)行插入和刪除； 棧只允許在表尾一端進(jìn)行插入和刪除； 隊(duì)列只允許在表尾一端插入，在表頭一端刪除。 棧和隊(duì)列與線性表對(duì)比：第三章第三章 棧和隊(duì)列棧和隊(duì)列3.1 棧棧 3.1.1 棧的類型定義棧的類型定義棧（棧（Stack）是限定只能在表的一端進(jìn)行插入和刪除操作的線性表。允許插入和刪除的一端稱作“棧頂(top)”不允

3、許插入和刪除的另一端稱作棧底(bottom) 通常稱往棧頂插入元素的操作為“入?！?，稱刪除棧頂元素的操作為“出?！?。棧被稱為是一種“后進(jìn)先出”的結(jié)構(gòu)，又稱LIFO（Last In First Out的縮寫(xiě)）表。 如下圖所示的鐵路調(diào)度站 棧的類型定義如下：ADT Stack 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：Dai | ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R1 | ai-1 , ai D, i=2,.,n 約定 an 端為棧頂，a1 端為棧底。基本操作：基本操作： InitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧 S。 DestroyStack(&S)初始條

4、件：棧 S 已存在。操作結(jié)果：棧 S 被銷毀。 ClearStack(&S)初始條件：棧 S 已存在。操作結(jié)果：將 S 清為空棧。StackEmpty(S)初始條件：棧 S 已存在。操作結(jié)果：若棧 S 為空棧，則返回TRUE， 否則 返回FALSE。StackLength(S)初始條件：棧 S 已存在。操作結(jié)果：返回棧 S 中元素個(gè)數(shù)，即棧的長(zhǎng)度 GetTop(S, &e)初始條件：棧 S 已存在且非空。操作結(jié)果：用 e 返回S的棧頂元素。 Push (&S, e)初始條件：棧 S 已存在。操作結(jié)果：插入元素 e 為新的棧頂元素。Pop (&S, &e)

5、初始條件：棧 S 已存在且非空。操作結(jié)果：刪除 S 的棧頂元素，并用 e 返回其值。StackTraverse ( S, visit( ) )初始條件：棧 S 已存在且非空，visit( )為元素的訪問(wèn)函數(shù)。操作結(jié)果：從棧底到棧頂依次對(duì)S的每個(gè)元素調(diào)用函數(shù)visit( )，一旦visit( )失敗，則操作失敗。 ADT Stack 3.1棧棧3.1.2 棧的存儲(chǔ)表示和操作的實(shí)現(xiàn)棧的存儲(chǔ)表示和操作的實(shí)現(xiàn)棧也有兩種存儲(chǔ)表示：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ) 順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序棧鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈棧棧頂指針意為指示棧頂元素在棧中的位置，但它的值實(shí)際是棧中元素的個(gè)數(shù)，和順序表中的 length 值的意義相同。

6、 一、順序棧類型的定義一、順序棧類型的定義 /結(jié)構(gòu)定義：結(jié)構(gòu)定義： typedef struct elemType *base; / 存儲(chǔ)空間基址 int top; / 棧頂指針 int stacksize; / 允許的最大存儲(chǔ)空間以元素為單位 Stack; 3.1棧棧3.1.2 棧的存儲(chǔ)表示和操作的實(shí)現(xiàn)棧的存儲(chǔ)表示和操作的實(shí)現(xiàn)/ 基本操作接口基本操作接口(函數(shù)聲明函數(shù)聲明)：void InitStack (Stack &S，int maxsize); /構(gòu)造一個(gè)最大存儲(chǔ)容量為 maxsize 的空棧S。void DestroyStack (Stack &S);/銷毀棧S，S

7、不再存在。 void ClearStack (Stack &S);/將 S 置為空棧。 bool StackEmpty (Stack S);/若棧 S 為空棧，則返回 TRUE，否則返回 FALSE int StackLength (Stack S);/返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度。 bool GetTop (Stack S, ElemType &e);/若棧不空，則用 e 返回S的棧頂元素，并返回TRUE； /否則返回 FALSE。 bool Push (Stack &S, ElemType e);/若棧的存儲(chǔ)空間不滿，則插入元素 e 為新的棧頂 /元素，并返回 TR

8、UE；否則返回FALSE。 bool Pop (Stack &S, ElemType &e);/若棧不空，則刪除S的棧頂元素，用e返回其值， /并返回TRUE；否則返回FALSE。 void StackTraverse (Stack S, void (*visit(ElemType )/依次對(duì)S的每個(gè)元素調(diào)用函數(shù) visit( )， /一旦 visit( ) 失敗，則操作失敗。 void InitStack (Stack &S，int maxsize)/ 構(gòu)造一個(gè)最大存儲(chǔ)容量為構(gòu)造一個(gè)最大存儲(chǔ)容量為 maxsize 的空棧的空棧 Sif (maxsize = 0)max

9、size = MAXLISTSIZE;S.base = new SElemTypemaxsize;if (!S.base) exit(1); / 存儲(chǔ)分配失敗S.stacksize = maxsize;S.top = 0; / 空棧中元素個(gè)數(shù)為0bool Push (Stack &S, ElemType e) / 若棧的存儲(chǔ)空間不滿，則插入元素若棧的存儲(chǔ)空間不滿，則插入元素 e 為新的棧頂元素，為新的棧頂元素， / 并返回并返回 TRUE；否則返回；否則返回 FALSEif (S.top = S.stacksize) / 棧已滿，無(wú)法進(jìn)行插入 return FALSE;*(S.base

10、 + S.top) = e; / 插入新的元素+S.top;/ 棧頂指針后移return TRUE;在此只給出其中在此只給出其中4個(gè)函數(shù)的定義。個(gè)函數(shù)的定義。 bool GetTop (Stack S, ElemType &e) / 若棧不空，則用若棧不空，則用 e 返回返回S的棧頂元素，返回的棧頂元素，返回TRUE； /否則返回否則返回FALSEif (S.top = 0) return FALSE;e = *(S.base + S.top-1); / 返回非空棧中棧頂元素S.baseS.top-1 return TRUE;bool Pop (Stack &S, ElemTy

11、pe &e) / 若棧不空，則刪除若棧不空，則刪除S的棧頂元素，用的棧頂元素，用 e 返回其值，返回其值， / 并返回并返回 TRUE；否則返回；否則返回 FALSE if (S.top = 0) return FALSE; e = *(S.base + S.top-1); / 返回非空棧中棧頂元素返回非空棧中棧頂元素 -S.top; / 棧頂指針前移棧頂指針前移return TRUE; Pop和 GetTop 不同僅在于多一句移動(dòng)指針的語(yǔ)句。 圖中的順序棧的最大容量為7，當(dāng)前棧中元素個(gè)數(shù)為4，因此，我們也可認(rèn)為棧頂指針總是指在棧頂元素的后面一個(gè)位置上。用圖表示順序棧如下：abcdS.

12、 top S. stacksize 二、鏈棧鏈棧即為棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。結(jié)點(diǎn)結(jié)構(gòu)和單鏈表中的結(jié)點(diǎn)結(jié)構(gòu)相同，鏈棧中不需要頭結(jié)點(diǎn)，但鏈棧中指針的方向是從棧頂指向棧底的，正好和單鏈表是相反的。S. top棧頂棧底3.1棧棧3.1.2 棧的存儲(chǔ)表示和操作的實(shí)現(xiàn)棧的存儲(chǔ)表示和操作的實(shí)現(xiàn)結(jié)構(gòu)定義：結(jié)構(gòu)定義：typedef struct SLink top; / 棧頂指針 int length; / 棧中元素個(gè)數(shù) Stack;只需對(duì)順序棧的基本操作接口作兩處改動(dòng)，便可作為鏈棧的基本操作接口。 其一：初始化時(shí)不需要“maxsize”的參數(shù)，因?yàn)樗恍枰?先分配空間其二：在進(jìn)行入棧操作時(shí)，不需要顧忌棧的空間是否

13、已 經(jīng)被填滿 鏈棧的基本操作鏈棧的基本操作void InitStack ( Stack &S ) / 構(gòu)造一個(gè)空棧構(gòu)造一個(gè)空棧 SS.top = NULL; / 設(shè)棧頂指針的初值為空 S.length = 0; / 空棧中元素個(gè)數(shù)為0 / InitStackvoid Push ( Stack &S, ElemType e )/ 在棧頂之上插入元素在棧頂之上插入元素 e 為新的棧頂元素為新的棧頂元素p = new LNode; / 建新的結(jié)點(diǎn)建新的結(jié)點(diǎn)if(!p) exit(1);/ 存儲(chǔ)分配失敗存儲(chǔ)分配失敗p - data = e;p - next = S.top;/ 鏈接到原

14、來(lái)的棧頂鏈接到原來(lái)的棧頂S.top = p; / 移動(dòng)棧頂指針移動(dòng)棧頂指針+S.length; / 棧的長(zhǎng)度增棧的長(zhǎng)度增1 / Pushbool Pop ( Stack &S, SElemType &e ) / 若棧不空，則刪除若棧不空，則刪除S的棧頂元素，用的棧頂元素，用 e 返回其值，返回其值，/ 并返回并返回 TRUE；否則返回；否則返回 FALSEif ( !S.top )return FALSE; else e = S.top - data; / 返回棧頂元素 q = S.top; S.top = S.top - next;/ 修改棧頂指針 -S.length; /

15、棧的長(zhǎng)度減1 delete q; / 釋放被刪除的結(jié)點(diǎn)空間 return TRUE; / Pop 3.2 棧的應(yīng)用舉例 3.2.1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換 十進(jìn)制數(shù)N和其他d進(jìn)制數(shù)的轉(zhuǎn)換，解決方法很多，其中一個(gè)簡(jiǎn)單算法基于下列原理：N = (N div d)d + N mod d (其中：div 為整除運(yùn)算，mod 為求余運(yùn)算)例如：(1348)10 = (2504)8 1348881684218820052計(jì)算過(guò)程輸出順序假設(shè)現(xiàn)要編制一個(gè)滿足下列要求的程序： 對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù)。問(wèn)題分析： 問(wèn)題很明確，就是要輸出計(jì)算過(guò)程中所得到的各個(gè)八進(jìn)制數(shù)位。然而從計(jì)算

16、過(guò)程可見(jiàn)，這八進(jìn)制的各個(gè)數(shù)位產(chǎn)生的順序是從低位到高位的，而打印輸出的順序從高位到低位，這恰好和計(jì)算過(guò)程相反。 因此，需要先保存在計(jì)算過(guò)程中得到的八進(jìn)制數(shù)的各位，然后逆序輸出，因?yàn)樗前春筮M(jìn)先出的規(guī)律進(jìn)行的，所以用棧最合適。 算法算法 3.1void conversion ( )/對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù),輸出與其等值的八進(jìn)制數(shù)輸出與其等值的八進(jìn)制數(shù)InitStack(S); / 構(gòu)造空棧cin N;/ 輸入一個(gè)十進(jìn)制數(shù)while(N)Push( S ,N % 8);/ 余數(shù)入棧N = N/8;/ 非零商繼續(xù)運(yùn)算 / whilewhile (!StackE

17、mpty) / 和“求余”所得相逆的順序輸出八進(jìn)制的各位數(shù) Pop(S , e);cout e; / while / conversion3.2.2 括弧匹配檢驗(yàn)括弧匹配檢驗(yàn) 假設(shè)表達(dá)式中允許包含兩種括號(hào)：圓括號(hào)和方括號(hào)其正確的匹配：如（ （）或（ ）等 錯(cuò)誤的匹配：（ ）或（ （ ）或 ( ( ) ) ）等 現(xiàn)在的問(wèn)題是，要求檢驗(yàn)一個(gè)給定表達(dá)式中的括弧是否正確匹配？問(wèn)題分析： 方法可用“期待的急迫程度”這個(gè)概念來(lái)描述。即后出現(xiàn)的“左括弧”，它等待與其匹配的“右括弧”出現(xiàn)的“急迫”心情要比先出現(xiàn)的左括弧高。即： 對(duì)“左括弧”來(lái)說(shuō)，后出現(xiàn)的比先出現(xiàn)的“優(yōu)先”等待檢。 對(duì)“右括弧”來(lái)說(shuō)，每個(gè)出現(xiàn)的

18、右括弧要去找在它之前“最后”出現(xiàn)的那個(gè)左括弧去匹配。 顯然，保存左括弧的結(jié)構(gòu)用棧最合適。例如考慮下列括號(hào)序列： ( ) 1 2 3 4 5 6 7 8上面列舉的三種錯(cuò)誤匹配從“期待匹配”的角度描述即為：1來(lái)的右括弧非是所“期待”的；2來(lái)的是“不速之客”；3直到結(jié)束，也沒(méi)有到來(lái)所“期待”的。這三種情況對(duì)應(yīng)到棧的操作即為：1和棧頂?shù)淖罄ɑ〔幌嗥ヅ洌?棧中并沒(méi)有左括弧等在哪里；3棧中還有左括弧沒(méi)有等到和它相匹配的右括弧。（自練習(xí)寫(xiě)算法） 3.2.3 迷宮求解問(wèn)題 計(jì)算機(jī)解迷宮時(shí)，通常用的是窮舉求解窮舉求解的方法 什么是迷宮問(wèn)題？ 先看兩個(gè)動(dòng)畫(huà)演示的例子（flash3-3-1; 3-3-2） 問(wèn)題分析

19、：1從入口進(jìn)入迷宮之后，不管在迷宮的哪一個(gè)位置上，都是先往東走，如果走得通就繼續(xù)往東走，如果在某個(gè)位置上往東走不通的話，就依次試探往南、往西和往北方向，從一個(gè)走得通的方向繼續(xù)往前直到出口為止； 2如果在某個(gè)位置上四個(gè)方向都走不通的話，就退回到前一個(gè)位置，換一個(gè)方向再試，如果這個(gè)位置已經(jīng)沒(méi)有方向可試了就再退一步，如果所有已經(jīng)走過(guò)的位置的四個(gè)方向都試探過(guò)了，一直退到起始點(diǎn)都沒(méi)有走通，那就說(shuō)明這個(gè)迷宮根本不通； 3所謂走不通不單是指遇到墻擋路，還有已經(jīng)走過(guò)的路不能重復(fù)走第二次，它包括曾經(jīng)走過(guò)而沒(méi)有走通的路。 顯然為了保證在任何位置上都能沿原路退回，需要用需要用一個(gè)一個(gè)“后進(jìn)先出后進(jìn)先出”的結(jié)構(gòu)即棧來(lái)

20、保存從入口到當(dāng)前位置的的結(jié)構(gòu)即棧來(lái)保存從入口到當(dāng)前位置的路徑路徑。并且在走出出口之后，棧中保存的正是一條從入口到出口的路徑。 求迷宮中一條路徑的算法的基本思想基本思想是： 若若當(dāng)前位置當(dāng)前位置“可通可通”， 則則納入納入“當(dāng)前路徑當(dāng)前路徑”，并繼續(xù)朝，并繼續(xù)朝“下一位置下一位置”探索；探索； 若若當(dāng)前位置當(dāng)前位置“不可通不可通”， 則則應(yīng)順著應(yīng)順著“來(lái)的方向來(lái)的方向”退回到退回到“前一通道塊前一通道塊”， 然后朝然后朝 著除著除“來(lái)向來(lái)向”之外的其他方向繼續(xù)探索；之外的其他方向繼續(xù)探索； 若若該通道塊的四周四個(gè)方塊均該通道塊的四周四個(gè)方塊均“不可通不可通”， 則則應(yīng)從應(yīng)從當(dāng)前路徑當(dāng)前路徑上刪除

21、該通道塊。上刪除該通道塊。 假設(shè)以棧棧S記錄記錄“當(dāng)前路徑當(dāng)前路徑”，則棧頂棧頂中存放的是存放的是“當(dāng)當(dāng)前路徑上前路徑上最后一個(gè)最后一個(gè)通道塊通道塊”。“納入路徑納入路徑”的操作即為的操作即為“當(dāng)前位置入棧當(dāng)前位置入?！?；從當(dāng)前路徑上刪除前一通道塊從當(dāng)前路徑上刪除前一通道塊的操作即為的操作即為出棧出棧。 求迷宮中一條從入口到出口的路徑的偽碼算法如下：設(shè)定當(dāng)前位置的初值為入口位置；do 若若當(dāng)前位置可通， 則則將當(dāng)前位置插入棧頂； / 納入路徑 若若該位置是出口位置，則則算法結(jié)束； / 此時(shí)棧中存放的是一條從入口位置到出口位置的路徑否則否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置； 否則否則 若若棧

22、不空且棧頂位置尚有其他方向未被探索，則則設(shè)定新的當(dāng)前位置為: 沿順時(shí)針?lè)较蛐D(zhuǎn)找到的棧頂位置的下一相鄰塊；若若棧不空但棧頂位置的四周均不可通， 則則 刪去棧頂位置； / 從路徑中刪去該通道塊若若棧不空，則則重新測(cè)試新的棧頂位置，直至直至找到一個(gè)可通的相鄰塊或出棧至?？?； while (棧不空棧不空)； 3.2.4 表達(dá)式求值問(wèn)題表達(dá)式求值問(wèn)題 任何一個(gè)表達(dá)式都是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成。 其中 操作數(shù)：常數(shù)、標(biāo)識(shí)符 運(yùn)算符：算術(shù)運(yùn)算符、關(guān)系運(yùn)算符和邏輯運(yùn)算符 基本界限符：左右括弧、表達(dá)式結(jié)束符等 以簡(jiǎn)單的二元運(yùn)算符的算術(shù)表達(dá)式 二

23、元表達(dá)式： 操作數(shù)1 （S1）操作符（OP）操作數(shù)2 （S2）其中：操作數(shù)可以是簡(jiǎn)單變量，也可以是表達(dá)式； 而簡(jiǎn)單變量可以是標(biāo)識(shí)符，也可以是無(wú)符號(hào)整數(shù)。 問(wèn)題分析： 由于算術(shù)運(yùn)算的規(guī)則是：先乘除后加減、先左后右和先括弧內(nèi)后括弧外，不按其中運(yùn)算符出現(xiàn)的先后次序。那么怎么辦？其中一個(gè)方法是先將它轉(zhuǎn)換成另一種形式。 在計(jì)算機(jī)中，對(duì)這種二元表達(dá)式可以有三種不同的標(biāo)識(shí)方法。假設(shè) Exp = S1 + OP + S2則稱 OP + S1 + S2 為表達(dá)式的前綴表示法前綴表示法（簡(jiǎn)稱前綴式前綴式）稱 S1 + OP + S2 為表達(dá)式的中綴表示法中綴表示法（簡(jiǎn)稱中綴式中綴式）稱 S1 + S2 + OP

24、為表達(dá)式的后綴表示法后綴表示法（簡(jiǎn)稱后綴式后綴式） 例如：若 則它的前綴式為： 中綴式為： 后綴式為： 綜合比較它們之間的關(guān)系可得下列結(jié)論：1三式中的 “操作數(shù)操作數(shù)之間的相對(duì)次序相同之間的相對(duì)次序相同”；2三式中的 “運(yùn)算符運(yùn)算符之間的的相對(duì)次序不同之間的的相對(duì)次序不同”；3中綴式丟失了括弧信息，致使運(yùn)算的次序不確定；4前綴前綴式的運(yùn)算規(guī)則式的運(yùn)算規(guī)則為：連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小表達(dá)式；它們之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小表達(dá)式；5后綴后綴式的運(yùn)算規(guī)則式的運(yùn)算規(guī)則為：運(yùn)算符運(yùn)算符在式中出現(xiàn)的順序恰為表達(dá)式的運(yùn)算順序；在式中出現(xiàn)的

25、順序恰為表達(dá)式的運(yùn)算順序；每個(gè)運(yùn)算符和在它之前出現(xiàn)且緊靠它的兩個(gè)操作數(shù)每個(gè)運(yùn)算符和在它之前出現(xiàn)且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式；構(gòu)成一個(gè)最小表達(dá)式；以下就分如何按后綴式進(jìn)行運(yùn)算和如何將原表達(dá)式轉(zhuǎn)換成后綴式兩個(gè)問(wèn)題進(jìn)行討論。 如何按后綴式進(jìn)行運(yùn)算？“先找運(yùn)算符，后找操作數(shù)?！?如：后綴式參看動(dòng)畫(huà)flash3-3-5運(yùn)算過(guò)程為： 對(duì)后綴式從左向右“掃描”，遇見(jiàn)操作數(shù)則暫時(shí)保存，遇見(jiàn)運(yùn)算符即可進(jìn)行運(yùn)算；此時(shí)參加運(yùn)算的兩個(gè)操作數(shù)應(yīng)該是在它之前剛剛碰到的兩個(gè)操作數(shù)，并且先出現(xiàn)的是第一操作數(shù)，后出現(xiàn)的是第二操作數(shù)。 由此可見(jiàn)，在運(yùn)算過(guò)程中保存操作數(shù)的結(jié)構(gòu)應(yīng)該是個(gè)棧。 如何由原表達(dá)式轉(zhuǎn)換成后綴式？先分

26、析一下原表達(dá)式和后綴式兩者中運(yùn)算符出現(xiàn)的次序有什么不同。 例一例一原表達(dá)式： 后綴式： 例二例二原表達(dá)式： 后綴式： 先分析一下原表達(dá)式和后綴式兩者中運(yùn)算符出現(xiàn)的次序有什么不同。 例一例一原表達(dá)式： 后綴式： 例二例二原表達(dá)式： 后綴式： 給每個(gè)運(yùn)算符賦以一個(gè)優(yōu)先數(shù)的值，如下所列：運(yùn)算符 優(yōu)先數(shù) 優(yōu)先數(shù)高的優(yōu)先于優(yōu)先數(shù)低的進(jìn)行運(yùn)算 顯然，保存運(yùn)算符的結(jié)構(gòu)應(yīng)該是個(gè)棧，從棧底到棧頂?shù)倪\(yùn)算符的優(yōu)先數(shù)是從低到高的，因此它們運(yùn)算的先后應(yīng)是從棧頂?shù)綏５椎摹?因此，從原表達(dá)式求得后綴式的規(guī)則為： 1) 設(shè)立運(yùn)算符棧棧；2) 設(shè)表達(dá)式的結(jié)束符為“#”，為棧底；3) 若當(dāng)前字符是操作數(shù)，則直接發(fā)送給后綴式；4)

27、 若當(dāng)前字符為運(yùn)算符且優(yōu)先數(shù)大于棧頂運(yùn)算符，則進(jìn)棧，否則退出棧頂運(yùn)算符發(fā)送給后綴式；5) 若當(dāng)前字符是結(jié)束符，則自棧頂至棧底依次將棧中所有運(yùn)算符發(fā)送給后綴式；6) “(”對(duì)它之前后的運(yùn)算符起隔離作用，則若當(dāng)前運(yùn)算符為“(”時(shí)進(jìn)棧；7) )可視為自相應(yīng)左括弧開(kāi)始的表達(dá)式的結(jié)束符，則從棧頂起，依次退出棧頂運(yùn)算符發(fā)送給后綴式直至棧頂字符為(止。算法算法3.2void transform (char suffix, char exp ) / 從合法的表達(dá)式字符串從合法的表達(dá)式字符串 exp 求得其相應(yīng)的后綴式求得其相應(yīng)的后綴式 suffixInitStack (S); Push (S, # );p =

28、 exp; ch = *p;while (!StackEmpty(S) if (! IN(ch, OP) Pass( suffix, ch);/ 直接發(fā)送給后綴式else switch (ch) case ( : Push(S, ch); break; case ) : Pop(S, c);while (c!= ( ) Pass( suffix, c); Pop(S, c) break; defult : while (!Gettop(S, c) & ( precede(c,ch) Pass( suffix, c); Pop(S, c); if ( ch!= # ) Push( S,

29、ch); break; / defult / switch / elseif ( ch!= # ) p+; ch = *p; / while / transform 算法的時(shí)間復(fù)雜度為O (n)，其中 n 為表達(dá)式字符串的長(zhǎng)度。 3.2.5 遞歸函數(shù)的實(shí)現(xiàn) 當(dāng)一個(gè)函數(shù)在運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行該被調(diào)用函數(shù)之前，需先完成三件事： 1) 將所有的實(shí)在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存； 2) 為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū)； 3) 將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。而從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成： 1) 保存被調(diào)函數(shù)的計(jì)算結(jié)果； 2) 釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)； 3) 依照被調(diào)函

30、數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。 當(dāng)多個(gè)函數(shù)嵌套調(diào)用時(shí)，由于函數(shù)的運(yùn)行規(guī)則是：后調(diào)用先返回，因此各函數(shù)占有的存儲(chǔ)管理應(yīng)實(shí)行棧式管理?xiàng)Ｊ焦芾怼?假設(shè)主函數(shù)調(diào)用函數(shù)A，函數(shù)A又調(diào)用函數(shù)B，顯然，在函數(shù)B運(yùn)行期間主函數(shù)和函數(shù)A占用的存儲(chǔ)都不能被覆蓋，反之，當(dāng)函數(shù)B運(yùn)行結(jié)束，它所占用的存儲(chǔ)區(qū)便可釋放，同時(shí)因?yàn)槌绦蚩刂妻D(zhuǎn)移到函數(shù)A，當(dāng)前程序訪問(wèn)的數(shù)據(jù)自然就是函數(shù)A占用的存儲(chǔ)區(qū)了。 遞歸函數(shù): 類似于多個(gè)函數(shù)的嵌套調(diào)用，差別僅在于調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個(gè)函數(shù)。 遞歸工作棧:遞歸過(guò)程執(zhí)行過(guò)程中所占用的數(shù)據(jù)區(qū)遞歸工作記錄:每一層的遞歸參數(shù)等數(shù)據(jù)合成一個(gè)記錄當(dāng)前活動(dòng)記錄:棧頂記錄指示當(dāng)前層的執(zhí)行情況當(dāng)

31、前環(huán)境指針:遞歸工作棧的棧頂指針 以大家熟悉的 hanoi塔問(wèn)題為例，來(lái)看一下棧是如何實(shí)現(xiàn)遞歸函數(shù)的問(wèn)題描述: 教材p55-例3-2 動(dòng)畫(huà)演示看 flash 3-3-9總結(jié)：實(shí)現(xiàn)步驟1.先將x 盤上的n-1個(gè)編號(hào)從小到大的盤子借助y盤移動(dòng)到z盤2.將x 盤上的n號(hào)盤移動(dòng)到z盤3.將y盤上的n-1個(gè)編號(hào)從小到大的盤子借助x盤移動(dòng)到z盤（1次遞歸調(diào)用）算法算法3.3void hanoi (int n, char x, char y, char z, int &i )/ 將塔座將塔座 x 上按直徑由小到大且至上而下編號(hào)為上按直徑由小到大且至上而下編號(hào)為1至至 n/ 的的 n 個(gè)圓盤按規(guī)則搬到

32、塔座個(gè)圓盤按規(guī)則搬到塔座 z 上，上，y 可用作輔助塔座?？捎米鬏o助塔座。if (n=1) move(x, 1, z); / 將編號(hào)為1的圓盤從 x 移到 zi+; else hanoi(n-1, x, z, y); / 將 x 上編號(hào)為1至 n-1 的圓盤移到 y,z 作輔助塔move(x, n, z); / 將編號(hào)為 n 的圓盤從 x 移到 z i+; hanoi(n-1, y, x, z); / 將 y 上編號(hào)為1至 n-1 的圓盤移到 z,x 作輔助塔 3.3 隊(duì)列 3.3.1 隊(duì)列的類型定義隊(duì)列的類型定義 隊(duì)列（隊(duì)列（Queue）是限定只能在表的一端進(jìn)行插入和在另一端進(jìn)行刪除操作的線

33、性表。允許插入的一端稱作“隊(duì)列尾(tail)”，允許刪除的另一端稱作隊(duì)列頭(front)。 隊(duì)列的修改是依先進(jìn)先出的原則進(jìn)行的，因此隊(duì)列又稱FIFO（First In First Out 的縮寫(xiě)）表 其類型定義如下：ADT Queue 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象：Dai|aiElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系：R1 |, ai , ai+1 D, i=2,.,n 約定其中a1端為隊(duì)列頭,an 端為隊(duì)列尾。 基本操作基本操作： InitQueue(&Q) 操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列 Q。 DestroyQueue(&Q) 初始條件：隊(duì)列 Q 已存在。 操作結(jié)果：隊(duì)

34、列 Q 被銷毀，不再存在。 ClearQueue(&Q) 初始條件：隊(duì)列 Q 已存在。 操作結(jié)果：將 Q 清為空隊(duì)列。 QueueEmpty(Q)初始條件：隊(duì)列 Q 已存在。操作結(jié)果：若 Q 為空隊(duì)列，則返回TRUE， 否則返回FALSE。 QueueLength(Q)初始條件：隊(duì)列 Q 已存在。 操作結(jié)果：返回 Q 的元素個(gè)數(shù)，即隊(duì)列的長(zhǎng)度。GetHead(Q,&e)初始條件：Q 為非空隊(duì)列。操作結(jié)果：用 e 返回Q的隊(duì)頭元素。EnQueue(&Q,e) 初始條件：隊(duì)列 Q 已存在。操作結(jié)果：插入元素 e 為 Q 的新的隊(duì)尾元素。DeQueue(&Q,&

35、;e)初始條件：Q 為非空隊(duì)列。操作結(jié)果：刪除 Q 的隊(duì)頭元素，并用 e 返回其值。QueueTraverse(Q,visit( )初始條件：隊(duì)列 Q 已存在且非空， visit( )為元素的訪問(wèn)函數(shù)。操作結(jié)果：依次對(duì) Q 的每個(gè)元素調(diào)用函數(shù) visit( )，一旦 visit( ) 失敗則操作失敗。 ADT Queue 3.3.2 隊(duì)列的存儲(chǔ)表示和操作的實(shí)現(xiàn)隊(duì)列的存儲(chǔ)表示和操作的實(shí)現(xiàn)隊(duì)列也有兩種存儲(chǔ)表示方法：鏈?zhǔn)?、順?一、鏈隊(duì)列一、鏈隊(duì)列鏈隊(duì)列是隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，其結(jié)構(gòu)示意圖如下：附加一個(gè) 頭結(jié)點(diǎn)，指針?lè)较蚝途€性表一致，“隊(duì)尾指針(Q.rear)”，指向鏈隊(duì)列中的隊(duì)尾元素結(jié)點(diǎn)，“隊(duì)頭指針

36、(Q.front)”，指向鏈表的頭結(jié)點(diǎn)，空隊(duì)列中只含一個(gè)其指針域?yàn)榭盏念^結(jié)點(diǎn)，并且頭、尾指針都指向頭結(jié)點(diǎn)而不為空。 鏈隊(duì)列的類型定義：/ 結(jié)構(gòu)定義結(jié)構(gòu)定義typedef SLink QueuePtr; / 鏈隊(duì)列的結(jié)點(diǎn)結(jié)構(gòu)和單鏈表相同typedef structQueuePtr front; / 隊(duì)列的頭指針QueuePtr rear; / 隊(duì)列的尾指針int length; / 隊(duì)列元素個(gè)數(shù) Queue; / 鏈隊(duì)列/ 基本操作接口（函數(shù)聲明）基本操作接口（函數(shù)聲明）void InitQueue (Queue &Q); /構(gòu)造一個(gè)空隊(duì)列 Q void DestroyQueue (Qu

37、eue &Q); /銷毀隊(duì)列Q，Q 不再存在void ClearQueue (Queue &Q); /將 Q 置為空隊(duì)列 bool QueueEmpty (Queue Q); /若隊(duì)列 Q 為空隊(duì)列，則返回TRUE，否則返回FALSE int QueueLength (Queue Q); /返回隊(duì)列 Q 中元素個(gè)數(shù)，即隊(duì)列的長(zhǎng)度 bool GetHead (Queue Q, ElemType &e); /若隊(duì)列不空，則用 e 返回Q的隊(duì)列頭元素， /并返回TRUE；否則返回FALSE void EnQueue (Queue &Q, ElemType e); /在

38、當(dāng)前隊(duì)列的尾元素之后插入元素 e 為新隊(duì)列尾元素bool DeQueue (Queue &Q, ElemType &e); /若隊(duì)列不空，則刪除當(dāng)前隊(duì)列Q中的頭元素，/用 e 返回其值，并返回TRUE；否則返回 FALSE void QueueTraverse (Queue Q, void (*visit(ElemType )/依次對(duì)Q的每個(gè)元素調(diào)用函數(shù)visit( )， /一旦visit( )失敗，則操作失敗。 void InitQueue (Queue &Q) / 構(gòu)造一個(gè)空隊(duì)列構(gòu)造一個(gè)空隊(duì)列 Q Q.front=Q.rear=new LNode; if (!Q.f

39、ront) exit(1);/ 存儲(chǔ)分配失敗Q.front-next=NULL; Q.length=0; void EnQueue (Queue &Q,ElemType e) / 在當(dāng)前隊(duì)列的尾元素之后插入元素在當(dāng)前隊(duì)列的尾元素之后插入元素 e 為新隊(duì)列尾元素為新隊(duì)列尾元素s = new LNode; if (!s) exit(1);/ 存儲(chǔ)分配失敗 s-data=e; s-next = NULL;Q.rear-next=s;/ 修改尾結(jié)點(diǎn)的指針Q.rear=s; / 移動(dòng)隊(duì)尾指針+Q.length; / 隊(duì)列長(zhǎng)度增1bool DeQueue (Queue &Q, ElemTy

40、pe &e) / 若隊(duì)列不空，則刪除當(dāng)前隊(duì)列若隊(duì)列不空，則刪除當(dāng)前隊(duì)列 Q 中的頭元素，中的頭元素， /用用 e 返回其值，并返回返回其值，并返回 TRUE；否則返回；否則返回 FALSE if ( Q.front = Q.rear ) / 鏈隊(duì)列中只有一個(gè)頭結(jié)點(diǎn)return FALSE; p = Q.front-next; e = p-data;/ 返回被刪元素Q.front-next=p-next; / 修改頭結(jié)點(diǎn)指針if(Q.rear = p) Q.rear = Q.front;delete p;/ 釋放被刪結(jié)點(diǎn)return TRUE; / DeQueue鏈隊(duì)列的基本操作的時(shí)間復(fù)

41、雜度，除遍歷之外，都是常量級(jí)的。 二、循環(huán)隊(duì)列 循環(huán)隊(duì)列是隊(duì)列的一種順序存儲(chǔ)表示。 循環(huán)隊(duì)列的一種模擬參看動(dòng)畫(huà)flash3-3-13 利用順序分配存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)隊(duì)列時(shí)，用一維數(shù)組描述隊(duì)列中數(shù)據(jù)元素的存儲(chǔ)區(qū)域， 設(shè)立兩個(gè)指針 front 隊(duì)頭和 rear 隊(duì)尾假設(shè)又有兩個(gè)元素 f 和 g 相繼入隊(duì)列，而隊(duì)列中的元素 b 和 c 又相繼出隊(duì)列。致使下一個(gè)入隊(duì)操作無(wú)法進(jìn)行(請(qǐng)注意此時(shí)隊(duì)列空間并未滿)。為此，設(shè)想這個(gè)數(shù)組的存儲(chǔ)空間是個(gè)環(huán)，認(rèn)定7的下一個(gè)位置是0。如下圖所示。循環(huán)隊(duì)列的結(jié)構(gòu)定義如下：typedef struct ElemType *elem;/ 存儲(chǔ)空間基址int rear; / 隊(duì)尾指針

42、int front;/ 隊(duì)頭指針int queuesize;/ 允許的最大存儲(chǔ)空間，以元素為單位 Queue; 以下是循環(huán)隊(duì)列的主要操作的函數(shù)定義 void InitQueue (Queue &Q，int maxsize ) / 構(gòu)造一個(gè)最大存儲(chǔ)空間為構(gòu)造一個(gè)最大存儲(chǔ)空間為 maxsize 的空隊(duì)列的空隊(duì)列 Q if (maxsize = 0) maxsize = MAXLISTSIZE;Q.elem = new ElemTypemaxsize; / 為循環(huán)隊(duì)列分配存儲(chǔ)空間if (!Q.elem) exit(1);/ 存儲(chǔ)分配失敗Q.queuesize = maxsize; Q.fro

43、nt = Q.rear = 0; / InitQueue bool DeQueue (Queue &Q, ElemType &e)/ 若隊(duì)列不空，則刪除當(dāng)前隊(duì)列若隊(duì)列不空，則刪除當(dāng)前隊(duì)列Q中的頭元素，用中的頭元素，用 e 返回其值返回其值/ 并返回并返回TRUE；否則返回；否則返回 FALSEif (Q.front = Q.rear)return FALSE; e = Q.elemQ.front;Q.front = (Q.front+1) % Q.queuesize;return TRUE; bool EnQueue (Queue &Q,ElemType e)/ 若當(dāng)前隊(duì)列不滿，這在當(dāng)前隊(duì)列的尾元素之后，若當(dāng)前隊(duì)列不滿，這在當(dāng)前隊(duì)列的尾元素之后，/ 插入元素插入元素 e 為新的隊(duì)列尾元素為新的隊(duì)列尾元素,并返回并返回TRUE,否則返回否則返回FALSEif (Q.rear + 1) % Q.queuesize = Q.front ) return FALSE;Q. elemQ.rear = e;Q .rear = (Q.rear+1) % Q.queuesize;return TRUE; int QueueLength (Queue Q)/ 返回隊(duì)列返回隊(duì)列Q中元素個(gè)數(shù)，即隊(duì)列的長(zhǎng)度中元素個(gè)數(shù)，