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

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

基本介紹

• 中文名：數據結構——從概念到C++實現（第3版）
• 作者：王紅梅、王慧、王新穎 
• 出版社：清華大學出版社
• 出版時間：2019年05月01日
• 定價：45 元 
• ISBN：9787302505761 

內容簡介

數據結構是計算機及相關專業的核心課程，也是計算機及相關專業碩士研究生入學考試的必考科目，而且是理工專業的熱門公選課程。本書介紹數據結構、算法以及抽象數據類型的概念；介紹線性表、棧和佇列、字元串和多維數組、樹和二叉樹、圖等常用數據結構；討論查找和排序技術。本書合理規劃教學內容，梳理知識單元及其拓撲結構，兼顧概念層和實現層，既強調數據結構的基本概念和原理方法，又注重數據結構的程式實現和實際運用，在提煉基礎知識的同時，進行適當的擴展和提高。 本書內容豐富，層次清晰，深入淺出，結合實例，可作為高等學校計算機及相關專業數據結構課程的教材，也可供從事計算機軟體開發和套用的工程技術人員參考和閱讀。

目錄

第1章 緒論 1

1.1問題求解與程式設計2

1.1.1程式設計的一般過程2

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

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

1.1.4本書討論的主要內容7

1.2數據結構的基本概念9

1.2.1數據結構9

1.2.2抽象數據類型11

1.3算法的基本概念13

1.3.1算法及算法的特性13

1.3.2算法的描述方法14

1.4算法分析16

1.4.1算法的時間複雜度16

1.4.2算法的空間複雜度18

1.4.3算法分析舉例18

1.5 擴展與提高21

1.5.1從數據到大數據21

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

思想火花——機率算法23

習題1 24

第2章 線性表 27

2.1引言28

2.2線性表的邏輯結構 29

2.2.1線性表的定義 29

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

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

2.3.1順序表的存儲結構31

2.3.2順序表的實現32

2.3.3順序表的使用37

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

2.4.1單鍊表的存儲結構38

2.4.2單鍊表的實現40

2.4.3單鍊表的使用48

2.4.4雙鍊表49

2.4.5循環鍊表50

2.5順序表和鍊表的比較51

2.6擴展與提高52

2.6.1線性表的靜態鍊表存儲52

2.6.2順序表的動態分配方式54

2.7套用實例56

2.7.1約瑟夫環問題56

2.7.2一元多項式求和59

思想火花——好算法是反覆努力和重新修...

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

習題2 64

實驗題2 67

第3章 棧和佇列 69

3.1引言70

3.2棧71

3.2.1棧的邏輯結構71

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

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

3.2.4順序棧和鏈棧的比較77

3.3 佇列 78

3.3.1佇列的邏輯結構78

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

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

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

3.4擴展與提高86

3.4.1兩棧共享空間86

3.4.2雙端佇列88

3.5套用舉例89

3.5.1括弧匹配問題89

3.5.2表達式求值91

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

習題3 95

實驗題3 97

第4章字元串和多維數組99

4.1引言100

4.2字元串101

4.2.1字元串的邏輯結構101

4.2.2字元串的存儲結構103

4.2.3模式匹配103

4.3多維數組107

4.3.1數組的邏輯結構107

4.3.2數組的存儲結構與定址108

4.4矩陣的壓縮存儲109

4.4.1特殊矩陣的壓縮存儲109

4.4.2稀疏矩陣的壓縮存儲112

4.5擴展與提高114

4.5.1稀疏矩陣的轉置運算114

4.5.2廣義表116

4.6套用實例119

4.6.1發紙牌119

4.6.2八皇后問題121

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

習題4 124

實驗題4 126

第5章 樹和二叉樹 127

5.1引言128

5.2樹的邏輯結構129

5.2.1樹的定義和基本術語129

5.2.2樹的抽象數據類型定義131

5.2.3樹的遍歷操作131

5.3樹的存儲結構132

5.3.1雙親表示法132

5.3.2孩子表示法132

5.3.3孩子兄弟表示法133

5.4二叉樹的邏輯結構134

5.4.1二叉樹的定義134

5.4.2二叉樹的基本性質136

5.4.3二叉樹的抽象數據類型定義138

5.4.4二叉樹的遍歷操作139

5.5二叉樹的存儲結構140

5.5.1順序存儲結構140

5.5.2二叉鍊表141

5.5.3三叉鍊表146

5.6森林147

5.6.1森林的邏輯結構147

5.6.2樹、森林與二叉樹的轉換147

5.7最優二叉樹149

5.7.1哈夫曼算法149

5.7.2哈夫曼編碼152

5.8擴展與提高153

5.8.1二叉樹遍歷的非遞歸算法153

5.8.2線索鍊表157

5.9套用實例161

5.9.1堆與優先佇列161

5.9.2並查集164

思想火花——調試程式與魔術表演166

習題5 167

實驗題5 169

第6章 圖 171

6.1引言172

6.2圖的邏輯結構173

6.2.1圖的定義和基本術語173

6.2.2圖的抽象數據類型定義176

6.2.3圖的遍歷操作176

6.3圖的存儲結構及實現179

6.3.1鄰接矩陣179

6.3.2鄰接表182

6.3.3鄰接矩陣和鄰接表的比較187

6.4最小生成樹188

6.4.1Prim算法189

6.4.2Kruskal算法191

6.5最短路徑195

6.5.1Dijkstra算法196

6.5.2Floyd算法199

6.6有向無環圖及其套用200

6.6.1AOV網與拓撲排序201

6.6.2AOE網與關鍵路徑203

6.7擴展與提高206

6.7.1圖的其他存儲方法206

6.7.2圖的連通性208

6.8套用實例209

6.8.1七巧板塗色問題209

6.8.2醫院選址問題211

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

習題6 214

實驗題6 218

第7章 查找技術 219

7.1概述220

7.1.1查找的基本概念220

7.1.2查找算法的性能221

7.2線性表的查找技術221

7.2.1線性表查找結構的類定義221

7.2.2順序查找222

7.2.3折半查找223

7.3樹表的查找技術226

7.3.1二叉排序樹226

7.3.2平衡二叉樹231

7.3.3B樹235

7.4散列表的查找技術239

7.4.1散列查找的基本思想239

7.4.2散列函式的設計241

7.4.3處理衝突的方法242

7.4.4散列查找的性能分析246

7.4.5開散列表與閉散列表的比較247

7.5各種查找方法的比較247

7.6擴展與提高248

7.6.1順序查找的改進——分塊查找248

7.6.2折半查找的改進——插值查找249

7.6.3B樹的改進——B+樹250

思想火花——把注意力集中於主要因素，不要糾纏於噪聲251

習題7251

實驗題7254

第8章排序技術255

8.1概述256

8.1.1排序的基本概念256

8.1.2排序算法的性能257

8.1.3排序類的定義257

8.2插入排序258

8.2.1直接插入排序258

8.2.2希爾排序260

8.3交換排序262

8.3.1起泡排序262

8.3.2快速排序264

8.4選擇排序267

8.4.1簡單選擇排序267

8.4.2堆排序269

8.5歸併排序274

8.5.1二路歸併排序的遞歸實現274

8.5.2二路歸併排序的非遞歸實現275

8.6各種排序方法的比較277

8.6.1 各種排序技術的使用範例277

8.6.2各種排序方法的綜合比較278

8.7擴展與提高280

8.7.1排序問題的時間下界280

8.7.2基數排序281

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

習題8 284

實驗題8 286

附錄A 預備知識 289

附錄B C++語言基本語法 293

附錄C 辭彙索引 307

參考文獻 311