數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊列b-資料下載頁
2025-04-29 08:39本頁面
【正文】 r=(rear+1)%M。 ?出隊： front=(front+1)%M。 電氣信息學(xué)院 計算機(jī)系 數(shù)據(jù)結(jié)構(gòu) 第 28頁 例 2 ： 數(shù)組Ｑ [n]用來表示一個循環(huán)隊列， f 為當(dāng)前隊列頭元素的前一位置， r 為隊尾元素的位置。假定隊列中元素的個數(shù)小于 n，計算隊列中元素的公式為 : （Ａ） 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á)最為合理 例 3： 在一個循環(huán)隊列中，若約定隊首指針指向隊首元素的前一個位置。那么，從循環(huán)隊列中刪除一個元素時，其操作是 先 ，后 。 移動隊首指針 取出元素 √ rear 1 2 3 4 5 0 J4,J5,J6入隊 J4 J5 J6 front 電氣信息學(xué)院 計算機(jī)系 數(shù)據(jù)結(jié)構(gòu) 第 29頁 基本運算如下： ⑴ 置空隊 分配空間 ， 頭尾指針賦值 ， 計數(shù)賦 0 ⑵ 入隊 順序表插入 ， 調(diào)整頭尾指針 計數(shù)賦＋＋ ⑶ 出隊 順序表刪除 ， 調(diào)整頭尾指針 計數(shù)賦 ―― ⑷ 判隊空 隊列中數(shù)據(jù)數(shù)目為 0。 ③ 使用計數(shù)器的循環(huán)隊列的類型定義： Java實現(xiàn)使用計數(shù)器的循環(huán)隊列 .txt 電氣信息學(xué)院 計算機(jī)系 數(shù)據(jù)結(jié)構(gòu) 第 30頁 結(jié)點接口 Public interface Node { public Object getData( )。 //獲取結(jié)點數(shù)據(jù)域 Public void setData(Object object)。 //設(shè)置結(jié)點數(shù)據(jù)域 } Public class SLNode implements Node{ private Object element。 private SLNode next。 public SLNode {this(null,null)。} public SLNode(Object ele, SLnode next){ =ele。 =next。 } public SLNode getNext( ) {return next。} public void setNext(SLNode next) { =next。} public Object getData( ) {return element。} public void setData(Object obj) { element=obj。 } } ?鏈隊列 ?結(jié)點定義 同 SLNode的定義 電氣信息學(xué)院 計算機(jī)系 數(shù)據(jù)結(jié)構(gòu) 第 31頁 ?鏈隊列 頭結(jié)點 ^ …... front 隊頭 隊尾 rear 設(shè)隊首、隊尾指針 front和 rear, front指向頭結(jié)點， rear指向隊尾 電氣信息學(xué)院 計算機(jī)系 數(shù)據(jù)結(jié)構(gòu) 第 32頁 front rear x入 隊 ^ x front rear y入 隊 x ^ y front rear x出 隊 x ^ y front rear 空隊 ^ front rear y出 隊 ^ 電氣信息學(xué)院 計算機(jī)系 數(shù)據(jù)結(jié)構(gòu) 第 33頁 討論： ① 空隊列的特征？ Q (隊尾 ) (隊首 ) front a1 a2 a3 ^ rear p front ^ rear ③ 怎樣實現(xiàn)入隊和出隊操作？ 入隊（尾部插入）： 出隊（頭部刪除）： P74入隊、出隊 Java實現(xiàn) ② 隊列會滿嗎？ front==rear 一般不會，因為刪除時有 free動作。除非內(nèi)存不足！ 電氣信息學(xué)院 計算機(jī)系 數(shù)據(jù)結(jié)構(gòu) 第 34頁 問：為什么要設(shè)計隊列？它有什么獨特用途？ 1. 離散事件的模擬（模擬事件發(fā)生的先后順序） 。 2. 實時監(jiān)控系統(tǒng) （ 循環(huán)隊列 ） 3. 操作系統(tǒng)中多道作業(yè)的處理（一個 CPU執(zhí)行多個作業(yè)）； 4. 簡化程序設(shè)計。 舞伴問題 ， 迷宮的最短路徑問題 答：只要是 存儲和使用順序相同 ， 兩端受限操作就應(yīng)該想到用隊列這種數(shù)據(jù)結(jié)構(gòu)。
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1