第3章棧與隊(duì)列(已修改).ppt

1 57 2 第3章棧和隊(duì)列 棧和隊(duì)列被稱為操作受限的線性表 本章介紹棧和隊(duì)列的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu) 以及棧和隊(duì)列的基本運(yùn)算以及實(shí)現(xiàn)算法 3 a1 a2 ai 1 ai ai 1 an 3 1棧 只允許在線性表的一端進(jìn)行插入和刪除操作的線性表允許插入和刪除的一端稱為棧頂 top 另一端稱為棧底 bottom 特點(diǎn)后進(jìn)先出 LIFO 4 棧的基本操作INITSTACK s 構(gòu)造一個空棧s STACKEMPTY s 判斷s是否為空棧 若s為空棧 返回1 否則返回0 PUSH s x 進(jìn)棧操作 在棧s頂部插入一個新的元素x POP s x 退棧操作 若s非空 刪除s中的棧頂元素 并返回該元素 5 GETTOP s 取棧s的棧頂元素 若s非空 返回棧頂元素 但與POP s x 的區(qū)別是GETTOP s 不改變棧的狀態(tài) CLEASTACK s 將棧s清為空棧 STACKLENGTH s 求棧的長度 返回棧s中的元素個數(shù) 6 棧的表示和實(shí)現(xiàn) 由于棧是運(yùn)算受限的線性表 因此線性表的存儲結(jié)構(gòu)對棧也適應(yīng) 1 順序棧棧的順序存儲結(jié)構(gòu) 順序棧 可以將棧底位置設(shè)置在數(shù)組的低地址端點(diǎn) 棧頂位置是隨著進(jìn)棧和退棧操作而變化的 故需用一個整型變量top 指明當(dāng)前棧頂?shù)奈恢?同樣將data數(shù)組和top封裝在一個結(jié)構(gòu)中 順序棧的類型描述如下 defineMAXSIZE1024typedefstructSeqStack datatypedata MAXSIZE inttop SeqStack 7 8 bottom bottom A A B C D E A B 棧操作圖示 A進(jìn)棧 BCDE進(jìn)棧 EDC出棧 C D E 棧的特點(diǎn)后進(jìn)先出LIFO 入棧與出棧 9 約定棧頂指針指向向棧頂元素的位置 順序棧的圖示 ?？?棧滿 Top 1 Top maxlen 1 10 2 順序棧的基本運(yùn)算算法 1 初始化棧voidINITSTACK seqstack s 創(chuàng)建一個空棧由指針S指向 s top 1 思考 voidINITSTACK seqstacks s top 1 哪個是對的 為什么 11 12 2 判棧空判定順序棧S是否空棧 S為空時 返回為1 非空時 返回為0intSTACKEMPTY seqstack s if s top 0 s top 0 return0 elsereturn1 13 3 入棧操作PUSH seqstacks datatypex if s top maxsize 1 error overflow returnNULL 上溢 退出運(yùn)行 else s top 棧頂指針 1 s data s top x 將x入棧 14 4 出棧操作datatypePOP seqstacks ifSTACKEMPTY s error underflow 下溢 returnNULL else return s data s top s top 15 5 取棧頂元素操作datatypeGETTOP seqstacks if STACKEMPTY s error stackisempty returnNULL ?？?elsereturn s data s top 取棧頂元素 16 順序棧的不足 存在棧滿以后就不能再進(jìn)棧的問題 這是因?yàn)橛昧硕ㄩL的數(shù)組存儲棧的元素 解決方法 使用鏈?zhǔn)酱鎯Y(jié)構(gòu) 17 2 鏈棧棧的鏈?zhǔn)酱鎯Y(jié)構(gòu) 也稱鏈棧 沒有頭結(jié)點(diǎn)的單鏈表 其各結(jié)點(diǎn)的結(jié)構(gòu)與單鏈表中的結(jié)點(diǎn)結(jié)構(gòu)完全相同 如圖所示 在前面學(xué)習(xí)了線性鏈表的插入刪除操作算法 不難寫出鏈?zhǔn)綏３跏蓟?進(jìn)棧 出棧等操作的算法 結(jié)點(diǎn)結(jié)構(gòu)定義 Typedefstructnode elemtypedata structnode next node pointer 18 1 初始化棧Voidinitstack pointers s null 19 進(jìn)棧前進(jìn)棧后 2 進(jìn)棧 20 進(jìn)棧算法Voidpush pointers datatypex p pointer malloc sizeof node p data x p next s s p 21 出棧前出棧后 3 出棧 22 出棧算法 Datatypepop pointers if s null return null else p s x p data s p next free p return x 23 3 2隊(duì)列 隊(duì)列是只允許在一端刪除 在另一端插入的順序表允許刪除的一端叫做隊(duì)頭 front 允許插入的一端叫做隊(duì)尾 rear 特性先進(jìn)先出 FIFO FirstInFirstOut 24 隊(duì)列的基本運(yùn)算 隊(duì)列初始化 Init Queue q 初始條件 隊(duì)q不存在 操作結(jié)果 構(gòu)造一個空隊(duì) 入隊(duì)操作 In Queue q x 初始條件 隊(duì)q存在 操作結(jié)果 對已存在的隊(duì)列q 插入一個元素x到隊(duì)尾 隊(duì)發(fā)生變化 出隊(duì)操作 Out Queue q x 初始條件 隊(duì)q存在且非空操作結(jié)果 刪除隊(duì)首元素 并返回其值 隊(duì)發(fā)生變化 讀隊(duì)頭元素 Front Queue q x 初始條件 隊(duì)q存在且非空操作結(jié)果 讀隊(duì)頭元素 并返回其值 隊(duì)不變 判隊(duì)空操作 Empty Queue q 初始條件 隊(duì)q存在操作結(jié)果 若q為空隊(duì)則返回為1 否則返回為0 25 隊(duì)列的存儲結(jié)構(gòu)及操作實(shí)現(xiàn) 1 鏈隊(duì)列用鏈表表示的隊(duì)列簡稱為鏈隊(duì)列 在一個鏈隊(duì)列中需設(shè)定兩個指針 頭指針和尾指針 分別指向隊(duì)列的頭和尾 給鏈隊(duì)列添加一個頭結(jié)點(diǎn) 并設(shè)定頭指針指向頭結(jié)點(diǎn) 空隊(duì)列的判定條件為頭指針和尾指針都指向頭結(jié)點(diǎn) 26 typedefstructnode datatypedata structnode next QNode 鏈隊(duì)結(jié)點(diǎn)的類型 typedefstruct QNnode front rear LQueue 將頭尾指針封裝在一起的鏈隊(duì) 27 討論 空鏈隊(duì)的特征 怎樣實(shí)現(xiàn)鏈隊(duì)的入隊(duì)和出隊(duì)操作 鏈隊(duì)會滿嗎 front rear 一般不會 因?yàn)閯h除時有free動作 除非內(nèi)存不足 入隊(duì) 尾部插入 rear next S rear S 出隊(duì) 頭部刪除 front next p next 鏈隊(duì)示意圖 28 刪除 一個元素 添加一個元素 e Q front Q rear 隊(duì)頭 隊(duì)尾 Q rear 注意 linkqueueQ 29 鏈隊(duì)列的主要運(yùn)算算法 置空隊(duì)列voidINITQUEUE linkqueue q 構(gòu)造一個只含頭結(jié)點(diǎn)的空隊(duì)列 q linkqueue malloc sizeof linkqueue q rear q front 尾指針指向頭結(jié)點(diǎn) q front next NULL 頭結(jié)點(diǎn)指針為空 置空隊(duì)列voidINITQUEUE linkqueueq 構(gòu)造一個只含頭結(jié)點(diǎn)的空隊(duì)列 q rear q front 尾指針指向頭結(jié)點(diǎn) q front next NULL 頭結(jié)點(diǎn)指針為空 注意 linkqueue Q 注意 linkqueueQ 30 判隊(duì)空boolEMPTYQUEUE linkqueue q 判斷隊(duì)列是否為空 為空返回TRUE 否則返回FALSE if q front q rear return TRUE elsereturn FALSE 31 入隊(duì)voidENQUEUE linkqueue q datatypee 將元素e插入鏈隊(duì)列尾部 p queuenode malloc sizeof queuenode p data e p next NULL q rear next p q rear p 32 出隊(duì)datatypeDEQUEUE linkqueue q datatype 33 取隊(duì)頭元素datatypeGETFIRST linkqueue q if EMPTYQUEUE q printf EMPTYQUEUE returnNULL 隊(duì)列空 elsereturn q front next data GETFIRST 34 2 順序隊(duì)列隊(duì)列的順序存儲結(jié)構(gòu)可以簡稱為順序隊(duì)列 用一組地址連續(xù)的存儲單元依次存放隊(duì)列中的數(shù)據(jù)元素 設(shè)立兩個指示器 指向隊(duì)頭元素的指示器front 指向隊(duì)尾的元素位置的指示器rear 35 a 線性隊(duì)列 e2 c e2入隊(duì) e0 e1出隊(duì) rear 3 front e0 e1 b rear front b e0 e1入隊(duì) 隊(duì)空時 令rear front 0 當(dāng)有新元素入隊(duì)時 尾指針加1 當(dāng)有元素出隊(duì)時 頭指針加1 故在非空隊(duì)列中 頭指針始終指向隊(duì)頭元素位置 而尾指針始終指向隊(duì)尾元素的下一位置 36 順序隊(duì)列的類型定義如下 definemax100 隊(duì)列最大長度 typedefstructsequeue datatypedata max intfront intrear sequeue 順序隊(duì)列類型 sequeue sq sq為順序隊(duì)列類型的指針 37 順序隊(duì)列的缺點(diǎn) 當(dāng)前隊(duì)列并未占滿 但隊(duì)列中元素出隊(duì)后讓出的實(shí)際可用空間卻不能得以使用 因此把這種溢出現(xiàn)象稱為 假溢出 解決辦法之一 將隊(duì)列元素存放數(shù)組首尾相接 形成循環(huán) 環(huán)形 隊(duì)列 38 循環(huán)隊(duì)列 在將順序隊(duì)列的存儲區(qū)假想為一個環(huán)狀的空間 假想q queue 0 接在q queue MAXNUM 1 的后面 當(dāng)發(fā)生假溢出時 將新元素插入到第一個位置上 入列和出列仍按 先進(jìn)先出 的原則進(jìn)行 首指針front和尾指針rear沿環(huán)順時針移動 只要尾指針rear不與首指針相遇 該隊(duì)列就可繼續(xù)操作 稱這種隊(duì)列為循環(huán)隊(duì)列 sequeue sq sq為順序隊(duì)列類型的指針 sqq q為順序隊(duì)列sq類型 39 循環(huán)隊(duì)列為隊(duì)列空時 有q front q rear q front rear 隊(duì)列滿時 也有q front q rear 因此僅憑q front q rear不能判定隊(duì)列是空還是滿 規(guī)定循環(huán)隊(duì)列中少用一個元素空間 以尾指針在頭指針的前一位置作為隊(duì)列滿的條件 40 0 1 2 3 4 5 6 7 front 0 1 2 3 4 5 6 7 front 0 1 2 3 4 5 6 7 front rear A A B C rear rear 空隊(duì)列 A進(jìn)隊(duì) B C進(jìn)隊(duì) 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 A退隊(duì) B退隊(duì) 0 1 2 3 4 5 6 7 D E F G H進(jìn)隊(duì) 隊(duì)滿 front B C rear A front B C rear front C rear D E F G H I 41 隊(duì)空條件 front rear 初始化時 front rear 隊(duì)滿條件 front rear 1 N N maxsize 隊(duì)列長度 即數(shù)據(jù)元素個數(shù) L N rear front N 令front指向?qū)嵲?rear指向空閑元素 問3 在具有N個單元的循環(huán)隊(duì)列中 隊(duì)滿時共有多少個元素 N 1個 6 問1 左圖中隊(duì)列maxsizeN 問2 左圖中隊(duì)列長度L 5 42 r f n f r n n r f n r f n 要分析4種公式哪種最合理 當(dāng)r f時 A 合理 當(dāng)r f時 C 合理 答 綜合2種情況 以 D 的表達(dá)最為合理 例2 在一個循環(huán)隊(duì)列中 若約定隊(duì)首指針指向隊(duì)首元素的前一個位置 那么 從循環(huán)隊(duì)列中刪除一個元素時 其操作是先 移動隊(duì)首指針 取出元素 后 例1 數(shù)組 n 用來表示一個循環(huán)隊(duì)列 f為當(dāng)前隊(duì)列頭元素的前一位置 r為隊(duì)尾元素的位置 假定隊(duì)列中元素的個數(shù)小于n 計(jì)算隊(duì)列中元素的公式為 43 例3 一循環(huán)隊(duì)列如下圖所示 若先刪除4個元素 接著再插入4個元素 請問隊(duì)頭和隊(duì)尾指針分別指向哪個位置 解 由圖可知 隊(duì)頭和隊(duì)尾指針的初態(tài)分別為front 1和rear 0 刪除4個元素后f 5 再插入4個元素后 r 0 4 6 4 rear 4 44 2 循環(huán)隊(duì)列的操作實(shí)現(xiàn) 初始化操作 注意 這里的sq為變量 算法voidINITQUEUE sequeue sq sq sequeue malloc sizeof sequeue sq front 0 sq rear 0 頭 尾指針指向位置0 初始化操作算法voidINITQUEUE sequeuesq sq front 0 sq rear 0 頭 尾指針指向位置0 45 判隊(duì)空操作算法intEMPTYQUEUE sequeue sq 判斷循環(huán)隊(duì)列是否為空 if sq rear sq front return1 elsereturn0 46 入隊(duì)操作算法voidENQUEUE sequeue 47 出隊(duì)操作算法datatypeDEQUEUE sequeue sq datatypee 若隊(duì)列非空從隊(duì)頭刪除一個元素 if EMPTYQUEUE sq returnNULL 隊(duì)列空 else e sq data sq front sq front sq front 1 max return e 48 取隊(duì)頭元素算法datatypeGETFIRST sequeue sq if EMPTYQUEUE sq returnNULL elsereturn sq data sq front 49 停車車管理系統(tǒng) 設(shè)停車場內(nèi)只有一個可停放n輛汽車的狹長通道 且只有一個大門可供汽車進(jìn)出 汽車在停車場內(nèi)按車輛到達(dá)時間的先后順序 依次由北向南排列 大門在最南端 最先到達(dá)的第一輛車停放在車場的最北端 若車場內(nèi)已停滿n輛汽車 則后來的汽車只能在門外的便道上等候 一旦有車開走 則排在便道上的第一輛車即可開入 當(dāng)停車場內(nèi)某輛車要離開時 在它之后開入的車輛必須先退出車場為它讓路 待該輛車開出大門外 其它車輛再按原次序進(jìn)入車場 每輛停放在