數據結構（C語言版）

數據結構是計算機及相關專業的核心課程，是計算機程序設計的基礎,是程序員和許多高校研究生入學考試的必考科目。

本書共分10章，第1章是數據結構的概述；後9章分別介紹了線性表、棧、隊列、串、數組、廣義表、樹、二叉樹、圖、查找、內部排序、外部排序、動態存儲管理和文件等基本類型的數據結構。本書中的算法都已通過調試，不用修改就能運行。本書可作為計算機和相關專業的教材，也可作為自學者或各種計算機培訓班的教材。 ^[1] 

第1章概述1

1.1數據結構的發展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基本操作在順序表上的實現15

2.3鏈表19

2.3.1單鏈表的表示和實現19

2.3.2雙鏈表的表示和實現27

2.3.3循環鏈表的表示和實現31

*2.3.4靜態鏈表的表示和實現38

2.4棧43

2.4.1棧的定義及其基本操作43

2.4.2順序棧的表示和實現44

*2.4.3鏈棧的表示和實現48

2.5隊列51

2.5.1隊列的定義及其基本操作51

2.5.2順序隊列的表示和實現52

2.5.3鏈隊列的表示和實現56

2.6串58數據結構(C語言版)目錄2.6.1串的定義及其基本操作58

2.6.2順序串的表示和實現59

*2.6.3鏈串的表示和實現64

**2.6.4串的模式匹配70

習題275

第3章數組和廣義表81

3.1數組81

3.1.1數組的定義及基本操作81

3.1.2數組存儲結構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深度優先搜索及其生成樹152

5.3.2廣度優先搜索及其生成樹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靜態查找表168

6.1.1順序查找168

6.1.2二分查找169

6.1.3分塊查找171

6.2動態查找表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散列函數的構造方法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計數排序與基數排序219

7.7各種排序方法的綜合比較222

習題7223

第8章外部排序227

8.1外存儲器簡介227

8.2外部排序的方法229

8.3多路歸併排序230

8.4置換選擇排序232

8.5最佳歸併樹234

習題8235

第9章動態存儲管理237

9.1概述237

9.2可利用空間表及分配方法239

9.3邊界標識法242

9.3.1可利用空間表的結構242

9.3.2分配算法243

9.3.3回收算法244

9.4夥伴系統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 ^[1-2]