數據結構——從概念到C++實現（第4版）

目錄

第1章緒論1

1.1引言2

1.2問題求解與程序設計3

1.2.1程序設計的一般過程3

1.2.2數據結構在程序設計中的作用6

1.2.3算法在程序設計中的作用7

1.2.4本書討論的主要內容8

1.3數據結構的基本概念10

1.3.1數據結構10

1.3.2抽象數據類型12

1.4算法的基本概念14

1.4.1算法及算法的特性14

1.4.2算法的描述方法15

1.5算法分析16

1.5.1算法的時間復雜度16

1.5.2算法的空間復雜度17

1.5.3算法分析實例18

1.6擴展與提高20

1.6.1概率算法20

1.6.2算法分析的其他漸進符號21

思想火花——好算法是反復努力和重新修正的結果21

習題122

考研真題125第2章線性表27

2.1引言28

2.2線性表的邏輯結構29

2.2.1線性表的定義29

2.2.2線性表的抽象數據類型定義29

2.3線性表的順序存儲結構及實現31

2.3.1順序表的存儲結構31

2.3.2順序表的實現31

2.4線性表的鏈式存儲結構及實現36

2.4.1單鏈表的存儲結構36

2.4.2單鏈表的實現38

2.4.3雙鏈表46

數據結構——從概念到C++實現（第4版）

目錄

2.4.4循環鏈表47

2.5擴展與提高48

2.5.1線性表的靜態鏈表存儲48

2.5.2順序表的動態分配方式50

2.5.3順序表和鏈表的比較52

2.6上機實驗53

2.6.1順序表的上機實現53

2.6.2單鏈表的上機實現53

2.6.3提純線性表54

2.6.4約瑟夫環問題55

思想火花——好程序要能識別和處理各種輸入57

習題257

考研真題261第3章棧、隊列和數組63

3.1引言64

3.2棧65

3.2.1棧的邏輯結構65

3.2.2棧的順序存儲結構及實現66

3.2.3棧的鏈式存儲結構及實現68

3.2.4順序棧和鏈棧的比較70

3.2.5棧的應用70

3.3隊列72

3.3.1隊列的邏輯結構72

3.3.2隊列的順序存儲結構及實現73

3.3.3隊列的鏈式存儲結構及實現76

3.3.4循環隊列和鏈隊列的比較79

3.3.5隊列的應用79

3.4多維數組79

3.4.1數組的邏輯結構79

3.4.2數組的存儲結構與尋址80

3.5矩陣的壓縮存儲81

3.5.1特殊矩陣的壓縮存儲82

3.5.2稀疏矩陣的壓縮存儲84

3.6擴展與提高86

3.6.1兩棧共享空間86

3.6.2雙端隊列87

3.6.3廣義表88

3.7上機實驗92

3.7.1順序棧的上機實現92

3.7.2鏈隊列的上機實現92

3.7.3括號匹配問題93

3.7.4機器翻譯94

思想火花——用常識性的思維去思考問題96

習題396

考研真題399第4章樹和二叉樹102

4.1引言103

4.2樹的邏輯結構104

4.2.1樹的定義和基本術語104

4.2.2樹的抽象數據類型定義105

4.2.3樹的遍歷操作106

4.3樹的存儲結構107

4.3.1雙親表示法107

4.3.2孩子表示法107

4.3.3孩子兄弟表示法108

4.4二叉樹的邏輯結構109

4.4.1二叉樹的定義109

4.4.2二叉樹的基本性質110

4.4.3二叉樹的抽象數據類型定義112

4.4.4二叉樹的遍歷操作113

4.4.5二叉樹的構造114

4.5二叉樹的存儲結構115

4.5.1順序存儲結構116

4.5.2二叉鏈表116

4.5.3三叉鏈表121

4.6森林122

4.6.1森林的邏輯結構122

4.6.2樹、森林與二叉樹的轉換122

4.7最優二叉樹124

4.7.1哈夫曼算法124

4.7.2哈夫曼編碼127

