●出版者的話譯者序前言第1章  引論┊11.1  本書討論的內容┊21.2  數學知識復習┊31.2.1  指數┊31.2.2  對數┊31.2.3  級數┊41.2.4  模運算┊51.2.5  證明方法┊51.3  遞歸簡論┊7總結┊10練習┊10參考文獻┊11第2章  算法分析┊132.1  數學基礎┊142.2  模型┊162.3  要分析的問題┊162.4  運行時間計算┊182.4.1  一個簡單的例子┊182.4.2  一般法則┊192.4.3  優選子序列和┊202.4.4  運行時間中的對數┊242.4.5  檢驗你的分析┊272.4.6  分析結果的準確性┊28總結┊28練習┊29參考文獻┊32第3章  表、棧和隊列┊353.1  抽像數據類型┊363.2  表ADT┊363.2.1  表的簡單數組實現┊373.2.2  鏈表┊373.2.3  程序設計細節┊383.2.4  常見的錯誤┊423.2.5  雙鏈表┊433.2.6  循環鏈表┊433.2.7  例子┊433.2.8  鏈表的遊標實現┊473.3  棧ADT┊503.3.1  棧模型┊503.3.2  棧的實現┊513.3.3  應用┊563.4  隊列ADT┊623.4.1  隊列模型┊623.4.2  隊列的數組實現┊623.4.3  隊列的應用┊65總結┊66練習┊66第4章  樹┊714.1  預備知識┊724.1.1  樹的實現┊734.1.2  樹的遍歷及應用┊744.2  二叉樹┊764.2.1  實現┊774.2.2  表達式樹┊774.3  查找樹ADT——二叉查找樹┊804.3.1  MakeEmpty┊804.3.2  Find┊814.3.3  FindMin和FindMax┊814.3.4  Insert┊814.3.5  Delete┊834.3.6  平均情形分析┊844.4  AVL樹┊864.4.1  單旋轉┊884.4.2  雙旋轉┊904.5  伸展樹┊954.5.1  一個簡單的想法┊964.5.2  展開┊974.6  樹的遍歷┊1024.7  B樹┊103總結┊107練習┊108參考文獻┊113第5章  散列┊1175.1  一般想法┊1185.2  散列函數┊1185.3  分離鏈接法┊1205.4  開放定址法┊1235.4.1  線性探測法┊1245.4.2  平方探測法┊1255.4.3  雙散列┊1295.5  再散列┊1305.6  可擴散列┊132總結┊133練習┊134參考文獻┊137第6章  優先隊列（堆）┊1396.1  模型┊1406.2  一些簡單的實現┊1416.3  二叉堆┊1416.3.1  結構性質┊1416.3.2  堆序性質┊1426.3.3  基本的堆操作┊1436.3.4  其他的堆操作┊1466.4  優先隊列的應用┊1496.4.1  選擇問題┊1496.4.2  事件模擬┊1506.5  d-堆┊1516.6  左式堆┊1526.6.1  左式堆的性質┊1526.6.2  左式堆的操作┊1536.7  斜堆┊1586.8  二項隊列┊1596.8.1  二項隊列結構┊1596.8.2  二項隊列操作┊1606.8.3  二項隊列的實現┊162總結┊165練習┊166參考文獻┊169第7章  排序┊1737.1  預備知識┊1747.2  插入排序┊1747.2.1  算法┊1747.2.2  插入排序的分析┊1757.3  一些簡單排序算法的下界┊1757.4  希爾排序┊1767.5  堆排序┊1797.6  歸並排序┊1827.7  快速排序┊1867.7.1  選┊1877.7.2  分割策略┊1887.7.3  小數組┊1907.7.4  實際的快速排序例程┊1907.7.5  快速排序的分析┊1927.7.6  選擇的線性期望時間算法┊1947.8  大型結構的排序┊1957.9  排序的一般下界┊1967.10  桶式排序┊1987.11  外部排序┊1987.11.1  為什麼需要新的算法┊1987.11.2  外部排序模型┊1997.11.3  簡單算法┊1997.11.4  多路合並┊2007.11.5  多相合並┊2017.11.6  替換選擇┊202總結┊203練習┊204參考文獻┊207第8章  不相交集ADT┊2098.1  等價關繫┊2108.2  動態等價性問題┊2108.3  基本數據結構┊2128.4  靈巧求並算法┊2148.5  路徑壓縮┊2168.6  按秩求並和路徑壓縮的最壞情形┊2178.7  一個應用┊221總結┊222練習┊222參考文獻┊223第9章  圖論算法┊2259.1  若干定義┊2269.2  拓撲排序┊2289.3  最短路徑算法┊2309.3.1  無權最短路徑┊2329.3.2  Dijkstra算法┊2359.3.3  具有負邊值的圖┊2409.3.4  無圈圖┊2419.3.5  所有點對最短路徑┊2439.4  網絡流問題┊2439.5  最小生成樹┊2479.5.1  Prim算法┊2489.5.2  Kruskal算法┊2509.6  深度優先搜索的應用┊2519.6.1  無向圖┊2529.6.2  雙連通性┊2539.6.3  歐拉回路┊2569.6.4  有向圖┊2599.6.5  查找強分支┊2609.7  NP-接近性介紹┊2629.7.1  難與易┊2629.7.2  NP類┊2639.7.3  NP-接近問題┊264總結┊266練習┊266參考文獻┊270第10章  算法設計技巧┊27310.1  貪婪算法┊27410.1.1  一個簡單的調度問題┊27410.1.2  Huffman編碼┊27610.1.3  近似裝箱問題┊28010.2  分治算法┊28610.2.1  分治算法的運行時間┊28710.2.2  最近點問題┊28910.2.3  選擇問題┊29110.2.4  一些運算問題的理論改進┊29410.3  動態規劃┊29710.3.1  用一個表代替遞歸┊29810.3.2  矩陣乘法的順序安排┊30010.3.3  很優二叉查找樹┊30110.3.4  所有點對最短路徑┊30410.4  隨機化算法┊30610.4.1  隨機數發生器┊30710.4.2  跳躍表┊31010.4.3  素性測試┊31210.5  回溯算法┊31410.5.1  收費公路重建問題┊31410.5.2  博弈┊318總結┊323練習┊323參考文獻┊329第11章  攤還分析┊33311.1  一個無關的智力問題┊33411.2  二項隊列┊33511.3  斜堆┊33911.4  斐波那契堆┊34111.4.1  切除左式堆中的節點┊34111.4.2  二項隊列的懶惰合並┊34311.4.3  斐波那契堆操作┊34611.4.4  時間界的證明┊34611.5  伸展樹┊348總結┊351練習┊351參考文獻┊353第12章  高級數據結構及其實現┊35512.1  自頂向下伸展樹┊35612.2  紅黑樹┊36112.2.1  自底向上插入┊36212.2.2  自頂向下紅黑樹┊36312.2.3  自頂向下刪除┊36712.3  確定性跳躍表┊36812.4  AA樹┊37312.5  treap樹┊37812.6  k-d樹┊37912.7  配對堆┊383總結┊387練習┊387參考文獻┊389索引┊391

