數據結構--從概念到Java實現

《數據結構--從概念到Java實現》是2019年3月清華大學出版社出版的圖書，作者是王紅梅、黨源源、劉冰。

基本介紹

• 中文名：數據結構--從概念到Java實現
• 作者：王紅梅、黨源源、劉冰
• 出版社：清華大學出版社
• 出版時間：2019年3月
• 定價：49 元
• ISBN：9787302513407

內容簡介

數據結構是計算機及相關專業的核心課程，也是計算機及相關專業碩士研究生入學考試的必考科目，而且是理工專業的熱門公選課程。本書介紹了數據結構、算法以及抽象數據類型的概念，講述了線性表、棧和佇列、字元串和多維數組、樹和二叉樹、圖等常用數據結構，討論了查找和排序技術。本書通過合理規劃教學內容，梳理了知識單元及其拓撲結構，併兼顧概念層和實現層，既強調數據結構的基本概念和原理及方法，又注重數據結構的程式實現和實際運用，在提煉基礎知識的同時，進行了適當的擴展和提高。

本書內容豐富，層次清晰，深入淺出且結合了實例，可作為計算機及相關專業數據結構課程的教材，也可供從事計算機軟體開發和套用的工程技術人員參考和閱讀。

圖書目錄

第1章緒論1

1.1問題求解與程式設計2

1.1.1程式設計的一般過程2

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

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

1.1.4本書討論的主要內容7

1.2數據結構的基本概念8

1.2.1數據結構8

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

習題24

第2章線性表27

2.1引言28

2.2線性表的邏輯結構29

2.2.1線性表的定義29數據結構——從概念到Java實現2.2.2線性表的抽象數據類型29

2.2.3線性表的Java接口定義31

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

2.3.1順序表的存儲結構31

2.3.2順序表的實現32

2.3.3順序表的使用37

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

2.4.1單鍊表的存儲結構39

2.4.2單鍊表的實現41

2.4.3單鍊表的使用47

2.4.4雙鍊表48

2.4.5循環鍊表50

2.5順序表和鍊表的比較51

2.6擴展與提高52

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

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

2.7套用實例55

2.7.1約瑟夫環問題55

2.7.2一元多項式求和57

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

習題62

實驗題65

第3章棧和佇列67

3.1引言68

3.2棧69

3.2.1棧的邏輯結構69

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

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

3.2.4順序棧和鏈棧的比較76

3.3佇列76

3.3.1佇列的邏輯結構76

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

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

3.3.4循環佇列與鏈佇列的比較85

3.4擴展與提高85

3.4.1兩棧共享空間85

3.4.2雙端佇列87

3.5套用舉例88

3.5.1括弧匹配問題88

3.5.2表達式求值89

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

習題93

實驗題95

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

4.1引言98

4.2字元串99

4.2.1字元串的邏輯結構99

4.2.2字元串的存儲結構101

4.2.3模式匹配101

4.3多維數組105

4.3.1數組的邏輯結構105

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

4.4矩陣的壓縮存儲107

4.4.1特殊矩陣的壓縮存儲107

4.4.2稀疏矩陣的壓縮存儲110

4.5擴展與提高112

4.5.1稀疏矩陣的轉置運算112

4.5.2廣義表114

4.6套用實例118

4.6.1發紙牌118

4.6.2八皇后問題119

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

習題121

實驗題123

第5章樹和二叉樹125

5.1引言126

5.2樹的邏輯結構127

5.2.1樹的定義和基本術語127

5.2.2樹的抽象數據類型128

5.2.3樹的遍歷操作定義129

5.3樹的存儲結構130

5.3.1雙親表示法130

5.3.2孩子表示法131

5.3.3孩子兄弟表示法131

5.4二叉樹的邏輯結構133

5.4.1二叉樹的定義133

5.4.2二叉樹的基本性質134

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

5.4.4二叉樹的遍歷操作定義137

5.4.5二叉樹的Java接口定義139

5.5二叉樹的存儲結構及實現139

5.5.1順序存儲結構139

5.5.2二叉鍊表140

5.5.3三叉鍊表145

5.6森林146

5.6.1森林的邏輯結構146

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

5.7最優二叉樹149

5.7.1哈夫曼算法149

5.7.2哈夫曼編碼152

5.8擴展與提高154

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

5.8.2線索二叉樹157

5.9套用實例161

5.9.1堆與優先佇列161

5.9.2並查集165

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

習題168

實驗題169

第6章圖171

6.1引言172

6.2圖的邏輯結構173

6.2.1圖的定義和基本術語173

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

6.2.3圖的遍歷操作176

6.2.4圖的Java接口定義178

6.3圖的存儲結構及實現179

6.3.1鄰接矩陣179

6.3.2鄰接表183

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

6.4最小生成樹188

6.4.1Prim算法189

6.4.2Kruskal算法192

6.5最短路徑196

6.5.1Dijkstra算法196

6.5.2Floyd算法199

6.6有向無環圖及其套用201

6.6.1AOV網與拓撲排序201

6.6.2AOE網與關鍵路徑204

6.7擴展與提高206

6.7.1圖的其他存儲方法206

6.7.2圖的連通性208

6.8套用實例210

6.8.1七巧板塗色問題210

6.8.2醫院選址問題211

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

習題214

實驗題217

第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折半查找222

7.3樹表的查找技術225

7.3.1二叉排序樹225

7.3.2平衡二叉樹231

7.3.3B樹235

7.4散列表的查找技術239

7.4.1散列查找的基本思想239

7.4.2散列函式的設計240

7.4.3處理衝突的方法242

7.4.4散列查找的性能分析245

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

7.5各種查找方法的比較247

7.6擴展與提高247

7.6.1順序查找的改進——分塊查找247

7.6.2折半查找的改進——插值查找248

7.6.3B樹的改進——B+樹249

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

習題251

實驗題253

第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交換排序261

8.3.1起泡排序261

8.3.2快速排序263

8.4選擇排序266

8.4.1簡單選擇排序266

8.4.2堆排序268

8.5歸併排序273

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

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

8.6各種排序技術的使用277

8.7各種排序方法的比較277

8.8擴展與提高279

8.8.1排序問題的時間下界279

8.8.2基數排序280

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

習題284

實驗題286

附錄A預備知識289

A.1數學術語289

A.2級數求和289

A.3集合290

A.4關係291

附錄BJava語言基本語法293

B.1程式檔案結構293

B.2數據類型294

B.3Java編程規範295

B.4控制語句295

B.5函式296

B.6類與對象297

B.7接口298

B.8異常處理299

附錄C中英文辭彙對照表301

參考文獻305