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)和分類 3
1.2.1 數(shù)據(jù)結(jié)構(gòu)的分類 .3
1.2.2 常用的數(shù)據(jù)結(jié)構(gòu) .6
1.3 數(shù)據(jù)類型和抽象數(shù)據(jù)類型 7
1.3.1 數(shù)據(jù)類型 .7
1.3.2 抽象數(shù)據(jù)類型 .7
第2 章 算法
2.1 算法是程序的靈魂 9
2.1.1 算法的定義 .9
2.1.2 算法的特征 .10
2.1.3 為什么說算法是程序的靈魂 .10
2.1.4 認(rèn)識計(jì)算機(jī)中的算法 .11
2.2 數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系 12
2.3 在計(jì)算機(jī)中表示算法的方法 13
2.3.1 用流程圖來表示算法 .13
2.3.2 用N-S 流程圖來表示算法 .14
2.3.3 用計(jì)算機(jī)語言來表示算法 .15
2.4 時(shí)間復(fù)雜度 15
2.4.1 尋找最優(yōu)算法 .16
2.4.2 常見算法的時(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)演練——排序類定義的實(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)建并訪問元組 .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)先級隊(duì)列 .33
3.3 使用字典 35
3.3.1 實(shí)戰(zhàn)演練——?jiǎng)?chuàng)建并訪問字典 .36
3.3.2 實(shí)戰(zhàn)演練——添加、修改、刪除字典中的元素 .36
3.3.3 實(shí)戰(zhàn)演練——映射多個(gè)值 .38
3.3.4 實(shí)戰(zhàn)演練——使用OrderedDict 類創(chuàng)建有序字典 .39
3.3.5 實(shí)戰(zhàn)演練——獲取字典中的最大值和最小值 .40
3.3.6 實(shí)戰(zhàn)演練——獲取兩個(gè)字典中的相同鍵值對 .41
3.3.7 實(shí)戰(zhàn)演練——使用函數(shù)itemgetter() 對字典進(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 章 線性表
4.1 線性表的定義和基本特征 49
4.1.1 線性表和線性結(jié)構(gòu) .49
4.1.2 線性表的基本操作過程 .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ì)列簡單模擬 .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)演練——檢查小括號是否成對 .109
第6 章 樹
6.1 樹的基礎(chǔ)知識 111
6.1.1 什么是樹 .111
6.1.2 樹的相關(guān)概念 .112
6.2 使用列表構(gòu)建樹 113
6.2.1 實(shí)戰(zhàn)演練——實(shí)現(xiàn)一個(gè)簡單的樹 .113
6.2.2 實(shí)戰(zhàn)演練——使用列表創(chuàng)建二叉樹 .114
6.3 二叉樹 115
6.3.1 二叉樹的定義 .115
6.3.2 二叉樹的性質(zhì) .116
6.3.3 二叉樹存儲(chǔ) .117
6.3.4 實(shí)戰(zhàn)演練——使用嵌套列表構(gòu)建樹 .119
6.3.5 實(shí)戰(zhàn)演練——把二叉樹的任何子節(jié)點(diǎn)當(dāng)成二叉樹進(jìn)行處理 .121
6.3.6 實(shí)戰(zhàn)演練——實(shí)現(xiàn)二叉搜索樹查找操作 .122
6.3.7 實(shí)戰(zhàn)演練——實(shí)現(xiàn)二叉搜索樹的刪除操作 .128
6.3.8 實(shí)戰(zhàn)演練——遍歷二叉樹 .136
6.3.9 實(shí)戰(zhàn)演練——使用線索二叉樹 .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 哈夫曼樹 151
6.5.1 哈夫曼樹基礎(chǔ) .152
6.5.2 實(shí)戰(zhàn)演練——使用面向過程方式和面向?qū)ο蠓绞綄?shí)現(xiàn)哈夫曼樹 .154
6.5.3 實(shí)戰(zhàn)演練——實(shí)現(xiàn)哈夫曼樹的基本操作 .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 鄰接矩陣與鄰接表的對比 .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 無向圖連通分量 .175
7.5.2 實(shí)戰(zhàn)演練——通過二維數(shù)組建立無向圖 .176
7.5.3 實(shí)戰(zhàn)演練——根據(jù)鄰接矩陣?yán)L制無向圖 .177
7.5.4 最小生成樹 .178
7.5.5 實(shí)戰(zhàn)演練——實(shí)現(xiàn)最小生成樹和拓?fù)湫蛄?.179
7.5.6 關(guān)鍵路徑 .180
7.5.7 實(shí)戰(zhàn)演練——使用遞歸解決AOE 網(wǎng)絡(luò)最長路關(guān)鍵路徑的問題 .182
7.6 尋求最短路徑 184
7.6.1 求某一頂點(diǎn)到其他各頂點(diǎn)的最短路徑 .184
7.6.2 任意一對頂點(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)最短路徑問題 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 查找算法的分類 .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)演練———遍歷無序列表 .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)演練——升級策略后的分塊查找算法 .212
8.5.5 實(shí)戰(zhàn)演練——一道算法題 .213
8.6 二叉排序樹法 216
8.6.1 二叉排序樹法基礎(chǔ) .216
8.6.2 分析二叉排序樹法的性能 .216
8.6.3 實(shí)戰(zhàn)演練——實(shí)現(xiàn)二叉樹的搜索、插入、刪除、先序遍歷
和后序遍歷操作 .217
8.7 平衡查找樹法 221
8.7.1 2-3 查找樹 .221
8.7.2 平衡查找樹之紅黑樹（Red-Black Tree） 225
8.7.3 平衡二叉樹 .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ǔ)知識 238
9.1.1 排序算法的定義和評價(jià)標(biāo)準(zhǔn) .238
9.1.2 排序算法的分類 .239
9.2 使用插入排序算法 239
9.2.1 插入排序算法基礎(chǔ) .239
9.2.2 直接插入排序 .240
9.2.3 實(shí)戰(zhàn)演練——使用直接插入排序算法對列表中的元素進(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)演練——對鏈表進(jìn)行插入排序 .244
9.3 使用希爾排序算法 245
9.3.1 希爾排序算法基礎(chǔ) .245
9.3.2 分析希爾排序算法的性能 .246
9.3.3 實(shí)戰(zhàn)演練——使用希爾排序算法對數(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 樹形選擇排序 .257
9.6.4 實(shí)戰(zhàn)演練——?jiǎng)?chuàng)建二叉樹并實(shí)現(xiàn)完整樹形排序 .257
9.6.5 堆排序 .259
9.6.6 實(shí)戰(zhàn)演練——對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