第1章緒論1
1.1數(shù)據(jù)結(jié)構(gòu)的概念及分類1
1.1.1為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)1
1.1.2與數(shù)據(jù)結(jié)構(gòu)相關(guān)的基本術(shù)語(yǔ)2
1.1.3數(shù)據(jù)結(jié)構(gòu)的分類5
1.1.4數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)7
1.1.5定義在數(shù)據(jù)結(jié)構(gòu)上的操作8
1.1.6“好”數(shù)據(jù)結(jié)構(gòu)8
1.2使用C語(yǔ)言描述數(shù)據(jù)結(jié)構(gòu)8
1.2.1C的數(shù)據(jù)類型9
1.2.2算法的控制結(jié)構(gòu)10
1.2.3算法的函數(shù)結(jié)構(gòu)11
1.2.4動(dòng)態(tài)存儲(chǔ)分配14
1.2.5邏輯和關(guān)系運(yùn)算的約定15
1.2.6輸入與輸出15
1.3算法和算法設(shè)計(jì)16
1.3.1算法的定義和特性16
1.3.2算法的設(shè)計(jì)步驟17
1.3.3算法設(shè)計(jì)的基本方法18
1.4算法分析與度量21
1.4.1算法的評(píng)價(jià)標(biāo)準(zhǔn)22
1.4.2算法的時(shí)間和空間復(fù)雜性度量22
1.4.3算法的漸進(jìn)分析25
本章小結(jié)28
習(xí)題28
第2章線性表32
2.1線性表32
2.1.1線性表的定義和特點(diǎn)32
2.1.2線性表的主要操作33
2.2順序表34
2.2.1順序表的定義和特點(diǎn)34
2.2.2順序表的結(jié)構(gòu)定義35
2.2.3順序表主要操作的實(shí)現(xiàn)36
2.2.4順序表主要操作的性能分析39
2.2.5順序表的應(yīng)用舉例41
2.3單鏈表42
2.3.1單鏈表的定義和特點(diǎn)42
2.3.2單鏈表的結(jié)構(gòu)定義43
2.3.3單鏈表中指針的操作43
2.3.4單鏈表中的插入與刪除43
2.3.5帶頭結(jié)點(diǎn)的單鏈表47
2.3.6單鏈表主要操作的性能分析48
2.3.7單鏈表的順序訪問(wèn)與尾遞歸49
2.3.8單鏈表的應(yīng)用——用有序鏈表表示集合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線性表的應(yīng)用: 一元多項(xiàng)式及其運(yùn)算65
2.6.1一元多項(xiàng)式的表示66
2.6.2多項(xiàng)式的結(jié)構(gòu)定義與建立67
2.6.3多項(xiàng)式的加法69
2.6.4多項(xiàng)式的乘法70
本章小結(jié)71
習(xí)題72
〖2〗〖2〗第3章棧和隊(duì)列78
3.1棧78
3.1.1棧的概念78
3.1.2順序棧79
3.1.3鏈?zhǔn)綏?5
3.1.4棧的混洗87
3.2隊(duì)列90
3.2.1隊(duì)列的概念90
3.2.2循環(huán)隊(duì)列91
3.2.3雙循環(huán)隊(duì)列95
3.2.4鏈?zhǔn)疥?duì)列96
3.3棧的應(yīng)用99
3.3.1數(shù)制轉(zhuǎn)換99
3.3.2括號(hào)匹配100
3.3.3表達(dá)式的計(jì)算與優(yōu)先級(jí)處理101
3.3.4棧與遞歸的實(shí)現(xiàn)105
3.4隊(duì)列的應(yīng)用108
3.4.1打印楊輝三角形與逐行處理108
3.4.2電路布線與兩點(diǎn)間的最短路徑110
3.5在算法設(shè)計(jì)中使用遞歸113
3.5.1漢諾塔問(wèn)題與分治法113
3.5.2排列組合與減治法116
3.5.3迷宮問(wèn)題與回溯法118
3.5.4計(jì)算組合數(shù)與動(dòng)態(tài)規(guī)劃123
3.6雙端隊(duì)列125
3.6.1雙端隊(duì)列的概念125
3.6.2輸入受限的雙端隊(duì)列125
3.6.3輸出受限的雙端隊(duì)列126
3.6.4雙端隊(duì)列的順序存儲(chǔ)表示127
3.6.5雙端隊(duì)列的鏈接存儲(chǔ)表示128
本章小結(jié)130
習(xí)題130
第4章數(shù)組、串和廣義表136
4.1數(shù)組136
4.1.1一維數(shù)組136
4.1.2多維數(shù)組138
4.1.3數(shù)組的應(yīng)用舉例140
4.2特殊矩陣的壓縮存儲(chǔ)141
4.2.1對(duì)稱矩陣的壓縮存儲(chǔ)142
4.2.2三對(duì)角矩陣的壓縮存儲(chǔ)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語(yǔ)言中有關(guān)字符串的庫(kù)函數(shù)154
4.4.4自定義字符串的存儲(chǔ)表示156
4.4.5串的模式匹配161
4.4.6字符串的應(yīng)用實(shí)例166
4.5廣義表170
4.5.1廣義表的概念170
4.5.2廣義表的性質(zhì)171
4.5.3廣義表的鏈接表示171
4.5.4三元多項(xiàng)式的表示174
本章小結(jié)176
習(xí)題177
第5章樹與二叉樹182
5.1樹的基本概念182
5.1.1樹的定義和術(shù)語(yǔ)182
5.1.2樹的基本操作185
5.2二叉樹186
5.2.1二叉樹的概念186
5.2.2二叉樹的性質(zhì)187
5.2.3二叉樹的主要操作189
5.3二叉樹的存儲(chǔ)表示190
5.3.1二叉樹的順序存儲(chǔ)表示190
5.3.2二叉樹的鏈表存儲(chǔ)表示195
5.4二叉樹的遍歷199
5.4.1二叉樹遍歷的遞歸算法199
5.4.2遞歸遍歷算法的應(yīng)用舉例200
5.4.3二叉樹遍歷的非遞歸算法203
5.4.4層次序遍歷算法的應(yīng)用舉例208
5.4.5二叉樹的計(jì)數(shù)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森林與二叉樹的轉(zhuǎn)換232
5.6.5樹與森林的深度優(yōu)先遍歷234
5.6.6樹與森林的廣度優(yōu)先遍歷236
5.6.7樹遍歷算法的應(yīng)用舉例238
本章小結(jié)239
習(xí)題240
第6章樹與二叉樹的應(yīng)用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中序線索二叉查找樹的構(gòu)建253
6.2.2中序線索二叉查找樹的插入254
6.2.3中序線索二叉查找樹的刪除256
6.2.4中序線索二叉查找樹的范圍查找257
6.3AVL樹257
6.3.1AVL樹的概念258
6.3.2平衡化旋轉(zhuǎn)258
6.3.3AVL樹的插入262
6.3.4AVL樹的刪除264
6.3.5AVL樹的性能分析268
6.4Huffman樹270
6.4.1帶權(quán)路徑長(zhǎng)度的概念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并查集的定義及其實(shí)現(xiàn)285
6.6.2并查集操作的分析和改進(jìn)287
6.7八皇后問(wèn)題與樹的剪枝289
6.7.1八皇后問(wèn)題的提出289
6.7.2八皇后問(wèn)題的狀態(tài)樹290
6.7.3八皇后問(wèn)題算法292
本章小結(jié)293
習(xí)題293
第7章圖298
7.1圖的基本概念298
7.1.1與圖有關(guān)的若干概念298
7.1.2圖的基本操作301
7.2圖的存儲(chǔ)結(jié)構(gòu)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無(wú)向圖的連通分量323
7.4.2重連通圖325
7.4.3有向圖的強(qiáng)連通分量327
7.5最小生成樹330
7.5.1最小生成樹求解和貪婪法330
7.5.2Kruskal算法332
7.5.3Prim算法335
7.6最短路徑337
7.6.1非負(fù)權(quán)值的單源最短路徑337
7.6.2任意權(quán)值的單源最短路徑341
7.6.3所有頂點(diǎn)之間的最短路徑344
7.6.4無(wú)權(quán)值圖的最短路徑347
7.7活動(dòng)網(wǎng)絡(luò)348
7.7.1AOV網(wǎng)絡(luò)與拓?fù)渑判?48
7.7.2AOE網(wǎng)絡(luò)與關(guān)鍵路徑法352
本章小結(jié)356
習(xí)題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重復(fù)元素序列上的折半查找371
8.3.3斐波那契查找: 折半查找的變形372
8.3.4插值查找: 折半查找的變形375
8.4最優(yōu)二叉查找樹376
8.4.1自下向上構(gòu)造最優(yōu)二叉查找樹376
8.4.2自上向下構(gòu)造近似最優(yōu)二叉查找樹380
8.5B樹384
8.5.1索引順序表與分塊查找384
8.5.2多級(jí)索引結(jié)構(gòu)與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常見的散列函數(shù)407
8.7.3解決沖突的開地址法410
8.7.4解決沖突的鏈地址法418
8.7.5散列法分析422
本章小結(jié)424
習(xí)題424
第9章內(nèi)排序432
9.1排序概述432
9.1.1排序的概念432
9.1.2排序算法的性能433
9.1.3數(shù)據(jù)表的結(jié)構(gòu)定義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快速排序的改進(jìn)算法449
9.4選擇排序452
9.4.1簡(jiǎn)單選擇排序452
9.4.2堆排序454
9.4.3錦標(biāo)賽排序457
9.5歸并排序460
9.5.1二路歸并排序的設(shè)計(jì)思路460
9.5.2二路歸并排序的遞歸算法461
9.5.3基于鏈表的歸并排序算法463
9.5.4迭代的歸并排序算法464
9.5.5利用循環(huán)右移的二路歸并算法466
9.6基數(shù)排序468
9.6.1基數(shù)排序概述469
9.6.2MSD基數(shù)排序469
9.6.3LSD基數(shù)排序472
9.7內(nèi)排序算法的分析和比較475
9.7.1排序方法的下界475
9.7.2各種內(nèi)排序方法的比較476
9.8時(shí)間復(fù)雜度小于O(nlog2n)的排序算法478
9.8.1計(jì)數(shù)排序算法478
9.8.2鴿巢排序算法479
9.9選擇算法480
9.9.1在順序表中查找值第k小的元素480
9.9.2在帶頭結(jié)點(diǎn)的單鏈表中查找倒數(shù)第k個(gè)結(jié)點(diǎn)481
9.9.3在帶頭結(jié)點(diǎn)的單鏈表中查找值為倒數(shù)第k的元素482
9.9.4不要求完全排序求前k個(gè)值最小的元素483
本章小結(jié)484
習(xí)題485
第10章外排序491
10.1主存儲(chǔ)器和外存儲(chǔ)器491
10.1.1磁帶491
10.1.2磁盤存儲(chǔ)器492
10.1.3緩沖區(qū)493
10.2基于磁盤的外排序過(guò)程494
10.2.1基于磁盤排序的過(guò)程494
10.2.2基于磁盤排序的性能分析495
10.3m路平衡歸并496
10.3.1m路平衡歸并的過(guò)程496
10.3.2用敗者樹選最小記錄497
10.3.3敗者樹的構(gòu)造498
10.3.4排序算法中的讀寫磁盤操作500
10.3.5使用敗者樹進(jìn)行m路平衡歸并排序的算法502
10.4初始?xì)w并段的生成504
10.4.1置換選擇排序504
10.4.2用敗者樹實(shí)現(xiàn)置換選擇排序505
10.4.3置換選擇排序算法的實(shí)現(xiàn)505
10.4.4置換選擇排序的性能分析508
10.5最佳歸并樹509
10.5.1歸并樹的構(gòu)造509
10.5.2構(gòu)造最佳歸并樹的算法510
10.5.3根據(jù)最佳歸并樹實(shí)現(xiàn)M路歸并排序512
10.6并行操作的緩沖區(qū)處理514
10.6.1使用固定緩沖區(qū)實(shí)現(xiàn)并行操作514
10.6.2使用緩沖區(qū)隊(duì)列實(shí)現(xiàn)并行操作515
10.7磁帶歸并排序517
10.7.1平衡歸并排序517
10.7.2多步歸并排序518
10.7.3多步歸并排序初始?xì)w并段的分配518
本章小結(jié)519
習(xí)題520
附錄清華大學(xué)本科生考試試題525
參考文獻(xiàn)528