|
|
|
瞭解資料結構與演算法是透徹理解電腦科學的前提。隨著Python日益廣泛的應用，Python程式師需要實現與傳統的物件導向程式設計語言相似的資料結構與演算法。
本書是用Python描述資料結構與演算法的開山之作，彙聚了作者多年的實戰經驗，向讀者透徹講解在Python環境下，如何通過一系列存儲機制高效地實現各類演算法。通過本書，讀者將深刻理解Python資料結構、遞迴、搜索、排序、樹與圖的應用，等等。
布蘭得利·米勒（Bradley N. Miller）
美國路德學院電腦科學名譽教授，曾獲美國電腦協會軟體系統獎，對Python課程開發有深入研究，由他創立的互動式教科書平臺Runestone Interactive與全球600多家教育機構有合作。
大衛·拉努姆（David L. Ranum）
IBM Watson認知軟體工程師，醫學資訊學博士，致力於利用自然語言處理等人工智慧技術解決醫療問題，曾在美國路德學院講授電腦科學課程近三十載。
第 1章 導論 1
1．1 本章目標 1
1．2 入門 1
1．3 何謂電腦科學 1
1．3．1 何謂程式設計 3
1．3．2 為何學習資料結構及抽象資料類型 4
1．3．3 為何學習演算法 4
1．4 Python基礎 5
1．4．1 數據 5
1．4．2 輸入與輸出 16
1．4．3 控制結構 18
1．4．4 異常處理 21
1．4．5 定義函數 23
1．4．6 Python物件導向程式設計：定義類 24
1．5 小結 37
1．6 關鍵術語 38
1．7 討論題 38
1．8 程式設計練習 38
第2章 演算法分析 40
2．1 本章目標 0
2．2 何謂演算法分析 40
2．2．1 大O記法 43
2．2．2 異序詞檢測示例 46
2．3 Python資料結構的性能 49
2．3．1 列表 49
2．3．2 字典 53
2．4 小結 55
2．5 關鍵術語 55
2．6 討論題 56
2．7 程式設計練習 56
第3章 基本資料結構 57
3．1 本章目標 57
3．2 何謂線性資料結構 57
3．3 棧 58
3．3．1 何謂棧 58
3．3．2 棧抽象資料類型 59
3．3．3 用Python實現棧 60
3．3．4 匹配括弧 62
3．3．5 普通情況：匹配符號 64
3．3．6 將十進位數字轉換成二進位數字 65
3．3．7 前序、中序和後序運算式 67
3．4 佇列 75
3．4．1 何謂佇列 75
3．4．2 佇列抽象資料類型 75
3．4．3 用Python實現佇列 76
3．4．4 模擬：傳土豆 77
3．4．5 模擬：列印任務 79
3．5 雙端佇列 84
3．5．1 何謂雙端佇列 84
3．5．2 雙端佇列抽象資料類型 84
3．5．3 用Python實現雙端佇列 85
3．5．4 回文檢測器 86
3．6 列表 88
3．6．1 無序列表抽象資料類型 88
3．6．2 實現無序列表：鏈表 89
3．6．3 有序列表抽象資料類型 97
3．6．4 實現有序列表 97
3．7 小結 100
3．8 關鍵術語 101
3．9 討論題 101
3．10 程式設計練習 102
第4章 遞迴 105
4．1 本章目標 105
4．2 何謂遞迴 105
4．2．1 計算一列數之和 105
4．2．2 遞迴三原則 107
4．2．3 將整數轉換成任意進制的字串 108
4．3 棧幀：實現遞迴 110
4．4 遞迴視覺化 111
4．5 複雜的遞迴問題 116
4．6 探索迷宮 118
4．7 動態規劃 123
4．8 小結 128
4．9 關鍵術語 129
4．10 討論題 129
4．11 程式設計練習 129
第5章 搜索和排序 131
5．1 本章目標 131
5．2 搜索 131
5．2．1 循序搜尋 131
5．2．2 二分搜索 134
5．2．3 散列 136
5．3 排序 145
5．3．1 冒泡排序 145
5．3．2 選擇排序 147
5．3．3 插入排序 149
5．3．4 希爾排序 151
5．3．5 歸併排序 153
5．3．6 快速排序 156
5．4 小結 159
5．5 關鍵術語 160
5．6 討論題 160
5．7 程式設計練習 161
第6章 樹 163
6．1 本章目標 163
6．2 示例 163
6．3 術語及定義 166
6．4 實現 168
6．4．1 列表之列表 168
6．4．2 節點與引用 171
6．5 二叉樹的應用 173
6．5．1 解析樹 173
6．5．2 樹的遍歷 179
6．6 利用二叉堆實現優先順序佇列 182
6．6．1 二叉堆的操作 182
6．6．2 二叉堆的實現 183
6．7 二叉搜尋樹 189
6．7．1 搜尋樹的操作 190
6．7．2 搜尋樹的實現 190
6．7．3 搜尋樹的分析 201
6．8 平衡二叉搜尋樹 202
6．8．1 AVL樹的性能 203
6．8．2 AVL樹的實現 204
6．8．3 映射實現總結 210
6．9 小結 211
6．10 關鍵術語 211
6．11 討論題 211
6．12 程式設計練習 213
第7章 圖及其演算法 214
7．1 本章目標 214
7．2 術語及定義 215
7．3 圖的抽象資料類型 216
7．3．1 鄰接矩陣 216
7．3．2 鄰接表 217
7．3．3 實現 218
7．4 寬度優先搜索 220
7．4．1 詞梯問題 220
7．4．2 構建詞梯圖 221
7．4．3 實現寬度優先搜索 223
7．4．4 分析寬度優先搜索 226
7．5 深度優先搜索 226
7．5．1 騎士周遊問題 226
7．5．2 構建騎士周遊圖 227
7．5．3 實現騎士周遊 229
7．5．4 分析騎士周遊 231
7．5．5 通用深度優先搜索 233
7．5．6 分析深度優先搜索 236
7．6 拓撲排序 236
7．7 強連通單元 238
7．8 最短路徑問題 241
7．8．1 Dijkstra演算法 243
7．8．2 分析Dijkstra演算法 245
7．8．3 Prim演算法 245
7．9 小結 248
7．10 關鍵術語 249
7．11 討論題 249
7．12 程式設計練習 250
第8章 附加內容 251
8．1 本章目標 251
8．2 複習Python列表 251
8．3 複習遞迴 256
8．3．1 同余定理 257
8．3．2 冪剩餘 257
8．3．3 最大公因數與逆元 258
8．3．4 RSA演算法 261
8．4 複習字典：跳表 264
8．4．1 映射抽象資料類型 265
8．4．2 用Python實現字典 265
8．5 複習樹：量化圖片 274
8．5．1 數位圖像概述 274
8．5．2 量化圖片 275
8．5．3 使用八叉樹改進量化演算法 277
8．6 複習圖：模式匹配 284
8．6．1 生物學字串 285
8．6．2 簡單比較 285
8．6．3 使用圖：DFA 287
8．6．4 使用圖：KMP 288
8．7 小結 291
8．8 關鍵術語 291
8．9 討論題 291
8．10 程式設計練習 292
附錄A Python圖形包 293
附錄B Python資源 294
參考資料295
