資料結(jié)構(gòu)-堆疊與佇列_第1頁(yè)
資料結(jié)構(gòu)-堆疊與佇列_第2頁(yè)
資料結(jié)構(gòu)-堆疊與佇列_第3頁(yè)
資料結(jié)構(gòu)-堆疊與佇列_第4頁(yè)
資料結(jié)構(gòu)-堆疊與佇列_第5頁(yè)
已閱讀5頁(yè),還剩16頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、資料結(jié)構(gòu)第三章堆疊與佇列1大綱第一節(jié)堆疊 第二節(jié)佇列 2第一節(jié)堆疊一、定義 堆疊是一個(gè)有序串列,所有的加入(insert)與刪除(delete)動(dòng)作均是在堆疊的頂端(top)進(jìn)行,具有先進(jìn)後出(FILO)或後進(jìn)先出(LIFO)的特性。 3第一節(jié)堆疊二、應(yīng)用 1. 副程式的呼叫及返回處理。 2. 遞迴程式的呼叫及返回處理。 3. 算術(shù)式的轉(zhuǎn)換。 4. 二元樹(shù)的走訪(fǎng)。 5. 圖形的走訪(fǎng)。 6. 中斷的處理。 4第一節(jié)堆疊三、堆疊的工作定義 1. CREATE(S):建立一個(gè)空的堆疊。 2. PUSH(data, S):將資料加入堆疊的頂端。 3. POP(S):傳回堆疊頂端的資料,並將該筆資料 自

2、堆疊中刪除。 4. TOP(S):傳回堆疊頂端的資料,但不將該筆資 料自堆疊中刪除。 5. EMPTY(S):若堆疊內(nèi)已無(wú)任何資料,就傳回真 (true),否則就傳回假(false)。 5第一節(jié)堆疊四、加入及刪除資料的演算法 將一筆資料加入堆疊中的演算法:Procedure PUSH(data, stack, n, top)If (topn) then Call STACK-FULL( )Else stack(top)data toptop+1end if end PUSH6第一節(jié)堆疊 (1) data:代表欲加入堆疊中的資料。 (2) stack:是一個(gè)指向堆疊起點(diǎn)的指標(biāo)(pointer)。

3、 (3) n:記錄堆疊的大小。 (4) top:是一個(gè)指向堆疊頂端的指標(biāo),亦即指向堆疊中下一個(gè)可以再存放資料的指標(biāo)。 (5) STACK-FULL( ):是一個(gè)錯(cuò)誤警告副程式,用來(lái)表示現(xiàn)在的堆疊已經(jīng)滿(mǎn)了,無(wú)法再做加入資料的動(dòng)作了。(6) :表示將右邊的資料存入左邊所指的位置,所以“stack(top)data”表示將資料data存入stack + top所指的位置中。 7第一節(jié)堆疊自堆疊中取出一筆資料,並刪除該筆資料的演算法: Procedure POP(stack, data, top)if ( top=1) then Call STACK_EMPTY( )else top top-1 da

4、ta stack(top)end if end POP 8第一節(jié)堆疊 STACK_EMPTY( )是一個(gè)錯(cuò)誤警告副程式,用來(lái)表示現(xiàn)在的堆疊已經(jīng)是空的,無(wú)法再做取出或刪除資料的動(dòng)作了。 註:以上兩個(gè)演算法PUSH( )及POP( ),若陣列起始編碼是從1開(kāi)始,則堆疊可以加入或刪除n筆資料;但若是從零開(kāi)始,則演算法POP( )中之if判斷式須修改成if (top=0) then call STACK-EMPTY( ),如此即可加入或刪除n+1筆資料了。 9第二節(jié)佇列一、定義 佇列是一個(gè)有序串列 (ordered list),所有的加入與刪除分別發(fā)生在串列的不同端,加入的一端稱(chēng)為後端 (rear),

