第三章棧和隊(duì)列

第三章棧和隊(duì)列 2 教學(xué)目標(biāo)掌握棧和隊(duì)列的基本概念 ADT描述方法 掌握棧的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的基本操作及其實(shí)現(xiàn)算法 掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法 學(xué)會(huì)運(yùn)用棧和隊(duì)列解決實(shí)際問題 3 1棧3 2棧的應(yīng)用舉例3 4隊(duì)列 3 棧和隊(duì)列是兩種常用的數(shù)據(jù)類型 棧和隊(duì)列也是兩種特殊的線性表 它們是運(yùn)算時(shí)要受到某些限制的線性表 故也稱為限定性的數(shù)據(jù)結(jié)構(gòu) 通常稱 棧和隊(duì)列是限定插入和刪除只能在表的 端點(diǎn) 進(jìn)行的線性表 4 如果所有的操作均被限定在線性表的一端 那么就稱該線性表為棧 Stack 如果線性表的一端僅允許插入元素 而另一端僅允許刪除元素 那么該線性表被稱為隊(duì)列 Queue 棧和隊(duì)列是兩種在計(jì)算機(jī)程序設(shè)計(jì)中廣泛運(yùn)用的線性表 5 一 棧的概念 3 1棧的概念 3 1棧 1 棧的定義 棧 限定只能在表的一端進(jìn)行插入和刪除的特殊的線性表設(shè)棧s a1 a2 ai an 其中a1是棧底元素 an是棧頂元素 出棧 棧頂 top 允許插入和刪除的一端 約定top始終指向新數(shù)據(jù)元素將存放的位置 棧底 bottom 不允許插入和刪除的一端 插入 即進(jìn)棧 在n 1位置插入 刪除 即出棧 刪除第n位置元素 棧的特點(diǎn)后進(jìn)先出 6 2 棧的類型定義 抽象數(shù)據(jù)類型棧的定義如下 P44 3 1棧的概念 7 3 1棧的表示和實(shí)現(xiàn) 二 棧的表示和實(shí)現(xiàn) 1 順序存儲(chǔ)和實(shí)現(xiàn) 順序棧 用一組連續(xù)的存儲(chǔ)單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素 一般用一維數(shù)組表示 設(shè)置一個(gè)簡(jiǎn)單變量top指示棧頂位置 稱為棧頂指針top 約定棧頂指針指向棧頂元素的下一個(gè)位置 8 進(jìn)棧 A 出棧 B C D E F 棧滿 ?？?棧頂指針top 指向?qū)嶋H棧頂后的空位置 初值為0 當(dāng)棧滿時(shí)再做進(jìn)棧運(yùn)算必定產(chǎn)生空間溢出 簡(jiǎn)稱 上溢 overflow 當(dāng)?？諘r(shí)再做退棧運(yùn)算也將產(chǎn)生溢出 簡(jiǎn)稱 下溢 underflow 3 1棧的表示實(shí)現(xiàn) 9 上溢是一種出錯(cuò)狀態(tài) 應(yīng)該設(shè)法避免之 下溢則可能是正?，F(xiàn)象 因?yàn)闂Ｔ诔绦蛑惺褂脮r(shí) 其初態(tài)或終態(tài)都是空棧 所以下溢常常用來作為程序控制轉(zhuǎn)移的條件 順序棧的操作算法 順序棧的類型定義 棧的順序存儲(chǔ)表示 defineSTACK NINT SIZE100 存儲(chǔ)空間初始分配量 defineSTACKINCREMENT10 存儲(chǔ)空間分配增量typedefstruct SElemType base 在棧構(gòu)造之前和銷毀之后 bade的值為NULLSElemType top 棧頂指針intstacksize 當(dāng)前已分配的存儲(chǔ)空間 以元素為單位 SqStack 10 11 3 1棧的表示和實(shí)現(xiàn) 2 判斷棧是否為滿 3 判斷棧是否為空 12 3 1棧的表示和實(shí)現(xiàn) 4 取棧頂元素 13 3 1棧的表示和實(shí)現(xiàn) 5 進(jìn) 壓 棧push StatusPush SqStack push 分析演示 14 3 1棧的表示和實(shí)現(xiàn) statusPop SqStack Pop 6 出棧pop 分析演示 15 例1 如書中P44頁圖3 1 b 所示鐵道車廂調(diào)度 1 如果進(jìn)站的車廂序列為123 則可能得到的出站車廂序列是什么 2 如果進(jìn)站的車廂序列為123456 則能否得到435612和135426的出站序列 16 例2 如下列算法 執(zhí)行完后能輸出什么結(jié)果 Voidmain stacks charx y initstack s x c y k push s x push s a push s y pop s x push s t push s x pop s x push s s while Stackempty s pop s y printf y printf x c a y 由上算法分析 設(shè)定了棧S 棧S的元素類型為char push為進(jìn)棧 pop為出棧 棧S t c s x k 17 例3 棧S中存放了已知數(shù)組a 2 4 6 8 10 中的元素 寫一算法將數(shù)組中的值逆置 即 a 1 的值2與a 5 的值10互換 如下圖 Statusalgo1 stacks inti n a 5 n 0 While stackempty s n pop s a n for i 1 i 5 i push s a i 18 2 鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn) 3 1棧的表示和實(shí)現(xiàn) 鏈棧 即棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 與線性鏈表類似 如圖所示 注意 鏈棧中指針的方向 19 3 1棧的表示和實(shí)現(xiàn) 鏈棧的操作算法 鏈棧的類型定義 typedefstructLNode 結(jié)點(diǎn)類型ElemTypedata structLNode next Lnode Linkstack LinkstackS StatusInitLStack Linkstack InitLStack 1 建立一個(gè)空棧 20 StatusGettopLStack Linkstack GettopLStack 2 取棧頂元素 3 1棧的表示和實(shí)現(xiàn) 21 StatusPushLStack Linkstack PushLStack 3 進(jìn) 壓 棧push 22 3 1棧的表示和實(shí)現(xiàn) StatusPopLStack Linkstack PopLStack 4 出棧push 23 3 1棧的表示和實(shí)現(xiàn) 例4 在棧頂指針為HS的鏈棧中 寫出計(jì)算該鏈棧中結(jié)點(diǎn)個(gè)數(shù)的函數(shù) Intcount LinkListHS LinkListp intn 0 p HS While P n p p next return n 24 例若進(jìn)棧序列為3 5 7 9 進(jìn)棧過程中可以出棧 則不可能的一個(gè)出棧次序是 7 5 3 9 b 9 7 5 3 c 7 5 9 3 d 9 5 7 3 例用一維數(shù)組設(shè)計(jì)棧 初態(tài)是?？?top 0 現(xiàn)有輸入序列是a b c d 經(jīng)過push push pop push pop push操作后 輸出序列是 棧頂指針是 b c 2 d 25 小結(jié)1棧是限定僅能在表尾一端進(jìn)行插入 刪除操作的線性表 2棧的元素具有后進(jìn)先出的特點(diǎn) 3棧頂元素的位置由一個(gè)稱為棧頂指針的變量指示 進(jìn)棧 出棧操作要修改棧頂指針 26 3 2棧的應(yīng)用舉例 例1數(shù)制轉(zhuǎn)換對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制數(shù) 顯示輸出與其等值的八進(jìn)制數(shù) 3 2棧的應(yīng)用 例把十進(jìn)制數(shù)159轉(zhuǎn)換成八進(jìn)制數(shù) 27 3 2棧的應(yīng)用 voidconversion InitStack s 建空棧scanf d 28 3 2棧的應(yīng)用 例2括號(hào)匹配的檢驗(yàn) 假設(shè)在表達(dá)式中 或 等為正確的格式 或 或 均為不正確的格式 則檢驗(yàn)括號(hào)是否匹配的方法 可用 期待的急迫程度 這個(gè)概念來描述 例如 考慮下列括號(hào)序列 12345678 分析可能出現(xiàn)的不匹配的情況 到來的右括弧并非是所 期待 的 到來的是 不速之客 直到結(jié)束 也沒有到來所 期待 的括弧 29 3 2棧的應(yīng)用 算法的設(shè)計(jì)思想 1 凡出現(xiàn)左括弧 則進(jìn)棧 2 凡出現(xiàn)右括弧 首先檢查棧是否空若?？?則表明該 右括弧 多余 否則和棧頂元素比較 若相匹配 則 左括弧出棧 否則表明不匹配 3 表達(dá)式檢驗(yàn)結(jié)束時(shí) 若?？?則表明表達(dá)式中匹配正確 否則表明 左括弧 有余 30 3 2棧的應(yīng)用 Statusmatching string 31 例3行編輯程序問題 在用戶輸入一行的過程中 允許用戶輸入出差錯(cuò) 并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正 合理的作法是 設(shè)立一個(gè)輸入緩沖區(qū) 用以接受用戶輸入的一行字符 然后逐行存入用戶數(shù)據(jù)區(qū) 并假設(shè) 為退格符 為退行符 假設(shè)從終端接受了這樣兩行字符 whli ilr e s s outcha putchar s 則實(shí)際有效的是下列兩行 while s putchar s 3 2棧的應(yīng)用 32 while ch EOF 從終端接收下一個(gè)字符 ClearStack S 重置S為空棧if ch EOF ch getchar while ch EOF EOF為全文結(jié)束符 將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū) 3 2棧的應(yīng)用 33 例4表達(dá)式求值 表達(dá)式的構(gòu)成操作數(shù) 運(yùn)算符 界符 如括號(hào) 表達(dá)式的求值 按照四則運(yùn)算法則 例5 6 1 2 4計(jì)算過程為 5 6 1 2 4 5 6 3 4 5 18 4 23 4 19 1 2 3 4 3 2棧的應(yīng)用 表達(dá)式求值是程序設(shè)計(jì)語言編譯中的一個(gè)最基本問題 它的實(shí)現(xiàn)需要借助棧來完成 介紹一種簡(jiǎn)單直觀 廣為使用的算法 即 算符優(yōu)先法 34 表達(dá)式中任何相鄰運(yùn)算符c1 c2的優(yōu)先關(guān)系有 c1c2 c1的優(yōu)先級(jí)高于c2 注 c1c2是相鄰算符 c1在左 c2在右 算符間的優(yōu)先關(guān)系表 3 2棧的應(yīng)用 35 基本思想 實(shí)現(xiàn)算符優(yōu)先算法 可以使用兩個(gè)工作棧 一個(gè)稱為OPTR 用以寄存運(yùn)算符 另一個(gè)稱為OPND 用以寄存操作數(shù)或運(yùn)算結(jié)果 1 首先置操作數(shù)棧為空棧 表達(dá)式起始符 為運(yùn)算符的棧底元素 2 依次讀入表達(dá)式中每個(gè)字符 若是操作數(shù)則進(jìn)OPND棧 若是運(yùn)算符 則和OPTR棧的棧頂運(yùn)算符比較 高進(jìn)棧 否則低于或相同則作相應(yīng)操作 直至整個(gè)表達(dá)式求值完畢 即OPTR棧的棧頂元素和當(dāng)前讀入的字符均為 例 S 4 2 3 10 5 36 如下所示 操作過程 例如 利用算符優(yōu)先算法對(duì)算術(shù)表達(dá)式3 7 2 求值 37 OperandTypeEvaluateExpression 算術(shù)表達(dá)式求值設(shè)OPTR和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧 InitStack OPET Push OPTR initStack OPND c getchar while c GetTop OPTR if In c OP Push OPND c c getchar 不是運(yùn)算符則進(jìn)棧elseswitch Precede GetTop OPTR c case 棧頂元素優(yōu)先權(quán)低Push OPTR c c getch break 算法描述P53 38 case 脫括號(hào)并接收下一個(gè)字符Pop OPTR x c getch break case 退棧并將運(yùn)算結(jié)果入棧Pop OPTR theta Pop OPND b Pop OPND a Push OPND Operate a theta b break swith whilereturnGetTop OPND EvaluateExpression 例 地圖四染色問題 四染色 定理是計(jì)算機(jī)科學(xué)中著名的定理之一 使地圖中相鄰的國家或行政區(qū)域不重色 最少可用四種顏色對(duì)地圖著色 證明此定理的結(jié)論 利用棧采用回溯法對(duì)地圖著色 思想 對(duì)每個(gè)行政區(qū)編號(hào) 1 7 對(duì)顏色編號(hào) a b c d 從第一號(hào)行政區(qū)開始逐一染色 每一個(gè)區(qū)域逐次用四種顏色進(jìn)行試探 若所取顏色與周圍不重 則用棧記下來該區(qū)域的色數(shù) 否則依次用下一色數(shù)進(jìn)行試探 若出現(xiàn)a d均與周圍發(fā)生重色 則需退棧回溯 修改當(dāng)前棧頂?shù)纳珨?shù) 40 1 2 4 5 6 7 3 1 粉色2 黃色3 紅色4 綠色 41 例 迷宮求解 通常用的是 窮舉求解 的方法 42 求迷宮路徑算法的基本思想是 若當(dāng)前位置 可通 則納入路徑 繼續(xù)前進(jìn) 若當(dāng)前位置 不可通 則后退 換方向繼續(xù)探索 若四周 均無通路 則將當(dāng)前位置從路徑中刪除出去 43 設(shè)定當(dāng)前位置的初值為入口位置 do 若當(dāng)前位置可通 則 將當(dāng)前位置插入棧頂 若該位置是出口位置 則算法結(jié)束 否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置 否則 while 棧不空 求迷宮中一條從入口到出口的路徑的算法 44 若棧不空且棧頂位置尚有其他方向未被探索 則設(shè)定新的當(dāng)前位置為 沿順時(shí)針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊 若棧不空但棧頂位置的四周均不可通 則 刪去棧頂位置 從路徑中刪去該通道塊若棧不空 則重新測(cè)試新的棧頂位置 直至找到一個(gè)可通的相鄰塊或出棧至?？?若?？?則表明迷宮沒有通路 45 3 4隊(duì)列一 隊(duì)列的概念二 隊(duì)列的順序存儲(chǔ)和實(shí)現(xiàn)三 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn) 46 一 隊(duì)列的概念定義 隊(duì)列是限定只能在表的一端進(jìn)行插入 在表的另一端進(jìn)行刪除的線性表隊(duì)尾 rear 允許插入的一端隊(duì)頭 front 允許刪除的一端隊(duì)列特點(diǎn) 先進(jìn)先出 FIFO 雙端隊(duì)列 47 a1a2a3an 入隊(duì)列 隊(duì)頭 隊(duì)尾 出隊(duì)列 隊(duì)列的示意圖 隊(duì)列的特點(diǎn)先進(jìn)先出 第一個(gè)入隊(duì)的元素在隊(duì)頭最后一個(gè)入隊(duì)的元素在隊(duì)尾第一個(gè)出隊(duì)的元素為隊(duì)頭元素最后一個(gè)出隊(duì)的元素為隊(duì)尾元素 48 隊(duì)列的類型定義 ADTQueue 數(shù)據(jù)對(duì)象 D ai ai ElemSet i 1 2 n n 0 數(shù)據(jù)關(guān)系 R1 ai 1 ai D i 2 n 約定其中a1端為隊(duì)列頭 an端為隊(duì)列尾 基本操作 P59 ADTQueue 隊(duì)列的主要運(yùn)算 1 設(shè)置一個(gè)空隊(duì)列 2 插入一個(gè)新的隊(duì)尾元素 稱為進(jìn)隊(duì) 3 刪除隊(duì)頭元素 稱為出隊(duì) 4 讀取隊(duì)頭元素 49 二 隊(duì)列的順序存儲(chǔ)和實(shí)現(xiàn) J1 J2 J3 設(shè)兩個(gè)指針front rear 約定 Rear始終指向隊(duì)尾元素的下一個(gè)位置 front始終指向隊(duì)頭元素 空隊(duì)列條件 front rear入隊(duì)列 sq rear x 出隊(duì)列 x sq front 50 存在問題設(shè)數(shù)組維數(shù)為M 則 當(dāng)front 1 rear M 1時(shí) 再有元素入隊(duì)發(fā)生溢出 真溢出當(dāng)front 1 rear M 1時(shí) 再有元素入隊(duì)發(fā)生溢出 假溢出解決方案 循環(huán)隊(duì)列 51 2 循環(huán)隊(duì)列基本思想 把隊(duì)列設(shè)想成環(huán)形 讓sq 0 接在sq M 1 之后 若rear 1 M 則令rear 0 實(shí)現(xiàn) 利用 模 運(yùn)算入隊(duì) rear rear 1 M sq rear x 出隊(duì) front front 1 M x sq front 隊(duì)滿 隊(duì)空判定條件 52 隊(duì)空 front rear隊(duì)滿 front rear 解決方案 1 另外設(shè)一個(gè)標(biāo)志以區(qū)別隊(duì)空 隊(duì)滿2 少用一個(gè)元素空間 隊(duì)空 front rear隊(duì)滿 rear 1 M front 53 循環(huán)隊(duì)列類型定義 defineMAXQSIZE100 最大隊(duì)列長度typedefstruct QElemType base 動(dòng)態(tài)分配存儲(chǔ)空間intfront 頭指針 若隊(duì)列不空 指向隊(duì)列頭元素intrear 尾指針 若隊(duì)列不空 指向 隊(duì)列尾元素的下一個(gè)位置 SqQueue 54 循環(huán)隊(duì)列的主要運(yùn)算 1 初始化操作功能 建一個(gè)空隊(duì)列Q StatusInitQueue SqQueue 55 2 入隊(duì)操作功能 將元素x插入隊(duì)尾 算法 StatusEnQueue SqQueue 動(dòng)畫演示 56 3 出隊(duì)操作功能 刪除隊(duì)頭元素 StatusDeQueue SqQueue 動(dòng)畫演示 57 三 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn) front rear 空鏈隊(duì)列 鏈隊(duì)列圖示 1 鏈隊(duì)列 58 2 鏈隊(duì)列的類型定義結(jié)點(diǎn)類型 typedefstructQNode QElemTypedata structQNode next QNode QueuePtr 鏈隊(duì)列類型 typedefstruct QueuePtrfront 隊(duì)頭指針QueuePtrrear 隊(duì)尾指針 LinkQueue 59 鏈隊(duì)列的主要運(yùn)算 1 初始化操作功能 建一個(gè)空隊(duì)列Q StatusInitQueue LinkQueue 60 2 入隊(duì)操作功能 將元素x插入隊(duì)尾 p data e p next NULL Q rear next p Q rear p 61 算法 StatusEnQueue LinkQueue 62 3 出隊(duì)操作功能 刪除隊(duì)頭元素 p Q front next e p data Q front next p next 63 算法 StatusDeQueue LinkQueue 64 小結(jié)1隊(duì)列是限定僅能在表尾一端進(jìn)行插入 表頭一端刪除操作的線性表 2隊(duì)列中的元素具有先進(jìn)先出的特點(diǎn) 3隊(duì)頭 隊(duì)尾元素的位置分別由稱為隊(duì)頭指針和隊(duì)尾指針的變量指示 4入隊(duì)操作要修改隊(duì)尾指針 出隊(duì)操作要修改隊(duì)頭指針 65 例 循環(huán)隊(duì)列SQ采用數(shù)組空間SQ base 0 n 1 存放其元素值 已知其頭尾指針分別是front和rear 則判定此循環(huán)隊(duì)列Q為空的條件是 A Q rear Q front nB Q rear Q front 1 nC Q rear Q frontD Q rear Q front 1 C 例 循環(huán)隊(duì)列SQ采用數(shù)組空間SQ base 0 n 1 存放其元素值 已知其頭尾指針分別是front和rear 則判定此循環(huán)隊(duì)列Q為滿的條件是 A Q rea Q frontB Q front Q rearC Q front Q rear 1 nD Q front Q rear 1 n C 66 例 循環(huán)隊(duì)列用數(shù)組A 0 m 1 存放其元素值 已知其頭尾指針分別是front和rear則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是 A rear front m m B rear front 1 C rear front 1 D rear front B 例 棧和隊(duì)列的共同點(diǎn)是 A 都是先進(jìn)后出 B 都是先進(jìn)先出 C 只允許在端點(diǎn)處插入和刪除元素 D 沒有共同點(diǎn) C 67 例 以數(shù)組Q 0 m 1 存放循環(huán)隊(duì)列中的元素 變量rear和qulen分別指示循環(huán)隊(duì)列中隊(duì)尾元素的實(shí)際位置和當(dāng)前隊(duì)列中元素的個(gè)數(shù) 隊(duì)列第一個(gè)元素的實(shí)際位置是 A rear qulen B rear qulen m C m qulen D 1 rear m qulen m D 68 例 若在一個(gè)大小為6的數(shù)組上實(shí)現(xiàn)循環(huán)隊(duì)列 且當(dāng)前rear和front的值分別為0和3 當(dāng)從隊(duì)列中刪除一個(gè)元素 再加入兩個(gè)元素后 rear和front的值分別是 例 判定一個(gè)鏈隊(duì)列Q 最多元素個(gè)數(shù)為N 為空的條件是 A Q front Q rearB Q front Q rearC Q