本書是國外數據結構與算法分析方面的標準教材,介紹了數據結構(大量數據的組織方法)以及算法分析(算法運行時間的估算)。本書的編寫目標是同時講授好的程序設計和算法分析技巧,使讀者可以開發出具有*高效率的程序。本書可作為高級數據結構課程或研究生一年級算法分析課程的教材,使用本書需具有一些中級程序設計知識,還需要離散數學的一些背景知識。

[美]馬克·艾倫·維斯（MarkAllenWeiss） 著 馮舜璽 譯 譯

目的本書討論數據結構和算法分析。數據結構主要研究組織大量數據的方法，而算法分析則是對算法運行時間的評估。隨著計算機的速度越來越快，對於能夠處理大量輸入數據的程序的需求變得日益急切。可是，由於在輸入量很大的時候程序的低效率現像變得非常明顯，因此這又要求對效率問題給予更仔細的關注。通過在實際編程前對算法進行分析，學生可以決定一個特定的解法是否可行。例如，學生在本書中將讀到一些特定的問題並看到精心的實現方法是如何把處理大量數據的時間從16年減至不到1秒的。因此，若無運行時間的闡釋，就不會有算法和數據結構的提出。在某些情況下，對於影響算法實現的運行時間的一些微小細節都需要認真探究。一旦確定解法，還必須編寫程序。隨著計算機的日益強大，它們必須解決的問題也變得更加巨大和復雜，這就要求開發更加復雜的程序。本書的目的是教授學生良好的程序設計技巧和提高學生的算法分析能力，使得他們能夠開發出具有優選效率的程序等