出版者的話前言第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.3Java Collections API中的表413.3.1Collection接口413.3.2Iterator接口423.3.3List接口、ArrayList類和LinkedList類433.3.4例子：remove方法對LinkedList類的使用443.3.5關於ListIterator接口463.4ArrayList類的實現463.4.1基本類463.4.2迭代器、Java嵌套類和內部類493.5LinkedList類的實現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.1contains方法794.3.2findMin方法和findMax方法804.3.3insert方法804.3.4remove方法824.3.5平均情況分析834.4AVL樹864.4.1單旋轉874.4.2雙旋轉894.5伸展樹944.5.1一個簡單的想法（不能直接使用）954.5.2展開964.6再探樹的遍歷1004.7B樹1014.8標準庫中的集合與映射1054.8.1關於Set接口1054.8.2關於Map接口1054.8.3TreeSet類和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章優先隊列（堆）1566.1模型1566.2一些簡單的實現1566.3二叉堆1576.3.1結構性質1576.3.2堆序性質1576.3.3基本的堆操作1586.3.4其他的堆操作1626.4優先隊列的應用1646.4.1選擇問題1646.4.2事件模擬1656.5d-堆1666.6左式堆1676.6.1左式堆性質1676.6.2左式堆操作1686.7斜堆1726.8二項隊列1736.8.1二項隊列結構1746.8.2二項隊列操作1746.8.3二項隊列的實現1766.9標準庫中的優先隊列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動態等價性問題2278.3基本數據結構2298.4靈巧求並算法2318.5路徑壓縮2338.6路徑壓縮和按秩求並的壞情形2348.6.1緩慢增長的函數2358.6.2利用遞歸分解的分析2358.6.3O(M log*N)界2408.6.4O(Mα(M,N))界2408.7一個應用241小結243練習243參考文獻244第9章圖論算法2469.1若干定義2469.2拓撲排序2489.3短路徑算法2509.3.1無權短路徑2519.3.2Dijkstra算法2549.3.3具有負邊值的圖2589.3.4無圈圖2599.3.5所有點對短路徑2619.3.6短路徑的例子2619.4網絡流問題2629.5小生成樹2679.5.1Prim算法2679.5.2Kruskal算法2699.6深度優先搜索的應用2709.6.1無向圖2709.6.2雙連通性2719.6.3歐拉回路2739.6.4有向圖2759.6.5查找強分支2769.7NP-完全性介紹2779.7.1難與易2789.7.2NP類2789.7.3NP-完全問題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動態規劃30710.3.1用一個表代替遞歸30710.3.2矩陣乘法的順序安排30910.3.3二叉查找樹31110.3.4所有點對短路徑31210.4隨機化算法31410.4.1隨機數發生器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切除左式堆中的節點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.3treap樹36812.4後綴數組與後綴樹37012.4.1後綴數組37112.4.2後綴樹37312.4.3線性時間的後綴數組和後綴樹的構建37512.5k-d樹38512.6配對堆387小結392練習393參考文獻396索引399

