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

《數據結構——從概念到C實現（第2版）》是2023年清華大學出版社出版的圖書，作者是王紅梅。

基本介紹

• 中文名：數據結構——從概念到C實現（第2版）
• 作者：王紅梅
• 出版時間：2023年3月1日
• 出版社：清華大學出版社
• ISBN：9787302615682 
• 定價：58 元

內容簡介

本書按照《全國碩士研究生招生考試計算機科學與技術學科聯考計算機學科專業基礎考試大綱》（以下簡稱《考試大綱》）重新組織目錄，涵蓋《考試大綱》的全部考查內容。本書介紹了數據結構、算法以及抽象數據類型的概念；線性表、棧和佇列、多維數組、樹和二叉樹、圖等基本數據結構及實現方法；常用查找技術和排序技術。本書兼顧概念層和實現層，既強調了數據結構的基本概念和原理方法，又注重了數據結構的程式實現和實際運用，在提煉基礎知識的同時，進行了適當的擴展和提高。

圖書目錄

目錄

第1章緒論1

1.1問題求解與程式設計2

1.1.1程式設計的一般過程2

1.1.2數據結構在程式設計中的作用4

1.1.3算法在程式設計中的作用5

1.1.4本書討論的主要內容6

1.2數據結構的基本概念8

1.2.1數據結構8

1.2.2抽象數據類型11

1.3算法的基本概念12

1.3.1算法及算法的特性12

1.3.2算法的描述方法13

1.4算法分析15

1.4.1算法的時間複雜度15

1.4.2算法的空間複雜度17

1.4.3算法分析舉例17

1.5擴展與提高20

1.5.1從數據到大數據20

1.5.2算法分析的其他漸近符號22

1.6考研加油站23第2章線性表25

2.1引言26

2.2線性表的邏輯結構27

2.2.1線性表的定義27

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

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

2.3.1順序表的存儲結構定義29

2.3.2順序表的實現30

2.3.3順序表的使用34

2.4線性表的連結存儲結構及實現35

2.4.1單鍊表的存儲結構定義35

2.4.2單鍊表的實現37

2.4.3單鍊表的使用45

2.4.4雙鍊表46

2.4.5循環鍊表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一元多項式求和55

2.7考研加油站60第3章棧、佇列和數組63

3.1引言64

3.2棧65

3.2.1棧的邏輯結構65

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

3.2.3棧的連結存儲結構及實現69

3.2.4順序棧和鏈棧的比較72

3.3佇列72

3.3.1佇列的邏輯結構72

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

3.3.3佇列的連結存儲結構及實現77

3.3.4循環佇列和鏈佇列的比較81

3.4多維數組81

3.4.1數組的邏輯結構81

3.4.2數組的存儲結構與定址82

3.5矩陣的壓縮存儲83

3.5.1特殊矩陣的壓縮存儲83

3.5.2稀疏矩陣的壓縮存儲86

3.6擴展與提高88

3.6.1兩棧共享空間88

3.6.2雙端佇列89

3.6.3廣義表91

3.7套用實例94

3.7.1括弧匹配問題94

3.7.2表達式求值95

3.7.3八皇后問題99

3.8考研加油站102第4章樹和二叉樹105

4.1引言106

4.2樹的邏輯結構107

4.2.1樹的定義和基本術語107

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

4.2.3樹的遍歷操作109

4.3樹的存儲結構110

4.3.1雙親表示法110

4.3.2孩子表示法111

4.3.3孩子兄弟表示法112

4.4二叉樹的邏輯結構113

4.4.1二叉樹的定義113

4.4.2二叉樹的基本性質115

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

4.4.4二叉樹的遍歷操作117

4.5二叉樹的存儲結構119

4.5.1順序存儲結構119

4.5.2二叉鍊表120

4.5.3三叉鍊表124

4.6森林124

4.6.1森林的邏輯結構124

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

4.7最優二叉樹127

4.7.1哈夫曼算法127

4.7.2哈夫曼編碼129

4.8擴展與提高131

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

4.8.2線索二叉樹134

