數(shù)據(jù)結(jié)構(gòu)第六次課-棧和隊(duì)列b(已修改)
2025-05-11 08:39 本頁面
【正文】 電氣信息學(xué)院 計(jì)算機(jī)系 數(shù)據(jù)結(jié)構(gòu) 第 1頁 每課一貼 ： 原來很簡(jiǎn)單 有一個(gè)人去應(yīng)征工作，隨手將走廊上的紙屑撿起來，放進(jìn)了垃圾桶，被路過的口試官看到了，因此他得到了這份工作。 原來獲得賞識(shí)很簡(jiǎn)單，養(yǎng)成好習(xí)慣就可以了。 住在田邊的青蛙對(duì)住在路邊的青蛙說：「你這里太危險(xiǎn)，搬來跟我住吧！ 路邊的青蛙說：「我已經(jīng)習(xí)慣了，懶得搬了。」 幾天后，田邊的青蛙去探望路邊的青蛙，卻發(fā)現(xiàn)他已被車子壓死，暴尸在馬路 。 原來掌握命運(yùn)的方法很簡(jiǎn)單，遠(yuǎn)離懶惰就可以了。 電氣信息學(xué)院 計(jì)算機(jī)系 數(shù)據(jù)結(jié)構(gòu) 第 2頁 2. 邏輯結(jié)構(gòu) 與同線性表相同，仍為一對(duì)一關(guān)系。 3. 運(yùn)算規(guī)則 只能在 棧頂 運(yùn)算，且訪問結(jié)點(diǎn)時(shí)依照 后進(jìn)先出 （ LIFO） 或先進(jìn)后出 （ FILO） 的原則。 ： 1. 定義 限定只能在 表的一端 進(jìn)行插入和刪除運(yùn)算的 線性表 （只能在 棧頂 操作） 上次課內(nèi)容回顧 電氣信息學(xué)院 計(jì)算機(jī)系 數(shù)據(jù)結(jié)構(gòu) 第 3頁 討論：有無通用的判別原則？ 有。在可能的輸出序列中，不存在這樣的輸入序列 i，j， k，能同時(shí)滿足 入棧 順序 i， j， k 和 出棧 順序 k ，i， j。 例 4 一個(gè)棧的輸入序列為 12345，若在入棧的過程中允許出棧，則可能得到的出棧序列 有多少種，分別是什么 ？ 211nnCn ?電氣信息學(xué)院 計(jì)算機(jī)系 數(shù)據(jù)結(jié)構(gòu) 第 4頁 例 1： 回文游戲 設(shè)計(jì)思路：用棧暫存回文 例 2： 數(shù)制轉(zhuǎn)換（十轉(zhuǎn) N） 設(shè)計(jì)思路：用棧暫存低位值 例 3 ：括號(hào)匹配的檢驗(yàn) 設(shè)計(jì)思路：用棧暫存左括號(hào) 例 4： 表達(dá)式求值 設(shè)計(jì)思路：用棧暫存運(yùn)算符 ? 簡(jiǎn)化程序設(shè)計(jì)問題 電氣信息學(xué)院 計(jì)算機(jī)系 數(shù)據(jù)結(jié)構(gòu) 第 5頁 ?回文游戲：順讀與逆讀字符串一樣（不含空格） d a d top 若不等，非回文 若直到?？斩枷嗟龋瑒t是回文 有沒有更簡(jiǎn)潔的辦法呢？ (讀入字符串，壓入 n/2個(gè)字符 ,n為字符個(gè)數(shù) ) ?多進(jìn)制輸出： 字符串：“ madam I madam” “上海自來水來自海上” 例 把十進(jìn)制數(shù) 159轉(zhuǎn)換成八進(jìn)制數(shù) (159)10=(237)8 159 8 19 8 2 8 0 2 3 7 余 7 余 3 余 2 top top 7 top 7 3 top 7 3 2 電氣信息學(xué)院 計(jì)算機(jī)系 數(shù)據(jù)結(jié)構(gòu) 第 6頁 ?多進(jìn)制輸出： 例 把十進(jìn)制數(shù) 159轉(zhuǎn)換成八進(jìn)制數(shù) (159)10=(237)8 159 8 19 8 2 8 0 2 3 7 余 7 余 3 余 2 top top 7 top 7 3 top 7 3 2 public class Test { public static void main(String args[]) { int i=159。 String binStr=(i)。 String otcStr=(i)。 String hexStr=(i)。 (binStr)。 } } 電氣信息學(xué)院 計(jì)算機(jī)系 數(shù)據(jù)結(jié)構(gòu) 第 7頁 ?多進(jìn)制輸出： import .*。 class T { public static void main(String[] args) { (toOctal(159))。 } public static String toOctal(int a) { String str = 。 Stack s = new Stack()。 while(a!=0) { (a%8)。 a=a/8。 } while(!()) {str += ()。} return str。 } } 例 把十進(jìn)制數(shù) 159轉(zhuǎn)換成八進(jìn)制數(shù) 電氣信息學(xué)院 計(jì)算機(jī)系 數(shù)據(jù)結(jié)構(gòu) 第 8頁 例如： 3*（
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1