第5章 堆疊（Stacks） 5-1 堆疊的基礎 5-2 堆疊的表示法 5-3 堆疊的應用 - 運算式的計算與轉換

Presentation on theme: "第5章 堆疊（Stacks） 5-1 堆疊的基礎 5-2 堆疊的表示法 5-3 堆疊的應用 - 運算式的計算與轉換"— Presentation transcript:

1 第5章 堆疊（Stacks） 5-1 堆疊的基礎 5-2 堆疊的表示法 5-3 堆疊的應用 - 運算式的計算與轉換
5-4 堆疊與遞迴的應用 - 走迷宮問題 5-5 再談遞迴的應用 - 河內塔問題

2 5-1 堆疊的基礎-說明 「堆疊」（Stacks）屬於一種擁有特定進出規則的線性串列結構，如同在餐廳廚房的工人清洗餐盤，將洗好的餐盤疊在一起，每一個洗好的餐盤放在這疊餐盤的頂端，如下圖所示：

3 5-1 堆疊的基礎-操作 堆疊的基本操作，如下所示： pop( )：從堆疊取出資料，每執行一次，就從頂端取出一個資料。
push( )：將資料存入堆疊，在堆疊的頂端新增資料。 isStackEmpty( )：檢查堆疊是否是空的，以便判斷是否還有資料可以取出。

4 5-1 堆疊的基礎-特性 堆疊的資料因為是從頂端一一存入，堆疊內容是依序執行push(1)、push(2)、push(3)、push(4)和push(5)的結果，接著從堆疊取出資料，依序執行pop()取出堆疊資料，如下所示： pop()：5 pop()：4 pop()：3 pop()：2 pop()：1 取出的資料順序是5、4、3、2、1，可以看出其順序和存入時相反，稱為「先進後出」（Last Out, First In）的特性。總之，堆疊擁有的特性，如下所示： 只允許從堆疊的頂端存取資料。 資料存取的順序是先進後出（Last Out, First In），也就是後存入堆疊的資料，反而先行取出。

5 5-1 堆疊的基礎- C語言的函數呼叫(說明) C語言函數呼叫的執行過程就是使用作業系統的堆疊儲存目前的執行狀態，例如：C程式擁有主程式main()和a()和b()兩個函數，M1、M2、A1、A2和B分別代表程式區塊，程式的執行順序依序為：M1→A1→B→A2→M2。

6 5-1 堆疊的基礎- C語言的函數呼叫 當主程式main()呼叫和進入函數a()，main()的返回位址1存入堆疊，
接著進入函數b()，返回位址2被存入堆疊，執行完函數b()後，從堆疊取出返回位址2，繼續執行A2程式區塊，再繼續從堆疊取出返回位址1，繼續主程式的執行，如下圖所示：

7 5-1 堆疊的基礎- C語言的區域變數 C語言的全域變數是在編譯階段就配置記憶體空間，區域變數則是在執行階段進入函數後，才配置變數所需的記憶體空間，而且在結束函數執行後，就馬上釋放區域變數佔用的記憶體空間。 函數的參數也屬於一種區域變數，C語言函數呼叫在處理區域變數和參數時，就是將這些變數和參數的值都使用堆疊保留下來，其操作類似前述使用堆疊保留返回位址的方式，程式在呼叫函數前，將返回位址、各區域變數和參數都一一存入堆疊，等到返回後，再一一取出堆疊內容，恢復成函數呼叫前的執行狀態。

8 5-2 堆疊的表示法 5-2-1 使用陣列建立堆疊 5-2-2 使用鏈結串列建立堆疊

9 5-2-1 使用陣列建立堆疊-標頭檔 01: /* 程式範例: Ch5-2-1.h */ 02: #define MAXSTACK 100
03: int stack[MAXSTACK]; /* 堆疊的陣列宣告 */ 04: int top = -1; /* 堆疊的頂端 */ 05: /* 抽象資料型態的操作函數宣告 */ 06: extern int isStackEmpty(); 07: extern int push(int d); 08: extern int pop();

