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