|
|
演算法不僅可用來解決現實世界中的種種實際問題，如透過關鍵字尋找網上最有用的資訊，尋找最短的旅遊路線來遊歷所有的景點，再比如無線通訊中的通道編碼和解碼；很多美妙的演算法源於人類對一些挑戰自身智力的謎題的思考，比如經典的華容道問題，尋找數獨的解法，再比如用程式戰勝九段圍棋高手等。書中的這些謎題深刻卻不枯燥，它適合也值得任何學術背景的人花時間閱讀和思考。使用和發現演算法是快樂的，這也是本書特別美好之處。畢竟人類的最高階段就是認識宇宙，瞭解生命起源，而更高階段是創造和優雅地解決那些有趣的謎題！
本書同時用函數式方法和傳統方法介紹主要的基本演算法和資料結構，資料結構部分包括二元樹、紅黑樹、AVL樹、Trie、Patricia、後綴樹、B樹、二元堆積、二項式堆積、斐波那契堆、Pairing堆、佇列、序列等；基本演算法部分包括各種排序演算法、序列搜索演算法，字串匹配演算法（KMP等），深度優先、廣度有限搜索演算法、貪心演算法及動態規劃。
作者簡介
劉新宇
1999年和2001年分別獲得清華大學自動化系學士和碩士學位，之後長期從事軟體研發工作。關注基本演算法和資料結構，尤其是函數式演算法，目前任職於亞馬遜中國倉儲和物流技術團隊。
前言
第一部分 樹
01 二元搜尋樹：資料結構中的「hello world」
1.1 定義.
1.2 資料組織
1.3 插入
1.4 檢查.
1.5 搜索
1.6 刪除.
1.7 隨機建置二元搜尋樹
02 插入排序的進化.
2.1 簡介
2.2 插入
2.3 改進一：二分尋找
2.4 改進二：使用鏈結串列
2.5 使用二元搜尋樹的最後改進
2.6 小結
03 並不複雜的紅黑樹
3.1 紅黑樹的定義
3.2 插入
3.3 刪除
3.4 指令式的紅黑樹演算法
3.5 小結
04 AVL 樹
4.1 AVL樹的定義
4.2 插入
4.3 刪除
4.4 AVL樹的指令式演算法
4.5 小結.
05 基數樹： Trie 和Patricia
5.1 整數Trie
5.2 整數Patricia
5.3 字元Trie
5.4 字元Patricia
5.5 Trie 和Patricia 的應用
5.6 小結
06 後綴樹
6.1 後綴Trie
6.2 後綴樹
6.3 後綴樹的應用
6.4 小結
07 B樹.
7.1 插入
7.2 刪除
7.3 搜索
7.4 小結
第二部分 堆積
08 二元堆積
8.1 用陣列實現隱式二元堆積
8.2 左偏堆積和skew 堆積：顯性的二元堆積
8.3 延伸堆積
8.4 小結
09 從吃葡萄到世界盃：選擇排序的進化
9.1 尋找最小元素
9.2 細微改進.
9.3 本質改進
9.4 小結
10 二項式堆積、費氏堆積和配對堆積
10.1 二項式堆積
10.2 費氏堆積
10.3 配對堆積
10.4 小結
第三部分 佇列和序列
11 並不簡單的佇列
11.1 單向鏈結串列和循環緩衝區實現的佇列
11.2 純函數式實現.
11.3 小改進：平衡佇列.
11.4 進一步改進：即時佇列
11.5 惰性即時佇列
11.6 小結
12 序列：最後一塊磚
12.1 二元隨機存取列表
12.2 二元隨機存取列表的數值表示
12.3 指令式雙陣列清單
12.4 可連接列表
12.5 手指樹
12.6 小結
第四部分 排序和搜索
13 分而治之：快速排序和歸併排序
13.1 快速排序
13.2 快速排序的效能分析
13.3 工程實作中的改進
13.4 針對最差情況的工程實作
13.5 其他工程實作
13.6 其他
13.7 歸併排序
13.8 原地歸併排序
13.9 自然歸併排序
13.10 自底向上歸併排序.
13.11 平行處理
13.12 小結
14 搜索
14.1 序列搜索
14.2 解的搜索.
14.3 小結
A 列表
B 參考文獻