本書目標本書新的Java版論述數據結構——組織大量數據的方法，以及算法分析——算法運行時間的估計。隨著計算機的速度越來越快，對於能夠處理大量輸入數據的程序的需求變得日益迫切。可是，由於在輸入量很大的時候程序的低效率變得非常明顯，因此這又要求對效率問題給予更仔細的關注。通過在實際編程之前對算法的分析，我們可以確定某個特定的解法是否可行。例如，查閱本書中一些特定的問題，可以看到我們如何通過巧妙的實現，將其處理大量數據的時間限制從幾個世紀減至不到1秒。因此，我們在提出所有算法和數據結構時都會闡釋其運行時間。在某些情況下，對於影響實現的運行時間的一些微小細節都需要認真探究。 一旦確定了解法，接著就要編寫程序。隨著計算機功能的日益強大，它們必須解決的問題也變得更加龐大和復雜，這就要求我們開發更加復雜的程序。本書的目的是同時教授學生良好的程序設計技巧和算法分析能力，使得他們能夠以的效率開發出這種程序。 本書適用於高級數據結構（CS7）課程或是年研究生的算法分析課程。學生應該掌握一些中級編程知識，包括基於對像的程序設計和遞歸等內容，並具備一些離散數學的背景。 第3版中顯著的變化第3版訂正了大量的錯誤，也修改了很多地方，以使內容更加清晰。此外還有以下修訂： ●第4章包括了AVL樹的刪除算法——這也是讀者經常需要的內容。 ●第5章進行了大量修改和擴充，現在包含兩種新算法：布谷鳥散列（cuckoo hashing）和跳房子散列（hopscotch hashing）。此外還增加了一節討論通用散列法。 ●第7章現在包含了基數排序的內容，並且增加了一節討論下界的證明。 ●第8章用到Seidel和Sharir提出的新的並查集分析，並且證明了O(Mα(M,N))界，而不是前一版中比較弱的O(Mlog*N)界。 ●第12章增加了後綴樹和後綴數組的內容，包括Karkkainen和Sanders提出的構造後綴數組的線性時間算法（附帶實現）。關於確定性跳躍表和AA樹的章節被刪除。 ●通篇代碼已做更新，使用了Java 7的菱形運算符。 處理方法雖然本書的內容大部分都與語言無關，但是，程序設計還是需要使用某種特定的語言。正如書名所示，我們為本書選擇了Java。 人們常常將Java和C 比較。Java具有許多優點，程序員常常把Java看成是一種比C 更安全、更具有可移植性並且更容易使用的語言。因此，這使得它成為討論和實現基礎數據結構的一種優秀的核心語言。Java的其他重要的方面，諸如線程和GUI（圖形用戶界面），雖然很重要，但是本書並不需要，因此也就不再討論。 完整的Java和C 版數據結構均在互聯網上提供。我們采用相似的編碼約定以使得這兩種語言之間的對等性更加明顯。 內容概述第1章包含離散數學和遞歸的一些復習材料。我相信熟練掌握遞歸的辦法是反復不斷地研讀一些好的用法。因此，除第5章外，遞歸遍及本書每一章的例子之中。第1章還介紹了一些相關內容，作為對Java中“繼承”的復習，包括對Java泛型的討論。 第2章討論算法分析，闡述漸近分析及其主要缺點，提供了許多例子，包括對對數級運行時間的深入分析。我們通過直觀地把遞歸程序轉變成迭代程序，對一些簡單遞歸程序進行了分析。更復雜的分治程序也在此介紹，不過有些分析（求解遞推關繫）要推遲到第7章再進行詳細討論。 第3章介紹表、棧和隊列。包括對Collections API ArrayList類和LinkedList類的討論，提供了Collections API ArrayList類和LinkedList類的一個重要子集的若干實現。 .第4章討論樹，重點是查找樹，包括外部查找樹（B-樹）。UNIX文件繫統和表達式樹是作為例子來介紹的。這一章還介紹了AVL樹和伸展樹。查找樹實現細節的更仔細的處理可在第12章找到。樹的另外一些內容（如文件壓縮和博弈樹）推遲到第10章討論。外部介質上的數據結構作為若干章中的後論題來考慮。對於Collections API TreeSet類和TreeMap類的討論，則通過一個重要的例子來展示三種單獨的映射在求解同一個問題中的使用。 第5章討論散列表，既包括經典算法，如分離鏈接法和線性及平方探測法，同時也包括幾個新算法，如布谷鳥散列和跳房子散列。本章還討論了通用散列法，並且在章末討論了可擴散列。 第6章是關於優先隊列的。二叉堆也在這裡講授，還有些附加的材料論述優先隊列某些理論上有趣的實現方法。斐波那契堆在第11章討論，配對堆在第12章討論。 第7章論述排序。這一章特別關注編程細節和分析。所有重要的通用排序算法均在該章進行了討論和比較。此外，還對四種排序算法做了詳細的分析，它們是插入排序、希爾排序、堆排序以及快速排序。這一版新增的是基數排序以及對選擇類問題的下界的證明。本章末尾討論了外部排序。 第8章討論不相交集算法並證明其運行時間。分析部分是新的。這是簡短且特殊的一章，如果不討論Kruskal算法則可跳過該章。 第9章講授圖論算法。圖論算法之所以有趣，不僅因為它們在實踐中經常出現，而且還因為它們的運行時間強烈地依賴於數據結構的恰當使用。實際上，所有標準算法都和適用的數據結構、偽代碼以及運行時間的分析一起介紹。為了恰當地理解這些問題，我們對復雜性理論（包括NP-完全性和不可判定性）進行了簡短的討論。 第10章通過考察一般性的問題求解技術來介紹算法設計。本章通過大量的例子來增強理解。這一章及後面各章使用的偽代碼使得讀者在理解例子時不會被實現的細節所困擾。 第11章處理攤還分析，主要分析三種數據結構，它們分別在第4章、第6章以及本章（斐波那契堆）介紹。 第12章討論查找樹算法、後綴樹和數組、k-d樹和配對堆。不同於其他各章，本章給出了查找樹和配對堆完整且仔細的實現。材料的安排使得教師可以把一些內容納入其他各章的討論之中。例如，第12章中的自頂向下紅黑樹可以和（第4章的）AVL樹一起討論。 第1~9章為大多數一學期的數據結構課程提供了足夠的材料。如果時間允許，那麼第10章也可以包括進來。研究生的算法分析課程可以使用第7~11章的內容。第11章所分析的高級數據結構可以很容易地被前面各章所提及。第9章裡所討論的NP-完全性太過簡短，不適用於這樣的課程。另外再用一部NP-完全性方面的著作作為本教材的補充可能是比較有益的。 練習每章末尾提供的練習與正文中所述內容的順序相一致。後的一些練習是對應整章而不是針對特定的某一節的。難度較大的練習標有一個星號，更具挑戰的練習標有兩個星號。 參考文獻參考文獻列於每章的後。通常，這些參考文獻或者是具有歷史意義的、給出書中材料的原始出處，或者闡述對書中給出的結果的擴展和改進。有些文獻為一些練習提供了解法。 補充材料下面的補充材料在www.pearsonhighered.com/cssupport對所有讀者公開： ●例子程序的源代碼此外，下述材料僅提供給經培生教師資源中心（Pearson’s Instructor Resource Center，IRC）(www.pearsonhighered.com/irc)認可的教師。有意者請訪問IRC或聯繫培生的校園代表以獲得訪問權限。關於本書教輔資源，用書教師可向培生教育出版集團北京代表處申請，電話：010-5735 5169/5735 5171，電子郵件：service.cn@pearson.com。——編輯注●部分練習的解答●來自本書的一些附圖致謝在本書的準備過程中，我得到了許多人的幫助，有些已在本書的其他版本中列出，感謝大家。 一如既往地，培生的專家們的努力使得本書的寫作過程更加輕松。我願在此感謝我的編輯Michael Hirsch以及制作編輯Pat Brown。我還要感謝Abinaya Rajendran和她在Integra Software Services的同事，感謝他們使後的散稿成書的出色工作。賢妻Jill所做的每一件事情都值得我特別感謝。 後，我還想感謝發來E-mail並指出前面各版中錯誤和矛盾之處的廣大讀者。我的網頁www.cis.fiu.edu/~weiss包含更新後的源代碼（用Java和C 編寫）、勘誤表以及提交問題報告的鏈接。 M.A.W.佛羅裡達州邁阿密市