算法資料循環(huán)隊(duì)列_第1頁(yè)
算法資料循環(huán)隊(duì)列_第2頁(yè)
算法資料循環(huán)隊(duì)列_第3頁(yè)
算法資料循環(huán)隊(duì)列_第4頁(yè)
算法資料循環(huán)隊(duì)列_第5頁(yè)
已閱讀5頁(yè),還剩27頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

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

文檔簡(jiǎn)介

1、3.2循環(huán)隊(duì)列目錄隊(duì)列的邏輯結(jié)構(gòu)和基本計(jì)算隊(duì)列的存儲(chǔ)結(jié)構(gòu)循環(huán)隊(duì)列的運(yùn)算隊(duì)列的概念隊(duì)列是一種只允許在表的一端(稱為隊(duì)尾)進(jìn)行插入,在另一端(稱為對(duì)頭)進(jìn)行刪除的線性表。隊(duì)列的概念隊(duì)列是一種只允許在表的一端(稱為隊(duì)尾)進(jìn)行插入,在另一端(稱為對(duì)頭)進(jìn)行刪除的線性表。只能刪除隊(duì)頭的結(jié)點(diǎn)a1只能在隊(duì)尾插入結(jié)點(diǎn)x增加結(jié)點(diǎn)刪除結(jié)點(diǎn)隊(duì)列的概念隊(duì)列是一種只允許在表的一端(稱為隊(duì)尾)進(jìn)行插入,在另一端(稱為對(duì)頭)進(jìn)行刪除的線性表。 先排隊(duì)的先離開(kāi)與我們生活中的排隊(duì)非常相似 晚排隊(duì)的晚離開(kāi) 不允許插隊(duì) 不允許中途離隊(duì)隊(duì)列有5種基本運(yùn)算因此,隊(duì)列也稱先進(jìn)先出(FIFO)來(lái)使用和管理隊(duì)列。隊(duì)列的5種基本運(yùn)算將隊(duì)列Q置

2、成空隊(duì)列置隊(duì)空SetNull(Q)獲取有效結(jié)點(diǎn)長(zhǎng)度GetLength(Q)取頭結(jié)點(diǎn)GetHead(Q)入隊(duì)InsQueue(Q, x)出隊(duì)DelQueue(Q)54321隊(duì)列的5種基本運(yùn)算N個(gè)結(jié)點(diǎn)數(shù)返回隊(duì)列中的結(jié)點(diǎn)數(shù)置隊(duì)空SetNull(Q)獲取有效結(jié)點(diǎn)長(zhǎng)度GetLength(Q)若N為零,則為空隊(duì)列取頭結(jié)點(diǎn)GetHead(Q)入隊(duì)InsQueue(Q, x)出隊(duì)DelQueue(Q)54321隊(duì)列的5種基本運(yùn)算讀取隊(duì)列Q中頭結(jié)點(diǎn)的值置隊(duì)空SetNull(Q)隊(duì)列中的結(jié)點(diǎn)保持不變獲取有效結(jié)點(diǎn)長(zhǎng)度GetLength(Q)取頭結(jié)點(diǎn)GetHead(Q)入隊(duì)InsQueue(Q, x)出隊(duì)DelQue

3、ue(Q)54321隊(duì)列的5種基本運(yùn)算x將結(jié)點(diǎn)x插入到隊(duì)列Q的隊(duì)尾置隊(duì)空SetNull(Q)獲取有效結(jié)點(diǎn)長(zhǎng)度GetLength(Q)取頭結(jié)點(diǎn)GetHead(Q)入隊(duì)InsQueue(Q, x)出隊(duì)DelQueue(Q)54321隊(duì)列的5種基本運(yùn)算刪除隊(duì)列頭結(jié)點(diǎn)置隊(duì)空SetNull(Q)獲取有效結(jié)點(diǎn)長(zhǎng)度GetLength(Q)取頭結(jié)點(diǎn)GetHead(Q)入隊(duì)InsQueue(Q, x)出隊(duì)DelQueue(Q)54321目錄隊(duì)列的邏輯結(jié)構(gòu)和基本計(jì)算隊(duì)列的存儲(chǔ)結(jié)構(gòu)循環(huán)隊(duì)列的運(yùn)算隊(duì)列的存儲(chǔ)結(jié)構(gòu)常用隊(duì)列的存儲(chǔ)結(jié)構(gòu)順序隊(duì)列循環(huán)隊(duì)列鏈接隊(duì)列本章重點(diǎn)講解順序隊(duì)列的存儲(chǔ)結(jié)構(gòu)一維數(shù)組來(lái) 存放節(jié)點(diǎn)數(shù)據(jù)數(shù)組下標(biāo)01

