Python數(shù)據(jù)結(jié)構(gòu)與算法從入門到精通

第1章 數(shù)據(jù)結(jié)構(gòu)概述  001
1.1 基本概念和術(shù)語(yǔ)  002
1.2 數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)  004
1.2.1 邏輯結(jié)構(gòu)  004
1.2.2 存儲(chǔ)結(jié)構(gòu)  005
1.3 抽象數(shù)據(jù)類型及其描述  005
1.3.1 什么是抽象數(shù)據(jù)類型  005
1.3.2 抽象數(shù)據(jù)類型的描述  006
第2章 算法概述  010
2.1 算法的相關(guān)概念  011
2.1.1 數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系  011
2.1.2 什么是算法  012
2.1.3 算法的五大特性  012
2.1.4 算法的描述  012
2.2 算法分析  014
2.2.1 算法設(shè)計(jì)的4 個(gè)目標(biāo)  014
2.2.2 算法效率評(píng)價(jià)  015
2.2.3 算法的時(shí)間復(fù)雜度  016
2.2.4 算法的空間復(fù)雜度  019
第3章 數(shù)據(jù)結(jié)構(gòu)與算法的語(yǔ)言基礎(chǔ)—— Python語(yǔ)言  020
3.1 Python 語(yǔ)言開(kāi)發(fā)環(huán)境  021
3.2 Python 基本語(yǔ)法及輸入輸出  023
3.2.1 基本語(yǔ)法  023
3.2.2 輸入與輸出  024
3.3 Python 列表、元組、字典、集合  027
3.3.1 列表  027
3.3.2 元組  029
3.3.3 字典  030
3.3.4 集合  030
3.4 函數(shù)與類  031
3.4.1 函數(shù)  031
3.4.2 類  032
3.5 NumPy 中的array  033
第4章 線性表——最簡(jiǎn)單的線性結(jié)構(gòu)  036
4.1 線性表的定義及抽象數(shù)據(jù)類型  038
4.1.1 什么是線性表  038
4.1.2 線性表的抽象數(shù)據(jù)類型  038
4.2 線性表的順序表示與實(shí)現(xiàn)  039
4.2.1 線性表的順序存儲(chǔ)結(jié)構(gòu)  039
4.2.2 順序表的基本運(yùn)算  040
4.2.3 順序表的基本運(yùn)算性能分析  043
4.2.4 順序表的優(yōu)缺點(diǎn)  044
4.2.5 順序表應(yīng)用舉例  044
4.3 線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)  048
4.3.1 單鏈表的存儲(chǔ)結(jié)構(gòu)  048
4.3.2 單鏈表上的基本運(yùn)算  050
4.3.3 單鏈表存儲(chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)  055
4.3.4 單鏈表應(yīng)用舉例  055
4.4 循環(huán)單鏈表  059
4.4.1 循環(huán)單鏈表的鏈?zhǔn)酱鎯?chǔ)  059
4.4.2 循環(huán)單鏈表應(yīng)用舉例  061
4.5 雙向鏈表  063
4.5.1 雙向鏈表的存儲(chǔ)結(jié)構(gòu)  063
4.5.2 雙向鏈表的插入和刪除操作  064
4.6 綜合案例：一元多項(xiàng)式的表示與相乘  066
4.6.1 一元多項(xiàng)式的表示  066
4.6.2 一元多項(xiàng)式相乘  067
第5章 棧與遞歸——一種后進(jìn)先出的線性結(jié)構(gòu)  071
5.1 棧的表示與實(shí)現(xiàn)  072
5.1.1 什么是棧  072
5.1.2 棧的抽象數(shù)據(jù)類型  073
5.1.3 順序棧  074
5.1.4 鏈棧  077
5.2 棧的應(yīng)用  080
5.2.1 數(shù)制轉(zhuǎn)換  080
5.2.2 行編輯程序  081
5.2.3 算術(shù)表達(dá)式求值——計(jì)算機(jī)如何計(jì)算表達(dá)式的值  083
5.3 遞歸  090
5.3.1 遞歸——自己調(diào)用自己  090
5.3.2 消除遞歸——用棧模擬遞歸調(diào)用過(guò)程  093
第6章 隊(duì)列  097
6.1 隊(duì)列的表示與實(shí)現(xiàn)  098
6.1.1 隊(duì)列的定義  098
6.1.2 隊(duì)列的抽象數(shù)據(jù)類型  099
6.1.3 順序隊(duì)列  100
6.1.4 順序循環(huán)隊(duì)列  101
6.1.5 雙端隊(duì)列  104
6.1.6 鏈?zhǔn)疥?duì)列  104
6.2 隊(duì)列的應(yīng)用  107
6.2.1 舞伴問(wèn)題  107
6.2.2 隊(duì)列在楊輝三角中的應(yīng)用  109
6.2.3 隊(duì)列在回文中的應(yīng)用  112
第7章 串——數(shù)據(jù)為字符串的線性結(jié)構(gòu)  114
7.1 串的定義及抽象數(shù)據(jù)類型  115
7.1.1 什么是串  115
7.1.2 串的抽象數(shù)據(jù)類型  116
7.2 串的存儲(chǔ)表示  118
7.2.1 串的順序存儲(chǔ)  118
7.2.2 串的鏈?zhǔn)酱鎯?chǔ)  119
7.2.3 順序串應(yīng)用舉例  120
7.3 串的模式匹配  122
7.3.1 樸素模式匹配算法——模式匹配算法Brute-Force  122
7.3.2 KMP 算法  124
7.3.3 模式匹配應(yīng)用舉例  129
第8章 數(shù)組與廣義表  131
8.1 數(shù)組的定義及抽象數(shù)據(jù)類型  132
8.1.1 什么是數(shù)組  132
8.1.2 數(shù)組的順序存儲(chǔ)結(jié)構(gòu)  133
8.1.3 特殊矩陣的壓縮存儲(chǔ)  134
8.1.4 稀疏矩陣的壓縮存儲(chǔ)  137
8.2 廣義表  145
8.2.1 什么是廣義表  145
8.2.2 廣義表的抽象數(shù)據(jù)類型  146
8.2.3 廣義表的頭尾鏈表表示  146
8.2.4 廣義表的擴(kuò)展線性鏈表表示  147
第9章 樹和二叉樹——一對(duì)多的數(shù)據(jù)結(jié)構(gòu)  149
9.1 樹  151
9.1.1 什么是樹  151
9.1.2 樹的邏輯表示  152
9.2 二叉樹  153
9.2.1 什么是二叉樹  153
9.2.2 二叉樹的性質(zhì)  155
9.2.3 二叉樹的抽象數(shù)據(jù)類型  156
9.2.4 二叉樹的存儲(chǔ)表示  158
9.3 二叉樹的遍歷  161
9.3.1 什么是二叉樹的遍歷  161
9.3.2 二叉樹的先序遍歷  161
9.3.3 二叉樹的中序遍歷  163
9.3.4 二叉樹的后序遍歷  165
9.3.5 二叉樹的層次遍歷  167
9.3.6 二叉樹遍歷的應(yīng)用  167
9.4 二叉樹的線索化及應(yīng)用  169
9.4.1 什么是二叉樹的線索化  169
9.4.2 二叉樹的線索化  171
9.4.3 線索二叉樹的遍歷  172
9.4.4 線索二叉樹的應(yīng)用舉例  174
9.5 樹、森林與二叉樹  176
9.5.1 樹的存儲(chǔ)結(jié)構(gòu)  176
9.5.2 樹轉(zhuǎn)換為二叉樹  179
9.5.3 森林轉(zhuǎn)換為二叉樹  180
9.5.4 二叉樹轉(zhuǎn)換為樹和森林  181
9.5.5 樹和森林的遍歷  182
9.6 并查集  182
9.6.1 并查集的定義  182
9.6.2 并查集的實(shí)現(xiàn)  183
9.6.3 并查集的應(yīng)用  186
9.7 二叉樹的典型應(yīng)用——哈夫曼樹  187
9.7.1 哈夫曼樹及應(yīng)用  187
9.7.2 利用二叉樹求解算術(shù)表達(dá)式的值  193
第10章 圖——多對(duì)多的數(shù)據(jù)結(jié)構(gòu)類型  199
10.1 圖的定義與相關(guān)概念  200
10.1.1 什么是圖  200
10.1.2 圖的相關(guān)概念  201
10.1.3 圖的抽象數(shù)據(jù)類型  204
10.2 圖的存儲(chǔ)結(jié)構(gòu)  205
10.2.1 鄰接矩陣表示法  205
10.2.2 鄰接表表示法  208
10.2.3 十字鏈表表示法  212
10.2.4 鄰接多重表表示法  213
10.3 圖的遍歷  214
10.3.1 圖的深度優(yōu)先遍歷  214
10.3.2 圖的廣度優(yōu)先遍歷  217
10.4 圖的連通性問(wèn)題  219
10.4.1 無(wú)向圖的連通分量與生成樹  219
10.4.2 最小生成樹  220
10.5 有向無(wú)環(huán)圖  226
10.5.1 AOV 網(wǎng)與拓?fù)渑判? 226
10.5.2 AOE 網(wǎng)與關(guān)鍵路徑  229
10.6 最短路徑  235
10.6.1 從某個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑  235
10.6.2 每一對(duì)頂點(diǎn)之間的最短路徑  242
第11章 查找  247
11.1 查找的基本概念  248
11.2 靜態(tài)查找  249
11.2.1 順序表的查找  249
11.2.2 有序順序表的查找  251
11.2.3 索引順序表的查找  253
11.3 動(dòng)態(tài)查找  254
11.3.1 二叉排序樹  254
11.3.2 平衡二叉樹  260
11.4 B- 樹與B 樹  268
11.4.1 B- 樹  268
11.4.2 B 樹  276
11.5 哈希表  277
11.5.1 哈希表的定義  277
11.5.2 哈希函數(shù)的構(gòu)造方法  278
11.5.3 處理沖突的方法  279
11.5.4 哈希表應(yīng)用舉例  281
第12章 排序  285
12.1 排序的基本概念  286
12.2 插入排序  287
12.2.1 直接插入排序  288
12.2.2 折半插入排序  289
12.2.3 希爾排序  289
12.2.4 插入排序應(yīng)用舉例  290
12.3 選擇排序  291
12.3.1 簡(jiǎn)單選擇排序  292
12.3.2 堆排序  293
12.4 交換排序  298
12.4.1 冒泡排序  298
12.4.2 快速排序  299
12.4.3 交換排序應(yīng)用舉例  301
12.5 歸并排序  304
12.6 非比較類排序  306
12.6.1 基數(shù)排序  306
12.6.2 桶排序  311
12.6.3 計(jì)數(shù)排序  314
第13章 回溯算法——深度優(yōu)先搜索的方法  317
13.1 回溯算法的基本思想  318
13.1.1 問(wèn)題的解空間  318
13.1.2 回溯算法的求解步驟  319
13.2 和式分解（非遞歸實(shí)現(xiàn)）  322
13.3 填字游戲  325
13.4 裝載問(wèn)題  329
13.5 迷宮求解  333
第14章 遞歸與分治算法——化繁為簡(jiǎn)  338
14.1 分治算法的基本思想  339
14.2 簡(jiǎn)單遞歸  342
14.2.1 求n 的階乘  342
14.2.2 斐波那契數(shù)列  345
14.2.3 求n 個(gè)數(shù)中的最大者  346
14.2.4 求n 個(gè)數(shù)的和  347
14.2.5 將十進(jìn)制整數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)  347
14.2.6 求整數(shù)的逆序數(shù)  348
14.2.7 求最大公約數(shù)  349
14.2.8 求Ackermann 函數(shù)的值  350
14.2.9 求C(n ,m ) 的值  350
14.3 復(fù)雜遞歸  351
14.3.1 逆置字符串  351
14.3.2 求最大和次大元素  352
14.3.3 求第K 大個(gè)數(shù)  354
14.3.4 和式分解  355
14.3.5 臺(tái)階問(wèn)題  357
14.3.6 大牛生小牛問(wèn)題  359
14.3.7 從1~n 自然數(shù)中任選r 個(gè)數(shù)的所有組合數(shù)  360
14.3.8 求最大子序列的和  361
14.3.9 找假硬幣問(wèn)題  363
14.3.10 表達(dá)式求值  365
14.3.11 大整數(shù)乘法  366
參考文獻(xiàn)  368