10 5-2-1 使用陣列建立堆疊-存入元素(步驟) 因為堆疊的特性是只能從堆疊頂端存取資料，所以需要一個額外的top變數來指向堆疊頂端的陣列索引值，使用此索引值將資料存入堆疊。 push( )函數將資料存入堆疊的步驟，如下所示： Step 1：將堆疊頂端的指標top加1。 Step 2：將參數的資料存入指標top所指的陣列元素。 stack[++top] = d;

11 5-2-1 使用陣列建立堆疊-存入元素(圖例) 例如：依序將值1~6存入堆疊的圖例，如下圖所示：

12 5-2-1 使用陣列建立堆疊-取出元素(步驟) 從堆疊取出資料的是pop( )函數，取出資料的步驟，如下所示：
Step 1：取出目前堆疊指標top所指的陣列值。 Step 2：將堆疊指標top的內容減1，即指向下一個堆疊元素。 return stack[top--];

13 5-2-1 使用陣列建立堆疊-取出元素(圖例) 例如：在依序將值1~6存入堆疊後，從堆疊取出各元素的圖例，如下圖所示：

14 5-2-2 使用鏈結串列建立堆疊-標頭檔 01: /* 程式範例: Ch5-2-2.h */
02: struct Node { /* 堆疊節點的宣告 */ 03: int data; /* 儲存堆疊資料 */ 04: struct Node *next; /* 指向下一節點 */ 05: }; 06: typedef struct Node SNode; /* 堆疊節點的新型態 */ 07: typedef SNode *LStack; /* 串列堆疊的新型態 */ 08: LStack top = NULL; /* 堆疊頂端的指標 */ 09: /* 抽象資料型態的操作函數宣告 */ 10: extern int isStackEmpty(); 11: extern void push(int d); 12: extern int pop();

15 5-2-2 使用鏈結串列建立堆疊-存入元素(步驟)
函數push( )可以將資料存入堆疊，也就是新增節點成為串列的第1個節點，其步驟如下所示： Step 1：建立新節點儲存堆疊資料。 new_node = (LStack)malloc(sizeof(SNode)); Step 2：取出資料，將新節點的next指標指向原來堆疊頂端top指標的節點。 new_node->data = d; new_node->next = top; Step 3：堆疊頂端的top指標指向新節點。 top = new_node;

16 5-2-2 使用鏈結串列建立堆疊-存入元素(圖例)
例如：依序存入值1~3到堆疊的串列，如下圖所示：

17 5-2-2 使用鏈結串列建立堆疊-取出元素(步驟)
從堆疊取出資料的是pop( )函數，也就是刪除串列的第1個節點，其取出步驟如下所示： Step 1：將堆疊指標top指向下一個節點。 top = top->next; Step 2：取出原來堆疊指標所指節點的內容。 temp = ptr->data; Step 3：釋回原來堆疊指標的節點記憶體。 free(ptr);

18 5-2-2 使用鏈結串列建立堆疊-取出元素(圖例)
例如：在依序存入值1~3到堆疊後，呼叫二次pop()函數取出堆疊元素，可以看出取出2個堆疊元素，因為一共存入3個元素，所以目前堆疊還剩下一個元素1。如下圖所示：

19 5-3 堆疊的應用 - 運算式的計算與轉換 5-3-1 運算式的種類、計算與轉換 5-3-2 後序運算式的計算
5-3-3 中序運算式轉換成後序運算式

20 5-3-1 運算式的種類、計算與轉換-說明 算術運算式是使用「運算子」（Operators）和「運算元」（Operands）所組成，如下所示： A+B A*B+C 上述運算式的A、B和C是運算元，＋和*是運算子。

21 5-3-1 運算式的種類、計算與轉換-種類 運算式種類依據運算子位在運算式中的位置，可以分為三種，如下所示：
中序表示法（Infix）：運算式中的運算子是位在兩個運算元之間，例如：A+B和A*B+C。 前序表示法（Prefix）：運算子位在兩個運算元之前，例如：+AB和+*ABC。 後序表示法（Postfix）：運算子位在兩個運算元之後，例如：AB+和AB*C+。