4.8擴展與提高128

4.8.1二叉樹遍歷的非遞歸算法128

4.8.2線索鏈表131

4.8.3堆與優先隊列135

4.8.4並查集138

4.9上機實驗140

4.9.1二叉鏈表的上機實現140

4.9.2孩子兄弟鏈表的上機實現140

4.9.3最近共同祖先141

4.9.4鏡像對稱二叉樹142

思想火花——調試程序與魔術表演144

習題4145

考研真題4148第5章圖151

5.1引言152

5.2圖的邏輯結構153

5.2.1圖的定義和基本術語153

5.2.2圖的抽象數據類型定義155

5.2.3圖的遍歷操作156

5.3圖的存儲結構及實現158

5.3.1鄰接矩陣158

5.3.2鄰接表161

5.3.3鄰接矩陣和鄰接表的比較165

5.4最小生成樹166

5.4.1Prim算法167

5.4.2Kruskal算法169

5.5最短路徑173

5.5.1Dijkstra算法174

5.5.2Floyd算法176

5.6有向無環圖及其應用178

5.6.1AOV網與拓撲排序178

5.6.2AOE網與關鍵路徑181

5.7擴展與提高183

5.7.1圖的其他存儲方法183

5.7.2圖的連通性185

5.8上機實驗186

5.8.1鄰接矩陣的上機實現186

5.8.2鄰接表的上機實現187

5.8.3農夫抓牛187

5.8.4研發卡車189

思想火花——直覺可能是錯誤的190

習題5191

考研真題5195第6章查找技術198

6.1概述199

6.1.1查找的基本概念199

6.1.2查找算法的性能199

6.2線性表的查找技術200

6.2.1線性表查找結構的類定義200

6.2.2順序查找201

6.2.3折半查找201

6.3樹表的查找技術204

6.3.1二叉搜索樹204

6.3.2平衡二叉樹209

6.3.3B樹213

6.4散列表的查找技術217

6.4.1散列查找的基本思想217

6.4.2散列函數的設計218

6.4.3處理沖突的方法220

6.4.4散列查找的性能分析224

6.4.5開散列表與閉散列表的比較225

6.5模式匹配225

6.5.1BF算法225

6.5.2KMP算法227

6.6擴展與提高229

6.6.1順序查找的改進——分塊查找229

6.6.2折半查找的改進——插值查找229

6.6.3平衡二叉樹的改進——紅黑樹230

6.6.4B樹的改進——B+樹235

6.6.5各種查找方法的比較236

6.7上機實驗237

6.7.1折半查找算法的上機實現237

6.7.2散列查找算法的上機實現237

6.7.3團隊合照238

6.7.4獨一無二的雪花239

思想火花——把註意力集中於主要因素241

習題6242

考研真題6245第7章排序技術248

7.1概述249

7.1.1排序的基本概念249

7.1.2排序算法的性能250

7.1.3排序類的定義250

7.2插入排序251

7.2.1直接插入排序251

7.2.2希爾排序253

7.3交換排序255

7.3.1起泡排序255

7.3.2快速排序256

7.4選擇排序259

7.4.1簡單選擇排序259

7.4.2堆排序261

7.5歸並排序266

7.5.1二路歸並排序的遞歸實現266

7.5.2二路歸並排序的非遞歸實現267

7.6外部排序269

7.6.1外部排序的基本思想269

7.6.2置換選擇排序270

7.6.3敗者樹272

7.7各種排序算法的比較273

7.7.1各種排序算法的使用範例273

7.7.2各種排序算法的綜合比較273

7.8擴展與提高275

7.8.1排序問題的時間下界275

7.8.2基數排序277

7.9上機實驗279

7.9.1插入排序的上機實現279

7.9.2交換排序的上機實現279

7.9.3車廂重排280

7.9.4topK問題281

思想火花——學會“盒子以外的思考”282

習題7283

考研真題7286附錄A考研真題參考答案288附錄B實驗報告的一般格式293參考文獻294