出版者的話前言第1章　引論11.1　本書討論的內容11.2　數學知識復習21.2.1　指數21.2.2　對數21.2.3　級數21.2.4　模運算41.2.5　證明的方法41.3　遞歸簡論51.4　實現泛型構件pre-Java 571.4.1　使用Object表示泛型81.4.2　基本類型的包裝91.4.3　使用接口類型表示泛型91.4.4　數組類型的兼容性101.5　利用Java 5泛型特性實現泛型構件111.5.1　簡單的泛型類和接口111.5.2　自動裝箱/拆箱111.5.3　菱形運算符121.5.4　帶有限制的通配符121.5.5　泛型static方法141.5.6　類型限界141.5.7　類型擦除151.5.8　對于泛型的限制151.6　函數對象16小結18練習18參考文獻19第2章　算法分析202.1　數學基礎202.2　模型222.3　要分析的問題222.4　運行時間計算242.4.1　一個簡單的例子242.4.2　一般法則242.4.3　最大子序列和問題的求解262.4.4　運行時間中的對數312.4.5　分析結果的準確性33小結33練習34參考文獻37第3章　表、棧和隊列393.1　抽象數據類型393.2　表ADT393.2.1　表的簡單數組實現403.2.2　簡單鏈表403.3　Java Collections API中的表413.3.1　Collection接口413.3.2　Iterator接口423.3.3　List接口、ArrayList類和LinkedList類433.3.4　例子：remove方法對LinkedList類的使用443.3.5　關于ListIterator接口463.4　ArrayList類的實現463.4.1　基本類463.4.2　迭代器、Java嵌套類和內部類493.5　LinkedList類的實現523.6　棧ADT583.6.1　棧模型583.6.2　棧的實現593.6.3　應用593.7　隊列ADT653.7.1　隊列模型653.7.2　隊列的數組實現653.7.3　隊列的應用66小結67練習67第4章　樹714.1　預備知識714.1.1　樹的實現724.1.2　樹的遍歷及應用724.2　二叉樹754.2.1　實現764.2.2　例子：表達式樹764.3　查找樹ADT——二叉查找樹784.3.1　contains方法794.3.2　findMin方法和findMax方法804.3.3　insert方法804.3.4　remove方法824.3.5　平均情況分析834.4　AVL樹864.4.1　單旋轉874.4.2　雙旋轉894.5　伸展樹944.5.1　一個簡單的想法（不能直接使用）954.5.2　展開964.6　再探樹的遍歷1004.7　B樹1014.8　標準庫中的集合與映射1054.8.1　關于Set接口1054.8.2　關于Map接口1054.8.3　TreeSet類和TreeMap類的實現1064.8.4　使用多個映射的實例106小結111練習111參考文獻115第5章　散列1175.1　一般想法1175.2　散列函數1175.3　分離鏈接法1195.4　不用鏈表的散列表1235.4.1　線性探測法1235.4.2　平方探測法1245.4.3　雙散列1295.5　再散列1305.6　標準庫中的散列表1325.7　最壞情形下O(1)訪問的散列表 1335.7.1　完美散列1335.7.2　布谷鳥散列1355.7.3　跳房子散列1435.8　通用散列法1465.9　可擴散列148小結149練習150參考文獻153第6章　優(yōu)先隊列（堆）1566.1　模型1566.2　一些簡單的實現1566.3　二叉堆1576.3.1　結構性質1576.3.2　堆序性質1576.3.3　基本的堆操作1586.3.4　其他的堆操作1626.4　優(yōu)先隊列的應用1646.4.1　選擇問題1646.4.2　事件模擬1656.5　d-堆1666.6　左式堆1676.6.1　左式堆性質1676.6.2　左式堆操作1686.7　斜堆1726.8　二項隊列1736.8.1　二項隊列結構1746.8.2　二項隊列操作1746.8.3　二項隊列的實現1766.9　標準庫中的優(yōu)先隊列180小結180練習181參考文獻184第7章　排序1867.1　預備知識1867.2　插入排序1867.2.1　算法1867.2.2　插入排序的分析1877.3　一些簡單排序算法的下界1877.4　希爾排序1887.5　堆排序1917.6　歸并排序1937.7　快速排序1987.7.1　選取樞紐元1997.7.2　分割策略2007.7.3　小數組2027.7.4　實際的快速排序例程2027.7.5　快速排序的分析2037.7.6　選擇問題的線性期望時間算法2067.8　排序算法的一般下界2077.9　選擇問題的決策樹下界2097.10　對手下界2107.11　線性時間的排序：桶排序和基數排序2127.12　外部排序2167.12.1　為什么需要一些新的算法2177.12.2　外部排序模型2177.12.3　簡單算法2177.12.4　多路合并2187.12.5　多相合并2197.12.6　替換選擇219小結220練習221參考文獻225第8章　不相交集類2278.1　等價關系2278.2　動態(tài)等價性問題2278.3　基本數據結構2298.4　靈巧求并算法2318.5　路徑壓縮2338.6　路徑壓縮和按秩求并的最壞情形2348.6.1　緩慢增長的函數2358.6.2　利用遞歸分解的分析2358.6.3　O(M log*N)界2408.6.4　O(Mα(M,N))界2408.7　一個應用241小結243練習243參考文獻244第9章　圖論算法2469.1　若干定義2469.2　拓撲排序2489.3　最短路徑算法2509.3.1　無權最短路徑2519.3.2　Dijkstra算法2549.3.3　具有負邊值的圖2589.3.4　無圈圖2599.3.5　所有點對最短路徑2619.3.6　最短路徑的例子2619.4　網絡流問題2629.5　最小生成樹2679.5.1　Prim算法2679.5.2　Kruskal算法2699.6　深度優(yōu)先搜索的應用2709.6.1　無向圖2709.6.2　雙連通性2719.6.3　歐拉回路2739.6.4　有向圖2759.6.5　查找強分支2769.7　NP-完全性介紹2779.7.1　難與易2789.7.2　NP類2789.7.3　NP-完全問題279小結280練習280參考文獻284第10章　算法設計技巧28810.1　貪婪算法28810.1.1　一個簡單的調度問題28810.1.2　哈夫曼編碼29010.1.3　近似裝箱問題29310.2　分治算法29810.2.1　分治算法的運行時間29810.2.2　最近點問題30010.2.3　選擇問題30210.2.4　一些算術問題的理論改進30410.3　動態(tài)規(guī)劃30710.3.1　用一個表代替遞歸30710.3.2　矩陣乘法的順序安排30910.3.3　最優(yōu)二叉查找樹31110.3.4　所有點對最短路徑31210.4　隨機化算法31410.4.1　隨機數發(fā)生器31510.4.2　跳躍表31910.4.3　素性測試32010.5　回溯算法32210.5.1　收費公路重建問題32310.5.2　博弈326小結331練習331參考文獻336第11章　攤還分析34011.1　一個無關的智力問題34011.2　二項隊列34011.3　斜堆34411.4　斐波那契堆34511.4.1　切除左式堆中的節(jié)點34611.4.2　二項隊列的懶惰合并34711.4.3　斐波那契堆操作34911.4.4　時間界的證明35011.5　伸展樹351小結354練習354參考文獻355第12章　高級數據結構及其實現35612.1　自頂向下伸展樹35612.2　紅黑樹36212.2.1　自底向上的插入36212.2.2　自頂向下紅黑樹36312.2.3　自頂向下的刪除36712.3　treap樹36812.4　后綴數組與后綴樹37012.4.1　后綴數組37112.4.2　后綴樹37312.4.3　線性時間的后綴數組和后綴樹的構建37512.5　k-d樹38512.6　配對堆387小結392練習393參考文獻396索引399