4.9套用實例138

4.9.1堆與優先佇列138

4.9.2並查集140

4.10考研加油站141第5章圖145

5.1引言146

5.2圖的邏輯結構147

5.2.1圖的定義和基本術語147

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

5.2.3圖的遍歷操作150

5.3圖的存儲結構及實現153

5.3.1鄰接矩陣153

5.3.2鄰接表156

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

5.4最小生成樹161

5.4.1Prim算法162

5.4.2Kruskal算法165

5.5最短路徑169

5.5.1Dijkstra算法169

5.5.2Floyd算法172

5.6有向無環圖及其套用174

5.6.1AOV網與拓撲排序174

5.6.2AOE網與關鍵路徑177

5.7擴展與提高179

5.7.1圖的其他存儲方法179

5.7.2圖的連通性181

5.8套用實例183

5.8.1七巧板塗色問題183

5.8.2醫院選址問題184

5.9考研加油站187第6章查找技術189

6.1概述190

6.1.1查找的基本概念190

6.1.2查找算法的性能191

6.2線性表的查找技術191

6.2.1順序查找191

6.2.2折半查找192

6.3樹表的查找技術195

6.3.1二叉查找樹195

6.3.2平衡二叉樹201

6.3.3B樹204

6.4散列表的查找技術208

6.4.1散列查找的基本思想208

6.4.2散列函式的設計210

6.4.3處理衝突的方法211

6.4.4散列查找的性能分析215

6.5字元串模式匹配216

6.5.1BF算法216

6.5.2KMP算法218

6.6擴展與提高220

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

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

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

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

6.6.5各種查找方法的比較228

6.7考研加油站228第7章排序技術231

7.1概述232

7.1.1排序的基本概念232

7.1.2排序算法的性能233

7.2插入排序233

7.2.1直接插入排序233

7.2.2希爾排序235

7.3交換排序237

7.3.1起泡排序237

7.3.2快速排序239

7.4選擇排序242

7.4.1簡單選擇排序242

7.4.2堆排序244

7.5歸併排序248

7.5.1二路歸併排序的遞歸實現248

7.5.2二路歸併排序的非遞歸實現249

7.6外部排序251

7.6.1外部排序的基本思想251

7.6.2置換—選擇排序252

7.6.3敗者樹254

7.7擴展與提高255

7.7.1排序問題的時間下界255

7.7.2基數排序256

7.7.3各種排序方法的比較258

7.8考研加油站260參考文獻263第1章緒論1

1.1問題求解與程式設計2

1.1.1程式設計的一般過程2

1.1.2數據結構在程式設計中的作用4

1.1.3算法在程式設計中的作用5

1.1.4本書討論的主要內容6

1.2數據結構的基本概念8

1.2.1數據結構8

1.2.2抽象數據類型11

1.3算法的基本概念12

1.3.1算法及算法的特性12

1.3.2算法的描述方法13

1.4算法分析15

1.4.1算法的時間複雜度15

1.4.2算法的空間複雜度17

1.4.3算法分析舉例17

1.5擴展與提高20

1.5.1從數據到大數據20

1.5.2算法分析的其他漸進符號22

1.6考研加油站23第2章線性表24

2.1引言25

2.2線性表的邏輯結構26

2.2.1線性表的定義26

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

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

2.3.1順序表的存儲結構定義28

2.3.2順序表的實現29

2.3.3順序表的使用33

2.4線性表的連結存儲結構及實現34

2.4.1單鍊表的存儲結構定義34

2.4.2單鍊表的實現36

2.4.3單鍊表的使用44

2.4.4雙鍊表45

2.4.5循環鍊表46

2.5擴展與提高47

2.5.1線性表的靜態鍊表存儲47

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

2.5.3順序表和鍊表的比較51

2.6套用實例52

2.6.1約瑟夫環問題52

2.6.2一元多項式求和54

2.7考研加油站59第3章棧、佇列和數組61

3.1引言62

3.2棧63

3.2.1棧的邏輯結構63

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

3.2.3棧的連結存儲結構及實現67

