《世界著名計算機教材精選:算法與數據結構》內容精煉，強調了學生和專業人員必須熟悉的編程和基本數學語言，包括了數組與鍊表、散列表與關聯數組、排序與選擇、優先佇列、有序序列、圖的表示、圖的遍歷、最短路徑、最小生成樹和最佳化等章節。《世界著名計算機教材精選:算法與數據結構》首先提出問題，然後進行分析說明，最後給出問題的解決方案，在講解過程中，不僅給出清晰的定義，豐富的示例和練習，而且還採用插圖和偽代碼來解釋算法，再用真正的程式語言（如C++和Java）高效實現算法。
基本介紹
- 書名：世界著名計算機教材精選:算法與數據結構
- 又名：Algorithms and Data Structures the Basic Toolbox
- 作者：梅霍內 (Kurt Mehlhorn) 桑德斯 (Peter Sanders)
- ISBN：9787302310174
- 頁數：224頁
- 出版社：清華大學出版社
- 出版時間：2013年4月1日
- 開本：16
- 語種：簡體中文
基本介紹,內容簡介,作者簡介,圖書目錄,
基本介紹
內容簡介
《世界著名計算機教材精選:算法與數據結構》是作者多年的本科生和研究生算法課程的經驗薈萃，非常適合作為算法與數據結構課程的教材。
作者簡介
作者：（德國）梅霍內（Kurt Mehlhorn） （德國）桑德斯（Peter Sanders） 譯者：葛秀慧 田浩
圖書目錄
第1章開胃菜：整數運算1
1.1加法2
1.2乘法：學校方法2
1.3結果檢查5
1.4遞歸版的學校方法6
1.5Karatsuba乘法7
1.6算法工程9
1.7程式10
1.8引理1.5和定理1.7的證明13
1.9實現提示14
1.9.1C++14
1.9.2Java14
1.10歷史注釋與進一步的讀物15
第2章概述16
2.1漸近表示法16
2.2機器模型19
2.2.1外部存儲器20
2.2.2並行處理21
2.3偽代碼21
2.3.1變數和基本數據類型21
2.3.2語句23
2.3.3過程與函式23
2.3.4面向對象25
2.4設計正確的算法和程式25
2.4.1斷言和不變數26
2.4.2循環不變數26
2.4.3數據結構不變數27
2.4.4驗證算法27
2.5一個示例：二分查找27
2.6基本算法分析29
2.6.1求和29
2.6.2遞推30
2.6.3全局參數33
2.7平均情況分析33
2.7.1遞增計數器33
2.7.2從左到右的最大值34
2.7.3線性搜尋35
2.8隨機算法36
2.8.1形式模型37
2.8.2LasVegas和MonteCarlo算法38
2.9圖39
2.9.1第一個圖算法41
2.9.2樹41
2.9.3有序樹42
2.10P與NP43
2.11實現提示45
2.11.1C++45
2.11.2Java46
2.12歷史注釋與進一步的讀物46
第3章用數組與鍊表表示序列47
3.1鍊表48
3.1.1雙鍊表48
3.1.2單鍊表51
3.2無界數組52
3.2.1無界數組的平攤分析：全局參數53
3.2.2無界數組的平攤分析：局部參數55
3.2.3二進制計數器的平攤分析55
3.3*平攤分析56
3.3.1平攤分析：勢能方法或銀行賬戶方法57
3.3.2勢能方法的普遍性58
3.4棧與佇列58
3.5鍊表與數組60
3.6實現提示61
3.6.1C++61
3.6.2Java62
3.7歷史注釋與進一步的讀物62
第4章散列表與關聯數組64
4.1連結法散列66
4.2通用散列67
4.3線性探測散列71
4.4連結法與線性探測法72
4.5*完全散列73
4.6實現提示75
4.6.1C++76
4.6.2Java76
4.7歷史注釋與進一步的讀物76
第5章排序與選擇78
5.1簡單排序80
5.2歸併排序——O（nlogn）的排序算法81
5.3下界83
5.4快速排序85
5.4.1分析85
5.4.2細化87
5.5選擇89
5.6打破下界91
5.7外部排序93
5.7.1多路歸併94
5.7.2採樣排序94
5.8實現提示96
5.8.1C/C++97
5.8.2Java97
5.9歷史注釋與進一步的讀物97
第6章優先權佇列99
6.1二叉堆100
6.2可定址的優先權佇列104
6.2.1配對堆104
6.2.2斐波那契堆106
6.3外部存儲器109
6.4實現提示110
6.4.1C++110
6.4.2Java110
6.5歷史注釋與進一步的讀物111
第7章有序序列112
7.1二叉搜尋樹113
7.2（a，b）—樹與紅黑樹115
7.3更多的操作121
7.3.1連線121
7.3.2拆分122
7.4更新操作的平攤分析123
7.5增強搜尋樹124
7.5.1父指針125
7.5.2子樹大小125
7.6實現提示126
7.6.1C++127
7.6.2Java127
7.7歷史注釋與進一步的讀物128
第8章圖的表示130
8.1無序的邊序列131
8.2鄰接數組——靜態圖132
8.3鄰接表——動態圖132
8.4鄰接矩陣表示133
8.5隱式表示134
8.6實現提示134
8.6.1C++135
8.6.2Java135
8.7歷史注釋與進一步的讀物135
第9章圖的遍歷137
9.1廣度優先搜尋137
9.2深度優先搜尋139
9.2.1DFS編號、完成時間和拓撲排序140
9.2.2強連通分量142
9.3實現提示147
9.3.1C++147
9.3.2Java148
9.4歷史注釋與進一步的讀物148
第10章最短路徑149
10.1從基本概念到遺傳算法150
10.2有向無環圖153
10.3非負邊代價（Dijkstra算法）153
10.4*Dijkstra算法的平均情況分析156
10.5單調整數優先權佇列157
10.5.1桶佇列157
10.5.2*基數堆158
10.6任意邊代價（Bellman—Ford算法）161
10.7所有點對最短路徑和節點的勢162
10.8最短路徑查詢163
10.8.1目標定向搜尋164
10.8.2等級166
10.8.3中轉節點路線166
10.9實現提示167
10.9.1C++167
10.9.2Java167
10.10歷史注釋與進一步的讀物168
第11章最小生成樹169
11.1割和環的性質170
11.2Jarník—Prim算法171
11.3Kruskal算法172
11.4並—查數據結構173
11.5*外部存儲器176
11.5.1Semiexternal的Kruskal算法176
11.5.2邊收縮176
11.5.3Sibeyn算法176
11.6應用程式178
11.6.1Steiner樹問題178
11.6.2旅行推銷員之旅179
11.7實現提示180
11.7.1C++180
11.7.2Java180
11.8歷史注釋與進一步的讀物180
第12章遺傳方法最佳化182
12.1線性規劃：黑盒求解器183
12.1.1整數線性規劃185
12.2貪婪算法：永不回頭186
12.3動態規劃：子問題的構建189
12.4系統搜尋：有疑問，用蠻力192
12.4.1求解整數線性規劃194
12.5局部搜尋：全局思考，局部行動194
12.5.1爬山195
12.5.2模擬退火：從自然中學習196
12.5.3局部搜尋的最佳化201
12.6進化算法201
12.7實現提示203
12.8歷史注釋與進一步的讀物204
附錄A205
A.1數學符號205
A.2數學概念206
A.3機率論基礎207
A.4有用的公式210
A.4.1證明211
參考文獻21
1.1加法2
1.2乘法：學校方法2
1.3結果檢查5
1.4遞歸版的學校方法6
1.5Karatsuba乘法7
1.6算法工程9
1.7程式10
1.8引理1.5和定理1.7的證明13
1.9實現提示14
1.9.1C++14
1.9.2Java14
1.10歷史注釋與進一步的讀物15
第2章概述16
2.1漸近表示法16
2.2機器模型19
2.2.1外部存儲器20
2.2.2並行處理21
2.3偽代碼21
2.3.1變數和基本數據類型21
2.3.2語句23
2.3.3過程與函式23
2.3.4面向對象25
2.4設計正確的算法和程式25
2.4.1斷言和不變數26
2.4.2循環不變數26
2.4.3數據結構不變數27
2.4.4驗證算法27
2.5一個示例：二分查找27
2.6基本算法分析29
2.6.1求和29
2.6.2遞推30
2.6.3全局參數33
2.7平均情況分析33
2.7.1遞增計數器33
2.7.2從左到右的最大值34
2.7.3線性搜尋35
2.8隨機算法36
2.8.1形式模型37
2.8.2LasVegas和MonteCarlo算法38
2.9圖39
2.9.1第一個圖算法41
2.9.2樹41
2.9.3有序樹42
2.10P與NP43
2.11實現提示45
2.11.1C++45
2.11.2Java46
2.12歷史注釋與進一步的讀物46
第3章用數組與鍊表表示序列47
3.1鍊表48
3.1.1雙鍊表48
3.1.2單鍊表51
3.2無界數組52
3.2.1無界數組的平攤分析：全局參數53
3.2.2無界數組的平攤分析：局部參數55
3.2.3二進制計數器的平攤分析55
3.3*平攤分析56
3.3.1平攤分析：勢能方法或銀行賬戶方法57
3.3.2勢能方法的普遍性58
3.4棧與佇列58
3.5鍊表與數組60
3.6實現提示61
3.6.1C++61
3.6.2Java62
3.7歷史注釋與進一步的讀物62
第4章散列表與關聯數組64
4.1連結法散列66
4.2通用散列67
4.3線性探測散列71
4.4連結法與線性探測法72
4.5*完全散列73
4.6實現提示75
4.6.1C++76
4.6.2Java76
4.7歷史注釋與進一步的讀物76
第5章排序與選擇78
5.1簡單排序80
5.2歸併排序——O（nlogn）的排序算法81
5.3下界83
5.4快速排序85
5.4.1分析85
5.4.2細化87
5.5選擇89
5.6打破下界91
5.7外部排序93
5.7.1多路歸併94
5.7.2採樣排序94
5.8實現提示96
5.8.1C/C++97
5.8.2Java97
5.9歷史注釋與進一步的讀物97
第6章優先權佇列99
6.1二叉堆100
6.2可定址的優先權佇列104
6.2.1配對堆104
6.2.2斐波那契堆106
6.3外部存儲器109
6.4實現提示110
6.4.1C++110
6.4.2Java110
6.5歷史注釋與進一步的讀物111
第7章有序序列112
7.1二叉搜尋樹113
7.2（a，b）—樹與紅黑樹115
7.3更多的操作121
7.3.1連線121
7.3.2拆分122
7.4更新操作的平攤分析123
7.5增強搜尋樹124
7.5.1父指針125
7.5.2子樹大小125
7.6實現提示126
7.6.1C++127
7.6.2Java127
7.7歷史注釋與進一步的讀物128
第8章圖的表示130
8.1無序的邊序列131
8.2鄰接數組——靜態圖132
8.3鄰接表——動態圖132
8.4鄰接矩陣表示133
8.5隱式表示134
8.6實現提示134
8.6.1C++135
8.6.2Java135
8.7歷史注釋與進一步的讀物135
第9章圖的遍歷137
9.1廣度優先搜尋137
9.2深度優先搜尋139
9.2.1DFS編號、完成時間和拓撲排序140
9.2.2強連通分量142
9.3實現提示147
9.3.1C++147
9.3.2Java148
9.4歷史注釋與進一步的讀物148
第10章最短路徑149
10.1從基本概念到遺傳算法150
10.2有向無環圖153
10.3非負邊代價（Dijkstra算法）153
10.4*Dijkstra算法的平均情況分析156
10.5單調整數優先權佇列157
10.5.1桶佇列157
10.5.2*基數堆158
10.6任意邊代價（Bellman—Ford算法）161
10.7所有點對最短路徑和節點的勢162
10.8最短路徑查詢163
10.8.1目標定向搜尋164
10.8.2等級166
10.8.3中轉節點路線166
10.9實現提示167
10.9.1C++167
10.9.2Java167
10.10歷史注釋與進一步的讀物168
第11章最小生成樹169
11.1割和環的性質170
11.2Jarník—Prim算法171
11.3Kruskal算法172
11.4並—查數據結構173
11.5*外部存儲器176
11.5.1Semiexternal的Kruskal算法176
11.5.2邊收縮176
11.5.3Sibeyn算法176
11.6應用程式178
11.6.1Steiner樹問題178
11.6.2旅行推銷員之旅179
11.7實現提示180
11.7.1C++180
11.7.2Java180
11.8歷史注釋與進一步的讀物180
第12章遺傳方法最佳化182
12.1線性規劃：黑盒求解器183
12.1.1整數線性規劃185
12.2貪婪算法：永不回頭186
12.3動態規劃：子問題的構建189
12.4系統搜尋：有疑問，用蠻力192
12.4.1求解整數線性規劃194
12.5局部搜尋：全局思考，局部行動194
12.5.1爬山195
12.5.2模擬退火：從自然中學習196
12.5.3局部搜尋的最佳化201
12.6進化算法201
12.7實現提示203
12.8歷史注釋與進一步的讀物204
附錄A205
A.1數學符號205
A.2數學概念206
A.3機率論基礎207
A.4有用的公式210
A.4.1證明211
參考文獻21