22 5-3-1 運算式的種類、計算與轉換-優先順序 中序表示法在執行運算式的計算和轉換前，需要注意運算子的「優先順序」（Priority），運算子的優先順序，如下表所示：

23 5-3-1 運算式的種類、計算與轉換-中序計算 運算式在先計算B*C後才和A相加，因為運算子*的優先順序大於+。如果中序運算式不考慮運算子優先順序，同一個中序運算式可能產生不同的運算結果，如下所示： A+B*C：先算A+B，再和C相乘 A+B*C：先算B*C再加上A

24 5-3-1 運算式的種類、計算與轉換-前序與後序計算
前序和後序表示法，就不需要考慮運算子的優先順序，如下所示：

25 5-3-1 運算式的種類、計算與轉換-轉換(方法1)
運算式轉換分為中序轉前序和中序轉後序表示法，其轉換步驟十分相似，其差異只在運算子是位在運算元前或後。例如：中序運算式，如下： A*(B+C) 上述運算式轉換成前序和後序表示法的步驟，以運算子優先順序來進行處理，如下表所示：

26 5-3-1 運算式的種類、計算與轉換-轉換(方法2)
另一種方法是先替(1)中序運算式加上完整括號來確認運算的優先順序，如下所示： 中序運算式： A+B*(C+D)-E 加上括號的中序運算式： ((A+(B*(C+D)))-E) 上述是加上括號的中序運算式，現在 需(2)從最中間的括號開始，將運算子移到右括號的位置且刪除右括號，直到(3)刪除所有右括號為止，如下所示： 將運算子搬移到右括號： ((A(B(CD+*+E- 刪除所有的左括號： ABCD+*+E-

27 5-3-1 運算式的種類、計算與轉換-轉換(範例)
一些中序運算式轉換成前序和後序運算式的範例，如下表所示：

28 5-3-2 後序運算式的計算-說明 後序運算式的計算和前序運算式類似，都屬於無括號和優先順序的運算式計算，例如：一個後序運算式如下所示：
67*45++ 上述運算式的運算子是位在運算元之後，換句話說，當讀取運算式的運算元或運算子時，只需一個堆疊存放運算元即可，如果是運算子馬上取出堆疊的運算元，然後將計算結果存回到堆疊。

29 5-3-2 後序運算式的計算-過程1 後序運算式：67*45++的計算過程是在主迴圈依序讀取運算式的運算元或運算子，第1個讀入的字元是'6'，因為是運算元，所以存入運算元堆疊，如下圖所示：

30 5-3-2 後序運算式的計算-過程2 接著讀入的字元'7'是運算元，再存入運算元堆疊，如下圖所示：

31 5-3-2 後序運算式的計算-過程3 繼續讀入字元'*'是運算子，從運算元堆疊取出2個運算元7和6，將6*7的計算結果42存回堆疊，如下圖所示：

32 5-3-2 後序運算式的計算-過程4 接著讀入的是字元'4'和字元'5'兩個運算元，依序存入運算元堆疊，如下圖所示：

33 5-3-2 後序運算式的計算-過程5 繼續讀入的字元'+'是運算子，所以從運算元堆疊取出2個運算元5和4，然後將4+5計算結果9存回運算元堆疊，如下圖所示：

34 5-3-2 後序運算式的計算-過程6 最後一個讀入的字元是運算子'+'，從運算元堆疊取出2個運算元9和42，就可以得到後序運算式的計算結果是51。

35 5-3-2 後序運算式的計算-演算法 後序運算式計算的演算法可以依照前述計算過程來推導，其完整步驟如下所示：
Step 1：使用迴圈從左至右依序讀入後序運算式。 (1) 如果讀入的是運算子, 則： 1) 從運算元堆疊取出所需的運算元。 2) 計算此運算元和運算子的值後，存回運算元堆疊。 (2) 如果讀入的是運算元，直接存入運算元堆疊。 Step 2：最後取出運算元堆疊的內容，就是後序運算式的計算結果。

36 5-3-3 中序運算式轉換成後序運算式-說明 中序運算式轉換成後序運算式可以使用堆疊配合運算子優先順序來進行轉換。例如：相同運算結果的中序和後序運算式，如下所示： 中序運算式： (9+6)*4 後序運算式： 96+4* 上述後序運算式是從中序運算式轉換而成，可以看出兩個運算式中的運算元排列順序是相同的，只有運算子執行順序有優先順序的差異，所以中序運算式的轉換只需一個運算子堆疊，如果讀入運算元馬上輸出即可，運算子需要進行優先順序的比較，以決定輸出或存入堆疊。

37 5-3-3 中序運算式轉換成後序運算式-過程1 中序運算式：(9+6)*4的計算過程是在主迴圈從左至右依序讀取運算式的運算元或運算子，第1個讀入的字元是'('左括號，存入運算子堆疊，如下圖所示：

38 5-3-3 中序運算式轉換成後序運算式-過程2 接著讀入的字元是運算元'9'，直接輸出運算元，如下圖所示：

39 5-3-3 中序運算式轉換成後序運算式-過程3 繼續讀入字元'+'是運算子，因為不是右括號且'+'號的優先順序大於堆疊中的'('號（注意！括號的優先順序和第5-3-1節不同，左括號的優先順序最小），所以將運算子存入運算子堆疊，如下圖所示：

40 5-3-3 中序運算式轉換成後序運算式-過程4 然後讀入的字元是運算元'6'，直接輸出運算元，如下圖所示：

41 5-3-3 中序運算式轉換成後序運算式-過程5 接著讀入的是右括號')'，我們需要從運算子堆疊取出運算子'+'輸出，直到左括號為止，左括號在此的功能只是作為一個標籤，所以並不用輸出，此時的堆疊已經全空，如下圖所示：

42 5-3-3 中序運算式轉換成後序運算式-過程6 繼續讀入字元'*'是運算子，存入運算子堆疊，如下圖所示：

43 5-3-3 中序運算式轉換成後序運算式-過程7 接著讀入運算元'4'，直接輸出運算元，如下圖所示：

44 5-3-3 中序運算式轉換成後序運算式-過程8 現在已經讀完整個中序運算式，接著從運算子堆疊取出剩下的運算子'*'且輸出，可以得到轉換的後序運算式，如下所示： 96+4*

45 5-3-3 中序運算式轉換成後序運算式-演算法 中序轉成後序運算式的演算法可以依照前述計算過程來推導，其完整步驟如下所示：
Step 1：使用迴圈讀取中序運算式的運算元和運算子，若： (1) 讀取的是運算子： 1) 如果運算子堆疊是空的或是左括號，存入運算子堆疊。 2) 如果是右括號，從堆疊取出運算子輸出，直到左括號為止。 3) 如果堆疊不是空的，持續和堆疊的運算子比較優先順序，若： a. 優先順序比較低，輸出運算子。 b. 優先順序比較高或堆疊空了，將運算子存入運算子堆疊。 (2) 讀取的是運算元，直接輸出運算元。 Step 2：如果運算子堆疊不是空的，依序取出運算子堆疊的運算子。

