圖解Java數(shù)據(jù)結(jié)構(gòu)與算法（微課視頻版）

目    錄
 
第1章  數(shù)據(jù)結(jié)構(gòu)與算法概述 1
1.1  為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) 1
1.2  基本概念和術(shù)語(yǔ) 2
1.3  數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu) 4
1.3.1  邏輯結(jié)構(gòu) 4
1.3.2  存儲(chǔ)結(jié)構(gòu) 5
1.4  抽象數(shù)據(jù)類型及其描述 6
1.4.1  什么是抽象數(shù)據(jù)類型 6
1.4.2  抽象數(shù)據(jù)類型的描述 6
1.5  算法 8
1.5.1  數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系 9
1.5.2  什么是算法 9
1.5.3  算法的5個(gè)特性 9
1.5.4  算法的描述 10
1.6  算法分析 11
1.6.1  算法設(shè)計(jì)的4個(gè)目標(biāo) 11
1.6.2  算法效率評(píng)價(jià) 12
1.6.3  算法的時(shí)間復(fù)雜度 13
1.6.4  算法的空間復(fù)雜度 16
1.7  學(xué)好數(shù)據(jù)結(jié)構(gòu)的秘訣 17
1.8  小結(jié) 19
第2章  線性表 20
2.1  線性表的定義及抽象數(shù)據(jù)類型 20
2.1.1  線性表的定義 20
2.1.2  線性表的抽象數(shù)據(jù)類型 21
2.2  線性表的順序表示與實(shí)現(xiàn) 22
2.2.1  線性表的順序存儲(chǔ) 22
2.2.2  順序表的基本運(yùn)算 23
2.2.3  基本操作性能分析 26
2.2.4  順序表應(yīng)用舉例 27
2.3  線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 30
2.3.1  單鏈表的存儲(chǔ)結(jié)構(gòu) 30
2.3.2  單鏈表上的基本運(yùn)算 32
2.3.3  單鏈表應(yīng)用舉例 36
2.3.4  循環(huán)單鏈表 38
2.3.5  雙向鏈表 41
2.4  一元多項(xiàng)式的表示與相乘 44
2.4.1  一元多項(xiàng)式的表示 44
2.4.2  一元多項(xiàng)式相乘 45
2.5  小結(jié) 49
第3章  棧與隊(duì)列 50
3.1  棧的表示與實(shí)現(xiàn) 50
3.1.1  棧的定義 50
3.1.2  棧的抽象數(shù)據(jù)類型 51
3.1.3  順序棧 52
3.1.4  鏈棧 56
3.2  棧的應(yīng)用 59
3.2.1  數(shù)制轉(zhuǎn)換 59
3.2.2  行編輯程序 60
3.2.3  算術(shù)表達(dá)式求值 61
3.3  棧與遞歸 67
3.3.1  遞歸 68
3.3.2  消除遞歸 71
3.4  隊(duì)列的表示與實(shí)現(xiàn) 73
3.4.1  隊(duì)列的定義 73
3.4.2  隊(duì)列的抽象數(shù)據(jù)類型 73
3.4.3  順序隊(duì)列 74
3.4.4  順序循環(huán)隊(duì)列 76
3.4.5  雙端隊(duì)列 79
3.4.6  鏈?zhǔn)疥?duì)列 79
3.4.7  鏈?zhǔn)疥?duì)列的實(shí)現(xiàn) 81
3.5  隊(duì)列在楊輝三角中的應(yīng)用 82
3.5.1 什么是楊輝三角 82
3.5.2  構(gòu)造隊(duì)列 83
3.5.3  楊輝三角隊(duì)列的實(shí)現(xiàn) 83
3.6  小結(jié) 85
第4章  串、數(shù)組與廣義表 86
4.1  串的定義及抽象數(shù)據(jù)類型 86
4.1.1  什么是串 86
4.1.2  串的抽象數(shù)據(jù)類型 87
4.2  串的存儲(chǔ)表示 88
4.2.1  串的順序存儲(chǔ)結(jié)構(gòu) 88
4.2.2  串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 89
4.3  串的模式匹配 90
4.3.1  樸素模式匹配算法——Brute-Force 90
4.3.2  改進(jìn)算法—KMP算法 92
4.3.3  模式匹配應(yīng)用舉例 98
4.4  數(shù)組的定義及抽象數(shù)據(jù)類型 99
4.4.1  數(shù)組的基本概念 99
4.4.2  數(shù)組的抽象數(shù)據(jù)類型 100
4.4.3  數(shù)組的順序存儲(chǔ)結(jié)構(gòu) 100
4.4.4  特殊矩陣的壓縮存儲(chǔ) 101
4.4.5  稀疏矩陣的壓縮存儲(chǔ)及典型應(yīng)用 104
4.5  廣義表 111
4.5.1  什么是廣義表 111
4.5.2  廣義表的抽象數(shù)據(jù)類型 112
4.5.3  廣義表的頭尾鏈表表示 113
4.5.4  廣義表的擴(kuò)展線性鏈表表示 113
4.6  小結(jié) 115
第5章  樹(shù)和二叉樹(shù) 116
5.1  樹(shù)的定義和抽象數(shù)據(jù)類型 116
5.1.1  樹(shù)的定義 116
5.1.2  樹(shù)的邏輯表示 118
5.2  二叉樹(shù)的定義、性質(zhì)和抽象數(shù)據(jù)類型 118
5.2.1  二叉樹(shù)的定義 119
5.2.2  二叉樹(shù)的性質(zhì) 120
5.2.3  二叉樹(shù)的抽象數(shù)據(jù)類型 122
5.2.4  二叉樹(shù)的存儲(chǔ)表示 123
5.3  二叉樹(shù)的遍歷 125
5.3.1  二叉樹(shù)遍歷的定義 126
5.3.2  二叉樹(shù)的先序遍歷 126
5.3.3  二叉樹(shù)的中序遍歷 128
5.3.4  二叉樹(shù)的后序遍歷 130
5.4  二叉樹(shù)的線索化 132
5.4.1  二叉樹(shù)的線索化定義 132
5.4.2  二叉樹(shù)的線索化算法實(shí)現(xiàn) 133
5.4.3  線索二叉樹(shù)的遍歷 135
5.4.4  線索二叉樹(shù)的應(yīng)用舉例 137
5.5  樹(shù)、森林與二叉樹(shù) 139
5.5.1  樹(shù)的存儲(chǔ)結(jié)構(gòu) 139
5.5.2  樹(shù)轉(zhuǎn)換為二叉樹(shù) 142
5.5.3  森林轉(zhuǎn)換為二叉樹(shù) 143
5.5.4  二叉樹(shù)轉(zhuǎn)換為樹(shù)和森林 143
5.5.5  樹(shù)和森林的遍歷 144
5.6  并查集 145
5.6.1  并查集的定義 145
5.6.2  并查集的實(shí)現(xiàn) 146
5.6.3  并查集的應(yīng)用 149
5.7  哈夫曼樹(shù) 151
5.7.1  哈夫曼樹(shù)的定義 151
5.7.2  哈夫曼編碼 152
5.7.3  哈夫曼編碼算法的實(shí)現(xiàn) 153
5.8  小結(jié) 158
第6章  圖 159
6.1  圖的定義與相關(guān)概念 159
6.1.1  圖的定義 159
6.1.2  圖的相關(guān)概念 160
6.1.3  圖的抽象數(shù)據(jù)類型 162
6.2  圖的存儲(chǔ)結(jié)構(gòu) 163
6.2.1  鄰接矩陣表示法 163
6.2.2  鄰接表表示法 168
6.2.3  十字鏈表 172
6.2.4  鄰接多重表 173
6.3  圖的遍歷 174
6.3.1  圖的深度優(yōu)先遍歷 174
6.3.2  圖的廣度優(yōu)先遍歷 178
6.4  圖的連通性問(wèn)題 179
6.4.1  無(wú)向圖的連通分量與生成樹(shù) 180
6.4.2  最小生成樹(shù) 181
6.5  有向無(wú)環(huán)圖 187
6.5.1  AOV網(wǎng)與拓?fù)渑判?187
6.5.2  AOE網(wǎng)與關(guān)鍵路徑 190
6.6  最短路徑 196
6.6.1  從某個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑 196
6.6.2  每一對(duì)頂點(diǎn)之間的最短路徑 202
6.7  小結(jié) 206
第7章  查找 208
7.1  查找的基本概念 208
7.2  靜態(tài)查找 209
7.2.1  順序表的查找 209
7.2.2  有序順序表的查找 211
7.2.3  索引順序表的查找 213
7.3  動(dòng)態(tài)查找 215
7.3.1  二叉排序樹(shù) 215
7.3.2  平衡二叉樹(shù) 221
7.4  B-樹(shù)與B 樹(shù) 227
7.4.1  B-樹(shù) 227
7.4.2  B 樹(shù) 233
7.5  哈希表 233
7.5.1  哈希表的定義 234
7.5.2  哈希函數(shù)的構(gòu)造方法 234
7.5.3  處理沖突的方法 235
7.5.4  哈希表的查找與分析 237
7.5.5  哈希表應(yīng)用舉例 238
7.6  小結(jié) 242
第8章  排序 243
8.1  排序的基本概念 243
8.2  插入排序 244
8.2.1  直接插入排序 244
8.2.2  折半插入排序 246
8.2.3  希爾排序 246
8.2.4  插入排序應(yīng)用舉例 247
8.3  選擇排序 248
8.3.1  簡(jiǎn)單選擇排序 248
8.3.2  堆排序 249
8.4  交換排序 254
8.4.1  冒泡排序 254
8.4.2  快速排序 256
8.4.3  交換排序應(yīng)用舉例 258
8.5  歸并排序 261
8.6  基數(shù)排序 263
8.6.1  基數(shù)排序算法 263
8.6.2  基數(shù)排序應(yīng)用舉例 266
8.7  小結(jié) 269
第9章  分治算法 271
9.1  分治算法的基本思想 271
9.2  求最大子序列的和 274
9.3  求x的n次冪 277
9.4  眾數(shù)問(wèn)題 278
9.5  求n個(gè)數(shù)中的最大者和最小者 280
9.6  整數(shù)劃分問(wèn)題 283
9.7  大整數(shù)乘法 285
9.8  小結(jié) 290
第10章  貪心算法 291
10.1  貪心算法的思想 291
10.2  找零錢問(wèn)題 293
10.3  背包問(wèn)題 295
10.4  刪數(shù)問(wèn)題 299
10.5  加油站問(wèn)題 301
10.6  小結(jié) 302
第11章  回溯算法 303
11.1  回溯算法的基本思想 303
11.1.1  問(wèn)題的解空間 304
11.1.2  回溯算法的基本思想 305
11.2  裝載問(wèn)題 307
11.3  旅行商問(wèn)題 310
11.4  和式分解問(wèn)題 314
11.5  小結(jié) 317
參考文獻(xiàn) 318
課后習(xí)題（電子版見(jiàn)下載） 319