4、2amsizea1 a2 a3當(dāng)隊(duì)列采用順序存儲(chǔ)結(jié)構(gòu)時(shí),可利用一維數(shù)組來(lái)存放結(jié)點(diǎn)數(shù)據(jù)。ann - 1nmsize - 1順序隊(duì)列的存儲(chǔ)結(jié)構(gòu)必須有活動(dòng)的 表頭和表尾的索引一維數(shù)組來(lái) 存放節(jié)點(diǎn)數(shù)據(jù)數(shù)組下標(biāo)012amsize隊(duì)列的操作只能在表頭和表尾進(jìn)行,且不移動(dòng)隊(duì)列的結(jié)點(diǎn)。headn - 1n頭尾索引即頭尾結(jié)點(diǎn)對(duì)應(yīng)的數(shù)組下標(biāo)tailmsize - 1a1a2a3an順序隊(duì)列的結(jié)構(gòu)描述一維數(shù)組來(lái) 存放節(jié)點(diǎn)數(shù)據(jù)數(shù)組下標(biāo)012amsizen - 1nmsize - 1#definemsize128隊(duì)中可能he最a大d 結(jié)點(diǎn)數(shù)a1typedefstructa2a3unsigned chararraumsi

5、ze;隊(duì)中的結(jié)點(diǎn)存于一維數(shù)組中unsigned charhead;頭索引anunsgined chartail;尾索引tailQueue;順序隊(duì)列的存儲(chǔ)結(jié)構(gòu)當(dāng)要?jiǎng)h除一結(jié)點(diǎn)時(shí)一維數(shù)組來(lái) 存放節(jié)點(diǎn)數(shù)據(jù)數(shù)組下標(biāo)012amsizehead出隊(duì)運(yùn)算可描述為:head+;n - 1ntailmsize - 1再將頭索引加1, 使其指向下一結(jié)點(diǎn)a1a2a3an必須刪除索引head所指向的結(jié)點(diǎn)順序隊(duì)列的存儲(chǔ)結(jié)構(gòu)當(dāng)要插入一結(jié)點(diǎn)時(shí)amsize入隊(duì)運(yùn)算可描述為:arraytail+;012headn - 1ntailmsize - 1再將頭索引加1, 使其指向下一結(jié)點(diǎn)必須將結(jié)點(diǎn)值插入到尾索引tail所指向的結(jié)點(diǎn)a1

6、a2a3anx順序隊(duì)列的存儲(chǔ)結(jié)構(gòu)當(dāng)隊(duì)列裝滿時(shí)amsize產(chǎn)生該現(xiàn)象的原因是:被刪除的結(jié)點(diǎn)(出隊(duì)結(jié)點(diǎn)) 的空間永遠(yuǎn)不能再使用。012headn - 1nmsize - 1尾索引tail等于最大結(jié)點(diǎn)msize時(shí),采用循環(huán)隊(duì)列當(dāng)隊(duì)滿時(shí),若再做入隊(duì) tail操作會(huì)產(chǎn)生“上溢”a1a2a3an后果不可預(yù)測(cè)循環(huán)隊(duì)列將將順序隊(duì)列的數(shù)組設(shè)想為一個(gè)首尾相接的圓環(huán),即接在arraymsize -1之后的是array0。amsizea1012head1這種意義的隊(duì)列稱為循環(huán)隊(duì)列。a2a2 a3a1head0anann - 1n - 1mtasiilze - 1n在入隊(duì)和出隊(duì)操作時(shí)須對(duì)頭尾索引進(jìn)行特殊處理ntail