46 5-4 堆疊與遞迴的應用 - 走迷宮問題 5-4-1 使用堆疊的回溯控制走迷宮 5-4-2 使用遞迴走迷宮

47 5-4 堆疊與遞迴的應用 - 走迷宮問題 堆疊與遞迴有異曲同工之妙，因為遞迴函數是直接使用作業系統的堆疊，當然我們也可以自行在程式建立堆疊執行回溯控制，換句話說，走迷宮問題（A Mazing Problem）可以使用堆疊或遞迴方式來找出走出迷宮的路。

48 5-4-1 使用堆疊的回溯控制走迷宮-說明 「回溯」（Backtracking）屬於人工智慧的重要觀念，使用嘗試錯誤方式來找尋問題的解答。例如：在迷宮中找出一條走出迷宮的路，這就是回溯最常見的應用。

49 5-4-1 使用堆疊的回溯控制走迷宮-問題 假設：迷宮內的路只有向上下左右四個方向，而且行走的優先順序是上、下、左和右，對角線方向並不允許行走，迷宮的行走方式是依照上述四個方向，每次走一步，如果遇到牆壁，就需要嘗試剩下幾個方向是否有路可行，繼續相同的走法直到找出一條走出迷宮的路，如右圖所示：

50 5-4-1 使用堆疊的回溯控制走迷宮-迷宮圖形 迷宮的圖形是使用一個二維陣列來表示，陣列元素值0表示是可走的路，1代表是牆壁，如下圖所示：

