Python數據結構與算法分析（第3版） Problem Solving with Algorithms and Data Structures Using Python, 3/e

[美] 布拉德利·N. 米勒（Bradley N. Miller）美国路德学院计算机科学名誉教授，曾获美国计算机协会软件系统奖，对Python课程开发有深入研究，由他创立的互动式教科书平台Runestone Interactive与全球600多家教育机构有合作。

 

[美] 戴维·L. 拉努姆（David L. Ranum）

Merative高级科学家，医学信息学博士，致力于利用自然语言处理等人工智能技术解决医疗问题，曾在美国路德学院讲授计算机科学课程近三十载。

 

[乌] 罗曼·亚西诺夫斯基（Roman Yasinovskyy）

美国路德学院计算机科学系主任、副教授，授课范围涵盖算法、Web开发、计算机网络、数据库管理系统、操作系统、计算机体系结构以及信息安全等课程。博士毕业于陶森大学应用信息技术专业。

前言 iii

第 1章 導論 1

1.1 本章目標 1

1.2 入門 1

1.3 何謂電腦科學 1

1.3.1 何謂編程 3

1.3.2 為何學習數據結構及抽象數據類型 4

1.3.3 為何學習算法 5

1.4 Python基礎 5

1.4.1 數據 6

1.4.2 輸入與輸出 16

1.4.3 控制結構 20

1.4.4 異常處理 23

1.4.5 定義函數 25

1.4.6 Python面向對象編程：定義類 26

1.5 小結 39

1.6 關鍵術語 40

1.7 練習 40

第 2章 算法分析 42

2.1 本章目標 42

2.2 何謂算法分析 42

2.2.1 大O記法 45

2.2.2 異序詞檢測示例 48

2.3 Python數據結構的性能 51

2.3.1 列表 51

2.3.2 字典 56

2.4 小結 57

2.5 關鍵術語 57

2.6 練習 58

第3章 基本數據結構 59

3.1 本章目標 59

3.2 何謂線性數據結構 59

3.3 棧 60

3.3.1 棧抽象數據類型 61

3.3.2 用Python實現棧 62

3.3.3 匹配括號 64

3.3.4 通用問題：符號匹配 66

3.3.5 將十進制數轉換成二進制數 67

3.3.6 前序、中序和後序表達式 69

3.4 隊列 77

3.4.1 隊列抽象數據類型 78

3.4.2 用Python實現隊列 78

3.4.3 隊列模擬：傳馬鈴薯 80

3.4.4 隊列模擬：打印任務 81

3.4.5 雙端隊列 87

3.5 雙端隊列抽象數據類型 87

3.5.1 用Python實現雙端隊列 88

3.5.2 迴文檢測器 89

3.6 列表 91

3.6.1 無序列表抽象數據類型 91

3.6.2 實現無序列表：鏈表 92

3.6.3 有序列表抽象數據類型 100

3.6.4 實現有序列表 101

3.7 小結 104

3.8 關鍵術語 104

3.9 練習 105

第4章 遞歸 108

4.1 本章目標 108

4.2 何謂遞歸 108

4.2.1 計算一列數之和 108

4.2.2 遞歸三原則 111

4.2.3 將整數轉換成任意進制的字符串 111

4.3 棧幀：實現遞歸 113

4.4 可視化遞歸 115

4.5 復雜的遞歸問題 120

4.6 探索迷宮 123

4.7 動態規劃 128

4.8 小結 134

4.9 關鍵術語 134

4.10 練習 134

第5章 搜索和排序 137

5.1 本章目標 137

5.2 搜索 137

5.2.1 順序搜索 137

5.2.2 二分搜索 140

5.2.3 散列 142

5.3 排序 151

5.3.1 冒泡排序 151

5.3.2 選擇排序 154

5.3.3 插入排序 156

5.3.4 希爾排序 158

5.3.5 歸並排序 160

5.3.6 快速排序 163

5.4 小結 166

5.5 關鍵術語 167

5.6 練習 167

第6章 樹及其算法 170

6.1 本章目標 170

6.2 示例 170

6.3 術語及定義 173

6.4 實現 175

6.4.1 列表之列表 175

6.4.2 節點與引用 178

6.5 二叉樹的應用 180

6.5.1 解析樹 180

6.5.2 樹的遍歷 186

6.6 利用二叉堆實現優先級隊列 190

6.6.1 二叉堆的操作 190

6.6.2 二叉堆的實現 191

6.7 二叉搜索樹 198

6.7.1 搜索樹的操作 198

6.7.2 搜索樹的實現 198

6.7.3 搜索樹的分析 209

6.8 平衡二叉搜索樹 210

6.8.1 AVL樹的性能 211

6.8.2 AVL樹的實現 212

6.8.3 映射實現總結 219

6.9 小結 219

6.10 關鍵術語 219

6.11 練習 220

第7章 圖及其算法 223

7.1 本章目標 223

7.2 術語及定義 224

7.3 圖的抽象數據類型 225

7.3.1 鄰接矩陣 226

7.3.2 鄰接表 227

7.3.3 實現 227

7.4 廣度優先搜索 230

7.4.1 詞梯問題 230

7.4.2 構建詞梯圖 230

7.4.3 實現廣度優先搜索 232

7.4.4 分析廣度優先搜索 235

7.5 深度優先搜索 236

7.5.1 騎士周游問題 236

7.5.2 構建騎士周游圖 236

7.5.3 實現騎士周游 238

7.5.4 分析騎士周游 241

7.5.5 通用深度優先搜索 242

7.5.6 分析深度優先搜索 245

7.6 拓撲排序 246

7.7 強連通分量 247

7.8 最短路徑問題 250

7.8.1 Dijkstra算法 252

7.8.2 分析Dijkstra算法 254

7.8.3 Prim算法 254

7.9 小結 258

7.10 關鍵術語 259

7.11 練習 259

第8章 進階算法 261

8.1 本章目標 261

8.2 復習Python列表 261

8.3 復習遞歸 266

8.3.1 同餘定理 267

8.3.2 冪剩餘 267

8.3.3 最大公因子與逆元 268

8.3.4 RSA算法 271

8.4 復習字典：跳錶 275

8.4.1 映射抽象數據類型 276

8.4.2 用Python實現字典 276

8.5 復習樹：量化圖片 285

8.5.1 數字圖像概述 285

8.5.2 量化圖片 286

8.5.3 使用八叉樹改進量化算法 288

8.6 復習圖：模式匹配 296

8.6.1 生物學字符串 296

8.6.2 簡單比較 297

8.6.3 圖算法：DFA 298

8.6.4 圖算法：KMP 300

8.7 小結 302

8.8 關鍵術語 303

8.9 練習 303

參考資料 305

版權聲明 306