第4章 堆疊與佇列 堆疊簡介
遞迴
佇列
算術運算式的表示法
中序轉換為前序或後序
前序與後序轉換成中序
堆疊簡介
4-1 堆疊簡介 堆疊是一種具有後進先出(LIFO)特性的資料型態，所有的加入與刪除動作，皆在頂端完成。 最簡單的定義如下：
堆疊的應用
4-1 堆疊簡介 1.遞迴程式的呼叫返迴：在遞迴之前，先將下一個指令的位址及變數的值保存到堆疊。
2.二元樹的中序追蹤(Inorder)、前序追蹤(Preorder)和圖形的深入追蹤(DFS)。
3.CPU的中斷處理(Interrupt Handling)也需要堆疊的支援。
4.將算術式的中序法轉換成後序法。
5.副程式間的呼叫及返回(Subroutine Call and Return)。
6.某些所謂堆疊計算機(Stack Computer)，大部分透過彈出(Pop)及壓入(Push)兩個指令來處理程式。
堆疊基本運算與實作(1)
4-1 堆疊簡介 建立一個空堆疊。 CREATE 存放頂端資料，並傳回新堆疊。 PUSH 刪除頂端資料，並傳回新堆疊。 POP 判斷堆疊是否已滿，是則傳回true，不是則傳回false。 FULL 判斷堆疊是否為空堆疊，是則傳回true，不是則傳回false。 EMPTY 由於堆疊是一種抽象型資料結構(Abstract Data Type：ADT)，至於堆疊的基本工作運算可以具備以下五種定義：
堆疊基本運算與實作(2)
4-1 堆疊簡介 以下是C++寫成的加入節點與刪除節點程式碼：
陣列堆疊加入節點函數
遞迴的定義
4-2 遞迴 任何可以用if-else和while指令編寫的函數，都可以用遞迴來表示和編寫。 1.直接遞迴(Direct Recursion)
指遞迴函數中，允許直接呼叫該函數本身，稱為直接遞迴(Direct Recursion)。
2.間接遞迴
指遞迴函數中，如果呼叫其他遞迴函數，再從其他遞迴函數呼叫回原來的遞迴函數，我們就稱做間接遞迴(Indirect Recursion)。
遞迴的實作(1)
4-2 遞迴 n!=n×(n-1)×(n-2)……×1 3階乘等於3×2×1=6,而0階乘則定義為1。
一般以符號“！”來代表階乘。
如4階乘可寫為4!。任何問題想以遞迴式來表示，一般需要符合兩個條件：一個反覆的過程，以及一個跳出執行的缺口。
秉持這兩個原則，n!可以寫成：
遞迴的實作(2)
4-2 遞迴 int fact(int n) {
if (n==0)
return 1;
else
return n*fact(n-1);
}
範例程式：ch04_1.cpp
河內塔(1)
4-2 遞迴 在搬動時還必須遵守下列規則：
1.直徑較小的套環永遠置於直徑較大的套環上。
2.套環可任意地由任何一個木樁移到其他的木樁上。每一次僅能移動一個套環。
河內塔(2)
4-2 遞迴 範例程式：ch04_02.cpp
佇列的基本運算與實作(1)
4-3 佇列 若佇列為空集合，傳回真，否則傳回偽。 Empty 傳回佇列前端的值。 Front 刪除佇列前端的資料，傳回新佇列。 Delete 將新資料加入佇列的尾端，傳回新佇列。 ADD 建立空佇列。 CREATE 佇列的基本運算可以具備以下五種工作定義：
佇列的基本運算與實作(2)
4-3 佇列 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;
﹜/* 加新資料到佇列的尾端 */
﹜ 以下是嘗試利用C陣列為出發點來實作佇列的五種工作運算：
1 建立佇列 2 將新資料加入Q的尾端，傳 回新佇列。
佇列的基本運算與實作(3)
4-3 佇列 範例程式：ch04_03.cpp
Description:
堆疊基本運算與實作(1)4-1 堆疊簡介 建立一個空堆疊。 CREATE 存放頂端資料，並傳回新堆疊。 PUSH 刪除頂端資料，並傳回新堆疊。 POP 判斷堆疊是否已滿，是則傳回true，不是則傳回false。 FULL 判斷堆疊是否為空堆疊，是則傳回true，不是則傳回false。 EMPTY 由於堆疊是一種抽象型資料結構(Abstract Data Type：ADT)，至於堆疊的基本工作運算可以具備以下五種定義：
Tags:
int | queue | front | 中序轉換為前序或後序 | 堆疊簡介 | rear | 運算元 | 運算子
Created:
1/8/2008 3:16:01 AM
>
Share this presentation
|
Copy the following code to your webpage or blog to embed this presentation:
<a href="http://www.slidefinder.net/堆/堆疊基本運算與實作/33005973" class="slidefinder">04</a>
<script type="text/javascript" src="http://www.slidefinder.net/scripts/embedded.js"></script>
<a href="http://www.slidefinder.net/堆/堆疊基本運算與實作/33005973" class="slidefinder">04</a>
Det3
<script type="text/javascript" src="http://www.slidefinder.net/scripts/embedded.js"></script>
Share this presentation:
Comments