堆疊簡介 遞迴 佇列 算術運算式的表示法 中序轉換為前序或後序 前序與後序轉換成中序

Presentation on theme: "堆疊簡介 遞迴 佇列 算術運算式的表示法 中序轉換為前序或後序 前序與後序轉換成中序"— Presentation transcript:

1 堆疊簡介 遞迴 佇列 算術運算式的表示法 中序轉換為前序或後序 前序與後序轉換成中序
第4章 堆疊與佇列 堆疊簡介 遞迴 佇列 算術運算式的表示法 中序轉換為前序或後序 前序與後序轉換成中序

2 堆疊簡介 4-1 堆疊簡介 最簡單的定義如下： 堆疊是一種具有後進先出(LIFO)特性的資料型態，所有的加入與刪除動作，皆在頂端完成。

3 堆疊的應用 1.遞迴程式的呼叫返迴：在遞迴之前，先將下一個指令的位址及變數的值保存到堆疊。
4-1 堆疊簡介 1.遞迴程式的呼叫返迴：在遞迴之前，先將下一個指令的位址及變數的值保存到堆疊。 2.二元樹的中序追蹤(Inorder)、前序追蹤(Preorder)和圖形的深入追蹤(DFS)。 3.CPU的中斷處理(Interrupt Handling)也需要堆疊的支援。 4.將算術式的中序法轉換成後序法。 5.副程式間的呼叫及返回(Subroutine Call and Return)。 6.某些所謂堆疊計算機(Stack Computer)，大部分透過彈出(Pop)及壓入(Push)兩個指令來處理程式。

4 堆疊基本運算與實作(1) 4-1 堆疊簡介 由於堆疊是一種抽象型資料結構(Abstract Data Type：ADT)，至於堆疊的基本工作運算可以具備以下五種定義： CREATE 建立一個空堆疊。 PUSH 存放頂端資料，並傳回新堆疊。 POP 刪除頂端資料，並傳回新堆疊。 EMPTY 判斷堆疊是否為空堆疊，是則傳回true，不是則傳回false。 FULL 判斷堆疊是否已滿，是則傳回true，不是則傳回false。

5 堆疊基本運算與實作(2) 4-1 堆疊簡介 以下是C++寫成的加入節點與刪除節點程式碼： 陣列堆疊加入節點函數

6 4-1 堆疊簡介 陣列堆疊刪除節點函數

7 以下將分別介紹鏈結堆疊加入與刪除節點的演算法：
4-1 堆疊簡介 以下將分別介紹鏈結堆疊加入與刪除節點的演算法： 鏈結堆疊加入節點函數

8 4-1 堆疊簡介 鏈結堆疊刪除節點函數

9 遞迴的定義 1.直接遞迴(Direct Recursion) 2.間接遞迴
4-2 遞迴 1.直接遞迴(Direct Recursion) 指遞迴函數中，允許直接呼叫該函數本身，稱為直接遞迴(Direct Recursion)。 2.間接遞迴 指遞迴函數中，如果呼叫其他遞迴函數，再從其他遞迴函數呼叫回原來的遞迴函數，我們就稱做間接遞迴(Indirect Recursion)。 任何可以用if-else和while指令編寫的函數，都可以用遞迴來表示和編寫。

10 遞迴的實作(1) 3階乘等於3×2×1=6,而0階乘則定義為1。 一般以符號“！”來代表階乘。
4-2 遞迴 3階乘等於3×2×1=6,而0階乘則定義為1。 一般以符號“！”來代表階乘。 如4階乘可寫為4!。任何問題想以遞迴式來表示，一般需要符合兩個條件：一個反覆的過程，以及一個跳出執行的缺口。 秉持這兩個原則，n!可以寫成： n!=n×(n-1)×(n-2)……×1

11 遞迴的實作(2) 4-2 遞迴 範例程式：ch04_1.cpp

12 4-2 遞迴 執行結果

13 河內塔(1) 在搬動時還必須遵守下列規則： 1.直徑較小的套環永遠置於直徑較大的套環上。
4-2 遞迴 在搬動時還必須遵守下列規則： 1.直徑較小的套環永遠置於直徑較大的套環上。 2.套環可任意地由任何一個木樁移到其他的木樁上。每一次僅能移動一個套環。

