數據結構(C語言描述)

李曄

主要研究項目及領域：計算機應用技術
作者簡介：本科、碩士及博士所學專業均為計算機相
關專業，有二十多年從事計算機課程一線教學的經驗，
長期主講數據結構課程。

第1章緒論1
1.1什麼是數據結構1
1.2數據結構的概念及有關術語1
1.3算法和算法分析5
習題7

第2章線性表9
2.1線性表的定義9
2.2線性表的基本運算9
2.3順序存儲結構線性表10
2.3.1線性表的順序存儲結構10
2.3.2順序存儲結構線性表的基本運算11
2.3.3順序存儲結構線性表的應用15
2.4鍊式存儲結構線性表20
2.4.1單鍊錶20
2.4.2循環鍊錶28
2.4.3雙向鍊錶29
2.4.4靜態鍊錶30
2.4.5鍊式存儲結構線性表的應用31
2.5小結38
習題38

第3章棧和隊列42
3.1棧42
3.1.1棧的定義及基本運算42
3.1.2順序存儲結構棧的基本運算42
3.1.3鍊式存儲結構棧的基本運算45
3.1.4棧的應用實例47
3.1.5棧與遞歸48
3.2隊列50
3.2.1隊列的定義及基本運算50
3.2.2順序存儲結構隊列的基本運算50
3.2.3鍊式存儲結構隊列的基本運算53
3.2.4隊列的應用55
3.3小結57
習題58

第4章串61
4.1串的概念及基本運算61
4.1.1串的基本概念61
4.1.2串的基本運算62
4.2順序存儲結構串的運算63
4.2 .1串的定長順序存儲結構63
4.2.2定長順序存儲結構串的基本運算64
4.3串的堆分配存儲結構及其運算66
4.3.1串的堆分配存儲結構66
4.3.2堆分配存儲結構串的運算66
4.4串的鍊式存儲結構及基本運算68
4.4.1串的鍊式存儲結構68
4.4.2鏈串的基本運算69
4.5串的模式匹配70
4.5.1簡單模式匹配算法—— BF算法70
4.5.2無回溯的模式匹配算法——KMP算法72
*4.5.3 next函數的改進77
4.6小結79
習題79

第5章數組和廣義表81
5.1數組81
5.1.1數組的定義及邏輯結構81
5.1.2數組的存儲結構83
5.1.3特殊矩陣的壓縮存儲84
5.1.4數組應用舉例88
5.2廣義表91
5.2.1廣義表的定義91
5.2.2廣義表的存儲結構93
5.2.3廣義表基本操作實現94
5.2.4廣義表應用舉例97
5.3小結98
習題99

第6章樹和二叉樹102
6.1樹的定義及有關術語102
6.1.1樹的定義102
6.1.2常用術語102
6.2二叉樹103
6.2.1二叉樹的定義103
6.2.2二叉樹的性質105
6.2.3二叉樹的存儲結構105
6.2.4二叉樹的遍歷107
6.2.5線索二叉樹113
6.2.6哈夫曼樹117
6.3樹和森林122
6.3.1樹的存儲結構122
6.3.2樹或森林與二叉樹的轉換124
6.3.3樹和森林的遍歷125
6.4小結126
習題126

第7章圖130
7.1圖的定義及有關術語130
7.2圖的存儲結構134
7.2.1鄰接矩陣134
7.2.2鄰接表137
7.2.3十字鍊錶139
*7.2.4鄰接多重表141
7.3圖的遍歷143
7.3.1深度優先搜索143
7.3.2廣度優先搜索145
7.3.3圖的連通性148
7.4最小生成樹150
7.4.1普裏姆算法150
7.4.2克魯斯卡爾算法153
7.5有向無環圖及其應用156
7.5.1拓撲排序156
7.5.2關鍵路徑161
7.6最短路徑166
7.6.1單源最短路徑166
7.6.2每一對頂點之間的最短路徑169
7.7圖的應用實例172
7.8小結174
習題175

第8章查找180
8.1查找的有關概念180
8.2線性表的查找181
8.2.1順序查找181
8.2.2二分查找182
8.2.3分塊查找184
8.3樹表的查找185
8.3.1二叉排序樹185
8.3.2平衡二叉樹190
8.3.3 B-樹193
8.3.4 B+樹196
8.4哈希查找197
8.4.1哈希表的概念及哈希函數的構造197
8.4.2哈希表的建立199
8.4.3衝突的處理方法199
8.4.4哈希查找的實現201
8.5小結202
習題203

第9章排序206
9.1排序的有關概念206
9.2插入排序207
9.2.1直接插入排序207
9.2.2折半插入排序208
9.2.3希爾排序209
9.3交換排序211
9.3.1冒泡排序211
9.3 .2快速排序212
9.4選擇排序214
9.4.1簡單選擇排序214
9.4.2堆排序216
9.5歸併排序219
9.6基數排序221
9.7多關鍵字排序223
9.8小結224
習題225

參考文獻229