數(shù)據(jù)結(jié)構(gòu)與算法分析Java語(yǔ)言描述第2版

出版者的話
譯者序
前言
第1章　引論
　1.1　本書討論的內(nèi)容
　1.2　數(shù)學(xué)知識(shí)復(fù)習(xí)
　　1.2.1　指數(shù)
　　1.2.2　對(duì)數(shù)
　　1.2.3　級(jí)數(shù)
　　1.2.4　模運(yùn)算
　　1.2.5　證明的方法
　1.3　遞歸簡(jiǎn)論
　1.4　實(shí)現(xiàn)泛型特性構(gòu)件pre-Java5
　　1.4.1　使用Object表示泛型
　　1.4.2　基本類型的包裝
　　1.4.3　使用接口類型表示泛型
　　1.4.4　數(shù)組類型的兼容性
　1.5　利用Java5泛性實(shí)現(xiàn)泛型特性成分
　　1.5.1　簡(jiǎn)單的泛型類和接口
　　1.5.2　自動(dòng)裝箱/拆箱
　　1.5.3　帶有限制的通配符
　　1.5.4　泛型static方法
　　1.5.5　類型限界
　　1.5.6　類型擦除
　　1.5.7　對(duì)于泛型的限制
　　1.6　函數(shù)對(duì)象
　小結(jié)
　練習(xí)
　參考文獻(xiàn)
第2章　算法分析
　2.1　數(shù)學(xué)基礎(chǔ)
　2.2　模型
　2.3　要分析的問(wèn)題
　2.4　運(yùn)行時(shí)間計(jì)算
　　2.4.1　一個(gè)簡(jiǎn)單的例子
　　2.4.2　一般法則
　　2.4.3　最大子序列和問(wèn)題的求解
　　2.4.4　運(yùn)行時(shí)間中的對(duì)數(shù)
　　2.4.5　檢驗(yàn)?zāi)愕姆治?br />　　2.4.6　分析結(jié)果的準(zhǔn)確性
　小結(jié)
　練習(xí)
　參考文獻(xiàn)
第3章　表、棧和隊(duì)列
　3.1　抽象數(shù)據(jù)類型
　3.2　表ADT
　　3.2.1　表的簡(jiǎn)單數(shù)組實(shí)現(xiàn)
　　3.2.2　簡(jiǎn)單鏈表
　3.3　JavaCollectionsAPI中的表
　　3.3.1　Collection接口
　　3.3.2　Iterator接口
　　3.3.3　List接口、ArrayList類和LinkedList類
　　3.3.4　例：remove方法對(duì)LinkedList類的使用
　　3.3.5　關(guān)于ListIterator接口
　3.4　ArrayList類的實(shí)現(xiàn)
　　3.4.1　基本類
　　3.4.2　迭代器、Java嵌套類和內(nèi)部類
　3.5　LinkedList類的實(shí)現(xiàn)
　3.6　棧ADT
　　3.6.1　棧模型
　　3.6.2　棧的實(shí)現(xiàn)
　　3.6.3　應(yīng)用
　3.7　隊(duì)列ADT
　　3.7.1　隊(duì)列模型
　　3.7.2　隊(duì)列的數(shù)組實(shí)現(xiàn)
　　3.7.3　隊(duì)列的應(yīng)用
　小結(jié)
　練習(xí)
第4章　樹(shù)
　4.1　預(yù)備知識(shí)
　　4.1.1　樹(shù)的實(shí)現(xiàn)
　　4.1.2　樹(shù)的遍歷及應(yīng)用
　4.2　二叉樹(shù)
　　4.2.1　實(shí)現(xiàn)
　　4.2.2　例子：表達(dá)式樹(shù)
　4.3　查找樹(shù)ADT——二叉查找樹(shù)
　　4.3.1　contains方法
　　4.3.2　findMin方法和findMax方法
　　4.3.3　insert方法
　　4.3.4　remove方法
　　4.3.5　平均情況分析
　4.4　AVL樹(shù)
　　4.4.1　單旋轉(zhuǎn)
　　4.4.2　雙旋轉(zhuǎn)
　4.5　伸展樹(shù)
　　4.5.1　一個(gè)簡(jiǎn)單的想法（不能直接使用）
　　4.5.2　展開(kāi)
　4.6　樹(shù)的遍歷
　4.7　B樹(shù)
　4.8　標(biāo)準(zhǔn)庫(kù)中的集合與映射
　　4.8.1　關(guān)于Set接口
　　4.8.2　關(guān)于Map接口
　　4.8.3　TreeSet類和TreeMap類的實(shí)現(xiàn)
　4.8.4　使用多個(gè)映射的例
　小結(jié)
　練習(xí)
　參考文獻(xiàn)
第5章　散列
　5.1　一般想法
　5.2　散列函數(shù)
　5.3　分離鏈接法
　5.4　不用鏈表的散列表
　　5.4.1　線性探測(cè)法
　　5.4.2　平方探測(cè)法
　　5.4.3　雙散列
　5.5　再散列
　5.6　標(biāo)準(zhǔn)庫(kù)中的散列表
　5.7　可擴(kuò)散列
　小結(jié)
　練習(xí)
　參考文獻(xiàn)
第6章　優(yōu)先隊(duì)列（堆）
　6.1　模型
　6.2　一些簡(jiǎn)單的實(shí)現(xiàn)
　6.3　二叉堆
　　6.3.1　結(jié)構(gòu)性質(zhì)
　　6.3.2　堆序性質(zhì)
　　6.3.3　基本的堆操作
　　6.3.4　其他的堆操作
　6.4　優(yōu)先隊(duì)列的應(yīng)用
　　6.4.1　選擇問(wèn)題
　　6.4.2　事件模擬
　6.5　d-堆
　6.6　左式堆
　　6.6.1　左式堆性質(zhì)
　　6.6.2　左式堆操作
　6.7　斜堆
　6.8　二項(xiàng)隊(duì)列
　　6.8.1　二項(xiàng)隊(duì)列結(jié)構(gòu)
　　6.8.2　二項(xiàng)隊(duì)列操作
　　6.8.3　二項(xiàng)隊(duì)列的實(shí)現(xiàn)
　6.9　標(biāo)準(zhǔn)庫(kù)中的優(yōu)先隊(duì)列
　小結(jié)
　練習(xí)
　參考文獻(xiàn)
第7章　排序
　7.1　預(yù)備知識(shí)
　7.2　插入排序
　　7.2.1　算法
　　7.2.2　插入排序的分析
　7.3　一些簡(jiǎn)單排序算法的下界
　7.4　希爾排序
　7.5　堆排序
　7.6　歸并排序
　7.7　快速排序
　　7.7.1　選取樞紐元
　　7.7.2　分割策略
　　7.7.3　小數(shù)組
　　7.7.4　實(shí)際的快速排序例程
　　7.7.5　快速排序的分析
　　7.7.6　選擇問(wèn)題的線性期望時(shí)間算法
　7.8　排序算法的一般下界
　7.9　桶式排序
　7.10　外部排序
　　7.10.1　為什么需要一些新的算法
　　7.10.2　外部排序模型
　　7.10.3　簡(jiǎn)單算法
　　7.10.4　多路合并
　　7.10.5　多相合并
　　7.10.6　替換選擇
　小結(jié)
　練習(xí)題
　參考文獻(xiàn)
第8章　不相交集類
　8.1　等價(jià)關(guān)系
　8.2　動(dòng)態(tài)等價(jià)性問(wèn)題
　8.3　基本數(shù)據(jù)結(jié)構(gòu)
　8.4　靈巧求并算法
　8.5　路徑壓縮
　8.6　路徑壓縮和按秩求并的最壞情形
　8.7　一個(gè)應(yīng)用
　小結(jié)
　練習(xí)題
　參考文獻(xiàn)
第9章　圖論算法
　9.1　若干定義
　9.2　拓?fù)渑判?br />　9.3　最短路徑算法
　　9.3.1　無(wú)權(quán)最短路徑
　　9.3.2　Dijkstra算法
　　9.3.3　具有負(fù)邊值的圖
　　9.3.4　無(wú)圈圖
　　9.3.5　所有點(diǎn)對(duì)最短路徑
　　9.3.6　最短路徑的例子
　9.4　網(wǎng)絡(luò)流問(wèn)題
　9.5　最小生成樹(shù)
　　9.5.1　Prim算法
　　9.5.2　Kruskal算法
　9.6　深度優(yōu)先搜索的應(yīng)用
　　9.6.1　無(wú)向圖
　　9.6.2　雙連通性
　　9.6.3　歐拉回路
　　9.6.4　有向圖
　　9.6.5　查找強(qiáng)分支
　9.7　NP完全性介紹
　　9.7.1　難與易
　　9.7.2　NP類
　　9.7.3　NP完全問(wèn)題
　小結(jié)
　練習(xí)
　參考文獻(xiàn)
第10章　算法設(shè)計(jì)技巧
　10.1　貪婪算法
　　10.1.1　一個(gè)簡(jiǎn)單的調(diào)度問(wèn)題
　　10.1.2　哈夫曼編碼
　　10.1.3　近似裝箱問(wèn)題
　10.2　分治算法
　　10.2.1　分治算法的運(yùn)行時(shí)間
　　10.2.2　最近點(diǎn)問(wèn)題
　　10.2.3　選擇問(wèn)題
　　10.2.4　一些算術(shù)問(wèn)題的理論改進(jìn)
　10.3　動(dòng)態(tài)規(guī)劃
　　10.3.1　用一個(gè)表代替遞歸
　　10.3.2　矩陣乘法的順序安排
　　10.3.3　最優(yōu)二叉查找樹(shù)
　　10.3.4　所有點(diǎn)對(duì)最短路徑
　10.4　隨機(jī)化算法
　　10.4.1　隨機(jī)數(shù)發(fā)生器
　　10.4.2　跳躍表
　　10.4.3　素性測(cè)試
　10.5　回溯算法
　　10.5.1　收費(fèi)公路重建問(wèn)題
　　10.5.2　博弈
　小結(jié)
　練習(xí)
　參考文獻(xiàn)
第11章　攤還分析
　11.1　一個(gè)無(wú)關(guān)的智力問(wèn)題
　11.2　二項(xiàng)隊(duì)列
　11.3　斜堆
　11.4　斐波那契堆
　　11.4.1　切除左式堆中的節(jié)點(diǎn)
　　11.4.2　二項(xiàng)隊(duì)列的懶惰合并
　　11.4.3　斐波那契堆操作
　　11.4.4　時(shí)間界的證明
　11.5　伸展樹(shù)
　小結(jié)
　練習(xí)
　參考文獻(xiàn)
第12章　高級(jí)數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)
　12.1　自頂向下伸展樹(shù)
　12.2　紅黑樹(shù)
　　12.2.1　自底向上的插入
　　12.2.2　自頂向下紅黑樹(shù)
　　12.2.3　自頂向下的刪除
　12.3　確定性跳躍表
　12.4　AA樹(shù)
　12.5　treap樹(shù)
　12.6　kd樹(shù)
　12.7　配對(duì)堆
　小結(jié)
　練習(xí)
　參考文獻(xiàn)
索引