Microsoft Word - DataStruct-981.doc

Size: px

Start display at page:

Download "Microsoft Word - DataStruct-981.doc"

应破车
5 years ago
Views:

1 4. 堆疊與佇列 (Stack and Queue) 4. Stak (). 基本觀念定義 : 當將東西疊成一堆, 而取用的時候由上方來取出特性 : 先進後出, 後進先出 ( 號球先放, 但 3 號球會先拿出 ) (2). Stack 的運算基本運算 push: 將資料放入堆疊 pop: 將資料由堆疊最頂端取出一個 TopItem: 位於堆疊中最上面的一個資料 IsEmpty: 用來檢查目前堆疊是否為空 IsFull: 用來檢查目前堆疊是否已經滿了 push IsFull pop Stack 的實作 : 堆疊的宣告 int Item[5]; IsEmpty // 宣告一個堆疊共有 5 個位置 TopItem 37

2 放入資料 push(); push(); push(c); 取出資料 x = pop(); // C x2 = pop(); // 放入資料 push(d); 範例 : 執行下面指令後, 請填入堆疊的狀態 int Item[3]; () push(); (2) push(); (3) push(c); (4) push(d); (5) x = pop(); (6) x2 = pop(); (7) x3 = pop(); (8) x4 = pop(); (9) push(e); (0) x5 = pop(); () push(f); (2) push(g); 38

3 X = X2 = X3 = X4 = X5 = ns: X = C X2 = X3 = X4 = 0 X5 = E () (2) (3) (4) C C (5) (6) (7) (8) (9) (0) () (2) G E F F 範例 : 用鏈結串列實作堆疊原始的堆疊為 50,2,0 執行 push(2) 的指令執行 pop() 的指令 x () 將 2 的鏈結指向 50 x 50 2 () 將原來指向 50 的鏈結改成指向

4 (3). 利用 Link list 實作 Stack 優點不受堆疊長度的限制 ( 除非記憶體不足 ) 可以動態的加入堆疊的元素缺點必需多一個儲存指標的欄位實作上較為複雜 4.2 Stack 的應用 (). 主要的應用方向副程式的呼叫與返回運算式的轉換及求值遞迴 (2). 副程式的呼叫與返回基本觀念範例主程式執行並呼叫兩個副程式, 請寫出執行下面步驟後的返回位址堆疊的內容? 開始結束主程式 () 呼叫副程式 (4) 返回副程式 (2) 呼叫副程式 2 (3) 返回副程式 () (2) (3) (4) 執行上面各步驟後返回位址堆疊的內容 (3). 運算式的轉換及求值基本觀念 X = + * C ( D + E / F ) 運算式 : 等號的右邊稱為運算式運算子 (Operator) : +, -, *, / 40

5 運算元 (Operand) :,, C, D, E, F 運算子的優先順序 : (,) *, /, % +, - >, <, <=, >= &&, = 運算式的表示法 : 中序式 (infix): + 後序式 (postfix): + 前序式 (prefix): + 中序式轉成後序表示法的步驟 : +*C 將相關的運算元用括號括起來 ( + ( * C ) ) 找到他右邊最接近的右括號, 並加上箭號 ( + ( * C ) ) 將運算子移到右括號的位置 C * + 範例 ( 將下面的中序式轉成後序式 ) (+) * C D / E 答 : (((+) * C) (D/E)) (( + * C) D E/ ) ( + C* - D E/ ) + C* D E/ - 範例 ( 將下面的中序式轉成後序式 ) + (/C - D) * E F/G 答 : (( + (((/C) - D) * E)) (F/G)) (( + ((C/ - D) * E)) FG/ ) (( + (C/ D - * E)) FG/ ) (( + C/ D - E * ) FG/ ) ( C/ D - E * + FG/ ) C/ D - E * + FG/ - 範例 ( 將下面的中序式轉成後序式 ) (+) * (C D) / E 答 : (((+) * (C D)) / E ) ((+ * CD-) / E ) (+ CD- * / E ) + CD- * E / 範例 ( 將下面的中序式轉成後序式 ) + *C - (E + F) 4