5、而刪除的一端稱(chēng)為前端 (front),具有先進(jìn)先出 (FIFO) 的特性。 10第二節(jié)佇列二、應(yīng)用 1.作業(yè)系統(tǒng)的工作排程。 2.電腦的模擬(simulation)程式。 3.輸出入工作緩衝區(qū)(buffer)。 11第二節(jié)佇列三、佇列的工作定義 1. CREATE(Q):建立一個(gè)空的佇列。 2. ADDQ(data, Q):將資料加入佇列的尾端(rear)。 3. DELETEQ(Q):傳回佇列前端(front)的資料,並將 該筆資料自佇列中刪除。 4. FRONT(Q):傳回佇列前端的資料,但不會(huì)將該筆 資料自佇列中刪除。 5. EMPTY(Q):若佇列為空的(empty),代表佇列內(nèi)已 無(wú)

6、任何資料,因此就傳回真(true);否則就傳回假 (false),代表佇列不為空的,亦即佇列內(nèi)尚有資料。 12第二節(jié)佇列四、加入及刪除資料的演算法 將一筆資料加入佇列中的演算法: Procedure ADDQ(data, Q, n, rear) if (rearn) then call QUEUE_FULL( ) else Q(rear)data rearrear+1 end if end ADDQ 13第二節(jié)佇列 (1)data:代表欲加入佇列中的資料。(2)Q:是一個(gè)指向佇列起點(diǎn)的指標(biāo)。(3)n:記錄佇列的大小。(4)rear:是一個(gè)指向佇列尾端的指標(biāo)。(5)QUEUE_FULL( ):是

7、一個(gè)錯(cuò)誤警告副程式, 用來(lái)表示現(xiàn)在的佇列已經(jīng)滿(mǎn)了,無(wú)法再做加 入資料的動(dòng)作了。(6):表示將右邊的資料存入左邊所指的位 置,所以“Q (rear)data”表示將資料data存 入到Q + rear所指的位置中。 14第二節(jié)佇列自佇列中取出一筆資料,並刪除該筆資料的演算法: Procedure DELETEQ(Q, data, front, rear ) if(front=rear) then call QUEUE_EMPTY( )else dataQ(front) frontfront+1end if end DELETEQ 15第二節(jié)佇列 (1) front:是一個(gè)指向佇列前端的指標(biāo),與Q

8、指標(biāo) 的差別是,Q指標(biāo)不會(huì)任意改變,它永遠(yuǎn)指向佇 列開(kāi)始的位置,但front指標(biāo)會(huì)隨資料自佇列中 刪除而跟著做改變。 (2) QUEUE_EMPTY( ):是一個(gè)錯(cuò)誤警告副程 式,用來(lái)表示現(xiàn)在的佇列已經(jīng)是空的,無(wú) 法再做取出或刪除資料的動(dòng)作了。註:以上兩個(gè)演算法ADDQ( )及DELETEQ( ),若陣列起始編號(hào)是從0開(kāi)始,則可以加入或刪除n+1筆資料,若是從1開(kāi)始,則可以加入或刪除n筆資料。 16第二節(jié)佇列五、環(huán)狀佇列(Circular Queue) 將一筆資料加入circular queue中的演算法: Procedure ADDCQ(data, Q, n, front, rear)if(

9、rear MOD n)+1=front) then call QUEUE_FULL( )else Q(rear)data rear(rear MOD n)+1end ifend ADDCQ17第二節(jié)佇列自circular queue 中取出一筆資料,並刪除該資料的演算法: Procedure DELETECQ(data, Q, n, front, rear)if(front =rear) then call QUEUE_EMPTY( )else dataQ(front) front(front MOD n) + 1end if end DELETECQ 18第二節(jié)佇列以上兩個(gè)演算法ADDCQ( )及DELETECQ( ),若陣列起始編號(hào)是從1開(kāi)始,則可以加入或刪除n個(gè)資料;但若是從0開(kāi)始,則演算法須分別修改如下: (n必須大於0 才有意義) 19第二節(jié)佇列 Procedure ADDCQ(data, Q, n, front, rear)if (rear+1) MOD n=front) then call QUEUE_FULL( )else Q(rear)data rear(rear+1) MOD nend ifend ADD

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論