《算法（第4版）》是一本美 Robert Sedgewick / 美Kevin Wayne編寫，由人民郵電出版社在2012年出版的書籍。
基本介紹
- 作者：美 Robert Sedgewick / 美Kevin Wayne
- 譯者：謝路雲
- ISBN：9787115293800
- 頁數：636
- 定價：99.00元
- 出版社：人民郵電出版社
- 出版時間：2012-10
- 裝幀：平裝
內容介紹,作者介紹,作品目錄,
內容介紹
《算法(第4版)》是Sedgewick之巨著，與高德納TAOCP一脈相承，是算法領域經典的參考書，涵蓋所有程式設計師必須掌握的50種算法，全面介紹了關於算法和數據結構的必備知識，並特別針對排序、搜尋、圖處理和字元串處理進行了論述。第4版具體給出了每位程式設計師應知應會的50個算法，提供了實際代碼，而且這些Java代碼實現採用了模組化的編程風格，讀者可以方便地加以改造。配套網站提供了《算法(第4版)》內容的摘要及更多的代碼實現、測試數據、練習、教學課件等資源。
《算法(第4版)》適合用做大學教材或從業者的參考書。
作者介紹
Robert Sedgewick 史丹福大學博士，導師為Donald E. Knuth，從1985年開始一直擔任普林斯頓大學計算機科學系教授，曾任該系主任，也是Adobe Systems公司董事會成員，曾在Xerox PARC、國防分析研究所（Institute for Defense Analyses）和法國國家信息與自動化研究所（INRIA）從事研究工作。他的研究方向包括解析組合學、數據結構和算法的分析與設計、程式可視化等。
Kevin Wayne 康奈爾大學博士，普林斯頓大學計算機科學系高級講師，研究方向包括算法的設計、分析和實現，特別是圖和離散最佳化。
作品目錄
目錄
第1章 基礎 1
1.1 基礎編程模型 4
1.1.1 Java程式的基本結構 4
1.1.2 原始數據類型與表達式 6
1.1.3 語句 8
1.1.4 簡便記法 9
1.1.5 數組 10
1.1.6 靜態方法 12
1.1.7 API 16
1.1.8 字元串 20
1.1.9 輸入輸出 21
1.1.10 二分查找 28
1.1.11 展望 30
1.2 數據抽象 38
1.2.1 使用抽象數據類型 38
1.2.2 抽象數據類型舉例 45
1.2.3 抽象數據類型的實現 52
1.2.4 更多抽象數據類型的實現 55
1.2.5 數據類型的設計 60
1.3 背包、佇列和棧 74
1.3.1 API 74
1.3.2 集合類數據類型的實現 81
1.3.3 鍊表 89
1.3.4 綜述 98
1.4 算法分析 108
1.4.1 科學方法 108
1.4.2 觀察 108
1.4.3 數學模型 112
1.4.4 增長數量級的分類 117
1.4.5 設計更快的算法 118
1.4.6 倍率實驗 121
1.4.7 注意事項 123
1.4.8 處理對於輸入的依賴 124
1.4.9 記憶體 126
1.4.10 展望 129
1.5 案例研究：union-find算法 136
1.5.1 動態連通性 136
1.5.2 實現 140
1.5.3 展望 148
第2章 排序 152
2.1 初級排序算法 153
2.1.1 遊戲規則 153
2.1.2 選擇排序 155
2.1.3 插入排序 157
2.1.4 排序算法的可視化 159
2.1.5 比較兩種排序算法 159
2.1.6 希爾排序 162
2.2 歸併排序 170
2.2.1 原地歸併的抽象方法 170
2.2.2 自頂向下的歸併排序 171
2.2.3 自底向上的歸併排序 175
2.2.4 排序算法的複雜度 177
2.3 快速排序 182
2.3.1 基本算法 182
2.3.2 性能特點 185
2.3.3 算法改進 187
2.4 優先佇列 195
2.4.1 API 195
2.4.2 初級實現 197
2.4.3 堆的定義 198
2.4.4 堆的算法 199
2.4.5 堆排序 205
2.5 套用 214
2.5.1 將各種數據排序 214
2.5.2 我應該使用哪種排序算法 218
2.5.3 問題的歸約 219
2.5.4 排序套用一覽 221
第3章 查找 227
3.1 符號表 228
3.1.1 API 228
3.1.2 有序符號表 230
3.1.3 用例舉例 233
3.1.4 無序鍊表中的順序查找 235
3.1.5 有序數組中的二分查找 238
3.1.6 對二分查找的分析 242
3.1.7 預覽 244
3.2 二叉查找樹 250
3.2.1 基本實現 250
3.2.2 分析 255
3.2.3 有序性相關的方法與刪除操作 257
3.3 平衡查找樹 269
3.3.1 2-3查找樹 269
3.3.2 紅黑二叉查找樹 275
3.3.3 實現 280
3.3.4 刪除操作 282
3.3.5 紅黑樹的性質 284
3.4 散列表 293
3.4.1 散列函式 293
3.4.2 基於拉鏈法的散列表 297
3.4.3 基於線性探測法的散列表 300
3.4.4 調整數組大小 304
3.4.5 記憶體使用 306
3.5 套用 312
3.5.1 我應該使用符號表的哪種實現 312
3.5.2 集合的API 313
3.5.3 字典類用例 315
3.5.4 索引類用例 318
3.5.5 稀疏向量 322
第4章 圖 329
4.1 無向圖 331
4.1.1 術語表 331
4.1.2 表示無向圖的數據類型 333
4.1.3 深度優先搜尋 338
4.1.4 尋找路徑 342
4.1.5 廣度優先搜尋 344
4.1.6 連通分量 349
4.1.7 符號圖 352
4.1.8 總結 358
4.2 有向圖 364
4.2.1 術語 364
4.2.2 有向圖的數據類型 365
4.2.3 有向圖中的可達性 367
4.2.4 環和有向無環圖 369
4.2.5 有向圖中的強連通性 378
4.2.6 總結 385
4.3 最小生成樹 390
4.3.1 原理 391
4.3.2 加權無向圖的數據類型 393
4.3.3 最小生成樹的API和測試用例 396
4.3.4 Prim算法 398
4.3.5 Prim算法的即時實現 401
4.3.6 Kruskal算法 404
4.3.7 展望 407
4.4 最短路徑 412
4.4.1 最短路徑的性質 413
4.4.2 加權有向圖的數據結構 414
4.4.3 最短路徑算法的理論基礎 420
4.4.4 Dijkstra算法 421
4.4.5 無環加權有向圖中的最短路徑算法 425
4.4.6 一般加權有向圖中的最短路徑問題 433
4.4.7 展望 445
第5章 字元串 451
5.1 字元串排序 455
5.1.1 鍵索引計數法 455
5.1.2 低位優先的字元串排序 458
5.1.3 高位優先的字元串排序 461
5.1.4 三向字元串快速排序 467
5.1.5 字元串排序算法的選擇 470
5.2 單詞查找樹 474
5.2.1 單詞查找樹 475
5.2.2 單詞查找樹的性質 483
5.2.3 三向單詞查找樹 485
5.2.4 三向單詞查找樹的性質 487
5.2.5 應該使用字元串符號表的哪種實現 489
5.3 子字元串查找 493
5.3.1 歷史簡介 493
5.3.2 暴力子字元串查找算法 494
5.3.3 Knuth-Morris-Pratt子字元串查找算法 496
5.3.4 Boyer-Moore字元串查找算法 502
5.3.5 Rabin-Karp指紋字元串查找算法 505
5.3.6 總結 509
5.4 正則表達式 514
5.4.1 使用正則表達式描述模式 514
5.4.2 縮略寫法 516
5.4.3 正則表達式的實際套用 517
5.4.4 非確定有限狀態自動機 518
5.4.5 模擬NFA的運行 520
5.4.6 構造與正則表達式對應的
5.5 數據壓縮 529
5.5.1 遊戲規則 529
5.5.2 讀寫二進制數據 530
5.5.3 局限 533
5.5.4 熱身運動：基因組 534
5.5.5 遊程編碼 537
5.5.6 霍夫曼壓縮 540
第6章 背景 558
索引 611
第1章 基礎 1
1.1 基礎編程模型 4
1.1.1 Java程式的基本結構 4
1.1.2 原始數據類型與表達式 6
1.1.3 語句 8
1.1.4 簡便記法 9
1.1.5 數組 10
1.1.6 靜態方法 12
1.1.7 API 16
1.1.8 字元串 20
1.1.9 輸入輸出 21
1.1.10 二分查找 28
1.1.11 展望 30
1.2 數據抽象 38
1.2.1 使用抽象數據類型 38
1.2.2 抽象數據類型舉例 45
1.2.3 抽象數據類型的實現 52
1.2.4 更多抽象數據類型的實現 55
1.2.5 數據類型的設計 60
1.3 背包、佇列和棧 74
1.3.1 API 74
1.3.2 集合類數據類型的實現 81
1.3.3 鍊表 89
1.3.4 綜述 98
1.4 算法分析 108
1.4.1 科學方法 108
1.4.2 觀察 108
1.4.3 數學模型 112
1.4.4 增長數量級的分類 117
1.4.5 設計更快的算法 118
1.4.6 倍率實驗 121
1.4.7 注意事項 123
1.4.8 處理對於輸入的依賴 124
1.4.9 記憶體 126
1.4.10 展望 129
1.5 案例研究：union-find算法 136
1.5.1 動態連通性 136
1.5.2 實現 140
1.5.3 展望 148
第2章 排序 152
2.1 初級排序算法 153
2.1.1 遊戲規則 153
2.1.2 選擇排序 155
2.1.3 插入排序 157
2.1.4 排序算法的可視化 159
2.1.5 比較兩種排序算法 159
2.1.6 希爾排序 162
2.2 歸併排序 170
2.2.1 原地歸併的抽象方法 170
2.2.2 自頂向下的歸併排序 171
2.2.3 自底向上的歸併排序 175
2.2.4 排序算法的複雜度 177
2.3 快速排序 182
2.3.1 基本算法 182
2.3.2 性能特點 185
2.3.3 算法改進 187
2.4 優先佇列 195
2.4.1 API 195
2.4.2 初級實現 197
2.4.3 堆的定義 198
2.4.4 堆的算法 199
2.4.5 堆排序 205
2.5 套用 214
2.5.1 將各種數據排序 214
2.5.2 我應該使用哪種排序算法 218
2.5.3 問題的歸約 219
2.5.4 排序套用一覽 221
第3章 查找 227
3.1 符號表 228
3.1.1 API 228
3.1.2 有序符號表 230
3.1.3 用例舉例 233
3.1.4 無序鍊表中的順序查找 235
3.1.5 有序數組中的二分查找 238
3.1.6 對二分查找的分析 242
3.1.7 預覽 244
3.2 二叉查找樹 250
3.2.1 基本實現 250
3.2.2 分析 255
3.2.3 有序性相關的方法與刪除操作 257
3.3 平衡查找樹 269
3.3.1 2-3查找樹 269
3.3.2 紅黑二叉查找樹 275
3.3.3 實現 280
3.3.4 刪除操作 282
3.3.5 紅黑樹的性質 284
3.4 散列表 293
3.4.1 散列函式 293
3.4.2 基於拉鏈法的散列表 297
3.4.3 基於線性探測法的散列表 300
3.4.4 調整數組大小 304
3.4.5 記憶體使用 306
3.5 套用 312
3.5.1 我應該使用符號表的哪種實現 312
3.5.2 集合的API 313
3.5.3 字典類用例 315
3.5.4 索引類用例 318
3.5.5 稀疏向量 322
第4章 圖 329
4.1 無向圖 331
4.1.1 術語表 331
4.1.2 表示無向圖的數據類型 333
4.1.3 深度優先搜尋 338
4.1.4 尋找路徑 342
4.1.5 廣度優先搜尋 344
4.1.6 連通分量 349
4.1.7 符號圖 352
4.1.8 總結 358
4.2 有向圖 364
4.2.1 術語 364
4.2.2 有向圖的數據類型 365
4.2.3 有向圖中的可達性 367
4.2.4 環和有向無環圖 369
4.2.5 有向圖中的強連通性 378
4.2.6 總結 385
4.3 最小生成樹 390
4.3.1 原理 391
4.3.2 加權無向圖的數據類型 393
4.3.3 最小生成樹的API和測試用例 396
4.3.4 Prim算法 398
4.3.5 Prim算法的即時實現 401
4.3.6 Kruskal算法 404
4.3.7 展望 407
4.4 最短路徑 412
4.4.1 最短路徑的性質 413
4.4.2 加權有向圖的數據結構 414
4.4.3 最短路徑算法的理論基礎 420
4.4.4 Dijkstra算法 421
4.4.5 無環加權有向圖中的最短路徑算法 425
4.4.6 一般加權有向圖中的最短路徑問題 433
4.4.7 展望 445
第5章 字元串 451
5.1 字元串排序 455
5.1.1 鍵索引計數法 455
5.1.2 低位優先的字元串排序 458
5.1.3 高位優先的字元串排序 461
5.1.4 三向字元串快速排序 467
5.1.5 字元串排序算法的選擇 470
5.2 單詞查找樹 474
5.2.1 單詞查找樹 475
5.2.2 單詞查找樹的性質 483
5.2.3 三向單詞查找樹 485
5.2.4 三向單詞查找樹的性質 487
5.2.5 應該使用字元串符號表的哪種實現 489
5.3 子字元串查找 493
5.3.1 歷史簡介 493
5.3.2 暴力子字元串查找算法 494
5.3.3 Knuth-Morris-Pratt子字元串查找算法 496
5.3.4 Boyer-Moore字元串查找算法 502
5.3.5 Rabin-Karp指紋字元串查找算法 505
5.3.6 總結 509
5.4 正則表達式 514
5.4.1 使用正則表達式描述模式 514
5.4.2 縮略寫法 516
5.4.3 正則表達式的實際套用 517
5.4.4 非確定有限狀態自動機 518
5.4.5 模擬NFA的運行 520
5.4.6 構造與正則表達式對應的
5.5 數據壓縮 529
5.5.1 遊戲規則 529
5.5.2 讀寫二進制數據 530
5.5.3 局限 533
5.5.4 熱身運動：基因組 534
5.5.5 遊程編碼 537
5.5.6 霍夫曼壓縮 540
第6章 背景 558
索引 611
