出版者的話前言第1章　引論11.1　本書討論的內(nèi)容11.2　數(shù)學(xué)知識(shí)復(fù)習(xí)21.2.1　指數(shù)21.2.2　對(duì)數(shù)21.2.3　級(jí)數(shù)21.2.4　模運(yùn)算41.2.5　證明的方法41.3　遞歸簡(jiǎn)論51.4　實(shí)現(xiàn)泛型構(gòu)件pre-Java 571.4.1　使用Object表示泛型81.4.2　基本類型的包裝91.4.3　使用接口類型表示泛型91.4.4　數(shù)組類型的兼容性101.5　利用Java 5泛型特性實(shí)現(xiàn)泛型構(gòu)件111.5.1　簡(jiǎn)單的泛型類和接口111.5.2　自動(dòng)裝箱/拆箱111.5.3　菱形運(yùn)算符121.5.4　帶有限制的通配符121.5.5　泛型static方法141.5.6　類型限界141.5.7　類型擦除151.5.8　對(duì)于泛型的限制151.6　函數(shù)對(duì)象16小結(jié)18練習(xí)18參考文獻(xiàn)19第2章　算法分析202.1　數(shù)學(xué)基礎(chǔ)202.2　模型222.3　要分析的問題222.4　運(yùn)行時(shí)間計(jì)算242.4.1　一個(gè)簡(jiǎn)單的例子242.4.2　一般法則242.4.3　最大子序列和問題的求解262.4.4　運(yùn)行時(shí)間中的對(duì)數(shù)312.4.5　分析結(jié)果的準(zhǔn)確性33小結(jié)33練習(xí)34參考文獻(xiàn)37第3章　表、棧和隊(duì)列393.1　抽象數(shù)據(jù)類型393.2　表ADT393.2.1　表的簡(jiǎn)單數(shù)組實(shí)現(xiàn)403.2.2　簡(jiǎn)單鏈表403.3　Java Collections API中的表413.3.1　Collection接口413.3.2　Iterator接口423.3.3　List接口、ArrayList類和LinkedList類433.3.4　例子：remove方法對(duì)LinkedList類的使用443.3.5　關(guān)于ListIterator接口463.4　ArrayList類的實(shí)現(xiàn)463.4.1　基本類463.4.2　迭代器、Java嵌套類和內(nèi)部類493.5　LinkedList類的實(shí)現(xiàn)523.6　棧ADT583.6.1　棧模型583.6.2　棧的實(shí)現(xiàn)593.6.3　應(yīng)用593.7　隊(duì)列ADT653.7.1　隊(duì)列模型653.7.2　隊(duì)列的數(shù)組實(shí)現(xiàn)653.7.3　隊(duì)列的應(yīng)用66小結(jié)67練習(xí)67第4章　樹714.1　預(yù)備知識(shí)714.1.1　樹的實(shí)現(xiàn)724.1.2　樹的遍歷及應(yīng)用724.2　二叉樹754.2.1　實(shí)現(xiàn)764.2.2　例子：表達(dá)式樹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　一個(gè)簡(jiǎn)單的想法（不能直接使用）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類的實(shí)現(xiàn)1064.8.4　使用多個(gè)映射的實(shí)例106小結(jié)111練習(xí)111參考文獻(xiàn)115第5章　散列1175.1　一般想法1175.2　散列函數(shù)1175.3　分離鏈接法1195.4　不用鏈表的散列表1235.4.1　線性探測(cè)法1235.4.2　平方探測(cè)法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　可擴(kuò)散列148小結(jié)149練習(xí)150參考文獻(xiàn)153第6章　優(yōu)先隊(duì)列（堆）1566.1　模型1566.2　一些簡(jiǎn)單的實(shí)現(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)先隊(duì)列的應(yīng)用1646.4.1　選擇問題1646.4.2　事件模擬1656.5　d-堆1666.6　左式堆1676.6.1　左式堆性質(zhì)1676.6.2　左式堆操作1686.7　斜堆1726.8　二項(xiàng)隊(duì)列1736.8.1　二項(xiàng)隊(duì)列結(jié)構(gòu)1746.8.2　二項(xiàng)隊(duì)列操作1746.8.3　二項(xiàng)隊(duì)列的實(shí)現(xiàn)1766.9　標(biāo)準(zhǔn)庫中的優(yōu)先隊(duì)列180小結(jié)180練習(xí)181參考文獻(xiàn)184第7章　排序1867.1　預(yù)備知識(shí)1867.2　插入排序1867.2.1　算法1867.2.2　插入排序的分析1877.3　一些簡(jiǎn)單排序算法的下界1877.4　希爾排序1887.5　堆排序1917.6　歸并排序1937.7　快速排序1987.7.1　選取樞紐元1997.7.2　分割策略2007.7.3　小數(shù)組2027.7.4　實(shí)際的快速排序例程2027.7.5　快速排序的分析2037.7.6　選擇問題的線性期望時(shí)間算法2067.8　排序算法的一般下界2077.9　選擇問題的決策樹下界2097.10　對(duì)手下界2107.11　線性時(shí)間的排序：桶排序和基數(shù)排序2127.12　外部排序2167.12.1　為什么需要一些新的算法2177.12.2　外部排序模型2177.12.3　簡(jiǎn)單算法2177.12.4　多路合并2187.12.5　多相合并2197.12.6　替換選擇219小結(jié)220練習(xí)221參考文獻(xiàn)225第8章　不相交集類2278.1　等價(jià)關(guān)系2278.2　動(dòng)態(tài)等價(jià)性問題2278.3　基本數(shù)據(jù)結(jié)構(gòu)2298.4　靈巧求并算法2318.5　路徑壓縮2338.6　路徑壓縮和按秩求并的最壞情形2348.6.1　緩慢增長(zhǎng)的函數(shù)2358.6.2　利用遞歸分解的分析2358.6.3　O(M log*N)界2408.6.4　O(Mα(M,N))界2408.7　一個(gè)應(yīng)用241小結(jié)243練習(xí)243參考文獻(xiàn)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　所有點(diǎn)對(duì)最短路徑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　查找強(qiáng)分支2769.7　NP-完全性介紹2779.7.1　難與易2789.7.2　NP類2789.7.3　NP-完全問題279小結(jié)280練習(xí)280參考文獻(xiàn)284第10章　算法設(shè)計(jì)技巧28810.1　貪婪算法28810.1.1　一個(gè)簡(jiǎn)單的調(diào)度問題28810.1.2　哈夫曼編碼29010.1.3　近似裝箱問題29310.2　分治算法29810.2.1　分治算法的運(yùn)行時(shí)間29810.2.2　最近點(diǎn)問題30010.2.3　選擇問題30210.2.4　一些算術(shù)問題的理論改進(jìn)30410.3　動(dòng)態(tài)規(guī)劃30710.3.1　用一個(gè)表代替遞歸30710.3.2　矩陣乘法的順序安排30910.3.3　最優(yōu)二叉查找樹31110.3.4　所有點(diǎn)對(duì)最短路徑31210.4　隨機(jī)化算法31410.4.1　隨機(jī)數(shù)發(fā)生器31510.4.2　跳躍表31910.4.3　素性測(cè)試32010.5　回溯算法32210.5.1　收費(fèi)公路重建問題32310.5.2　博弈326小結(jié)331練習(xí)331參考文獻(xiàn)336第11章　攤還分析34011.1　一個(gè)無關(guān)的智力問題34011.2　二項(xiàng)隊(duì)列34011.3　斜堆34411.4　斐波那契堆34511.4.1　切除左式堆中的節(jié)點(diǎn)34611.4.2　二項(xiàng)隊(duì)列的懶惰合并34711.4.3　斐波那契堆操作34911.4.4　時(shí)間界的證明35011.5　伸展樹351小結(jié)354練習(xí)354參考文獻(xiàn)355第12章　高級(jí)數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(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í)間的后綴數(shù)組和后綴樹的構(gòu)建37512.5　k-d樹38512.6　配對(duì)堆387小結(jié)392練習(xí)393參考文獻(xiàn)396索引399