14 河內塔(2) 4-2 遞迴 範例程式：ch04_02.cpp

15 4-2 遞迴 執行結果

16 佇列的基本運算與實作(1) 佇列的基本運算可以具備以下五種工作定義： 4-3 佇列 CREATE 建立空佇列。 ADD
4-3 佇列 佇列的基本運算可以具備以下五種工作定義： CREATE 建立空佇列。 ADD 將新資料加入佇列的尾端，傳回新佇列。 Delete 刪除佇列前端的資料，傳回新佇列。 Front 傳回佇列前端的值。 Empty 若佇列為空集合，傳回真，否則傳回偽。

17 佇列的基本運算與實作(2) 以下是嘗試利用C陣列為出發點來實作佇列的五種工作運算： 1 建立佇列 2 將新資料加入Q的尾端，傳 回新佇列。
4-3 佇列 以下是嘗試利用C陣列為出發點來實作佇列的五種工作運算： 1 建立佇列 將新資料加入Q的尾端，傳 回新佇列。 CREATE_QUEUE (MAX_SIZE){ /* 如果佇列的內容是整數 */ #DEFINE MAX_SIZE 100 int Queue[MAX_SIZE]; int front=-1; int rear=-1; /* front及rear皆為全域變數 * ﹜ void AddQ(int item,int *Queue) ﹛ if (rear==MAX_SIZE-1) printf(“%s”,"佇列已滿！"); else rear++; Queue(rear)=item; ﹜/* 加新資料到佇列的尾端 */ ﹜

18 3.刪除佇列前端資料， 4 .傳回佇列前端的值。 傳回新佇列。
4-3 佇列 3.刪除佇列前端資料， 傳回佇列前端的值。 傳回新佇列。 void FRONT_VALUE(int *Queue) ﹛ if (front==rear) printf(“%s”," 這是空佇列"); else printf(“%d”,Queue[front]); } /* 傳回佇列前端的值 */ void DeleteQ(int item,int *Queue) ﹛ if (front==rear) printf(“%s”,"佇列已空！"); else front++; item=Queue[front]; } } /* 刪除佇列前端資料 */

19 5 若佇列為空集合，傳回真，否則傳回偽。 4-3 佇列 void Is_Empty (int* Queue) ﹛
4-3 佇列 5 若佇列為空集合，傳回真，否則傳回偽。 void Is_Empty (int* Queue) ﹛ if (front==rear) printf(“%s”," TRUE"); else printf(“%s”," FALSE"); } /* 判斷佇列是否空佇列 */ 由於佇列的兩端都會有資料進出的動作，因此若要使用串列來模擬佇列的存取，則必須記錄佇列的前端與後端。

20 佇列的基本運算與實作(3) 4-3 佇列 範例程式：ch04_03.cpp

21 4-3 佇列

22 4-3 佇列 執行結果

23 佇列的移動(1) 4-3 佇列 目前執行到步驟8之後，已經無法再加入資料了，現在的問題就是這個佇列事實上根本還有空間，因為rear=MAX_SIZE，使的新資料無法加入。 如下所示：

24 佇列的移動(2) 解決之道有二，請看以下說明：
4-3 佇列 解決之道有二，請看以下說明： 1.當佇列已滿時，便將所有的元素向前(左)移到Q(1)為止，如此可產生最大空間，最壞情況時移動佇列元素的時間複雜度為O(MAX_SIZE)，如圖所示: 2.利用環狀佇列(Circular Queue)，讓rear與front兩種指標能夠永遠介於0與n-1之間。 移動成本太不經濟了 移動成本還好

25 環狀佇列 是把佇列看成如下圖的環狀結構，不過front和rear的初始值設定為0或-1。
4-3 佇列 是把佇列看成如下圖的環狀結構，不過front和rear的初始值設定為0或-1。 front永遠以逆時鐘方向指著佇列中第一個元素的前一個位置，rear則指向佇列目前的最後位置。

