數據結構（C語言版 第3版）

第1章緒論1
1.1數據結構的概念及分類1
1.1.1為什么要學習數據結構1
1.1.2與數據結構相關的基本術語2
1.1.3數據結構的分類5
1.1.4數據結構的存儲結構7
1.1.5定義在數據結構上的操作8
1.1.6“好”數據結構8
1.2使用C語言描述數據結構8
1.2.1C的數據類型9
1.2.2算法的控制結構10
1.2.3算法的函數結構11
1.2.4動態(tài)存儲分配14
1.2.5邏輯和關系運算的約定15
1.2.6輸入與輸出15
1.3算法和算法設計16
1.3.1算法的定義和特性16
1.3.2算法的設計步驟17
1.3.3算法設計的基本方法18
1.4算法分析與度量21
1.4.1算法的評價標準22
1.4.2算法的時間和空間復雜性度量22
1.4.3算法的漸進分析25
本章小結28
習題28
第2章線性表32
2.1線性表32
2.1.1線性表的定義和特點32
2.1.2線性表的主要操作33
2.2順序表34
2.2.1順序表的定義和特點34
2.2.2順序表的結構定義35
2.2.3順序表主要操作的實現36
2.2.4順序表主要操作的性能分析39
2.2.5順序表的應用舉例41
2.3單鏈表42
2.3.1單鏈表的定義和特點42
2.3.2單鏈表的結構定義43
2.3.3單鏈表中指針的操作43
2.3.4單鏈表中的插入與刪除43
2.3.5帶頭結點的單鏈表47
2.3.6單鏈表主要操作的性能分析48
2.3.7單鏈表的順序訪問與尾遞歸49
2.3.8單鏈表的應用——用有序鏈表表示集合52
2.4順序表與線性鏈表的比較55
2.5線性鏈表的其他變形57
2.5.1循環(huán)鏈表57
2.5.2雙向鏈表61
2.5.3靜態(tài)鏈表65
2.6線性表的應用: 一元多項式及其運算65
2.6.1一元多項式的表示66
2.6.2多項式的結構定義與建立67
2.6.3多項式的加法69
2.6.4多項式的乘法70
本章小結71
習題72
〖2〗〖2〗第3章棧和隊列78
3.1棧78
3.1.1棧的概念78
3.1.2順序棧79
3.1.3鏈式棧85
3.1.4棧的混洗87
3.2隊列90
3.2.1隊列的概念90
3.2.2循環(huán)隊列91
3.2.3雙循環(huán)隊列95
3.2.4鏈式隊列96
3.3棧的應用99
3.3.1數制轉換99
3.3.2括號匹配100
3.3.3表達式的計算與優(yōu)先級處理101
3.3.4棧與遞歸的實現105
3.4隊列的應用108
3.4.1打印楊輝三角形與逐行處理108
3.4.2電路布線與兩點間的最短路徑110
3.5在算法設計中使用遞歸113
3.5.1漢諾塔問題與分治法113
3.5.2排列組合與減治法116
3.5.3迷宮問題與回溯法118
3.5.4計算組合數與動態(tài)規(guī)劃123
3.6雙端隊列125
3.6.1雙端隊列的概念125
3.6.2輸入受限的雙端隊列125
3.6.3輸出受限的雙端隊列126
3.6.4雙端隊列的順序存儲表示127
3.6.5雙端隊列的鏈接存儲表示128
本章小結130
習題130
第4章數組、串和廣義表136
4.1數組136
4.1.1一維數組136
4.1.2多維數組138
4.1.3數組的應用舉例140
4.2特殊矩陣的壓縮存儲141
4.2.1對稱矩陣的壓縮存儲142
4.2.2三對角矩陣的壓縮存儲144
4.3稀疏矩陣145
4.3.1稀疏矩陣的概念145
4.3.2稀疏矩陣的三元組表表示146
4.3.3稀疏矩陣的十字鏈表表示151
4.4字符串152
4.4.1字符串的概念153
4.4.2字符串的初始化和賦值153
4.4.3C語言中有關字符串的庫函數154
4.4.4自定義字符串的存儲表示156
4.4.5串的模式匹配161
4.4.6字符串的應用實例166
4.5廣義表170
4.5.1廣義表的概念170
4.5.2廣義表的性質171
4.5.3廣義表的鏈接表示171
4.5.4三元多項式的表示174
本章小結176
習題177
第5章樹與二叉樹182
5.1樹的基本概念182
5.1.1樹的定義和術語182
5.1.2樹的基本操作185
5.2二叉樹186
5.2.1二叉樹的概念186
5.2.2二叉樹的性質187
5.2.3二叉樹的主要操作189
5.3二叉樹的存儲表示190
5.3.1二叉樹的順序存儲表示190
5.3.2二叉樹的鏈表存儲表示195
5.4二叉樹的遍歷199
5.4.1二叉樹遍歷的遞歸算法199
5.4.2遞歸遍歷算法的應用舉例200
5.4.3二叉樹遍歷的非遞歸算法203
5.4.4層次序遍歷算法的應用舉例208
5.4.5二叉樹的計數212
5.5線索二叉樹215
5.5.1線索二叉樹的概念215
5.5.2線索二叉樹的種類216
5.5.3中序線索二叉樹的建立和遍歷217
5.5.4前序與后序線索二叉樹222
5.6樹與森林223
5.6.1樹的雙親表示223
5.6.2樹的子女鏈表表示227
5.6.3子女兄弟鏈表表示230
5.6.4森林與二叉樹的轉換232
5.6.5樹與森林的深度優(yōu)先遍歷234
5.6.6樹與森林的廣度優(yōu)先遍歷236
5.6.7樹遍歷算法的應用舉例238
本章小結239
習題240
第6章樹與二叉樹的應用245
6.1二叉查找樹245
6.1.1二叉查找樹的概念245
6.1.2二叉查找樹的查找246
6.1.3二叉查找樹的插入247
6.1.4二叉查找樹的刪除249
6.1.5二叉查找樹的性能分析250
6.2中序線索二叉查找樹253
6.2.1中序線索二叉查找樹的構建253
6.2.2中序線索二叉查找樹的插入254
6.2.3中序線索二叉查找樹的刪除256
6.2.4中序線索二叉查找樹的范圍查找257
6.3AVL樹257
6.3.1AVL樹的概念258
6.3.2平衡化旋轉258
6.3.3AVL樹的插入262
6.3.4AVL樹的刪除264
6.3.5AVL樹的性能分析268
6.4Huffman樹270
6.4.1帶權路徑長度的概念270
6.4.2Huffman樹的概念270
6.4.3最優(yōu)判定樹274
6.4.4Huffman編碼275
6.5堆280
6.5.1小根堆和大根堆280
6.5.2堆的建立281
6.5.3堆的插入283
6.5.4堆的刪除284
6.6并查集285
6.6.1并查集的定義及其實現285
6.6.2并查集操作的分析和改進287
6.7八皇后問題與樹的剪枝289
6.7.1八皇后問題的提出289
6.7.2八皇后問題的狀態(tài)樹290
6.7.3八皇后問題算法292
本章小結293
習題293
第7章圖298
7.1圖的基本概念298
7.1.1與圖有關的若干概念298
7.1.2圖的基本操作301
7.2圖的存儲結構303
7.2.1圖的鄰接矩陣表示303
7.2.2圖的鄰接表表示308
7.2.3鄰接矩陣表示與鄰接表表示的比較315
7.2.4圖的鄰接多重表表示315
7.3圖的遍歷317
7.3.1圖遍歷的概念317
7.3.2深度優(yōu)先搜索318
7.3.3廣度優(yōu)先搜索319
7.3.4圖中的路徑與回路320
7.4圖的連通性323
7.4.1無向圖的連通分量323
7.4.2重連通圖325
7.4.3有向圖的強連通分量327
7.5最小生成樹330
7.5.1最小生成樹求解和貪婪法330
7.5.2Kruskal算法332
7.5.3Prim算法335
7.6最短路徑337
7.6.1非負權值的單源最短路徑337
7.6.2任意權值的單源最短路徑341
7.6.3所有頂點之間的最短路徑344
7.6.4無權值圖的最短路徑347
7.7活動網絡348
7.7.1AOV網絡與拓撲排序348
7.7.2AOE網絡與關鍵路徑法352
本章小結356
習題357
第8章查找363
8.1查找的基本概念363
8.1.1查找的概念363
8.1.2查找算法的性能分析364
8.2順序查找法364
8.2.1在順序表上的順序查找算法364
8.2.2在線性鏈表上的順序查找算法368
8.3折半查找法368
8.3.1折半查找法368
8.3.2重復元素序列上的折半查找371
8.3.3斐波那契查找: 折半查找的變形372
8.3.4插值查找: 折半查找的變形375
8.4最優(yōu)二叉查找樹376
8.4.1自下向上構造最優(yōu)二叉查找樹376
8.4.2自上向下構造近似最優(yōu)二叉查找樹380
8.5B樹384
8.5.1索引順序表與分塊查找384
8.5.2多級索引結構與m叉查找樹387
8.5.3B樹的概念388
8.5.4B樹上的查找390
8.5.5B樹上的插入391
8.5.6B樹上的刪除393
8.5.7B 樹397
8.6鍵樹400
8.6.1鍵樹的概念400
8.6.2雙鏈樹400
8.6.3Trie樹405
8.7散列表及其查找406
8.7.1散列的概念406
8.7.2常見的散列函數407
8.7.3解決沖突的開地址法410
8.7.4解決沖突的鏈地址法418
8.7.5散列法分析422
本章小結424
習題424
第9章內排序432
9.1排序概述432
9.1.1排序的概念432
9.1.2排序算法的性能433
9.1.3數據表的結構定義434
9.2插入排序435
9.2.1直接插入排序436
9.2.2基于鏈表的直接插入排序437
9.2.3折半插入排序439
9.2.4希爾排序440
9.3交換排序442
9.3.1起泡排序442
9.3.2快速排序445
9.3.3快速排序的改進算法449
9.4選擇排序452
9.4.1簡單選擇排序452
9.4.2堆排序454
9.4.3錦標賽排序457
9.5歸并排序460
9.5.1二路歸并排序的設計思路460
9.5.2二路歸并排序的遞歸算法461
9.5.3基于鏈表的歸并排序算法463
9.5.4迭代的歸并排序算法464
9.5.5利用循環(huán)右移的二路歸并算法466
9.6基數排序468
9.6.1基數排序概述469
9.6.2MSD基數排序469
9.6.3LSD基數排序472
9.7內排序算法的分析和比較475
9.7.1排序方法的下界475
9.7.2各種內排序方法的比較476
9.8時間復雜度小于O(nlog2n)的排序算法478
9.8.1計數排序算法478
9.8.2鴿巢排序算法479
9.9選擇算法480
9.9.1在順序表中查找值第k小的元素480
9.9.2在帶頭結點的單鏈表中查找倒數第k個結點481
9.9.3在帶頭結點的單鏈表中查找值為倒數第k的元素482
9.9.4不要求完全排序求前k個值最小的元素483
本章小結484
習題485
第10章外排序491
10.1主存儲器和外存儲器491
10.1.1磁帶491
10.1.2磁盤存儲器492
10.1.3緩沖區(qū)493
10.2基于磁盤的外排序過程494
10.2.1基于磁盤排序的過程494
10.2.2基于磁盤排序的性能分析495
10.3m路平衡歸并496
10.3.1m路平衡歸并的過程496
10.3.2用敗者樹選最小記錄497
10.3.3敗者樹的構造498
10.3.4排序算法中的讀寫磁盤操作500
10.3.5使用敗者樹進行m路平衡歸并排序的算法502
10.4初始歸并段的生成504
10.4.1置換選擇排序504
10.4.2用敗者樹實現置換選擇排序505
10.4.3置換選擇排序算法的實現505
10.4.4置換選擇排序的性能分析508
10.5最佳歸并樹509
10.5.1歸并樹的構造509
10.5.2構造最佳歸并樹的算法510
10.5.3根據最佳歸并樹實現M路歸并排序512
10.6并行操作的緩沖區(qū)處理514
10.6.1使用固定緩沖區(qū)實現并行操作514
10.6.2使用緩沖區(qū)隊列實現并行操作515
10.7磁帶歸并排序517
10.7.1平衡歸并排序517
10.7.2多步歸并排序518
10.7.3多步歸并排序初始歸并段的分配518
本章小結519
習題520
附錄清華大學本科生考試試題525
參考文獻528