《算法新解》一書由劉新宇所著，本書適合軟體開發人員、編程和算法愛好者，以及高校學生閱讀參考。郵電出版社出版發行。
基本介紹
- 書名：算法新解
- 作者：劉新宇
- ISBN：9787115440358
- 頁數：592
- 定價：99.00元
- 出版社：人民郵電出版社
- 出版時間：2016-12
- 裝幀：平裝
內容簡介,作者簡介,目錄,
內容簡介
本書分4 部分，同時用函式式方法和傳統方法介紹了主要的基本算法和數據結構，數據結構部分包括二叉樹、紅黑樹、AVL樹、Trie、Patricia、後綴樹、B樹、二叉堆、二項式堆、斐波那契堆、Pairing堆、佇列、序列等；基本算法部分包括各種排序算法、序列搜尋算法，字元串匹配算法（KMP等），深度優先、廣度有限搜尋算法、貪心算法以及動態規劃。
作者簡介
劉新宇，1999年和2001年分別獲得清華大學自動化系學士和碩士學位，之後長期從事軟體研發工作。他關注基本算法和數據結構，尤其是函式式算法，目前就職於亞馬遜中國倉儲和物流技術團隊。
目錄
第一部分 樹
第1章 二叉搜尋樹：數據結構中的“hello world” 3
第1章 二叉搜尋樹：數據結構中的“hello world” 3
1.1 定義 3
1.2 數據組織 5
1.3 插入 6
1.4 遍歷 8
1.5 搜尋 10
1.5.1 lookup 10
1.5.2 最小元素和最大元素 11
1.5.3 前驅和後繼 12
1.6 刪除 14
1.7 隨機構建二叉搜尋樹 18
第2章 插入排序的進化 19
2.1 簡介 19
2.2 插入 20
2.3 改進一：二分查找 20
2.4 改進二：使用鍊表 22
2.5 使用二叉搜尋樹的最終改進 26
2.6 小結 27
第3章 並不複雜的紅黑樹 28
3.1 紅黑樹的定義 32
3.2 插入 33
3.3 刪除 36
3.4 命令式的紅黑樹算法?* 44
3.5 小結 47
第4章 AVL樹 48
4.1 AVL樹的定義 48
4.2 插入 51
4.2.1 平衡調整 53
4.2.2 模式匹配 57
4.3 刪除 59
4.4 AVL樹的命令式算法?* 59
4.5 小結 63
第5章 基數樹：Trie和Patricia 65
1.2 數據組織 5
1.3 插入 6
1.4 遍歷 8
1.5 搜尋 10
1.5.1 lookup 10
1.5.2 最小元素和最大元素 11
1.5.3 前驅和後繼 12
1.6 刪除 14
1.7 隨機構建二叉搜尋樹 18
第2章 插入排序的進化 19
2.1 簡介 19
2.2 插入 20
2.3 改進一：二分查找 20
2.4 改進二：使用鍊表 22
2.5 使用二叉搜尋樹的最終改進 26
2.6 小結 27
第3章 並不複雜的紅黑樹 28
3.1 紅黑樹的定義 32
3.2 插入 33
3.3 刪除 36
3.4 命令式的紅黑樹算法?* 44
3.5 小結 47
第4章 AVL樹 48
4.1 AVL樹的定義 48
4.2 插入 51
4.2.1 平衡調整 53
4.2.2 模式匹配 57
4.3 刪除 59
4.4 AVL樹的命令式算法?* 59
4.5 小結 63
第5章 基數樹：Trie和Patricia 65
5.1 整數Trie 65
5.1.1 整數Trie的定義 67
5.1.2 插入 67
5.1.3 查找 69
5.2 整數Patricia 70
5.2.1 定義 71
5.2.2 插入 72
5.2.3 查找 78
5.3 字元Trie 80
5.3.1 定義 80
5.3.2 插入 81
5.3.3 查找 83
5.4 字元Patricia 84
5.4.1 定義 84
5.4.2 插入 85
5.4.3 查找 90
5.5 Trie和Patricia的套用 92
5.5.1 電子詞典和單詞自動補齊 92
5.5.2 T9輸入法 97
5.6 小結 102
第6章 後綴樹 103
6.1 後綴Trie 104
6.1.1 節點轉移和後綴連結 105
6.1.2 on-line構造 107
6.2 後綴樹 111
6.3 後綴樹的套用 121
6.3.1 字元串搜尋和模式匹配 121
6.3.2 查找最長重複子串 123
6.3.3 查找最長公共子串 125
6.3.4 查找最長回文 127
6.3.5 其他 128
6.4 小結 128
第7章 B樹 129
7.1 插入 131
7.2 刪除 139
7.2.1 刪除前預合併 139
7.2.2 先刪除再修復 139
7.3 搜尋 153
7.4 小結 155
第二部分 堆
第8章 二叉堆 159
8.1 用數組實現隱式二叉堆 159
5.1.1 整數Trie的定義 67
5.1.2 插入 67
5.1.3 查找 69
5.2 整數Patricia 70
5.2.1 定義 71
5.2.2 插入 72
5.2.3 查找 78
5.3 字元Trie 80
5.3.1 定義 80
5.3.2 插入 81
5.3.3 查找 83
5.4 字元Patricia 84
5.4.1 定義 84
5.4.2 插入 85
5.4.3 查找 90
5.5 Trie和Patricia的套用 92
5.5.1 電子詞典和單詞自動補齊 92
5.5.2 T9輸入法 97
5.6 小結 102
第6章 後綴樹 103
6.1 後綴Trie 104
6.1.1 節點轉移和後綴連結 105
6.1.2 on-line構造 107
6.2 後綴樹 111
6.3 後綴樹的套用 121
6.3.1 字元串搜尋和模式匹配 121
6.3.2 查找最長重複子串 123
6.3.3 查找最長公共子串 125
6.3.4 查找最長回文 127
6.3.5 其他 128
6.4 小結 128
第7章 B樹 129
7.1 插入 131
7.2 刪除 139
7.2.1 刪除前預合併 139
7.2.2 先刪除再修復 139
7.3 搜尋 153
7.4 小結 155
第二部分 堆
第8章 二叉堆 159
8.1 用數組實現隱式二叉堆 159
8.1.1 定義 159
8.1.2 Heapify 160
8.1.3 構造堆 163
8.1.4 堆的基本操作 164
8.1.5 堆排序 168
8.2 左偏堆和skew堆:顯式的二叉堆 169
8.2.1 定義 170
8.2.2 合併 172
8.2.3 基本堆操作 173
8.2.4 使用左偏堆實現堆排序 174
8.2.5 skew堆 174
8.3 伸展堆 177
8.3.1 定義 177
8.3.2 堆排序 183
8.4 小結 183
第9章 從吃葡萄到世界盃：選擇排序的進化 184
9.1 查找最小元素 186
9.1.1 標記 186
9.1.2 分組 188
9.1.3 選擇排序的性能 189
9.2 細微改進 190
9.2.1 比較方法參數化 190
9.2.2 細微調整 191
9.2.3 雞尾酒排序 192
9.3 本質改進 196
9.3.1 錦標賽淘汰法 196
9.3.2 使用堆排序進行最後的改進 204
9.4 小結 204
第10章 二項式堆、斐波那契堆和配對堆 205
10.1 二項式堆 205
10.1.1 定義 205
10.1.2 基本的堆操作 209
10.2 斐波那契堆 220
10.2.1 定義 220
10.2.2 基本堆操作 221
10.2.3 彈出操作的性能分析 230
10.2.4 減小key 232
10.2.5 “斐波那契堆”名字的由來 234
10.3 配對堆 237
10.3.1 定義 237
10.3.2 基本堆操作 238
10.4 小結 244
第三部分 佇列和序列
第11章 並不簡單的佇列 247
11.1 單向鍊表和循環緩衝區實現的佇列 247
8.1.2 Heapify 160
8.1.3 構造堆 163
8.1.4 堆的基本操作 164
8.1.5 堆排序 168
8.2 左偏堆和skew堆:顯式的二叉堆 169
8.2.1 定義 170
8.2.2 合併 172
8.2.3 基本堆操作 173
8.2.4 使用左偏堆實現堆排序 174
8.2.5 skew堆 174
8.3 伸展堆 177
8.3.1 定義 177
8.3.2 堆排序 183
8.4 小結 183
第9章 從吃葡萄到世界盃：選擇排序的進化 184
9.1 查找最小元素 186
9.1.1 標記 186
9.1.2 分組 188
9.1.3 選擇排序的性能 189
9.2 細微改進 190
9.2.1 比較方法參數化 190
9.2.2 細微調整 191
9.2.3 雞尾酒排序 192
9.3 本質改進 196
9.3.1 錦標賽淘汰法 196
9.3.2 使用堆排序進行最後的改進 204
9.4 小結 204
第10章 二項式堆、斐波那契堆和配對堆 205
10.1 二項式堆 205
10.1.1 定義 205
10.1.2 基本的堆操作 209
10.2 斐波那契堆 220
10.2.1 定義 220
10.2.2 基本堆操作 221
10.2.3 彈出操作的性能分析 230
10.2.4 減小key 232
10.2.5 “斐波那契堆”名字的由來 234
10.3 配對堆 237
10.3.1 定義 237
10.3.2 基本堆操作 238
10.4 小結 244
第三部分 佇列和序列
第11章 並不簡單的佇列 247
11.1 單向鍊表和循環緩衝區實現的佇列 247
11.1.1 單向鍊表實現 247
11.1.2 循環緩衝區實現 251
11.2 純函式式實現 253
11.2.1 雙列表佇列 254
11.2.2 雙數組佇列：一種對稱實現 255
11.3 小改進：平衡佇列 257
11.4 進一步改進：實時佇列 259
11.5 惰性實時佇列 266
11.6 小結 269
第12章 序列：最後一塊磚 271
12.1 二叉隨機訪問列表 271
12.1.1 普通數組和列表 271
12.1.2 使用森林表示序列 272
12.1.3 在序列的頭部插入 273
12.2 二叉隨機訪問列表的數值表示 279
12.3 命令式雙數組列表 285
12.3.1 定義 285
12.3.2 插入和添加 286
12.3.3 隨機訪問 286
12.3.4 刪除和平衡 287
12.4 可連線列表 289
12.5 手指樹 293
12.5.1 定義 293
12.5.2 向序列的頭部插入元素 295
12.5.3 從頭部刪除元素 298
12.5.4 刪除時處理不規則的手指樹 300
12.5.5 在序列的尾部添加元素 304
12.5.6 從尾部刪除元素 306
12.5.7 連線 307
12.5.8 手指樹的隨機訪問 312
12.6 小結 325
第四部分 排序和搜尋
11.1.2 循環緩衝區實現 251
11.2 純函式式實現 253
11.2.1 雙列表佇列 254
11.2.2 雙數組佇列：一種對稱實現 255
11.3 小改進：平衡佇列 257
11.4 進一步改進：實時佇列 259
11.5 惰性實時佇列 266
11.6 小結 269
第12章 序列：最後一塊磚 271
12.1 二叉隨機訪問列表 271
12.1.1 普通數組和列表 271
12.1.2 使用森林表示序列 272
12.1.3 在序列的頭部插入 273
12.2 二叉隨機訪問列表的數值表示 279
12.3 命令式雙數組列表 285
12.3.1 定義 285
12.3.2 插入和添加 286
12.3.3 隨機訪問 286
12.3.4 刪除和平衡 287
12.4 可連線列表 289
12.5 手指樹 293
12.5.1 定義 293
12.5.2 向序列的頭部插入元素 295
12.5.3 從頭部刪除元素 298
12.5.4 刪除時處理不規則的手指樹 300
12.5.5 在序列的尾部添加元素 304
12.5.6 從尾部刪除元素 306
12.5.7 連線 307
12.5.8 手指樹的隨機訪問 312
12.6 小結 325
第四部分 排序和搜尋
第13章 分而治之：快速排序和歸併排序 329
13.1 快速排序 329
13.1.1 基本形式 330
13.1.2 嚴格弱序 331
13.1.3 劃分 331
13.1.4 函式式劃分算法的小改進 335
13.2 快速排序的性能分析 337
13.3 工程實踐中的改進 340
13.4 針對最差情況的工程實踐 348
13.5 其他工程實踐 351
13.6 其他 351
13.7 歸併排序 352
13.8 原地歸併排序 360
13.8.1 死板原地歸併 360
13.8.2 原地工作區 362
13.8.3 原地歸併排序與鍊表歸併排序 366
13.9 自然歸併排序 368
13.10 自底向上歸併排序 374
13.11 並行處理 377
13.12 小結 377
第14章 搜尋 379
14.1 序列搜尋 379
14.1.1 分而治之的搜尋 379
14.1.2 信息復用 400
14.2 解的搜尋 428
14.2.1 深度優先搜尋和廣度優先搜尋 428
14.2.2 搜尋最優解 468
14.3 小結 498
附錄 列表 500
列表的定義 500
列表的基本操作 502
變換 527
提取子列表 536
fold 543
搜尋和匹配 549
zip和unzip 555
小結 558
參考文獻 559
索引 563
13.1 快速排序 329
13.1.1 基本形式 330
13.1.2 嚴格弱序 331
13.1.3 劃分 331
13.1.4 函式式劃分算法的小改進 335
13.2 快速排序的性能分析 337
13.3 工程實踐中的改進 340
13.4 針對最差情況的工程實踐 348
13.5 其他工程實踐 351
13.6 其他 351
13.7 歸併排序 352
13.8 原地歸併排序 360
13.8.1 死板原地歸併 360
13.8.2 原地工作區 362
13.8.3 原地歸併排序與鍊表歸併排序 366
13.9 自然歸併排序 368
13.10 自底向上歸併排序 374
13.11 並行處理 377
13.12 小結 377
第14章 搜尋 379
14.1 序列搜尋 379
14.1.1 分而治之的搜尋 379
14.1.2 信息復用 400
14.2 解的搜尋 428
14.2.1 深度優先搜尋和廣度優先搜尋 428
14.2.2 搜尋最優解 468
14.3 小結 498
附錄 列表 500
列表的定義 500
列表的基本操作 502
變換 527
提取子列表 536
fold 543
搜尋和匹配 549
zip和unzip 555
小結 558
參考文獻 559
索引 563
