數據結構

本書系統地介紹了各種典型的數據結構，主要包括演演算法、線性表、棧和隊列、串、數組、樹、圖、查找、排序、遞歸和文件；為了加強對演演算法的理解，也介紹了演演算法分析方面的內容。本書語言精練、概念清楚、注重實用、邏輯性強，各章中所涉及的數據結構與演演算法都給出了C語言描述，並附有大量習題，便於學生理解與掌握。本書可作為高等院校計算機專業及相關專業的教材，也可作為計算機應用技術人員的參考書

第1章 緒論1

1.1 問題的提出1

1.2 基本術語2

1.3 數據結構的概念4

1.4 數據的邏輯結構6

1.5 數據的存儲結構7

1.6 數據的運算9

1.7 數據的邏輯結構、存儲結構及運算的關係9

1.8 演演算法概述10

1.8.1 演演算法與演演算法特性10

1.8.2 演演算法描述10

1.9 演演算法分析11

小結13

習題114

第2章 線性表15

2.1 線性表的定義與運算15

2.1.1 線性表的定義15

2.1.2 線性表的運算16

2.2 線性表的順序存儲19

2.2.1 順序存儲19

2.2.2 順序結構線性表的運算20

2.2.3 順序存儲結構的優點23

2.2.4 順序存儲結構的缺點23

2.3 線性表的鏈式存儲23

2.3.1 線性鏈表23

2.3.2 線性鏈表的運算26

2.3.3 靜態鏈表312.3.4 靜態鏈表的運算31

2.3.5 循環鏈表32

2.3.6 循環鏈表的運算33

2.3.7 雙向鏈表 34

2.3.8 雙向鏈表的運算35

2.3.9 鏈式存儲結構的特點37

2.4 鏈式存儲結構的應用37

2.4.1 約瑟夫問題37

2.4.2 一元多項式求和39

2.4.3 在集合方面的應用42

小結44

習題244

第3章棧和隊列46

3.1棧46

3.1.1棧的定義46

3.1.2棧的順序存儲結構47

3.1.3棧的鏈式存儲結構51

3.1.4順序棧和鏈式棧的比較53

3.2棧的應用53

3.2.1迷宮問題53

3.2.2算術表達式求值56

3.2.3子程序的調用和返回59

3.2.4數制轉換60

3.3隊列61

3.3.1隊列的定義61

3.3.2隊列的順序存儲62

3.3.3隊列的鏈式存儲68

3.3.4優先隊列72

3.4隊列的應用73

3.4.1設備速度不匹配問題73

3.4.2舞伴問題73

小結75

習題375

第4章串77

4.1串的基本概念77

4.2串的存儲結構78

4.2.1串的靜態存儲結構79

4.2.2串的動態存儲結構80

4.3串的基本運算及實現82

4.3.1串的基本運算82

4.3.2實現串的基本運算的演演算法83

4.4模式匹配87

4.4.1BF演演算法87

4.4.2KMP演演算法90

小結94

習題494

第5章數組96

5.1數組的概念96

5.1.1數組的定義及基本操作96

5.1.2抽象數據類型數組的定義98

5.2數組的順序存儲結構98

5.3矩陣的壓縮存儲102

5.3.1特殊矩陣的壓縮存儲102

5.3.2稀疏矩陣的壓縮存儲104

小結118

習題5118

第6章樹120

6.1樹120

6.1.1樹的定義120

6.1.2樹的表示方法121

6.1.3樹的基本術語121

6.1.4樹的ADT定義122

6.2二叉樹123

6.2.1二叉樹的定義及基本形態123

6.2.2二叉樹的存儲結構125

6.2.3二叉樹的遍歷127

6.3線索二叉樹130

6.3.1二叉樹的線索化131

6.3.2利用線索遍歷131

6.4樹、森林和二叉樹的關係136

6.4.1樹的存儲結構136

6.4.2森林與二叉樹的轉換139

6.4.3樹和森林的遍歷142

6.5哈夫曼樹及其應用143

6.5.1與哈夫曼樹有關的定義143

6.5.2哈夫曼樹的構造145

6.5.3哈夫曼樹的應用146

小結151

習題6151

第7章圖155

7.1圖的基本概念155

7.2圖的存儲結構159

7.2.1鄰接矩陣160

7.2.2鄰接表162

7.2.3十字鏈表166

7.2.4鄰接多重表167

7.3圖的遍歷169

7.3.1深度優先搜索169

7.3.2廣度優先搜索172

7.4生成樹174

7.4.1普里姆（Prim）演演算法175

7.4.2克魯斯卡爾(kruskal)演演算法178

7.5最短路徑180

7.5.1單源最短路徑180

7.5.2頂點之間的最短路徑183

7.6拓撲排序184

7.7關鍵路徑188

小結195

習題7195

第8章查找199

8.1基本概念199

8.2線性表的查找200

8.2.1順序查找200

8.2.2折半查找202

8.2.3分塊查找205

8.3樹表的查找208

8.3.1二叉查找樹208

8.3.2平衡二叉樹214

8.3.3B-樹220

8.4哈希表的查找222

8.4.1哈希表222

8.4.2構造哈希表的基本方法223

8.4.3解決衝突的方法225

8.4.4哈希表的查找方法228

8.5查找方法的比較228

小結229

習題8229

第9章排序232

9.1基本概念232

9.2內部排序方法235

9.2.1插入排序235

9.2.2冒泡排序239

9.2.3快速排序240

9.2.4選擇排序243

9.2.5歸併排序248

9.2.6基數排序251

9.3內部排序方法比較256

9.4外部排序方法簡介257

小結257

習題9258

第10章遞歸261

10.1遞歸的定義261

10.2典型遞歸問題262

10.2.1漢諾塔問題262

10.2.2八皇后問題264

10.3遞歸的實現266

10.4遞歸轉化為非遞歸的一般過程270

10.5遞歸的時間和空間複雜度273

小結274

習題10275

第11章文件276

11.1外存儲器的介紹276

11.2有關文件的概念277

11.2.1文件及其類別278

11.2.2文件的操作279

11.3文件的組織280

11.3.1順序文件281

11.3.2索引文件282

11.3.3散列文件287

11.3.4多關鍵字文件289

小結291

習題11291

附錄上機實驗293

參考文獻296