第1章數(shù)據(jù)結(jié)構(gòu)與算法概述1
1.1數(shù)據(jù)結(jié)構(gòu)1
1.1.1什么是數(shù)據(jù)結(jié)構(gòu)1
1.1.2數(shù)據(jù)結(jié)構(gòu)的分類2
1.2抽象數(shù)據(jù)類型6
1.3算法7
1.3.1什么是算法7
1.3.2算法的特性9
1.3.3算法的復(fù)雜度10
1.3.4算法與數(shù)據(jù)結(jié)構(gòu)12
1.4小結(jié)12
【思考題】12
第2章線性表13
2.1什么是線性表13
2.2線性表的順序存儲（順序表）14
2.2.1順序存儲的原理14
2.2.2順序存儲的實(shí)現(xiàn)15
2.3線性表的鏈?zhǔn)酱鎯Γㄦ湵恚?3
2.3.1鏈?zhǔn)酱鎯Φ脑��?3
2.3.2鏈?zhǔn)酱鎯Φ膶?shí)現(xiàn)24
2.4雙鏈表31
2.4.1什么是雙鏈表32
2.4.2雙鏈表的實(shí)現(xiàn)32
2.5循環(huán)鏈表39
2.5.1什么是循環(huán)鏈表39
2.5.2循環(huán)鏈表的實(shí)現(xiàn)40
2.5.3約瑟夫環(huán)43
2.6本章小結(jié)48
【思考題】49目錄數(shù)據(jù)結(jié)構(gòu)與算法——C語言版第3章棧和隊(duì)列50
3.1什么是棧50
3.2棧的實(shí)現(xiàn)51
3.2.1棧的順序存儲實(shí)現(xiàn)51
3.2.2棧的鏈?zhǔn)酱鎯��?shí)現(xiàn)56
3.3棧的應(yīng)用60
3.3.1用棧實(shí)現(xiàn)四則運(yùn)算60
3.3.2棧的遞歸應(yīng)用72
3.4什么是隊(duì)列75
3.5隊(duì)列的實(shí)現(xiàn)75
3.5.1順序隊(duì)列的實(shí)現(xiàn)76
3.5.2鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)80
3.5.3循環(huán)隊(duì)列84
3.6本章小結(jié)86
【思考題】87
第4章串88
4.1什么是串88
4.2串的存儲結(jié)構(gòu)89
4.2.1串的順序存儲89
4.2.2串的鏈?zhǔn)酱鎯?7
4.3串的模式匹配算法98
4.3.1樸素的模式匹配98
4.3.2KMP算法（無回溯的模式匹配）101
4.4本章小結(jié)105
【思考題】105
第5章數(shù)組和廣義表106
5.1數(shù)組106
5.2矩陣的壓縮存儲109
5.2.1特殊矩陣109
5.2.2稀疏矩陣的定義110
5.2.3稀疏矩陣的創(chuàng)建112
5.2.4稀疏矩陣的轉(zhuǎn)置114
5.2.5稀疏矩陣的十字鏈表表示118
5.3廣義表123
5.3.1廣義表的定義123
5.3.2廣義表的存儲結(jié)構(gòu)124
5.3.3廣義表的遞歸運(yùn)算125
5.4本章小結(jié)132
【思考題】132
第6章樹133
6.1樹133
6.1.1什么是樹133
6.1.2樹的表示法135
6.2二叉樹138
6.2.1什么是二叉樹138
6.2.2二叉樹的分類138
6.2.3二叉樹的性質(zhì)139
6.3二叉樹的存儲結(jié)構(gòu)141
6.3.1二叉樹的順序存儲141
6.3.2二叉樹的鏈?zhǔn)酱鎯?43
6.4二叉樹的遍歷147
6.4.1二叉樹的遍歷147
6.4.2遞歸思想的應(yīng)用151
6.5二叉樹的非遞歸遍歷154
6.6二叉樹與樹、森林之間的轉(zhuǎn)換162
6.6.1二叉樹與樹之間的轉(zhuǎn)換162
6.6.2二叉樹與森林之間的轉(zhuǎn)換162
6.7二叉樹的創(chuàng)建164
6.7.1中序和先序創(chuàng)建二叉樹164
6.7.2#號法創(chuàng)建樹166
6.8線索二叉樹169
6.8.1什么是線索二叉樹169
6.8.2二叉樹的線索化171
6.8.3線索化二叉樹的遍歷175
6.9赫夫曼樹177
6.9.1什么是赫夫曼樹177
6.9.2赫夫曼樹的構(gòu)造178
6.9.3赫夫曼編碼179
6.10本章小結(jié)180
【思考題】181
第7章圖182
7.1圖的基本概念182
7.1.1圖的定義與基本術(shù)語182
7.1.2圖的基本操作185
7.2圖的存儲結(jié)構(gòu)186
7.2.1圖的鄰接矩陣存儲187
7.2.2圖的鄰接表存儲189
7.2.3圖的十字鏈表存儲192
7.2.4圖的鄰接多重表存儲194
7.3圖的遍歷196
7.3.1深度優(yōu)先遍歷196
7.3.2廣度優(yōu)先遍歷198
7.4最小生成樹201
7.4.1什么是最小生成樹201
7.4.2Prim算法203
7.4.3Kruskal算法207
7.5最短路徑210
7.5.1從源點(diǎn)到其他頂點(diǎn)的最短路徑211
7.5.2每對頂點(diǎn)的最短路徑216
7.6拓?fù)渑判?19
7.7關(guān)鍵路徑224
7.8本章小結(jié)229
【思考題】230
第8章查找231
8.1查找概述231
8.2順序表的查找232
8.3有序表的查找233
8.3.1折半查找233
8.3.2插值查找235
8.3.3斐波納契查找235
8.4索引順序查找239
8.5二叉排序樹241
8.6平衡二叉樹246
8.6.1平衡二叉樹的概念246
8.6.2平衡二叉樹的插入247
8.6.3平衡二叉樹的刪除252
8.7B樹254
8.7.1B樹的概念254
8.7.2B樹的插入256
8.7.3B樹的刪除258
8.8鍵樹261
8.9哈希表265
8.9.1什么是哈希表265
8.9.2哈希函數(shù)的構(gòu)造方法267
8.9.3處理哈希沖突269
8.9.4哈希表的查找實(shí)現(xiàn)273
8.10本章小結(jié)275
【思考題】275
第9章內(nèi)部排序276
9.1排序的概念與分類276
9.2交換排序278
9.2.1冒泡排序279
9.2.2快速排序283
9.3插入排序286
9.3.1直接插入排序286
9.3.2折半插入排序289
9.3.3希爾排序290
9.4選擇排序294
9.4.1簡單選擇排序294
9.4.2樹形選擇排序296
9.4.3堆排序298
9.5歸并排序303
9.6基數(shù)排序307
9.6.1基數(shù)排序基礎(chǔ)307
9.6.2鏈?zhǔn)交鶖?shù)排序310
9.7內(nèi)部排序方法比較314
9.8磁盤排序315
9.8.1外部存儲設(shè)備315
9.8.2磁盤排序分析317
9.8.3置換�策x擇排序319
9.8.4多路平衡歸并321
9.8.5最佳歸并樹324
9.9本章小結(jié)325
【思考題】326
第10章文件327
10.1文件概述327
10.2順序文件和索引文件328
10.2.1順序文件328
10.2.2索引文件329
10.3ISAM文件和VSAM文件331
10.3.1ISAM文件331
10.3.2VSAM文件334
10.4哈希文件336
10.5多關(guān)鍵字文件337
10.5.1多重表文件337
10.5.2倒排文件338
10.6本章小結(jié)339
【思考題】339
第11章綜合項(xiàng)目——貪吃蛇340
11.1項(xiàng)目分析340
11.1.1模塊設(shè)計(jì)340
11.1.2模塊描述342
11.1.3項(xiàng)目分析345
11.2項(xiàng)目實(shí)現(xiàn)346
11.2.1創(chuàng)建項(xiàng)目346
11.2.2項(xiàng)目設(shè)計(jì)346
11.2.3項(xiàng)目實(shí)現(xiàn)349
11.2.4主函數(shù)實(shí)現(xiàn)360
11.2.5效果展示364
11.3項(xiàng)目心得365
【思考題】366