第 1 章 概論 ............................................... 1 
1.1數據結構的基本概念與術語 ..................................1
1.1.1數據結構的基本概念..................................................1
1.1.2數據的邏輯結構.........................................................2
1.1.3數據的存儲結構.........................................................3
1.1.4數據的運算集合.........................................................5
1.2數據類型和抽像數據類型.....................................5
1.2.1數據類型....................................................................6
1.2.2抽像數據類型.............................................................6
1.2.3抽像數據類型的描述和實現........................................7
1.3算法和算法分析 ................................................8
1.3.1算法的基本概念和基本特征........................................8
1.3.2算法的時間復雜度和空間復雜度.................................8
本章小結................................................................9
習題.....................................................................10
第2 章 線性表及其順序存儲..........................12
2.1線性表...........................................................12
2.2順序表 ..........................................................12
2.2.1順序表的基本概念及描述 .........................................12
2.2.2順序表的實現...........................................................13
2.3棧 ................................................................17
2.3.1棧的基本概念及描述 ................................................17
2.3.2順序棧及其實現 .......................................................18
2.3.3棧的應用之一——括號匹配......................................20
2.3.4棧的應用之二——算術表達式求值 ...........................22
2.4隊列 .............................................................26
2.4.1隊列的基本概念及描述.............................................26
2.4.2順序隊列及其實現....................................................27
2.4.3順序循環隊列及其實現.............................................30
2.4.4隊列的應用..............................................................31
本章小結...............................................................32
習題.....................................................................32
第3 章 線性表的鏈式存儲 ............................34
3.1鏈式存儲........................................................34
3.2單鏈表 ..........................................................35
3.2.1單鏈表的基本概念及描述 .........................................35
3.2.2單鏈表的實現...........................................................36
3.3帶頭節點的單鏈表 ...........................................39
3.3.1帶頭節點的單鏈表的基本概念及描述........................39
3.3.2帶頭節點的單鏈表的實現 .........................................40
3.4循環單鏈表.....................................................43
3.4.1循環單鏈表的基本概念及描述..................................43
3.4.2循環單鏈表的實現....................................................44
3.5雙鏈表 .........................................................49
3.5.1雙鏈表的基本概念及描述.........................................49
3.5.2雙鏈表的實現...........................................................49
3.6鏈式棧 .........................................................54
3.6.1鏈式棧的基本概念及描述.........................................54
3.6.2鏈式棧的實現...........................................................54
3.7鏈式隊列........................................................57
3.7.1鏈式隊列的基本概念及描述......................................57
3.7.2鏈式隊列的實現 .......................................................57
本章小結..............................................................60
習題.....................................................................61
第4 章 字符串、集合和特殊數組....................63
4.1字符串...........................................................63
4.1.1字符串的基本概念....................................................63
4.1.2字符串類的定義.......................................................64
4.1.3字符串的存儲結構及其實現......................................65
4.2字符串的模式匹配 ............................................71
4.2.1樸素模式匹配算法....................................................71
4.2.2快速模式匹配算法....................................................72
4.3集合 .............................................................75
4.3.1集合的定義和性質....................................................75
4.3.2集合類的定義...........................................................76
4.3.3集合的存儲結構及其實現.........................................76
4.4數組 ............................................................84
4.4.1數組素.......................................................84
4.4.2數組類的定義...........................................................85
4.4.3數組的順序存儲及其實現.........................................86
4.5特殊矩陣.......................................................89
4.5.1對稱矩陣的壓縮存儲................................................89
2
4.5.2三角矩陣的壓縮存儲................................................90
4.5.3帶狀矩陣的壓縮存儲................................................92
4.6稀疏矩陣.......................................................93
4.6.1稀疏矩陣類的定義....................................................93
4.6.2稀疏矩陣的順序存儲及其實現..................................94
4.6.3稀疏矩陣的鏈式存儲及其實現..................................96
本章小結.............................................................100
習題...................................................................100
第5 章 遞歸 ...........................................102
5.1遞歸的基本概念與遞歸程序設計 .........................102
5.2遞歸程序執行過程的分析..................................104
5.3遞歸程序到非遞歸程序的轉換 ............................106
5.3.1簡單遞歸程序到非遞歸程序的轉換.........................107
5.3.2復雜遞歸程序到非遞歸程序的轉換 .........................109
5.4遞歸程序設計的應用實例..................................114
本章小結.............................................................116
習題...................................................................116
第6 章 樹狀結構......................................118
6.1樹的基本概念 ................................................118
6.2樹類的定義...................................................120
6.3樹的存儲結構................................................120
6.3.1雙親表示法............................................................120
6.3.2孩子表示法............................................................121
6.3.3孩子兄弟表示法.....................................................124
6.4樹的遍歷......................................................125
6.5樹的線性表示................................................128
6.5.1樹的括號表示.........................................................128
6.5.2樹的層號表示.........................................................130
6.6並查集 ........................................................131
6.6.1並查集的定義.........................................................131
6.6.2並查集的構建.........................................................132
6.6.3基於樹狀結構的並查集實現....................................132
本章小結.............................................................137
習題...................................................................138
3
第7 章 二叉樹 ........................................139
7.1二叉樹的基本概念 ..........................................139
7.2二叉樹的基本操作 ..........................................141
7.3二叉樹的存儲結構 ..........................................141
7.3.1順序存儲結構.........................................................142
7.3.2鏈式存儲結構.........................................................143
7.4二叉樹的遍歷................................................145
7.4.1二叉樹遍歷的定義..................................................145
7.4.2二叉樹遍歷的遞歸實現...........................................145
7.4.3二叉樹遍歷的非遞歸實現.......................................147
7.5二叉樹其他運算的實現.....................................150
7.6線索二叉樹...................................................152
7.6.1線索二叉樹的定義..................................................152
7.6.2中序線索二叉樹的基本操作....................................153
7.6.3中序線索二叉樹的存儲結構及其實現......................154
7.7樹、森林和二叉樹的轉換..................................156
7.7.1樹、森林到二叉樹的轉換.......................................156
7.7.2二叉樹到樹、森林的轉換 .......................................157
本章小結.............................................................158
習題...................................................................158
第8 章 圖 ..............................................160
8.1圖的基本概念 ................................................160
8.2圖的基本操作................................................163
8.3圖的基本存儲結構 ..........................................164
8.3.1鄰接矩陣及其實現..................................................164
8.3.2鄰接表及其實現.....................................................167
8.3.3鄰接多重表............................................................169
8.4圖的遍歷......................................................170
8.4.1深度優先遍歷 ........................................................170
8.4.2廣度優先遍歷.........................................................172
8.5生成樹與最小生成樹 .......................................173
8.5.1最小生成樹的定義 .................................................175
8.5.2最小生成樹的 Prim 算法 ........................................176
8.5.3最小生成樹的 Kruskal 算法 ...................................179
8.6最短路徑......................................................182
8.6.1單源最短路徑 ........................................................182
4
8.6.2所有頂點對的最短路徑...........................................185
8.7拓撲排序......................................................188
8.8關鍵路徑......................................................191
本章小結.............................................................196
習題...................................................................196
第9 章 查找 ...........................................200
9.1查找的基本概念 .............................................200
9.2線性表的查找................................................201
9.2.1順序查找................................................................201
9.2.2二分查找................................................................203
9.2.3分塊查找................................................................205
9.3二叉排序樹...................................................207
9.4豐滿樹和平衡樹 .............................................213
9.4.1豐滿樹...................................................................214
9.4.2平衡二叉排序樹.....................................................215
9.4.3擴充二叉樹............................................................222
9.5紅黑樹 ........................................................223
9.5.1紅黑樹的定義.........................................................224
9.5.2紅黑樹的插入.........................................................224
9.5.3紅黑樹的刪除.........................................................227
9.6最佳二叉排序樹和 Huffman 樹 .........................230
9.6.1最佳二叉排序樹.....................................................230
9.6.2Huffman 樹...........................................................235
9.7B 樹 ...........................................................238
9.7.1B-樹的定義 ...........................................................238
9.7.2B-樹的基本操作 ....................................................239
9.7.3B 樹 .....................................................................243
9.8散列表查找...................................................245
9.8.1散列存儲 ...............................................................245
9.8.2散列函數的構造.....................................................246
9.8.3衝突處理 ...............................................................247
本章小結.............................................................251
習題...................................................................251
第10 章 排序..........................................255
10.1排序的基本概念 ...........................................255
5
10.2插入排序....................................................256
10.2.1直接插入排序 ......................................................256
10.2.2二分法插入排序...................................................259
10.2.3表插入排序..........................................................260
10.2.4Shell 插入排序 ....................................................262
10.3選擇排序....................................................263
10.3.1直接選擇排序 ......................................................263
10.3.2樹狀選擇排序 ......................................................265
10.3.3堆排序.................................................................267
10.4交換排序....................................................271
10.4.1冒泡排序 .............................................................271
10.4.2快速排序 .............................................................272
10.5歸並排序....................................................274
10.6基數排序....................................................278
10.6.1多排序碼的排序...................................................278
10.6.2靜態鏈式基數排序 ...............................................278
10.7外部排序....................................................281
10.7.1磁盤排序 .............................................................282
10.7.2多路平衡歸並 ......................................................283
10.7.3置換-選擇排序.....................................................285
10.7.4最佳歸並樹..........................................................288
本章小結.............................................................290
習題...................................................................291
附錄1 基礎實驗 ......................................294
實驗1 線性表的順序存儲實現 .................................294
實驗2 不帶頭節點的單鏈表....................................297
實驗3 帶頭節點的單鏈表.......................................301
實驗4 棧與字符串 ...............................................303
實驗5 遞歸........................................................306
實驗6 樹...........................................................310
實驗7 二叉樹.....................................................312
實驗8 圖...........................................................315
實驗9 查找........................................................317
實驗10 排序 ......................................................318
附錄2 綜合實驗