數據結構與算法分析（C++語言版 第2版）

張琨，南京理工大學計算機學院教授，博士生導師，現任計算機科學與工程學院副院長。
目前的研究領域主要包括：複雜網絡理論與應用、可信計算、網絡與信息安全、軟件工程。

第 1章 緒論 1
1．1數據結構的概念　1
1．1．1　數據結構的發展　1
1．1．2　什麼是數據結構　2
1．1．3　數據結構的研究對象　4
1．1．4　數據結構相關概念及術語　5
1．2數據類型和抽像數據類型　8
1．2．1　數據類型　8
1．2．2　抽像數據類型　9
1．3　算法和算法分析　11
1．3．1　算法特性　11
1．3．2　算法設計的要求　11
1．3．3　算法的性能分析與度量　12
1．4　並發數據結構概念　16
1．4．1並發的概念　18
1．4．1並發的途徑　18
1．4．2並發數據結構的設計原則　18
習題一　18

第　2章 線性表　23
2．1　線性表的基本概念　23
2．1．1　線性表的概念　23
2．1．2　線性表的抽像數據類型定義　24
2．2　線性表的順序存儲結構　27
2．2．1　線性表的順序存儲表示　27
2．2．2順序表的類定義和基本操作　28
2．2．3順序表的應用　35
2．2．4　順序表的特點　36
2．3　線性表的鍊式存儲結構　36
2．3．1單鍊錶　37
2．3．2　靜態鍊錶　43
2．3．3循環鍊錶　49
2．3．4雙向鍊錶　50
2．3．5　並發鍊錶　51
2．4　線性表的應用：一元多項式的表示及運算　52
2．4．1　一元多項式的表示　53
2．4．2　一元多項式的實現　54
習題二　58

第3章　棧和隊列　62
3．1棧的基本概念　62
3．1．1　棧的概念　62
3．1．2　棧的抽像數據類型　63
3．2　棧的順序存儲結構及實現　63
3．2．1　順序棧的概念　64
3．2．2　順序棧的類定義和基本操作　64
3．2．3　順序棧的應用　65
3．3　棧的鍊式存儲結構及實現　71
3．3．1　鏈棧的概念　71
3．3．2　鏈棧的類定義和基本操作　71
3．3．3　並發棧　72
3．4　隊列的基本概念　75
3．4．1　隊列的概念　75
3．4．2　隊列的抽像數據類型　75
3．5　隊列的順序存儲　76
3．5．1　循環隊列　77
3．5．2　循環隊列的類定義和基本操作　78
3．6　隊列的鍊式存儲　79
3．6．1　鏈隊列的概念　79
3．6．2　鏈隊列的類定義和基本操作　80
3．6．3　鏈隊列的應用　81
3．6．4　並發隊列　86
習題三　86

第4章　串　90
4．1　串的基本概念　90
4．1．1　串的概念　90
4．1．2　串的抽像數據類型　90
4．2　串的表示與實現　92
4．2．1　定長順序存儲表示　92
4．2．2　堆分配存儲表示　94
4．2．3　鍊式存儲表示　96
4．3　串的模式匹配　96
4．3．1　模式匹配方法BF　97
4．3．2　模式匹配方法KMP　98
習題四　100

第5章　數組和廣義表　104
5．1　數組的基本概念　104
5．1．1　數組的概念　104
5．1．2　數組的抽像數據類型　105
5．2　數組的存儲結構　105
5．3　矩陣的壓縮存儲　108
5．3．1　特殊矩陣的壓縮存儲　108
5．3．2　稀疏矩陣的壓縮存儲　110
5．4　廣義表的基本概念　118
5．4．1　廣義表的概念　118
5．4．2　廣義表的抽像數據類型　119
5．4．3　廣義表的存儲結構和類定義　120
5．4．4　廣義表的遞歸算法　121
習題五　123

第6章　樹和二叉樹　127
6．1　樹　127
6．1．1　樹的概念　127
6．1．2　基本術語　128
6．1．3　樹的抽像數據類型　129
6．1．4　樹的性質　131
6．1．5　樹的存儲結構　132
6．1．6　樹的遍歷　135
6．1．7　樹的應用　136
6．2　森林　138
6．2．1　森林的存儲結構　138
6．2．2　森林的遍歷　140
6．3　二叉樹　140
6．3．1　二叉樹的概念　140
6．3．2　二叉樹的性質　141
6．3．3　二叉樹的抽像數據類型　145
6．3．4　二叉樹的存儲結構　148
6．3．5　遍歷二叉樹　150
6．3．6　線索二叉樹　162
6．4　樹、森林與二叉樹的轉換　169
6．4．1　樹與二叉樹的轉換　169
6．4．2　森林與二叉樹的轉換　170
6．5　堆　172
6．6　哈夫曼樹和哈夫曼編碼　173
6．6．1　哈夫曼樹的概念　173
6．6．2　哈夫曼樹的構造　174
6．6．3　哈夫曼編碼　177
習題六　179

第7章　圖　182
7．1　圖的基本概念　182
7．1．1　圖的概念　182
7．1．2　圖的基本術語　183
7．1．3　圖的抽像數據類型　187
7．2　圖的存儲結構　188
7．2．1　圖的順序存儲結構－鄰接矩陣　188
7．2．2　圖的鍊式存儲結構　191
7．3　圖的遍歷　196
7．3．1　深度優先搜索　196
7．3．2　廣度優先搜索　197
7．3．3　連通分量和重連通分量　198
7．4　最小生成樹　201
7．4．1　最小生成樹的定義　202
7．4．2　最小生成樹的構造算法　202
7．5　有向無環圖及其應用　207
7．5．1　AOV網與拓撲排序　208
7．5．2　AOE網與關鍵路徑　211
7．6　最短路徑　218
7．6．1　單源最短路徑　218
7．6．2　每對頂點間的最短路徑　221
習題七　223

第8章　查找　226
8．1　查找的基本概念　226
8．2　靜態查找表　228
8．2．1　順序查找　228
8．2．2　有序表的查找　230
8．2．3　分塊查找　232
8．3　動態查找表　234
8．3．1　二叉排序樹　234
8．3．2　平衡二叉樹　241
8．3．3　B_樹　248
8．3．4　並發查找樹　256
8．4　哈希表　256
8．4．1　哈希表的概念　256
8．4．2　哈希函數　257
8．4．3　處理衝突的方法　259
8．4．4　哈希查找算法及分析　261
8．4．5　並發哈希表及其應用　263
習題八　264

第9章　內部排序　267
9．1　排序的基本概念　267
9．2　插入排序　269
9．2．1　直接插入排序　269
9．2．2　折半插入排序　272
9．2．3　表插入排序　274
9．2．4　希爾排序　278
9．3　交換排序　280
9．3．1　冒泡排序　280
9．3．2　快速排序　282
9．4　選擇排序　286
9．4．1　簡單選擇排序　286
9．4．2　樹形選擇排序　289
9．4．3　堆排序　291
9．5　歸併排序　295
9．6　基數排序　298
9．6．1　多關鍵字的排序　298
9．6．2　鍊式基數排序　298
9．7　各種內部排序方法的比較討論　302
習題九　303

第　10章 算法設計與分析　306
10．1　分治法　306
10．2　回溯法　308
10．3　貪心算法　313
10．4　動態規劃法　315
10．5　分支限界法　319
習題十　325

附錄　詞彙索引　327