7、msize - 1循環(huán)隊(duì)列的入隊(duì)出隊(duì)操作amsize1a2a1headtail0ann - 1msize - 1tail利用模運(yùn)算, 則可優(yōu)化為:tailnarraytail+ = x; tail % = msize;入隊(duì)后尾索引加1尾索引求模arraytail+ = x; if (tail =msize)tail = 0;入隊(duì)后尾索引加1若尾索引上溢則置尾索引為上界循環(huán)隊(duì)列的入隊(duì)出隊(duì)操作amsize1a2head0a1tailann - 1msize - 1nhead+;head % = msize;入隊(duì)后尾索引加1尾索引求模循環(huán)隊(duì)列的隊(duì)空與隊(duì)滿情況分析cdbaefgh如何確定隊(duì)空還是隊(duì)滿呢

8、?headtailhead tail循環(huán)隊(duì)列的類型定義count = 0head tailcount = msizecdbeheadaftailhg循環(huán)隊(duì)列的類型定義去掉尾索引#define typedefmsizestruct128增加結(jié)構(gòu)描述countunsigned char unsigned char unsgined charQueue;arraumsize; head;tail;#definemsize128typedefstructunsigned chararraumsize; unsigned charhead; unsgined charcount;Queue;有效結(jié)點(diǎn)數(shù)c

9、ount = 0head tail去掉尾索引count = msizecdbeheadaf hgtail循環(huán)隊(duì)列的類型定義#definemsize128count初始值為0typedefstruct u入隊(duì)時(shí),count加一head + countu 出un隊(duì)sig時(shí)ne,d ccohuanrt減arr一aumsize;u 滿un隊(duì)sig時(shí)ne,d cchoaurnth等ea于d;msizeunsgined charcount;u 空隊(duì)時(shí),count等于0Queue;有效結(jié)點(diǎn)數(shù)#definemsize128typedefstructunsigned chararrau tail =msize;

10、unsigned charhead; unsgined chartail;Queue;增加結(jié)構(gòu)描述countcount = 0head tailcount = msizecdbeheadaf tailhg目錄隊(duì)列的邏輯結(jié)構(gòu)和基本計(jì)算隊(duì)列的存儲(chǔ)結(jié)構(gòu)循環(huán)隊(duì)列的運(yùn)算循環(huán)隊(duì)列的運(yùn)算置隊(duì)空獲取有效結(jié)點(diǎn)長(zhǎng)度取頭結(jié)點(diǎn)入隊(duì)出隊(duì)置隊(duì)空置隊(duì)空獲取有效結(jié)點(diǎn)長(zhǎng)度習(xí)慣上也可順便取頭結(jié)點(diǎn)將頭索引置為0入隊(duì)只要將隊(duì)列的有效結(jié)點(diǎn)數(shù)置為0即可置隊(duì)空出隊(duì)void SetNull(lpQueue * lp)lp head= 0;lp count = 0;獲取有效結(jié)點(diǎn)長(zhǎng)度置隊(duì)空獲取有效結(jié)點(diǎn)長(zhǎng)度取頭結(jié)點(diǎn)入隊(duì)出隊(duì)unsigned cha

11、r GetLength(lpQueue * lp)return (lp count);獲取有效結(jié)點(diǎn)長(zhǎng)度置隊(duì)空獲取有效結(jié)點(diǎn)長(zhǎng)度取頭結(jié)點(diǎn)入隊(duì)出隊(duì)unsigned char GetHead(lpQueue * lp)return (lp arraylp head);獲取有效結(jié)點(diǎn)長(zhǎng)度置隊(duì)空獲取有效結(jié)點(diǎn)長(zhǎng)度取頭結(jié)點(diǎn)入隊(duì)出隊(duì)BOOL InsQueue(lpQueue * lp, unsigned char x)return TRUE; else return FALSE;if (lp count msize) lp array(lp head lp count)% msize = x;lp count+;獲取有效結(jié)點(diǎn)長(zhǎng)度unsigned char DelQueue(lpQueue * lp

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 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ì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論