51 5-4-1 使用堆疊的回溯控制走迷宮-走迷宮的路徑1

52 5-4-1 使用堆疊的回溯控制走迷宮-走迷宮的路徑2

53 5-4-1 使用堆疊的回溯控制走迷宮-走迷宮的路徑3

54 5-4-1 使用堆疊的回溯控制走迷宮 在迷宮中找出一條走出迷宮的路，是使用嘗試錯誤方式來找尋問題的解答，這種方法稱做「嘗試錯誤」(Try and Error)。在嘗試錯誤中一步一步退回原來走的路，這種技巧稱為「回溯」（Backtracking）。 在C程式處理回溯是使用推疊來記錄經過的路徑，當無路可前進時，即取出堆疊內的路徑記錄，退回上一步，再繼續找出路。

55 程式範例 5-4-1.c int main() { int maze[7][10] = {
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; 15 int i,j; 16 int x = 5; /* 迷宮入口座標 */ 17 int y = 8; 18 while ( x != 1 || y != 1 ) { /* 主迴圈 */ maze[x][y] = 2; /* 標示為已走過的路 */ if ( maze[x-1][y] <= 0 ) { /* 往上方走 */ x = x - 1; /* 座標x減1 */ push(x); /* 存入路徑 */ push(y); } else if ( maze[x+1][y] <= 0 ) { /* 往下方走 */ x = x + 1; push(x); push(y); } else if ( maze[x][y-1] <= 0 ) { /* 往左方走 */ y = y - 1; push(x); push(y); } 35 else if ( maze[x][y+1] <= 0 ) {/* 往右方走 */ y = y + 1; push(x); push(y); } else { /* 沒有路可走:迴溯 */ maze[x][y] = 3; /* 表示迴溯的路 */ y = pop(); /* 退回一步 */ x = pop(); } 45 } maze[x][y] = 2; /* 標示最後位置 */ printf("迷宮路徑圖(從右下角到左上角): \n"); for ( i = 0; i <= 6; i++) { /* 顯示迷宮圖形 */ for ( j = 0; j <= 9; j++) printf("%d ", maze[i][j]); /* 顯示座標值 */ printf("\n"); } printf("\n數字 1: 牆壁\n數字 2: 走過的路徑\n"); printf("數字 3: 回溯路徑\n"); system("PAUSE"); return 0;

56 5-4-2 使用遞迴走迷宮-走法 迷宮同樣採用二維陣列，陣列元素值1表示牆壁，0表示可走的路。如果目前的座標是(i, j)，走迷宮規則的下一步可以是往上、下、左和右走，優先順序是上、下、左和右，換句話說，第1優先是往上走，如果上方可以走就往上走，不行試第2優先下方，如果不行再試第3優先和第4優先。如下圖所示：

57 5-4-2 使用遞迴走迷宮-遞迴呼叫 findPath()遞迴函數的遞迴呼叫圖例，如下圖所示：

58 5-5 再談遞迴的應用 - 河內塔問題(說明) 「河內塔」（Tower of Hanoi）問題是流傳在Brahma廟內的遊戲，廟內的僧侶相信完成這個遊戲是一件不可能的任務。河內塔問題共有三根木樁，如下圖所示： 上述圖例一共有n個盤子放置在第一根木樁，盤子的尺寸由上而下依序遞增。河內塔問題是將所有的盤子從木樁1搬移到木樁3。

59 5-5 再談遞迴的應用 - 河內塔問題(規則) 河內塔問題是將所有的盤子從木樁1搬移到木樁3，其搬動規則，如下所示：
每次只能移動一個盤子，而且只能從最上面的盤子搬動。 盤子可以搬到任何一根木樁。 維持盤子的尺寸是由上而下依序的遞增。

60 5-5 再談遞迴的應用 - 河內塔問題(n=1) n=1 在木樁上只有一個盤子，只需從木樁1搬到木樁3即可。

61 5-5 再談遞迴的應用 - 河內塔問題(n=2) n=2 在木樁1一共有二個盤子，如下圖所示：

62 5-5 再談遞迴的應用 - 河內塔問題(n=2,步驟1,2)
Step 1：將盤子從木樁1搬移到木樁2，如下圖所示： Step 2：將盤子從木樁1搬移到木樁3，如下圖所示：

63 5-5 再談遞迴的應用 - 河內塔問題(n=2,步驟3)
Step 3：將盤子從木樁2搬移到木樁3，即可解出河內塔問題，如下圖所示：

64 5-5 再談遞迴的應用 - 河內塔問題(n=3) n=3 在木樁1上一共有三個盤子，如下圖所示：

65 5-5 再談遞迴的應用 - 河內塔問題(n=3,步驟1,2)
Step 1：將盤子從木樁1搬移到木樁3，如下圖所示： Step 2：將盤子從木樁1搬移到木樁2，如下圖所示：

66 5-5 再談遞迴的應用 - 河內塔問題(n=3,步驟3,4)
Step 3：將盤子從木樁3搬移到木樁2，如下圖所示： Step 4：將盤子從木樁1搬移到木樁3，如下圖所示：

67 5-5 再談遞迴的應用 - 河內塔問題(n=3,步驟5,6)
Step 5：將盤子從木樁2搬移到木樁1，如下圖所示： Step 6：將盤子從木樁2搬移到木樁3，如下圖所示：

68 5-5 再談遞迴的應用 - 河內塔問題(n=3,步驟7)
Step 7：將盤子從木樁1搬移到木樁3，即可完成河內塔問題，如下圖所示：

69 5-5 再談遞迴的應用 - 河內塔問題(演算法) 對於未知n值的河內塔問題需要使用遞迴。首先將河內塔問題分解成小問題，並且實際搬搬看，最後可以歸納出三個步驟，如下所示： Step 1：將最上面n-1個盤子從木樁1搬移到木樁2。 Step 2：將最後一個盤子從木樁1搬移到木樁3。 Step 3：將木樁2的n-1個盤子搬移到木樁3。

70 5-5 再談遞迴的應用 - 河內塔問題(遞迴呼叫)
遞迴呼叫過程如下圖所示：

71 本章結束

72 複習(一) 1.何謂堆疊? 2.堆疊的特性為何? 3.堆疊的基本操作有哪幾個?
4. 資料結構裡Last Out, First In意義為何? 5. C語言函數呼叫如何使用堆疊? 6. 全域變數與區域變數的記憶體空間配置有何不同? 7.資料存入陣列堆疊的步驟為何? 8.將資料自陣列堆疊取出的步驟為何?

73 複習(二) 9.資料存入鏈結串列堆疊的步驟為何? 10.將資料自鏈結串列堆疊取出的步驟為何?
11.運算式的表示法Infix, Prefix, Postfix之意義為何? 12.後序運算式計算的演算法為何? 13.中序轉換成後序運算式的演算法為何? 14.走迷宮問題可以用甚麼資料結構找出路? 15.何謂回溯? C語言如何處理回溯問題? 16.何謂「河內塔」（Tower of Hanoi）問題? 17.解決「河內塔」的步驟如何?