Python數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記

第1 章 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)
1.1 數(shù)據(jù)結(jié)構(gòu) 1
1.1.1 數(shù)據(jù)結(jié)構(gòu)的核心技術(shù) .1
1.1.2 數(shù)據(jù)結(jié)構(gòu)的起源和發(fā)展現(xiàn)狀 .2
1.1.3 數(shù)據(jù)結(jié)構(gòu)中的基本概念 .2
1.2 常用的數(shù)據(jù)結(jié)構(gòu)和分類(lèi) 3
1.2.1 數(shù)據(jù)結(jié)構(gòu)的分類(lèi) .3
1.2.2 常用的數(shù)據(jù)結(jié)構(gòu) .6
1.3 數(shù)據(jù)類(lèi)型和抽象數(shù)據(jù)類(lèi)型 7
1.3.1 數(shù)據(jù)類(lèi)型 .7
1.3.2 抽象數(shù)據(jù)類(lèi)型 .7
第2 章 算法
2.1 算法是程序的靈魂 9
2.1.1 算法的定義 .9
2.1.2 算法的特征 .10
2.1.3 為什么說(shuō)算法是程序的靈魂 .10
2.1.4 認(rèn)識(shí)計(jì)算機(jī)中的算法 .11
2.2 數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系 12
2.3 在計(jì)算機(jī)中表示算法的方法 13
2.3.1 用流程圖來(lái)表示算法 .13
2.3.2 用N-S 流程圖來(lái)表示算法 .14
2.3.3 用計(jì)算機(jī)語(yǔ)言來(lái)表示算法 .15
2.4 時(shí)間復(fù)雜度 15
2.4.1 尋找最優(yōu)算法 .16
2.4.2 常見(jiàn)算法的時(shí)間復(fù)雜度 .16
2.4.3 實(shí)戰(zhàn)演練——用Python 體驗(yàn)時(shí)間復(fù)雜度 17
2.5 常用的算法思想 19
2.5.1 枚舉算法思想 .19
2.5.2 遞歸算法思想 .20
2.5.3 分治算法思想 .20
2.5.4 貪心算法思想 .20
2.5.5 試探法算法思想 .21
2.5.6 迭代算法 .22
第3 章 Python 內(nèi)置的幾種數(shù)據(jù)結(jié)構(gòu)
3.1 使用列表 23
3.1.1 列表的基本用法 .23
3.1.2 實(shí)戰(zhàn)演練——?jiǎng)h除列表中的重復(fù)元素并保持順序不變 .25
3.1.3 實(shí)戰(zhàn)演練——找出列表中出現(xiàn)次數(shù)最多的元素 .26
3.1.4 實(shí)戰(zhàn)演練——排序類(lèi)定義的實(shí)例 .26
3.1.5 實(shí)戰(zhàn)演練——使用列表推導(dǎo)式 .27
3.1.6 實(shí)戰(zhàn)演練——命名切片 .28
3.2 使用元組 29
3.2.1 實(shí)戰(zhàn)演練——?jiǎng)?chuàng)建并訪(fǎng)問(wèn)元組 .29
3.2.2 實(shí)戰(zhàn)演練——連接組合元組 .30
3.2.3 實(shí)戰(zhàn)演練——?jiǎng)h除元組 .30
3.2.4 實(shí)戰(zhàn)演練——使用內(nèi)置方法操作元組 .31
3.2.5 實(shí)戰(zhàn)演練——將序列分解為單獨(dú)的變量 .31
3.2.6 實(shí)戰(zhàn)演練——將序列中的最后幾項(xiàng)作為歷史記錄 .33
3.2.7 實(shí)戰(zhàn)演練——實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 .33
3.3 使用字典 35
3.3.1 實(shí)戰(zhàn)演練——?jiǎng)?chuàng)建并訪(fǎng)問(wèn)字典 .36
3.3.2 實(shí)戰(zhàn)演練——添加、修改、刪除字典中的元素 .36
3.3.3 實(shí)戰(zhàn)演練——映射多個(gè)值 .38
3.3.4 實(shí)戰(zhàn)演練——使用OrderedDict 類(lèi)創(chuàng)建有序字典 .39
3.3.5 實(shí)戰(zhàn)演練——獲取字典中的最大值和最小值 .40
3.3.6 實(shí)戰(zhàn)演練——獲取兩個(gè)字典中的相同鍵值對(duì) .41
3.3.7 實(shí)戰(zhàn)演練——使用函數(shù)itemgetter() 對(duì)字典進(jìn)行排序 42
3.3.8 使用字典推導(dǎo)式 .43
3.3.9 實(shí)戰(zhàn)演練——根據(jù)記錄進(jìn)行分組 .44
3.3.10 實(shí)戰(zhàn)演練——轉(zhuǎn)換并換算數(shù)據(jù) .45
3.3.11 實(shí)戰(zhàn)演練——將多個(gè)映射合并為單個(gè)映射 .47
第4 章 線(xiàn)性表
4.1 線(xiàn)性表的定義和基本特征 49
4.1.1 線(xiàn)性表和線(xiàn)性結(jié)構(gòu) .49
4.1.2 線(xiàn)性表的基本操作過(guò)程 .50
4.2 順序表的基本操作 50
4.2.1 順序表的定義和操作 .50
4.2.2 實(shí)戰(zhàn)演練——建立空的順序表 .53
4.2.3 實(shí)戰(zhàn)演練——按值查找 .53
4.2.4 實(shí)戰(zhàn)演練——插入新元素 .54
4.2.5 實(shí)戰(zhàn)演練——?jiǎng)h除操作 .55
4.2.6 實(shí)戰(zhàn)演練——實(shí)現(xiàn)順序表的插入、檢索、刪除和反轉(zhuǎn)操作 .56
4.3 鏈表操作 59
4.3.1 什么是鏈表 .59
4.3.2 實(shí)戰(zhàn)演練——Python 中的鏈表操作 .59
4.3.3 實(shí)戰(zhàn)演練——單向鏈表 .62
4.3.4 實(shí)戰(zhàn)演練——單向循環(huán)鏈表 .70
4.3.5 實(shí)戰(zhàn)演練——雙向鏈表 .75
4.3.6 實(shí)戰(zhàn)演練——雙向循環(huán)鏈表 .78
4.3.7 實(shí)戰(zhàn)演練——在鏈表中增加比較功能 .83
4.3.8 實(shí)戰(zhàn)演練——單鏈表結(jié)構(gòu)字符串 .85
4.3.9 實(shí)戰(zhàn)演練——改進(jìn)后的多次匹配操作 .87
第5 章 隊(duì)列和棧
5.1 隊(duì)列 90
5.1.1 什么是隊(duì)列 .90
5.1.2 Python 內(nèi)置的隊(duì)列操作方法 .91
5.1.3 實(shí)戰(zhàn)演練——基于內(nèi)置模塊queue 的隊(duì)列 92
5.1.4 實(shí)戰(zhàn)演練——基于列表自定義實(shí)現(xiàn)的優(yōu)先隊(duì)列 .96
5.1.5 實(shí)戰(zhàn)演練——基于堆實(shí)現(xiàn)的優(yōu)先隊(duì)列 .98
5.1.6 實(shí)戰(zhàn)演練——雙端隊(duì)列 .100
5.1.7 實(shí)戰(zhàn)演練——銀行業(yè)務(wù)隊(duì)列簡(jiǎn)單模擬 .101
5.2 棧 103
5.2.1 什么是棧 .103
5.2.2 實(shí)戰(zhàn)演練——入棧和出棧 .103
5.2.3 實(shí)戰(zhàn)演練——順序棧 .105
5.2.4 實(shí)戰(zhàn)演練——鏈棧 .107
5.2.5 實(shí)戰(zhàn)演練——檢查小括號(hào)是否成對(duì) .109
第6 章 樹(shù)
6.1 樹(shù)的基礎(chǔ)知識(shí) 111
6.1.1 什么是樹(shù) .111
6.1.2 樹(shù)的相關(guān)概念 .112
6.2 使用列表構(gòu)建樹(shù) 113
6.2.1 實(shí)戰(zhàn)演練——實(shí)現(xiàn)一個(gè)簡(jiǎn)單的樹(shù) .113
6.2.2 實(shí)戰(zhàn)演練——使用列表創(chuàng)建二叉樹(shù) .114
6.3 二叉樹(shù) 115
6.3.1 二叉樹(shù)的定義 .115
6.3.2 二叉樹(shù)的性質(zhì) .116
6.3.3 二叉樹(shù)存儲(chǔ) .117
6.3.4 實(shí)戰(zhàn)演練——使用嵌套列表構(gòu)建樹(shù) .119
6.3.5 實(shí)戰(zhàn)演練——把二叉樹(shù)的任何子節(jié)點(diǎn)當(dāng)成二叉樹(shù)進(jìn)行處理 .121
6.3.6 實(shí)戰(zhàn)演練——實(shí)現(xiàn)二叉搜索樹(shù)查找操作 .122
6.3.7 實(shí)戰(zhàn)演練——實(shí)現(xiàn)二叉搜索樹(shù)的刪除操作 .128
6.3.8 實(shí)戰(zhàn)演練——遍歷二叉樹(shù) .136
6.3.9 實(shí)戰(zhàn)演練——使用線(xiàn)索二叉樹(shù) .140
6.4 堆排列和二叉堆 148
6.4.1 實(shí)戰(zhàn)演練——使用Python 內(nèi)置的堆操作方法 148
6.4.2 實(shí)戰(zhàn)演練——實(shí)現(xiàn)二叉堆操作 .149
6.5 哈夫曼樹(shù) 151
6.5.1 哈夫曼樹(shù)基礎(chǔ) .152
6.5.2 實(shí)戰(zhàn)演練——使用面向過(guò)程方式和面向?qū)ο蠓绞綄?shí)現(xiàn)哈夫曼樹(shù) .154
6.5.3 實(shí)戰(zhàn)演練——實(shí)現(xiàn)哈夫曼樹(shù)的基本操作 .155
第7 章 圖
7.1 圖的起源 159
7.2 圖的相關(guān)概念 160
7.3 存儲(chǔ)結(jié)構(gòu) 163
7.3.1 使用鄰接矩陣表示圖 .163
7.3.2 實(shí)戰(zhàn)演練——將鄰接矩陣輸出成圖 .165
7.3.3 實(shí)戰(zhàn)演練——使用鄰接表表示圖 .165
7.3.4 鄰接矩陣與鄰接表的對(duì)比 .168
7.4 圖的遍歷 169
7.4.1 深度優(yōu)先搜索 .169
7.4.2 廣度優(yōu)先搜索 .171
7.4.3 實(shí)戰(zhàn)演練——實(shí)現(xiàn)圖的深度優(yōu)先和廣度優(yōu)先 .172
7.4.4 深度優(yōu)先算法和廣度優(yōu)先算法的比較和選擇 .174
7.5 圖的連通性 175
7.5.1 無(wú)向圖連通分量 .175
7.5.2 實(shí)戰(zhàn)演練——通過(guò)二維數(shù)組建立無(wú)向圖 .176
7.5.3 實(shí)戰(zhàn)演練——根據(jù)鄰接矩陣?yán)L制無(wú)向圖 .177
7.5.4 最小生成樹(shù) .178
7.5.5 實(shí)戰(zhàn)演練——實(shí)現(xiàn)最小生成樹(shù)和拓?fù)湫蛄?.179
7.5.6 關(guān)鍵路徑 .180
7.5.7 實(shí)戰(zhàn)演練——使用遞歸解決AOE 網(wǎng)絡(luò)最長(zhǎng)路關(guān)鍵路徑的問(wèn)題 .182
7.6 尋求最短路徑 184
7.6.1 求某一頂點(diǎn)到其他各頂點(diǎn)的最短路徑 .184
7.6.2 任意一對(duì)頂點(diǎn)間的最短路徑 .186
7.6.3 實(shí)戰(zhàn)演練——使用Dijkstra 算法計(jì)算指定一個(gè)點(diǎn)到其他
各頂點(diǎn)的路徑 .188
7.6.4 實(shí)戰(zhàn)演練——使用Floyd-Warshall 算法計(jì)算圖的最短路徑 189
7.6.5 實(shí)戰(zhàn)演練——使用Bellman-Ford 算法計(jì)算圖的最短路徑 .190
7.6.6 實(shí)戰(zhàn)演練——使用Dijkstra 算法解決加權(quán)最短路徑問(wèn)題 191
7.6.7 幾種最短路徑算法的比較 .193
第8 章 數(shù)據(jù)結(jié)構(gòu)的查找算法
8.1 數(shù)據(jù)結(jié)構(gòu)的查找處理 195
8.1.1 查找的基本概念 .195
8.1.2 查找算法的分類(lèi) .196
8.2 順序查找 196
8.2.1 順序查找法基礎(chǔ) .196
8.2.2 分析順序查找的性能 .197
8.2.3 使用Python 內(nèi)置函數(shù)順序查找 197
8.2.4 實(shí)戰(zhàn)演練———遍歷有序列表 .198
8.2.5 實(shí)戰(zhàn)演練———遍歷無(wú)序列表 .198
8.2.6 實(shí)戰(zhàn)演練———查找兩個(gè)有序列表的中位數(shù) .201
8.2.7 實(shí)戰(zhàn)演練———在列表中順序查找最大值和最小值 .202
8.3 折半查找算法 202
8.3.1 折半查找法基礎(chǔ) .203
8.3.2 分析折半查找法的性能 .203
8.3.3 實(shí)戰(zhàn)演練——使用折半查找算法查找指定的數(shù)據(jù) .203
8.3.4 實(shí)戰(zhàn)演練——使用遞歸折半查找和非遞歸折半查找 .204
8.3.5 實(shí)戰(zhàn)演練——比較順序查找算法和折半查找算法的效率 .206
8.4 插值查找算法 207
8.4.1 插值查找算法基礎(chǔ) .207
8.4.2 分析插值查找的性能 .208
8.4.3 實(shí)戰(zhàn)演練——使用插值查找算法查找指定的數(shù)據(jù) .208
8.5 分塊查找算法 209
8.5.1 分塊查找算法基礎(chǔ) .209
8.5.2 分析分塊查找算法的性能 .210
8.5.3 實(shí)戰(zhàn)演練——使用分塊查找算法在列表中查找某元素 .210
8.5.4 實(shí)戰(zhàn)演練——升級(jí)策略后的分塊查找算法 .212
8.5.5 實(shí)戰(zhàn)演練——一道算法題 .213
8.6 二叉排序樹(shù)法 216
8.6.1 二叉排序樹(shù)法基礎(chǔ) .216
8.6.2 分析二叉排序樹(shù)法的性能 .216
8.6.3 實(shí)戰(zhàn)演練——實(shí)現(xiàn)二叉樹(shù)的搜索、插入、刪除、先序遍歷
和后序遍歷操作 .217
8.7 平衡查找樹(shù)法 221
8.7.1 2-3 查找樹(shù) .221
8.7.2 平衡查找樹(shù)之紅黑樹(shù)（Red-Black Tree） 225
8.7.3 平衡二叉樹(shù) .227
8.8 哈希查找算法 233
8.8.1 哈希查找算法的基本思想 .233
8.8.2 分析哈希查找算法的性能 .234
8.8.3 實(shí)戰(zhàn)演練——使用哈希查找算法查找數(shù)據(jù) .234
8.9 斐波那契查找算法 235
8.9.1 斐波那契查找算法基礎(chǔ) .235
8.9.2 實(shí)戰(zhàn)演練——使用斐波那契查找算法查找數(shù)據(jù) .236
第9 章 數(shù)據(jù)結(jié)構(gòu)的排序算法
9.1 數(shù)據(jù)結(jié)構(gòu)排序的基礎(chǔ)知識(shí) 238
9.1.1 排序算法的定義和評(píng)價(jià)標(biāo)準(zhǔn) .238
9.1.2 排序算法的分類(lèi) .239
9.2 使用插入排序算法 239
9.2.1 插入排序算法基礎(chǔ) .239
9.2.2 直接插入排序 .240
9.2.3 實(shí)戰(zhàn)演練——使用直接插入排序算法對(duì)列表中的元素進(jìn)行排序 .241
9.2.4 折半插入排序 .242
9.2.5 實(shí)戰(zhàn)演練——使用折半插入排序法查找指定數(shù)字 .243
9.2.6 實(shí)戰(zhàn)演練——使用折半插入排序 .243
9.2.7 實(shí)戰(zhàn)演練——對(duì)鏈表進(jìn)行插入排序 .244
9.3 使用希爾排序算法 245
9.3.1 希爾排序算法基礎(chǔ) .245
9.3.2 分析希爾排序算法的性能 .246
9.3.3 實(shí)戰(zhàn)演練——使用希爾排序算法對(duì)數(shù)據(jù)進(jìn)行排序處理 .246
9.3.4 實(shí)戰(zhàn)演練——排序一個(gè)大的隨機(jī)列表 .247
9.4 冒泡排序算法 249
9.4.1 冒泡排序算法基礎(chǔ) .249
9.4.2 分析冒泡排序算法的性能 .250
9.4.3 實(shí)戰(zhàn)演練——實(shí)現(xiàn)從大到小的冒泡排序 .250
9.4.4 實(shí)戰(zhàn)演練——使用冒泡排序法實(shí)現(xiàn)升序排序 .251
9.5 使用快速排序算法 252
9.5.1 快速排序算法基礎(chǔ) .252
9.5.2 分析快速排序算法的性能 .253
9.5.3 實(shí)戰(zhàn)演練——使用快速排序算法排列輸入的列表 .254
9.6 選擇排序 255
9.6.1 直接選擇排序 .255
9.6.2 實(shí)戰(zhàn)演練——使用直接選擇排序法排序列表list 中的元素 256
9.6.3 樹(shù)形選擇排序 .257
9.6.4 實(shí)戰(zhàn)演練——?jiǎng)?chuàng)建二叉樹(shù)并實(shí)現(xiàn)完整樹(shù)形排序 .257
9.6.5 堆排序 .259
9.6.6 實(shí)戰(zhàn)演練——對(duì)9 個(gè)待排序數(shù)字實(shí)現(xiàn)完整堆排序 .260
9.7 歸并排序 263
9.7.1 歸并排序算法原理與性能 .263
9.7.2 實(shí)戰(zhàn)演練——使用歸并排序算法由小到大排序一個(gè)列表 .265
9.8 基數(shù)排序 266
9.8.1 基數(shù)排序算法原理與性能 .266
9.8.2 實(shí)戰(zhàn)演練——使用基數(shù)排序算法排列一個(gè)列表 .267