數(shù)據(jù)結(jié)構(gòu)與算法：Python語言實(shí)現(xiàn)

出版者的話
譯者序
前言
致謝
作者簡(jiǎn)介
第1章　Python入門 1
1.1　Python概述 1
1.1.1　Python解釋器 1
1.1.2　Python程序預(yù)覽 1
1.2　Python對(duì)象 2
1.2.1　標(biāo)識(shí)符、對(duì)象和賦值語句 2
1.2.2　創(chuàng)建和使用對(duì)象 4
1.2.3　Python的內(nèi)置類 4
1.3　表達(dá)式、運(yùn)算符和優(yōu)先級(jí) 8
1.4　控制流程 12
1.4.1　條件語句 12
1.4.2　循環(huán)語句 14
1.5　函數(shù) 16
1.5.1　信息傳遞 17
1.5.2　Python的內(nèi)置函數(shù) 19
1.6　簡(jiǎn)單的輸入和輸出 20
1.6.1　控制臺(tái)輸入和輸出 21
1.6.2　文件 21
1.7　異常處理 22
1.7.1　拋出異常 23
1.7.2　捕捉異常 24
1.8　迭代器和生成器 26
1.9　Python的其他便利特點(diǎn) 28
1.9.1　條件表達(dá)式 29
1.9.2　解析語法 29
1.9.3　序列類型的打包和解包 30
1.10　作用域和命名空間 31
1.11　模塊和import語句 32
1.12　練習(xí) 34
擴(kuò)展閱讀 36
第2章　面向?qū)ο缶幊?37
2.1　目標(biāo)、原則和模式 37
2.1.1　面向?qū)ο蟮脑O(shè)計(jì)目標(biāo) 37
2.1.2　面向?qū)ο蟮脑O(shè)計(jì)原則 38
2.1.3　設(shè)計(jì)模式 39
2.2　軟件開發(fā) 40
2.2.1　設(shè)計(jì) 40
2.2.2　偽代碼 41
2.2.3　編碼風(fēng)格和文檔 42
2.2.4　測(cè)試和調(diào)試 43
2.3　類定義 44
2.3.1　例子：CreditCard類 45
2.3.2 運(yùn)算符重載和Python的特殊方法 48
2.3.3　例子：多維向量類 50
2.3.4　迭代器 51
2.3.5　例子：Range類 52
2.4　繼承 53
2.4.1　擴(kuò)展CreditCard類 54
2.4.2　數(shù)列的層次圖 57
2.4.3　抽象基類 60
2.5　命名空間和面向?qū)ο?62
2.5.1　實(shí)例和類命名空間 62
2.5.2　名稱解析和動(dòng)態(tài)調(diào)度 65
2.6　深拷貝和淺拷貝 65
2.7　練習(xí) 67
擴(kuò)展閱讀 70
第3章　算法分析 71
3.1　實(shí)驗(yàn)研究 71
3.2　本書使用的7種函數(shù) 74
3.2.1　常數(shù)函數(shù) 74
3.2.2　對(duì)數(shù)函數(shù) 74
3.2.3　線性函數(shù) 75
3.2.4　n-log-n函數(shù) 75
3.2.5　二次函數(shù) 76
3.2.6　三次函數(shù)和其他多項(xiàng)式 77
3.2.7　指數(shù)函數(shù) 77
3.2.8　比較增長率 79
3.3　漸近分析 79
3.3.1　大O符號(hào) 80
3.3.2　比較分析 82
3.3.3　算法分析示例 84
3.4　簡(jiǎn)單的證明技術(shù) 89
3.4.1　示例 89
3.4.2　反證法 89
3.4.3　歸納和循環(huán)不變量 90
3.5　練習(xí) 91
擴(kuò)展閱讀 95
第4章　遞歸 96
4.1　說明性的例子 96
4.1.1　階乘函數(shù) 96
4.1.2　繪制英式標(biāo)尺 97
4.1.3　二分查找 99
4.1.4　文件系統(tǒng) 101
4.2　分析遞歸算法 104
4.3　遞歸算法的不足 106
4.4　遞歸的其他例子 109
4.4.1　線性遞歸 109
4.4.2　二路遞歸 112
4.4.3　多重遞歸 113
4.5　設(shè)計(jì)遞歸算法 114
4.6　消除尾遞歸 115
4.7　練習(xí) 116
擴(kuò)展閱讀 118
第5章　基于數(shù)組的序列 119
5.1　Python序列類型 119
5.2　低層次數(shù)組 119
5.2.1　引用數(shù)組 121
5.2.2　Python中的緊湊數(shù)組 122
5.3　動(dòng)態(tài)數(shù)組和攤銷 124
5.3.1　實(shí)現(xiàn)動(dòng)態(tài)數(shù)組 126
5.3.2　動(dòng)態(tài)數(shù)組的攤銷分析 127
5.3.3　Python列表類 130
5.4　Python序列類型的效率 130
5.4.1　Python的列表和元組類 130
5.4.2　Python的字符串類 134
5.5　使用基于數(shù)組的序列 136
5.5.1　為游戲存儲(chǔ)高分 136
5.5.2　為序列排序 138
5.5.3　簡(jiǎn)單密碼技術(shù) 140
5.6　多維數(shù)據(jù)集 142
5.7　練習(xí) 145
擴(kuò)展閱讀 147
第6章　棧、隊(duì)列和雙端隊(duì)列 148
6.1　棧 148
6.1.1　棧的抽象數(shù)據(jù)類型 148
6.1.2 簡(jiǎn)單的基于數(shù)組的棧實(shí)現(xiàn) 149
6.1.3　使用棧實(shí)現(xiàn)數(shù)據(jù)的逆置 152
6.1.4　括號(hào)和HTML標(biāo)記匹配 152
6.2　隊(duì)列 155
6.2.1　隊(duì)列的抽象數(shù)據(jù)類型 155
6.2.2　基于數(shù)組的隊(duì)列實(shí)現(xiàn) 156
6.3　雙端隊(duì)列 160
6.3.1 雙端隊(duì)列的抽象數(shù)據(jù)類型 160
6.3.2 使用環(huán)形數(shù)組實(shí)現(xiàn)雙端隊(duì)列 161
6.3.3 Python collections模塊中的雙端隊(duì)列 162
6.4　練習(xí) 163
擴(kuò)展閱讀 165
第7章　鏈表 166
7.1　單向鏈表 166
7.1.1　用單向鏈表實(shí)現(xiàn)棧 169
7.1.2　用單向鏈表實(shí)現(xiàn)隊(duì)列 171
7.2　循環(huán)鏈表 173
7.2.1　輪轉(zhuǎn)調(diào)度 173
7.2.2　用循環(huán)鏈表實(shí)現(xiàn)隊(duì)列 174
7.3　雙向鏈表 175
7.3.1　雙向鏈表的基本實(shí)現(xiàn) 177
7.3.2　用雙向鏈表實(shí)現(xiàn)雙端隊(duì)列 179
7.4　位置列表的抽象數(shù)據(jù)類型 180
7.4.1 含位置信息的列表抽象數(shù)據(jù)類型 182
7.4.2　雙向鏈表實(shí)現(xiàn) 183
7.5　位置列表的排序 186
7.6　案例研究：維護(hù)訪問頻率 186
7.6.1　使用有序表 187
7.6.2　啟發(fā)式動(dòng)態(tài)調(diào)整列表 188
7.7 基于鏈接的序列與基于數(shù)組的序列 190
7.8　練習(xí) 192
擴(kuò)展閱讀 195
第8章　樹 196
8.1　樹的基本概念 196
8.1.1　樹的定義和屬性 196
8.1.2　樹的抽象數(shù)據(jù)類型 199
8.1.3　計(jì)算深度和高度 201
8.2　二叉樹 203
8.2.1　二叉樹的抽象數(shù)據(jù)類型 204
8.2.2　二叉樹的屬性 206
8.3　樹的實(shí)現(xiàn) 207
8.3.1　二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 207
8.3.2　基于數(shù)組表示的二叉樹 212
8.3.3　一般樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 214
8.4　樹的遍歷算法 214
8.4.1　樹的先序和后序遍歷 214
8.4.2　樹的廣度優(yōu)先遍歷 216
8.4.3　二叉樹的中