數據結構（思政版）

第1章  數據結構概述    1
1.1  數據結構研究的問題    1
1.1.1  計算機解決實際問題的一般步驟    1
1.1.2  數據結構學科概念及其所研究的內容    1
1.1.3  數據結構的建模舉例    2
1.2  數據結構的基本概念和相關術語    5
1.2.1  數據的基本概念    5
1.2.2  數據結構的相關術語    6
1.2.3  數據類型的概念    7
1.3  算法與算法性能分析    9
1.3.1  算法的概念及特征    10
1.3.2  算法的設計要求    10
1.3.3  算法的性能分析    11
1.4  數據結構的算法描述工具    15
1.4.1  符號常量定義    15
1.4.2  數據存儲結構定義    15
1.4.3  運算符    16
1.4.4  函數    16
1.4.5  語句    16
本章小結    18
習題1    18
第2章  線性表    21
2.1  線性表的類型定義    21
2.1.1  線性表的概念、特點與邏輯結構    21
2.1.2  線性表的ADT定義    22
2.2  線性表的順序存儲結構及其算法實現    24
2.2.1  線性表的順序存儲結構    24
2.2.2  順序表的基本算法實現    26
2.2.3  順序表應用舉例    29
2.3  線性表的鏈式存儲結構及其算法實現    32
2.3.1  單鏈表存儲結構    32
2.3.2  單鏈表的基本運算    36
2.3.3  雙向鏈表    43
2.3.4  循環鏈表    44
2.3.5  單鏈表應用舉例    46
本章小結    50
習題2    50

第3章  棧和隊列    55
3.1  棧    55
3.1.1  棧的概念及ADT定義    55
3.1.2  棧的存儲結構與算法實現    56
3.2  棧的應用舉例    61
3.3  隊列    75
3.3.1  隊列的定義及ADT定義    75
3.3.2  隊列的存儲結構及算法實現    77
本章小結    83
習題3    83
第4章  串    88
4.1  串的概念及ADT定義    88
4.1.1  串的基本概念及相關術語    88
4.1.2  串的ADT定義    88
4.2  串的定長順序存儲結構及其算法實現    90
4.2.1  串的定長順序存儲結構    90
4.2.2  定長順序串的基本運算    91
4.3  串的堆存儲結構及其算法實現    93
4.3.1  串的堆存儲結構    93
4.3.2  堆串的算法實現    94
4.4  串的模式匹配算法    96
4.4.1  簡單模式匹配算法    96
4.4.2  KMP算法    98
4.4.3  串的其他存儲映象    101
本章小結    104
習題4    104
第5章  數組與廣義表    106
5.1  數組    106
5.1.1  數組的類型定義與存儲結構    106
5.1.2  數組的內存映象    107
5.2  特殊矩陣的壓縮存儲    109
5.2.1  對稱矩陣    110
5.2.2  三角矩陣    111
5.2.3  帶狀矩陣    112
5.3  稀疏矩陣    113
5.3.1  稀疏矩陣的三元組存儲結構與矩陣的轉置和乘法    114
5.3.2  稀疏矩陣的十字鏈表存儲結構與矩陣的加法和減法    119
5.4  廣義表    122
5.4.1  廣義表的概念及ADT定義    123
5.4.2  廣義表的存儲結構    125
5.4.3  廣義表的基本運算    127
5.4.4  廣義表的應用舉例    130
本章小結    131
習題5    131
第6章  樹與二叉樹    135
6.1  樹    135
6.1.1  樹的定義及相關術語    135
6.1.2  樹的邏輯結構表示    138
6.1.3  樹的ADT定義    138
6.2  二叉樹    140
6.2.1  二叉樹的定義及ADT定義    140
6.2.2  二叉樹的性質    143
6.2.3  二叉樹的存儲結構    145
6.3  二叉樹的遍歷算法及其應用    148
6.3.1  二叉樹的遞歸遍歷算法    148
6.3.2  二叉樹的非遞歸遍歷算法    151
6.3.3  二叉樹遍歷算法的應用    154
6.4  二叉樹的構造    157
6.5  線索二叉樹    160
6.5.1  線索二叉樹的定義及結構    161
6.5.2  線索二叉樹的基本算法    163
6.6  樹和森林    168
6.6.1  樹與森林的性質    168
6.6.2  樹與森林的存儲結構    169
6.6.3  樹、森林與二叉樹的轉換    173
6.6.4  樹與森林的遍歷    176
6.7  哈夫曼樹    177
6.7.1  哈夫曼樹的概念與構造算法    177
6.7.2  哈夫曼樹的應用    181
6.8  用並查集求等價問題    185
6.8.1  並查集    185
6.8.2  並查集的算法實現    186
本章小結    188
習題6    189
第7章  圖    194
7.1  圖的基本概念及ADT定義    194
7.1.1  圖的基本概念與相關術語    194
7.1.2  圖的ADT定義    197
7.2  圖的存儲結構與創建算法    199
7.2.1  鄰接矩陣存儲結構與創建算法    199
7.2.2  鄰接表存儲結構與創建算法    202
7.2.3  有向圖的十字鏈表存儲結構與創建算法    204
7.2.4  無向圖的鄰接多重表存儲結構    206
7.3  圖的遍歷算法    208
7.3.1  深度優先搜索算法    208
7.3.2  廣度優先搜索算法    209
7.4  圖的連通性    211
7.4.1  無向圖的連通性    211
7.4.2  有向圖的連通性    211
7.4.3  生成樹與生成森林    212
7.4.4  關節點與重連通分量    214
7.5  最小生成樹    216
7.5.1  最小生成樹的基本概念    216
7.5.2  構造最小生成樹的Prim算法    217
7.5.3  構造最小生成樹的Kruskal算法    219
7.6  最短路徑問題    222
7.6.1  從一個源點到其他各頂點的最短路徑    222
7.6.2  每一對頂點之間的最短路徑    224
7.7  有向無環圖及其應用    227
7.7.1  有向無環圖的概念    227
7.7.2  AOV網與拓撲排序    228
7.7.3  AOE網與關鍵路徑    231
本章小結    234
習題7    235
第8章  查找    239
8.1  查找概述    239
8.1.1  查找表的相關概念    239
8.1.2  查找算法的性能分析    240
8.2  線性表的查找    240
8.2.1  順序查找    240
8.2.2  折半查找    241
8.2.3  分塊查找    245
8.3  樹表的查找    247
8.3.1  二叉排序樹    247
8.3.2  平衡二叉樹    252
8.3.3  紅黑樹    258
8.3.4  B-樹    264
8.3.5  B+樹    268
8.4  哈希表查找    269
8.4.1  哈希表與哈希方法    269
8.4.2  哈希函數的常用構造方法    270
8.4.3  處理沖突的方法    272
8.4.4  哈希表的查找性能分析    273
本章小結    276
習題8    276

第9章  排序    281
9.1  基本概念    281
9.2  插入排序    282
9.2.1  直接插入排序    282
9.2.2  折半插入排序    284
9.2.3  希爾排序    285
9.3  交換排序    286
9.3.1  冒泡排序    286
9.3.2  快速排序    288
9.4  選擇排序    291
9.4.1  簡單選擇排序    291
9.4.2  樹形選擇排序    292
9.4.3  堆排序    293
9.5  二路歸並排序    296
9.6  基數排序    298
9.6.1  多關鍵字排序    298
9.6.2  鏈式基數排序    299
9.6.3  計數排序    301
9.7  各種排序算法的比較    302
9.8  外部排序    303
9.8.1  外部排序的方法    303
9.8.2  多路平衡歸並的實現    304
本章小結    306
習題9    307