版權(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 中醫(yī)體質(zhì)的生理與病理
- 臨床醫(yī)學(xué)教學(xué)設(shè)計(jì)
- 2024年江西省精神病院高層次衛(wèi)技人才招聘筆試歷年參考題庫(kù)頻考點(diǎn)附帶答案
- 2024年江津市工人醫(yī)院高層次衛(wèi)技人才招聘筆試歷年參考題庫(kù)頻考點(diǎn)附帶答案
- 呼吸濕化治療的使用
- 2024年07月江蘇交通銀行江蘇分行社會(huì)招考(79)筆試歷年參考題庫(kù)附帶答案詳解
- 滬科版 信息技術(shù) 必修 2.4 信息價(jià)值的判斷 說(shuō)課稿001
- 第12課《醉翁亭記》說(shuō)課稿 2024-2025學(xué)年統(tǒng)編版語(yǔ)文九年級(jí)上冊(cè)
- 2024版特許經(jīng)營(yíng)延期合同協(xié)議
- 《動(dòng)機(jī)與激勵(lì)》課件
- 年度分析報(bào)告格式范文
- 2024年度吉林省國(guó)家電網(wǎng)招聘之法學(xué)類典型題匯編及答案
- 2024年世界職業(yè)院校技能大賽中職組“嬰幼兒保育組”賽項(xiàng)考試題庫(kù)-下(多選、判斷題)
- 2024電力建設(shè)工程質(zhì)量問(wèn)題通病防止手冊(cè)
- 【初中地理】世界的聚落+課件-2024-2025學(xué)年七年級(jí)地理上學(xué)期(湘教版2024)
- 辯論英文課件教學(xué)課件
- 2023-2024學(xué)年四川省宜賓市八年級(jí)上學(xué)期期末數(shù)學(xué)試卷及參考答案
- (統(tǒng)編版2024)語(yǔ)文七年級(jí)上冊(cè) 第四單元寫(xiě)作《思路要清晰》 課件(新教材)
- 浙江省臺(tái)州市2023-2024學(xué)年高一上學(xué)期期末考試 化學(xué) 含答案
- 2024年度工作總結(jié)模板
- 銑工高級(jí)工測(cè)試題(含答案)
評(píng)論
0/150
提交評(píng)論