6 答 : (( + (*C)) - (E + F)) (( + C*) - E F+) ( C*+ - E F+) C*+ E F+ - 範例 : 計算下面的後序式的值 =5, =6, C=2, D=3, E=2, F=9, G=3 +CD- * E / = ()CD- * E / = ()(-) * E / = (-) E / = -5.5 範例 : 計算下面的後序式的值 =5, =6, C=2, D=3, E=2, F=9, G=3 C*+ E F+ - = (2) + E F + - = (7) E F + - = (7) () = 6 範例 : 計算下面的後序式的值 =5, =6, C=2, D=3, E=2, F=9, G=3 + C* D E/ - = () C * D E / - = (22) D E / - = (22) (.5) = 20.5 範例 : 計算下面的後序式的值 =5, =6, C=2, D=3, E=2, F=9, G=3 C/ D - E * + FG/ - = (3) D - E * + F G / - = (0) E * + F G / - = (0) + F G / - = (5) F G / - = (5) (3) = 2 範例使用堆疊法將下面中序轉後序式 (+) * C D / E 次序運算式運算子堆疊 ( 底頂 ) 輸出的後序式 ( ( 2 ( 3 + (+ 4 (+ 5 ) + 42

7 6 * * + 7 C * +C C* 9 D - +C*D 0 / -/ +C*D E 4.3 Queue (). 基本觀念定義 : 將東西排成一列, 先到的先處理特性 : 先進先出, 後進後出 Queue 運算 EnQueue: 將資料放入佇列 DeQueue: 將資料由佇列的前端取出一個 IsEmpty: 用來檢查目前佇列是否為空 IsFull: 用來檢查目前佇列是否已經滿了 Queue 宣告 typredef struct tagqueue { 43

enqueue(); // 加入 rear = 0, front = - Item[3] Item[4] Item[5] Item[6] q.

8 char item[mx_item]; // 假設 MX_ITEM = 7; int front; // 下次將取出資料的地方 int rear; // 本次已加入資料的地方 } QUEUE; Queue 使用 QUEUE q; q.front = -; q.rear = -; 加入資料 : rear 加, 將新項目加入到 item[rear] 中取出資料 : front 加, 讀出 item[front] 中的資料 Queue 加入資料 q.enqueue(); // 加入 rear = 0, front = - Item[3] Item[4] Item[5] Item[6] q.enqueue(); // 加入 rear =, front = - Item[3] Item[4] Item[5] Item[6] q.enqueue(c); // 加入 C rear = 2, front = - Item[3] Item[4] Item[5] Item[6] Queue 取出資料 str = q.dequeue(); rear = 2, front = 0 Item[3] Item[4] Item[5] Item[6] C 44

enqueue(d); // 加入 D rear = 3, front = 0 Item[3] Item[4] Item[5] Item[6] D (2).

9 str2 = q.dequeue(); rear = 2, front = Item[3] Item[4] Item[5] Item[6] str3 = q.dequeue(); rear = 2, front = 2 C Item[3] Item[4] Item[5] Item[6] C q.enqueue(d); // 加入 D rear = 3, front = 0 Item[3] Item[4] Item[5] Item[6] D (2). 環狀佇列定義 : 將東西排成一列, 先到的先處理優點 : 可以重複使用佇列的位置 (3). 利用陣列來模擬環狀佇列判斷是否可以再加入資料 : MaxSize = 3 Rear = 2 Front = 利用陣列來模擬環狀佇列 (Rear+) Mod MaxSize = 3 Mod 0 = 0 45

無法放入資料 0 < Front 可以放入資料放入到 0 的位置範例 : MaxSize = 6, Rear = 4, Front = 3 () 是否可以再放入資料 (Rear + ) % MaxSize = 5 % 6 = 3 Rear (3) = Front (3) ns: 不可放入資料

10 比較 Rear 和 Front 的值 Rear < Front 則可以放入資料 Rear = Front 滿了!! 無法放入資料範例 : MaxSize = 5, Rear = 3, Front = 3, 表示目前為空 Rear = 4 (MaxSize), Front = 3, 無法放入資料利用陣列來模擬環狀佇列 (Rear+) Mod MaxSize = 5 Mod 5 = 0 比較 Rear 和 Front 的值 Rear < Front 則可以放入資料 Rear = Front 滿了!! 無法放入資料 0 < Front 可以放入資料放入到 0 的位置範例 : MaxSize = 6, Rear = 4, Front = 3 () 是否可以再放入資料 (Rear + ) % MaxSize = 5 % 6 = 3 Rear (3) = Front (3) ns: 不可放入資料 (2) 放入的資料位置在何處 ns: 不可放入資料範例 : MaxSize = 5, Rear = 2, Front = 4 () 是否可以再放入資料 (2+) % 5 = 3 3 < 4 ns: 可以再放資料 (2) 放入的資料位置在何處 ns: 放在 3 的位置範例 : MaxSize = 7, Rear = 7, Front = 6 () 是否可以再放入資料 (7+) % 7 = 4 46

11 4 < 6 ns: 可以再放資料 (2) 放入的資料位置在何處 ns: 放在 4 的位置範例 : MaxSize = 5, Rear = 3, Front = 4 () 是否可以再放入資料 (3+) % 5 = 2 2 < 4 ns: 可以再放資料 (2) 放入的資料位置在何處 ns: 放在 2 的位置 (4). 用陣列結構實作佇列範例範例範例使用函數動作說明 Rear 值 Front 值 EnQueue() 把加到 0 的位置 0-2 EnQueue() 把加到的位置 - 3 DeQueue() 取出 0 4 EnQueue(C) 把 C 加到 2 的位置 DeQueue() 取出 2 6 DeQueue() 使用函數動作說明 Rear 值 Front 值 EnQueue() 把加到 0 的位置 0 - EnQueue() 把加到的位置 - DeQueue() 取出 0 EnQueue(C) 把 C 加到 2 的位置 2 0 DeQueue() 取出 2 DeQueue() 取出 C 2 2 使用函數動作說明 Rear 值 Front 值 EnQueue() 把加到 3 的位置 3 47

12 EnQueue(C) 把 C 加到 0 的位置 0 EnQueue(D) 把 D 加到的位置 DeQueue() 取出 2 EnQueue(E) 把 E 加到 2 的位置 2 2 DeQueue() 取出 2 3 用鏈結串列實作佇列 4.4 綜合練習 (). 利用鏈結串列方式實作貨品管理程式 (array_link_list_0.txt) 本練習要利用陣列的方式撰寫一個進出貨管理程式 48

Microsoft PowerPoint - Fig03_Stack.ppt [相容模式]

Microsoft PowerPoint - Fig03_Stack.ppt [相容模式] 四堆疊與佇列 (Stack & Queue) 4-. 串列及鏈結串列 4-. 用陣列結構實作堆疊 4-3. 用鏈結串列實作堆疊 4-4. 堆疊的應用 4-5. 佇列 4-6. 用陣列結構實作佇列 4-7 7. 用鏈結串列實作佇列堆疊的基本觀念. 定義 : 4- 堆疊當將東西疊成一堆, 而取用的時候由上方來取出. 特性 : 先進後出, 後進先出 ( 號球先放, 但 3 號球會先拿出 ) 3 3