數(shù)據(jù)結(jié)構(gòu)和算法 Python和C++語言描述

目 錄
第　1 章 抽象與分析　1
1．1　概要　1
1．1．1　大型編程．　1
1．1．2　前方的道路　2
1．2　功能的抽象　3
1．2．1　契約式設(shè)計(jì)　3
1．2．2　驗(yàn)證先驗(yàn)條件　6
1．2．3　自上而下的設(shè)計(jì)．　9
1．2．4　記錄副作用．　11
1．3　算法分析．　12
1．3．1　線性搜索　12
1．3．2　二分搜索　14
1．3．3　非正式的算法比較．　15
1．3．4　算法的正式分析　17
1．3．5　大O 符號(hào)與Θ 符號(hào)　21
1．4　小結(jié)　23
1．5　練習(xí)　23
第　2 章 數(shù)據(jù)的抽象．　27
2．1　概要　27
2．2　抽象數(shù)據(jù)類型　27
2．2．1　從數(shù)據(jù)類型到抽象數(shù)據(jù)
類型．　28
2．2．2　定義抽象數(shù)據(jù)類型．　28
2．2．3　實(shí)現(xiàn)抽象數(shù)據(jù)類型．　30
2．3　抽象數(shù)據(jù)類型和對(duì)象　32
2．3．1　規(guī)范．　32
2．3．2　實(shí)現(xiàn)．　34
2．3．3　改變存儲(chǔ)方式　35
2．3．4　面向?qū)ο蟮脑O(shè)計(jì)和編程．　36
2．4　抽象數(shù)據(jù)類型的實(shí)例：
數(shù)據(jù)集（Dataset）　38
2．4．1　面向?qū)ο笤O(shè)計(jì)的過程　38
2．4．2　定義一個(gè)抽象數(shù)據(jù)
類型．　39
2．4．3　實(shí)現(xiàn)這個(gè)抽象數(shù)據(jù)類型．　41
2．5　抽象數(shù)據(jù)類型的實(shí)例：
有理數(shù)（Rational）　．42
2．5．1　運(yùn)算符重載．42
2．5．2　有理數(shù)（Rational）類44
2．6　增量開發(fā)以及單元測(cè)試45
2．7　小結(jié)48
2．8　練習(xí)48
第3　章 容器類52
3．1　概要52
3．2　Python 的列表52
3．3　順序集合：撲克牌牌組53
3．4　有序集合：手牌．56
3．4．1　創(chuàng)建橋牌的手牌56
3．4．2　比較撲克牌．58
3．4．3　撲克牌排序．59
3．5　Python 里列表的實(shí)現(xiàn)61
3．5．1　基于數(shù)組的列表61
3．5．2　效率分析62
3．6　Python 的字典（選讀） ．63
3．6．1　字典抽象數(shù)據(jù)類型63
3．6．2　熟悉Python 字典．64
3．6．3　字典的實(shí)現(xiàn)．65
3．6．4　擴(kuò)展示例：馬爾可夫鏈67
3．7　小結(jié)70
3．8　練習(xí)71
第4　章 鏈?zhǔn)浇Y(jié)構(gòu)和迭代器．75
4．1　概要75
4．2　Python 的內(nèi)存模型75
傳遞參數(shù)80
4．3　鏈表實(shí)現(xiàn)．81
4．4　鏈表抽象數(shù)據(jù)類型的實(shí)現(xiàn)．85
4．5　迭代器95
4．5．1　Python 的迭代器95
4．5．2　在鏈表（LList）里
添加迭代器．96
4．5．3　通過Python 的生成器來
迭代　97
4．6　基于游標(biāo)的列表API（選讀） ．　99
4．6．1　游標(biāo)（Cursor）的
API　99
4．6．2　Python 的游標(biāo)列表
（CursorList）　100
4．6．3　鏈?zhǔn)浇Y(jié)構(gòu)的游標(biāo)列表
（CursorList）　102
4．7　鏈表vs 數(shù)組　104
4．8　小結(jié)．　104
4．9　練習(xí)．　105
第5　章 堆棧和隊(duì)列　109
5．1　概要．　109
5．2　堆棧．　109
5．2．1　堆棧抽象數(shù)據(jù)類型　109
5．2．2　堆棧的簡(jiǎn)單應(yīng)用　110
5．2．3　堆棧的實(shí)現(xiàn)　112
5．2．4　應(yīng)用程序：處理算術(shù)
方程．　113
5．2．5　應(yīng)用程序：語法的處理
（選讀）?。?16
5．3　隊(duì)列．　119
5．3．1　隊(duì)列抽象數(shù)據(jù)類型　119
5．3．2　隊(duì)列的簡(jiǎn)單應(yīng)用　120
5．4　隊(duì)列的實(shí)現(xiàn)．　121
5．5　應(yīng)用程序示例：隊(duì)列的模擬
（選讀）?。?23
5．6　小結(jié)．　128
5．7　練習(xí)．　128
第6　章 遞歸　133
6．1　概要．　133
6．2　遞歸定義　134
6．3　簡(jiǎn)單的遞歸示例　136
6．3．1　示例：字符串反轉(zhuǎn)　136
6．3．2　示例：字謎　137
6．3．3　示例：快速計(jì)算指數(shù)．　138
6．3．4　示例：二分搜索　139
6．4　遞歸的分析．　140
6．5　排序．142
6．5．1　遞歸設(shè)計(jì)：歸并排序142
6．5．2　分析歸并排序．144
6．6　一個(gè)“難”題：漢諾塔146
6．7　小結(jié)．149
6．8　練習(xí)．150
第7　章 樹156
7．1　概要．156
7．2　樹的術(shù)語156
7．3　示例應(yīng)用程序：表達(dá)式樹158
7．4　樹的存儲(chǔ)方式159
7．5　應(yīng)用：二叉搜索樹．160
7．5．1　二分查找屬性．160
7．5．2　實(shí)現(xiàn)一個(gè)二叉搜索樹161
7．5．3　遍歷整個(gè)二叉搜索樹
（BST）　166
7．5．4　二叉搜索樹（BST）的
運(yùn)行時(shí)分析168
7．6　使用二叉搜索樹（BST）來
實(shí)現(xiàn)映射（選讀）169
7．7　小結(jié)．171
7．8　練習(xí)．172
第8　章 為Python 程序員準(zhǔn)備的
C++簡(jiǎn)介．177
8．1　概要．177
8．2　C++的歷史和背景178
8．3　注釋、代碼塊、變量名和
關(guān)鍵字．182
8．4　數(shù)據(jù)類型和變量聲明183
8．5　Include 語句、命名空間
以及輸入/輸出186
8．6　編譯．189
8．7　表達(dá)式和運(yùn)算符優(yōu)先級(jí)191
8．8　條件語句193
8．9　數(shù)據(jù)類型轉(zhuǎn)換196
8．10　循環(huán)語句197
8．11　數(shù)組199
8．11．1　一維數(shù)組199
8．11．2　多維數(shù)組201
8．11．3　字符數(shù)組．　201
8．12　函數(shù)的細(xì)節(jié)　202
8．12．1　聲明、定義以及原型．　202
8．12．2　值傳遞　205
8．12．3　引用傳遞．　205
8．12．4　將數(shù)組作為參數(shù)傳遞．　206
8．12．5　常量參數(shù)　208
8．12．6　默認(rèn)參數(shù)．　208
8．13　頭文件和內(nèi)聯(lián)函數(shù)　209
8．14　斷言與測(cè)試　213
8．15　變量的作用域以及生命周期．　214
8．16　Python 程序員編寫C++程序
時(shí)的常見錯(cuò)誤．　215
8．17　其他的C++相關(guān)話題
（選讀）　216
8．17．1　C++的Switch 語句．　216
8．17．2　創(chuàng)建C++的命名空間．　218
8．17．3　全局變量．　219
8．18　小結(jié)　220
8．19　練習(xí)　220
第9　章 C++類．　224
9．1　基本的語法和語義．　224
9．2　字符串　232
9．3　文件輸入和輸出　234
9．4　運(yùn)算符重載．　236
9．5　類變量和方法　242
9．6　小結(jié)．　246
9．7　練習(xí)．　246
第　10 章 C++的動(dòng)態(tài)內(nèi)存．　250
10．1　概要　250
10．2　C++的指針　254
10．3　動(dòng)態(tài)數(shù)組　259
10．4　動(dòng)態(tài)內(nèi)存類　263
10．4．1　析構(gòu)函數(shù)．　263
10．4．2　復(fù)制構(gòu)造函數(shù)　265
10．4．3　賦值運(yùn)算符　268
10．4．4　完整的動(dòng)態(tài)數(shù)組類　270
10．4．5　引用返回類型　275
10．5　動(dòng)態(tài)內(nèi)存錯(cuò)誤．　276
10．5．1　內(nèi)存泄漏．276
10．5．2　訪問無效內(nèi)存277
10．5．3　內(nèi)存錯(cuò)誤總結(jié)280
10．6　小結(jié)281
10．7　練習(xí)281
第　11 章 C++的鏈?zhǔn)浇Y(jié)構(gòu)285
11．1　概要285
11．2　C++鏈?zhǔn)浇Y(jié)構(gòu)的類286
11．3　C++鏈表．288
11．4　C++鏈接的動(dòng)態(tài)內(nèi)存錯(cuò)誤．298
11．5　小結(jié)299
11．6　練習(xí)300
第　12 章 C++模板．302
12．1　概要302
12．2　模板方法303
12．3　模板類．305
12．3．1　標(biāo)準(zhǔn)模板庫的
vector　類305
12．3．2　用戶定義的模板類．308
12．4　小結(jié)　311
12．5　練習(xí)312
第　13 章 堆、平衡樹和散列表314
13．1　概要314
13．2　優(yōu)先隊(duì)列和堆．314
13．2．1　堆排序320
13．2．2　關(guān)于堆和優(yōu)先隊(duì)列
實(shí)現(xiàn)的說明320
13．3　平衡樹．321
13．4　其他的樹結(jié)構(gòu)．329
13．5　散列表．329
13．6　小結(jié)339
13．7　練習(xí)339
第　14 章 圖．343
14．1　概要343
14．2　圖數(shù)據(jù)結(jié)構(gòu)344
14．3　最短路徑算法．347
14．3．1　無權(quán)最短路徑347
14．3．2　加權(quán)最短路徑350
14．4　深度優(yōu)先算法．353
14．5　最小生成樹　357
14．5．1　Kruskal 算法．　358
14．5．2　不交集數(shù)據(jù)結(jié)構(gòu)．　358
14．5．3　Prim 算法　361
14．6　小結(jié)　361
14．7　練習(xí)　362
第　15 章 算法技術(shù)　365
15．1　概要　365
15．2　分治算法　365
15．2．1　分析遞歸函數(shù)　366
15．2．2　快速排序．368
15．3　貪心算法372
15．4　動(dòng)態(tài)規(guī)劃378
15．4．1　最長(zhǎng)公共子序列379
15．4．2　記憶化382
15．4．3　矩陣鏈乘法382
15．5　NP 完全問題383
15．6　小結(jié)384
15．7　練習(xí)385
術(shù)語表387