數(shù)據(jù)結構

第1章概述1
1.1數(shù)據(jù)結構的發(fā)展1
1.2基本概念2
1.3算法描述與分析4
習題110

第2章線性表13
2.1線性表的定義及基本操作13
2.1.1線性表的基本概念13
2.1.2線性表的基本操作14
2.2順序表14
2.2.1順序表的定義14
2.2.2基本操作在順序表上的實現(xiàn)15
2.3鏈表19
2.3.1單鏈表的表示和實現(xiàn)19
2.3.2雙鏈表的表示和實現(xiàn)27
2.3.3循環(huán)鏈表的表示和實現(xiàn)31
*2.3.4靜態(tài)鏈表的表示和實現(xiàn)38
2.4棧43
2.4.1棧的定義及其基本操作43
2.4.2順序棧的表示和實現(xiàn)44
*2.4.3鏈棧的表示和實現(xiàn)48
2.5隊列51
2.5.1隊列的定義及其基本操作51
2.5.2順序隊列的表示和實現(xiàn)52
2.5.3鏈隊列的表示和實現(xiàn)56
2.6串58數(shù)據(jù)結構(C語言版)目錄2.6.1串的定義及其基本操作58
2.6.2順序串的表示和實現(xiàn)59
*2.6.3鏈串的表示和實現(xiàn)64
**2.6.4串的模式匹配70
習題275

第3章數(shù)組和廣義表81
3.1數(shù)組81
3.1.1數(shù)組的定義及基本操作81
3.1.2數(shù)組存儲結構82
3.1.3矩陣的壓縮存儲83
*3.2廣義表97
3.2.1廣義表的定義和基本操作97
3.2.2廣義表的存儲98
習題3103

第4章樹和二叉樹107
4.1樹的定義和基本操作107
4.1.1樹的定義和基本術語107
4.1.2樹的基本操作108
4.2二叉樹的定義和性質109
4.2.1二叉樹的定義109
4.2.2二叉樹的性質與結論110
4.3二叉樹的存儲112
4.3.1二叉樹的順序存儲結構112
4.3.2二叉樹的鏈式存儲結構114
4.4二叉樹的遍歷及應用116
4.4.1二叉樹的遍歷116
4.4.2二叉樹遞歸遍歷應用舉例119
*4.4.3二叉樹的非遞歸遍歷122
*4.5線索二叉樹124
4.5.1線索二叉樹的定義124
4.5.2線索化處理算法125
4.6樹和森林128
4.6.1樹的存儲結構128
4.6.2樹、森林與二叉樹之間的轉換132
4.6.3樹和森林的遍歷133
4.7霍夫曼樹及其應用133
4.7.1霍夫曼樹134
4.7.2霍夫曼編碼136
習題4139

第5章圖143
5.1圖的基本概念143
5.2圖的存儲146
5.2.1鄰接矩陣147
5.2.2鄰接表與逆鄰接表148
*5.2.3十字鏈表150
*5.2.4鄰接多重表151
5.3圖的遍歷152
5.3.1深度優(yōu)先搜索及其生成樹152
5.3.2廣度優(yōu)先搜索及其生成樹153
5.4最小生成樹154
5.4.1Kruskal算法154
5.4.2Prim算法156
5.5圖的應用157
5.5.1拓撲排序157
5.5.2關鍵路徑159
5.5.3最短路徑161
習題5163

第6章查找167
6.1靜態(tài)查找表168
6.1.1順序查找168
6.1.2二分查找169
6.1.3分塊查找171
6.2動態(tài)查找表173
6.2.1二叉排序樹173
6.2.2平衡二叉樹178
*6.2.3B_樹與B+樹184
*6.2.4鍵樹186
6.3散列表187
6.3.1散列表的定義187
6.3.2散列函數(shù)的構造方法188
6.3.3處理沖突的方法190
*6.3.4散列表的查找與分析192
習題6193

第7章內部排序197
7.1概述197
7.2插入排序199
7.3交換排序207
7.4選擇排序210
7.5歸并排序217
7.6計數(shù)排序與基數(shù)排序219
7.7各種排序方法的綜合比較222
習題7223

**第8章外部排序227
8.1外存儲器簡介227
8.2外部排序的方法229
8.3多路歸并排序230
8.4置換選擇排序232
8.5最佳歸并樹234
習題8235

**第9章動態(tài)存儲管理237
9.1概述237
9.2可利用空間表及分配方法239
9.3邊界標識法242
9.3.1可利用空間表的結構242
9.3.2分配算法243
9.3.3回收算法244
9.4伙伴系統(tǒng)246
9.4.1可利用空間表的結構246
9.4.2分配算法248
9.4.3回收算法249
9.5無用單元收集249
9.6存儲緊縮254

**第10章文件257
10.1表與文件257
10.1.1有關文件的基本概念257
10.1.2記錄的邏輯結構和物理結構258
10.1.3文件的操作258
10.2外存儲器簡介259
10.2.1文件的物理結構259
10.2.2文件的邏輯結構和文件的存儲結構260
10.2.3順序文件261
10.2.4索引文件262
10.3ISAM文件265
10.4VSAM文件266
10.5直接存取文件267
10.6多關鍵字文件268
10.6.1多重表文件268
10.6.2倒排文件269
習題10270

參考文獻271