




版權(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 礦石浮選工藝優(yōu)化-石墨滑石選礦考核試卷
- 畜禽繁殖力與遺傳改良研究考核試卷
- 紡織材料與纖維的研究與發(fā)展考核試卷
- 電腦系統(tǒng)優(yōu)化與提速技巧考核試卷
- 筆的制造生產(chǎn)計(jì)劃編制與執(zhí)行考核試卷
- 嘉興南湖學(xué)院《Python數(shù)據(jù)分析與應(yīng)用》2023-2024學(xué)年第二學(xué)期期末試卷
- 昆明理工大學(xué)津橋?qū)W院《CAD制圖》2023-2024學(xué)年第二學(xué)期期末試卷
- 咸陽(yáng)市2025年三年級(jí)數(shù)學(xué)第二學(xué)期期末學(xué)業(yè)水平測(cè)試試題含解析
- 日照職業(yè)技術(shù)學(xué)院《國(guó)際商務(wù)創(chuàng)業(yè)策劃案例分析》2023-2024學(xué)年第二學(xué)期期末試卷
- 寧德市周寧縣2024-2025學(xué)年數(shù)學(xué)四年級(jí)第二學(xué)期期末考試試題含解析
- 2025年入團(tuán)相關(guān)考試題型及答案
- 2023-2024學(xué)年北京市西城區(qū)德勝中學(xué)七年級(jí)(下)期中數(shù)學(xué)試卷
- 皮膚病靶向治療專(zhuān)家共識(shí)(2025版)解讀課件
- DB37-T 3274.3-2023 日光溫室建造技術(shù)規(guī)范 第3部分:山東VI型
- 《四輪驅(qū)動(dòng)電動(dòng)汽車(chē)制動(dòng)系統(tǒng)設(shè)計(jì)》14000字(論文)
- 鄭州食品工程職業(yè)學(xué)院《中國(guó)宗教史》2023-2024學(xué)年第一學(xué)期期末試卷
- 新蘇教版一年級(jí)數(shù)學(xué)下冊(cè)綜合實(shí)踐活動(dòng)1《抓抓數(shù)數(shù)》教案
- RoHS知識(shí)培訓(xùn)課件
- 醫(yī)學(xué)課件痛風(fēng)性關(guān)節(jié)炎
- 流程建設(shè)培訓(xùn)課件
- 水利工程冬季低溫施工方案
評(píng)論
0/150
提交評(píng)論