前言
第1章　緒論1
　1.1　計(jì)算機(jī)問題求解1
　　1.1.1　程序開發(fā)過程1
　　1.1.2　一個簡單例子3
　1.2　問題求解：交叉路口的紅綠燈安排4
　　1.2.1　問題分析和嚴(yán)格化5
　　1.2.2　圖的頂點(diǎn)分組和算法6
　　1.2.3　算法的精化和Python描述7
　　1.2.4　討論8
　1.3　算法和算法分析10
　　1.3.1　問題、問題實(shí)例和算法10
　　1.3.2　算法的代價(jià)及其度量13
　　1.3.3　算法分析19
　　1.3.4　Python程序的計(jì)算代價(jià)（復(fù)雜度）21
　1.4　數(shù)據(jù)結(jié)構(gòu)24
　　1.4.1　數(shù)據(jù)結(jié)構(gòu)及其分類24
　　1.4.2　計(jì)算機(jī)內(nèi)存對象表示27
　　1.4.3　Python對象和數(shù)據(jù)結(jié)構(gòu)30
　練習(xí)32
第2章　抽象數(shù)據(jù)類型和Python類34
　2.1　抽象數(shù)據(jù)類型34
　　2.1.1　數(shù)據(jù)類型和數(shù)據(jù)構(gòu)造34
　　2.1.2　抽象數(shù)據(jù)類型的概念36
　　2.1.3　抽象數(shù)據(jù)類型的描述37
　2.2　Python的類和面向?qū)ο缶幊?9
　　2.2.1　類的定義和使用39
　　2.2.2　繼承44
　　2.2.3　異常類和自定義異常48
　　2.2.4　本書采用的ADT描述形式50
　總結(jié)50
　練習(xí)51
第3章　線性表53
　3.1　線性表的概念和表抽象數(shù)據(jù)類型53
　　3.1.1　表的概念和性質(zhì)53
　　3.1.2　表抽象數(shù)據(jù)類型53
　　3.1.3　線性表的實(shí)現(xiàn)：基本考慮55
　3.2　順序表56
　　3.2.1　基本實(shí)現(xiàn)方式56
　　3.2.2　順序表基本操作的實(shí)現(xiàn)57
　　3.2.3　順序表的實(shí)現(xiàn)結(jié)構(gòu)61
　　3.2.4　Python的list64
　　3.2.5　順序表的簡單總結(jié)65
　3.3　鏈接表66
　　3.3.1　線性表的基本需要和鏈接表66
　　3.3.2　單鏈表67
　　3.3.3　單鏈表類的實(shí)現(xiàn)72
　3.4　鏈表的變形和操作75
　　3.4.1　單鏈表的簡單變形75
　　3.4.2　循環(huán)單鏈表78
　　3.4.3　雙鏈表79
　　3.4.4　兩個鏈表操作81
　　3.4.5　在順序表里實(shí)現(xiàn)“鏈表”85
　　3.4.6　不同鏈表的簡單總結(jié)86
　3.5　表的應(yīng)用87
　　3.5.1　Josephus問題和基于數(shù)組概念的解法87
　　3.5.2　基于順序表的解88
　　3.5.3　基于循環(huán)單鏈表的解88
*3.6　廣義表和數(shù)組�　”緯�中標(biāo)星號的小節(jié)為選學(xué)/選講內(nèi)容。��89
　　3.6.1　廣義表89
　　3.6.2　數(shù)組92
　　3.6.3　矩陣94
　總結(jié)97
　練習(xí)98
第4章　字符串102
　4.1　字符集、字符串和字符串操作102
　　4.1.1　字符串的相關(guān)概念102
　　4.1.2　字符串抽象數(shù)據(jù)類型104
　4.2　字符串的實(shí)現(xiàn)104
　　4.2.1　基本實(shí)現(xiàn)問題和技術(shù)104
　　4.2.2　實(shí)際語言里的字符串105
　　4.2.3　Python的字符串106
　4.3　字符串匹配（子串查找）107
　　4.3.1　字符串匹配問題107
　　4.3.2　串匹配和樸素匹配算法108
　　4.3.3　無回溯串匹配算法（KMP算法）110
　4.4　字符串匹配問題115
　　4.4.1　串匹配/搜索的不同需要115
　　4.4.2　一種簡化的正則表達(dá)式117
*4.5　Python正則表達(dá)式119
　　4.5.1　正則表達(dá)式標(biāo)準(zhǔn)庫包re119
　　4.5.2　基本情況119
　　4.5.3　主要操作120
　　4.5.4　正則表達(dá)式的構(gòu)造121
　　4.5.5　正則表達(dá)式的使用127
　總結(jié)127
　練習(xí)128
第5章　棧和隊(duì)列130
　5.1　概述130
　　5.1.1　棧、隊(duì)列和數(shù)據(jù)使用順序130
　　5.1.2　應(yīng)用環(huán)境131
　5.2　棧：概念和實(shí)現(xiàn)131
　　5.2.1　棧抽象數(shù)據(jù)類型131
　　5.2.2　棧的順序表實(shí)現(xiàn)132
　　5.2.3　棧的鏈接表實(shí)現(xiàn)134
　5.3　棧的應(yīng)用134
　　5.3.1　簡單應(yīng)用：括號匹配問題135
　　5.3.2　表達(dá)式的表示、計(jì)算和變換137
　　5.3.3　棧與遞歸144
　5.4　隊(duì)列149
　　5.4.1　隊(duì)列抽象數(shù)據(jù)類型149
　　5.4.2　隊(duì)列的鏈接表實(shí)現(xiàn)150
　　5.4.3　隊(duì)列的順序表實(shí)現(xiàn)150
　　5.4.4　隊(duì)列的list實(shí)現(xiàn)152
　　5.4.5　隊(duì)列的應(yīng)用155
　5.5　迷宮求解和狀態(tài)空間搜索156
　　5.5.1　迷宮求解：分析和設(shè)計(jì)156
　　5.5.2　求解迷宮的算法159
　　5.5.3　迷宮問題和搜索161
　5.6　幾點(diǎn)補(bǔ)充166
　　5.6.1　與棧或隊(duì)列相關(guān)的幾種結(jié)構(gòu)166
　　5.6.2　順序?qū)崿F(xiàn)和鏈接實(shí)現(xiàn)166
　總結(jié)167
　練習(xí)168
第6章　二叉樹和樹170
　6.1　二叉樹170
　　6.1.1　概念和性質(zhì)170
　　6.1.2　抽象數(shù)據(jù)類型175
　　6.1.3　遍歷二叉樹176
　6.2　二叉樹的list實(shí)現(xiàn)177
　　6.2.1　設(shè)計(jì)和實(shí)現(xiàn)178
　　6.2.2　二叉樹的簡單應(yīng)用：表達(dá)式樹179
　6.3　優(yōu)先隊(duì)列182
　　6.3.1　概念182
　　6.3.2　基于線性表的實(shí)現(xiàn)183
　　6.3.3　樹形結(jié)構(gòu)和堆185
　　6.3.4　優(yōu)先隊(duì)列的堆實(shí)現(xiàn)186
　　6.3.5　堆的應(yīng)用：堆排序189
　6.4　應(yīng)用：離散事件模擬190
　　6.4.1　通用的模擬框架191
　　6.4.2　海關(guān)檢查站模擬系統(tǒng)192
　6.5　二叉樹的類實(shí)現(xiàn)196
　　6.5.1　二叉樹結(jié)點(diǎn)類197
　　6.5.2　遍歷算法198
　　6.5.3　二叉樹類202
　6.6　哈夫曼樹203
　　6.6.1　哈夫曼樹和哈夫曼算法203
　　6.6.2　哈夫曼算法的實(shí)現(xiàn)204
　　6.6.3　哈夫曼編碼205
　6.7　樹和樹林207
　　6.7.1　實(shí)例和表示207
　　6.7.2　定義和相關(guān)概念208
　　6.7.3　抽象數(shù)據(jù)類型和操作210
　　6.7.4　樹的實(shí)現(xiàn)211
　　6.7.5　樹的Python實(shí)現(xiàn)212
*6.8　等價(jià)類和查并集214
　　6.8.1　概念和問