第 1章 導論 1 1.1　本章目標　1 1.2　入門　1 1.3　何謂計算機科學　1 1.3.1　何謂編程　3 1.3.2　為何學習數(shù)據(jù)結構及抽象數(shù)據(jù)類型　4 1.3.3　為何學習算法　4 1.4　Python基礎　5 1.4.1　數(shù)據(jù)　5 1.4.2　輸入與輸出　16 1.4.3　控制結構　18 1.4.4　異常處理　21 1.4.5　定義函數(shù)　23 1.4.6　Python面向?qū)ο缶幊蹋憾�義類　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數(shù)據(jù)結構的性能　49 2.3.1　列表　49 2.3.2　字典　53 2.4　小結　55 2.5　關鍵術語　55 2.6　討論題　56 2.7　編程練習　56 第3章　基本數(shù)據(jù)結構　57 3.1　本章目標　57 3.2　何謂線性數(shù)據(jù)結構　57 3.3　�！�58 3.3.1　何謂棧　58 3.3.2　棧抽象數(shù)據(jù)類型　59 3.3.3　用Python實現(xiàn)�！�60 3.3.4　匹配括號　62 3.3.5　普通情況：匹配符號　64 3.3.6　將十進制數(shù)轉(zhuǎn)換成二進制數(shù)　65 3.3.7　前序、中序和后序表達式　67 3.4　隊列　75 3.4.1　何謂隊列　75 3.4.2　隊列抽象數(shù)據(jù)類型　75 3.4.3　用Python實現(xiàn)隊列　76 3.4.4　模擬：傳土豆　77 3.4.5　模擬：打印任務　79 3.5　雙端隊列　84 3.5.1　何謂雙端隊列　84 3.5.2　雙端隊列抽象數(shù)據(jù)類型　84 3.5.3　用Python實現(xiàn)雙端隊列　85 3.5.4　回文檢測器　86 3.6　列表　88 3.6.1　無序列表抽象數(shù)據(jù)類型　88 3.6.2　實現(xiàn)無序列表：鏈表　89 3.6.3　有序列表抽象數(shù)據(jù)類型　97 3.6.4　實現(xiàn)有序列表　97 3.7　小結　100 3.8　關鍵術語　101 3.9　討論題　101 3.10　編程練習　102 第4章　遞歸　105 4.1　本章目標　105 4.2　何謂遞歸　105 4.2.1　計算一列數(shù)之和　105 4.2.2　遞歸三原則　107 4.2.3　將整數(shù)轉(zhuǎn)換成任意進制的字符串　108 4.3　棧幀：實現(xiàn)遞歸　110 4.4　遞歸可視化　111 4.5　復雜的遞歸問題　116 4.6　探索迷宮　118 4.7　動態(tài)規(guī)劃　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　實現(xiàn)　168 6.4.1　列表之列表　168 6.4.2　節(jié)點與引用　171 6.5　二叉樹的應用　173 6.5.1　解析樹　173 6.5.2　樹的遍歷　179 6.6　利用二叉堆實現(xiàn)優(yōu)先級隊列　182 6.6.1　二叉堆的操作　182 6.6.2　二叉堆的實現(xiàn)　183 6.7　二叉搜索樹　189 6.7.1　搜索樹的操作　190 6.7.2　搜索樹的實現(xiàn)　190 6.7.3　搜索樹的分析　201 6.8　平衡二叉搜索樹　202 6.8.1　AVL樹的性能　203 6.8.2　AVL樹的實現(xiàn)　204 6.8.3　映射實現(xiàn)總結　210 6.9　小結　211 6.10　關鍵術語　211 6.11　討論題　211 6.12　編程練習　213 第7章　圖及其算法　214 7.1　本章目標　214 7.2　術語及定義　215 7.3　圖的抽象數(shù)據(jù)類型　216 7.3.1　鄰接矩陣　216 7.3.2　鄰接表　217 7.3.3　實現(xiàn)　218 7.4　寬度優(yōu)先搜索　220 7.4.1　詞梯問題　220 7.4.2　構建詞梯圖　221 7.4.3　實現(xiàn)寬度優(yōu)先搜索　223 7.4.4　分析寬度優(yōu)先搜索　226 7.5　深度優(yōu)先搜索　226 7.5.1　騎士周游問題　226 7.5.2　構建騎士周游圖　227 7.5.3　實現(xiàn)騎士周游　229 7.5.4　分析騎士周游　231 7.5.5　通用深度優(yōu)先搜索　233 7.5.6　分析深度優(yōu)先搜索　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章　附加內(nèi)容　251 8.1　本章目標　251 8.2　復習Python列表　251 8.3　復習遞歸　256 8.3.1　同余定理　257 8.3.2　冪剩余　257 8.3.3　最大公因數(shù)與逆元　258 8.3.4　RSA算法　261 8.4　復習字典：跳表　264 8.4.1　映射抽象數(shù)據(jù)類型　265 8.4.2　用Python實現(xiàn)字典　265 8.5　復習樹：量化圖片　274 8.5.1　數(shù)字圖像概述　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