資料結構 第4章　堆疊.

Presentation on theme: "資料結構 第4章　堆疊."— Presentation transcript:

1 資料結構 第4章　堆疊

2 4-1　認識堆疊 堆疊 (stack) 是一個線性串列 (linear list)，兩端分別稱為頂端 (top) 與底端 (bottom)，無論要新增或刪除資料，都必須從堆疊的頂端開始。

3 4-2 堆疊的實作 4-2-1 使用陣列實作堆疊 堆疊應該要提供下列運算： #define MAX_SIZE 5
4-2　堆疊的實作 4-2-1　使用陣列實作堆疊 #define MAX_SIZE 5 typedef struct stk{ char data[MAX_SIZE]; int top; }stack; 堆疊應該要提供下列運算： 判斷堆疊已滿 (isFull) 判斷堆疊已空 (isEmpty) 推入 (push) 彈出 (pop)

4 堆疊的 [推入] 運算

5 堆疊的 [彈出] 運算

6 4-2-2 使用鏈結串列實作堆疊 typedef struct node{ int data; struct node *next;
4-2-2　使用鏈結串列實作堆疊 typedef struct node{ int data; struct node *next; }list_node; typedef list_node *list_pointer;

7 鏈結堆疊的 [推入] 運算

8 鏈結堆疊的 [彈出] 運算

9 4-3　堆疊的應用 資料反轉 (reversing) 資料剖析 (parsing) 回溯 (backtracking)

10 4-3-1　轉換運算式表示法 當運算子位於運算元的中間時 (例如a + b)，屬於中序表示法 (infix)；當運算子位於運算元的前面時 (例如+ab)，屬於前序表示法 (prefix)；當運算子位於運算元的後面時 (例如ab+)，屬於後序表示法 (postfix)。 範例4.7：使用 [括號法] 將a * (b + c) - d由中序表示法轉換成後序表示法。

11 範例4.8：使用 [括號法] 將a * (b + c) - d由中序表示法轉換成前序表示法。

12 範例4.9：使用 [堆疊法] 將a * (b + c) - d由中序表示法轉換成後序表示法。

13 4-3-2　計算後序表示法 範例4.11：[計算後序表示法] 假設a = 5、b = 6、c = 7、d = 8，試計算後序表示法abc+*d- 的結果。

14 4-3-3　系統堆疊

15 4-3-4 遞迴 河內塔 (towers of hanoi) 例如當河內塔有三個圓盤時，開始與結束情況如下： 一次只能移動一個圓盤
4-3-4　遞迴 河內塔 (towers of hanoi) 一次只能移動一個圓盤 小圓盤必須疊在大圓盤上 例如當河內塔有三個圓盤時，開始與結束情況如下：

16 從1、2、3個圓盤類推到n個圓盤： 當有1個圓盤時，直接將圓盤從柱子A移到柱子C即可。

17 當有2個圓盤時 (假設由小到大，依序編號為1、2)，搬移順序如下：

18 當有3個圓盤時 (假設由小到大，依序編號為1、2、3)，搬移順序如下：

19 當有n個圓盤時 (假設由小到大，依序編號為1、2、…、n)，搬移順序如下：