资料结构-堆叠与伫列.ppt

《资料结构-堆叠与伫列.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、資料結構第三章　堆疊與佇列大綱第一節　堆疊第二節　佇列第一節　堆疊一、定義堆疊是一個有序串列，所有的加入(insert)與刪除(delete)動作均是在堆疊的頂端(top)進行，具有先進後出(FILO)或後進先出(LIFO)的特性。第一節　堆疊二、應用1.副程式的呼叫及返回處理。2.遞迴程式的呼叫及返回處理。3.算術式的轉換。4.二元樹的走訪。5.圖形的走訪。6.中斷的處理。第一節　堆疊三、堆疊的工作定義1.CREATE(S)：建立一個空的堆疊。2.PUSH(data,S)：將資料加入堆疊的頂端。3.POP(S)：傳回堆疊頂端

2、的資料，並將該筆資料自堆疊中刪除。4.TOP(S)：傳回堆疊頂端的資料，但不將該筆資料自堆疊中刪除。5.EMPTY(S)：若堆疊內已無任何資料，就傳回真(true)，否則就傳回假(false)。第一節　堆疊四、加入及刪除資料的演算法將一筆資料加入堆疊中的演算法：ProcedurePUSH(data,stack,n,top)If(top>n)thenCallSTACK-FULL()Elsestack(top)←datatop←top+1endifendPUSH第一節　堆疊(1)data：代表欲加入堆疊中的資料。(2)stack：

3、是一個指向堆疊起點的指標(pointer)。(3)n：記錄堆疊的大小。(4)top：是一個指向堆疊頂端的指標，亦即指向堆疊中下一個可以再存放資料的指標。(5)STACK-FULL()：是一個錯誤警告副程式，用來表示現在的堆疊已經滿了，無法再做加入資料的動作了。(6)‘←’：表示將右邊的資料存入左邊所指的位置，所以“stack(top)←data”表示將資料data存入stack+top所指的位置中。第一節　堆疊自堆疊中取出一筆資料，並刪除該筆資料的演算法：ProcedurePOP(stack,data,top)if(top=1

4、)thenCallSTACK_EMPTY()elsetop←top-1data←stack(top)endifendPOP第一節　堆疊STACK_EMPTY()是一個錯誤警告副程式，用來表示現在的堆疊已經是空的，無法再做取出或刪除資料的動作了。註：以上兩個演算法PUSH()及POP()，若陣列起始編碼是從1開始，則堆疊可以加入或刪除n筆資料；但若是從零開始，則演算法POP()中之if判斷式須修改成if(top=0)thencallSTACK-EMPTY()，如此即可加入或刪除n+1筆資料了。第二節　佇列一、定義佇列是一個有序串

5、列(orderedlist)，所有的加入與刪除分別發生在串列的不同端，加入的一端稱為後端(rear)，而刪除的一端稱為前端(front)，具有先進先出(FIFO)的特性。第二節　佇列二、應用1.作業系統的工作排程。2.電腦的模擬（simulation）程式。3.輸出入工作緩衝區（buffer）。第二節　佇列三、佇列的工作定義1.CREATE(Q)：建立一個空的佇列。2.ADDQ(data,Q)：將資料加入佇列的尾端(rear)。3.DELETEQ(Q)：傳回佇列前端(front)的資料，並將該筆資料自佇列中刪除。4.FRONT

6、(Q)：傳回佇列前端的資料，但不會將該筆資料自佇列中刪除。5.EMPTY(Q)：若佇列為空的(empty)，代表佇列內已無任何資料，因此就傳回真(true)；否則就傳回假(false)，代表佇列不為空的，亦即佇列內尚有資料。第二節　佇列四、加入及刪除資料的演算法將一筆資料加入佇列中的演算法：ProcedureADDQ(data,Q,n,rear)if(rear>n)thencallQUEUE_FULL()elseQ(rear)←datarear←rear+1endifendADDQ第二節　佇列(1)data：代表欲加入佇列中的

7、資料。(2)Q：是一個指向佇列起點的指標。(3)n：記錄佇列的大小。(4)rear：是一個指向佇列尾端的指標。(5)QUEUE_FULL()：是一個錯誤警告副程式，用來表示現在的佇列已經滿了，無法再做加入資料的動作了。(6)‘←’：表示將右邊的資料存入左邊所指的位置，所以“Q(rear)←data”表示將資料data存入到Q+rear所指的位置中。第二節　佇列自佇列中取出一筆資料，並刪除該筆資料的演算法：ProcedureDELETEQ(Q,data,front,rear)if(front=rear)thencallQUEUE

8、_EMPTY()elsedata←Q(front)front←front+1endifendDELETEQ第二節　佇列(1)front：是一個指向佇列前端的指標，與Q指標的差別是，Q指標不會任意改變，它永遠指向佇列開始的位置，但front指標會隨資料自佇列中刪除而跟著做改變。