26 雙向佇列 雙向佇列(Double Ended Queues:Deque)為一有序串列，加入與刪除可在佇列的任意一端進行， 請看下圖:
4-3 佇列 雙向佇列(Double Ended Queues:Deque)為一有序串列，加入與刪除可在佇列的任意一端進行， 請看下圖: 雙向佇列就是允許兩端中的任意一端都具備有刪除或加入功能，而且無論左右兩端的佇列，首端與尾端指標都是朝佇列中央來移動。

27 優先佇列 特色是其中的元素並不以優先順序進出。 優先佇列可以用陣列結構來表示，也可以利用鏈結串列來解決。
4-3 佇列 特色是其中的元素並不以優先順序進出。 優先佇列可以用陣列結構來表示，也可以利用鏈結串列來解決。 不過利用陣列來製作優先佇列的缺點是經常需要移動大量資料，也無法預先知道需要保留多少尾部(Rear)空間給插入的工作使用。 以陣列結構實作的優先佇列

28 算術運算式的表示法 由運算元、運算子與某些間隔符號(Delimiter)所組成。例如：
4-4 算術運算式的表示法 由運算元、運算子與某些間隔符號(Delimiter)所組成。例如： 其中=、+、*、/等符號稱為運算子，而x、y、z等變數以及2、5等常數都是運算元，運算子兩旁都必須有一個運算元，才算完整的運算式。 z=(x+y)*(x+5)/2;

29 算術式的運算規則(1) 4-4 算術運算式的表示法 優先順序 運算子 1 .、[] 2 ++、--、!、~、+(正)、-(負) 3
4-4 算術運算式的表示法 優先順序 運算子 1 .、[] 2 ++、--、!、~、+(正)、-(負) 3 *、/、% 4 +(加)、-(減) 5 <<、>>、>>> 6 <、<=、>、>= 7 = =、!= 8 & 9 ^ 10 | 11 && 12 || 13 ?: 14 = 15 +=、-=、*=、/=、%=、&=、|=、^=

30 算術式的運算規則(2) 本節重點就是在中序、後序及前序三種之間的轉換。以下是三種表示法的簡單說明：
4-4 算術運算式的表示法 本節重點就是在中序、後序及前序三種之間的轉換。以下是三種表示法的簡單說明： 1.中序法(Infix):<運算元><運算子><運算元>，如A+B。例如2+3、3*5等都是中序表示法。 2.前序法(Prefix):<運算子><運算元><運算元>，如+AB。例如中序運算式2+3，前序運算式的表示法則為+23。 3.後序法(Postfix): <運算元><運算元><運算子>，如AB+。例如後序運算式的表示法為23+。

31 括號轉換法(1) 中序→前序(Infix→Prefix) 中序→後序(infix→postfix) 1.將算術式依據先後次序括號起來。
4-5 中序轉換為前序或後序 中序→前序(Infix→Prefix) 1.將算術式依據先後次序括號起來。 2.移動所有運算子來取代所有的左括號，並以最近者為原則。 3.去掉所有右括號。 中序→後序(infix→postfix) 1.將算術式依據先後次序完全括號起來。 2.移動所有運算子來取代所有的右括號，以最近者為原則。 3.去掉所有左括號。

32 括號轉換法(2) 請按照前面的括號法說明，將中序式括號後，可以得到下列式子，並移動運算子來取代左括號： 最後去掉所有右括號，可得下式：
4-5 中序轉換為前序或後序 請按照前面的括號法說明，將中序式括號後，可以得到下列式子，並移動運算子來取代左括號： 最後去掉所有右括號，可得下式： →前序式：-+/A**BC*DE*AC

33 括號轉換法(3) 接著要轉換成後序法也一樣，將中序式分別括號完後，移動運算子來取代右括號: 最後再去掉所有左括號，可得下式:
4-5 中序轉換為前序或後序 接著要轉換成後序法也一樣，將中序式分別括號完後，移動運算子來取代右括號: 最後再去掉所有左括號，可得下式: 括號法的優點是操作簡單，但標示上容易混淆。 →後序式:ABC**/DE*+AC*- 括號法的優點是操作簡單，但標示上容易混淆。