3.2.4順序棧和鏈棧的比較70

3.3佇列70

3.3.1佇列的邏輯結構70

3.3.2佇列的順序存儲結構及實現71

3.3.3佇列的連結存儲結構及實現75

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

3.4多維數組79

3.4.1數組的邏輯結構79

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

3.5矩陣的壓縮存儲81

3.5.1特殊矩陣的壓縮存儲81

3.5.2稀疏矩陣的壓縮存儲84

3.6擴展與提高86

3.6.1兩棧共享空間86

3.6.2雙端佇列87

3.6.3廣義表89

3.7套用舉例92

3.7.1括弧匹配問題92

3.7.2表達式求值93

3.7.3八皇后問題97

3.8考研加油站100第4章樹和二叉樹102

4.1引言103

4.2樹的邏輯結構104

4.2.1樹的定義和基本術語104

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

4.2.3樹的遍歷操作106

4.3樹的存儲結構107

4.3.1雙親表示法107

4.3.2孩子表示法108

4.3.3孩子兄弟表示法109

4.4二叉樹的邏輯結構110

4.4.1二叉樹的定義110

4.4.2二叉樹的基本性質112

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

4.4.4二叉樹的遍歷操作114

4.5二叉樹的存儲結構116

4.5.1順序存儲結構116

4.5.2二叉鍊表117

4.5.3三叉鍊表121

4.6森林121

4.6.1森林的邏輯結構121

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

4.7最優二叉樹124

4.7.1哈夫曼算法124

4.7.2哈夫曼編碼126

4.8擴展與提高128

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

4.8.2線索二叉樹131

4.9套用實例135

4.9.1堆與優先佇列135

4.9.2並查集137

4.10考研加油站138第5章圖141

5.1引言142

5.2圖的邏輯結構143

5.2.1圖的定義和基本術語143

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

5.2.3圖的遍歷操作146

5.3圖的存儲結構及實現149

5.3.1鄰接矩陣149

5.3.2鄰接表152

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

5.4最小生成樹157

5.4.1Prim算法158

5.4.3Kruskal算法161

5.5最短路徑165

5.5.1Dijkstra算法165

5.5.2Floyd算法168

5.6有向無環圖及其套用170

5.6.1AOV網與拓撲排序170

5.6.2AOE網與關鍵路徑173

5.7擴展與提高175

5.7.1圖的其他存儲方法175

5.7.2圖的連通性177

5.8套用實例179

5.8.1七巧板塗色問題179

5.8.2醫院選址問題180

5.9考研加油站183第6章查找技術185

6.1概述186

6.1.1查找的基本概念186

6.1.2查找算法的性能187

6.2線性表的查找技術187

6.2.1順序查找187

6.2.2折半查找188

6.3樹表的查找技術191

6.3.1二叉查找樹191

6.3.2平衡二叉樹197

6.3.3B樹200

6.4散列表的查找技術204

6.4.1散列查找的基本思想204

6.4.2散列函式的設計206

6.4.3處理衝突的方法207

6.4.4散列查找的性能分析211

6.5字元串模式匹配212

6.5.1BF算法212

6.5.2KMP算法214

6.6擴展與提高216

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

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

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

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

6.6.5各種查找方法的比較224

6.7考研加油站224第7章排序技術227

7.1概述228

7.1.1排序的基本概念228

7.1.2排序算法的性能229

7.2插入排序229

7.2.1直接插入排序229

7.2.2希爾排序231

7.3交換排序233

7.3.1起泡排序233

7.3.2快速排序235

7.4選擇排序238

7.4.1簡單選擇排序238

7.4.2堆排序240

7.5歸併排序244

7.5.1二路歸併排序的遞歸實現244

7.5.2二路歸併排序的非遞歸實現245

7.6外部排序247

7.6.1外部排序的基本思想247

7.6.2置換選擇排序248

7.6.3敗者樹250

7.7擴展與提高251

7.7.1排序問題的時間下界251

7.7.2基數排序252

7.7.3各種排序方法的比較254

7.8考研加油站256參考文獻258