34 堆疊法(1) 中序→前序 步驟運作： 1.由右至左讀入單一字元。 2.")"在堆疊中比任何運算子都小，不過在堆疊外卻是優先權最高者。
4-5 中序轉換為前序或後序 中序→前序 步驟運作： 1.由右至左讀入單一字元。 2.")"在堆疊中比任何運算子都小，不過在堆疊外卻是優先權最高者。 3.若遇" ("，彈出堆疊內的運算子，直到彈出遇到")"為止。 4.ISP>=ICP則將堆疊的運算子POP出來，否則就push到堆疊內。 5.輸入為運算元則直接輸出。

35 堆疊法(2) 中序→後序 步驟運作： 1.由左至右讀入單一字元。 2.輸入為運算元，則直接輸出。
4-5 中序轉換為前序或後序 中序→後序 步驟運作： 1.由左至右讀入單一字元。 2.輸入為運算元，則直接輸出。 3."("在堆疊中比任何運算子都小，不過如果在堆疊外卻是優先權最高者。 4.ISP>=ICP，則將堆疊的運算子POP出來，否則就push到堆疊內。 5.若遇")"，彈出堆疊內的運算子，直到彈出遇到" ("為止。

36 堆疊法(3) 利用圖示來說明堆疊內部轉換的操作過程： 中序表示法A*(B+C)*D轉成前序表示法的過程: 4-5 中序轉換為前序或後序
4-5 中序轉換為前序或後序 利用圖示來說明堆疊內部轉換的操作過程： 中序表示法A*(B+C)*D轉成前序表示法的過程: Next-token D * ) C + B ( A None Stack empty )* +)* ** Output CD BCD +BCD A+BCD **A+BCD

37 中序表示法A*(B+C)*D轉成後序表示法的過程:
4-5 中序轉換為前序或後序 中序表示法A*(B+C)*D轉成後序表示法的過程:

38 堆疊法(4) 範例 4.5.1 請使用堆疊法將中序法(A+B)*D+E/(F+A*D)+C轉換為前序法及後序法。 中序→前序 中序→後序
4-5 中序轉換為前序或後序 範例 4.5.1 請使用堆疊法將中序法(A+B)*D+E/(F+A*D)+C轉換為前序法及後序法。 中序→前序 中序→後序

39 括號轉換法(1) 前序→中序 例如:將-+/A**BC*DE*AC轉為中序法： 結果是:A/B**C+D*E-A*C
4-6 前序與後序轉換成中序 前序→中序 1.適當的以「運算子+運算元」方式括號。 2.由內而外，每個運算子取代後方右括號。 3.去左括號。 例如:將-+/A**BC*DE*AC轉為中序法： 結果是:A/B**C+D*E-A*C

40 括號轉換法(2) 後序→中序 例如:將ABC**/DE*+AC*-轉為中序法： 結果是:A/B**C+D*E-A*E
4-6 前序與後序轉換成中序 後序→中序 1.適當的以「運算元+運算子」方式括號。 2.每個運算子取代前方左括號。 3.去掉右括號。 例如:將ABC**/DE*+AC*-轉為中序法： 結果是:A/B**C+D*E-A*E

41 堆疊法(1) 前序→中序 1.由右至左讀入符號。 2.若讀入的是運算元，則放入堆疊中。
4-6 前序與後序轉換成中序 前序→中序 1.由右至左讀入符號。 2.若讀入的是運算元，則放入堆疊中。 3.若是運算子，則從堆疊中取出兩個運算元組成(OP2運算子OP1) 4.在前序→中序的堆疊轉換中，堆疊內的運算順序為

42 堆疊法(1) 後序→中序 1.由左至右讀入符號。 2.若讀入的是運算元，則放入堆疊中。
4-6 前序與後序轉換成中序 後序→中序 1.由左至右讀入符號。 2.若讀入的是運算元，則放入堆疊中。 3.若是運算子，則從堆疊中取出兩個運算元，組成(OP1運算子OP2)放入堆疊中。 4.在後序→中序的堆疊轉換中，堆疊內的運算順序為