數據結構（用面向對象方法與C++語言描述）第二版

《數據結構（用面向對象方法與C++語言描述）第二版》是2014年9月23日出版的一本書。

基本介紹

• 書名：數據結構（用面向對象方法與C++語言描述）第二版
• ISBN：9787302148111
• 定價：46元
• 出版社：清華大學出版社
• 出版時間：2014年9月23日
• 裝幀：平裝

圖書簡介

“數據結構”是計算機專業的核心課程，是從事計算機軟體開發和套用人員必備的專業基礎。隨著計算機的日益普及，“數據結構”課程也在不斷地發展。

本書按照清華大學計算機系本科“數據結構”大綱的要求，從面向對象的概念、對象類設計的風格和數據結構的層次開始,從線性結構到非線性結構，從簡單到復，深入地討論了各種數據結構內在的邏輯關係及其在計算機中的實現方式和使用。此外，對常用的疊代、遞歸、回溯等算法設計技巧，搜尋和排序算法等都做了詳盡的描述，並引入了簡單的算法分析。

目錄

第1章數據結構概論1

1.1數據結構的概念1

1.1.1數據結構舉例1

1.1.2數據與數據結構2

1.1.3數據結構的分類3

1.1.4數據結構課程的內容4

1.2數據結構的抽象形式6

1.2.1數據類型6

1.2.2數據抽象與抽象數據類型7

1.3作為ADT的C++類9

1.3.1面向對象的概念9

1.3.2C++中的類10

1.3.3C++中的對象12

1.3.4C++的輸入輸出13

1.3.5C++中的函式14

1.3.6動態存儲分配17

1.3.7C++中的繼承18

1.3.8多態性19

1.3.9C++的模板23

1.4算法定義24

1.5算法性能分析與度量26

1.5.1算法的性能標準26

1.5.2算法的後期測試26

1.5.3算法的事前估計27

1.5.4算法的漸進分析32

1.5.5最壞、最好和平均情況36

習題37

第2章線性表43

2.1線性表43

2.1.1線性表的概念43

2.1.2線性表的類定義44

2.2順序表45

2.2.1順序表的定義和特點45

2.2.2順序表的類定義及其操作45

2.2.3順序表的性能分析50

2.2.4順序表的套用52

2.3單鍊表52

2.3.1單鍊表的概念53

2.3.2單鍊表的類定義54

2.3.3單鍊表中的插入與刪除56

2.3.4帶附加頭結點的單鍊表59

2.3.5單鍊表的模板類60

2.4線性鍊表的其他變形66

2.4.1循環鍊表66

2.4.2雙向鍊表69

2.5單鍊表的套用：多項式及其運算73

2.5.1多項式的表示74

2.5.2多項式的類定義75

2.5.3多項式的加法77

2.5.4多項式的乘法79

2.6靜態鍊表80

習題83

第3章棧和佇列88

3.1棧88

3.1.1棧的定義88

3.1.2順序棧89

3.1.3鏈式棧92

3.1.4棧的套用之一——括弧匹配94

3.1.5棧的套用之二——表達式的計算95

3.2棧與遞歸101

3.2.1遞歸的概念101

3.2.2遞歸過程與遞歸工作棧105

3.2.3用回溯法求解迷宮問題109

3.3佇列114

3.3.1佇列的概念114

3.3.2循環佇列114

3.3.3鏈式佇列118

3.3.4佇列套用舉例：列印二項展開式(a+b)i的係數120

3.3.5佇列套用舉例：電路布線121

3.4優先權佇列124

3.4.1優先權佇列的概念124

3.4.2優先權佇列的存儲表示和實現125

3.5雙端佇列126

3.5.1雙端佇列的概念126

3.5.2雙端佇列的數組表示128

3.5.3雙端佇列的鍊表表示129

習題131

第4章數組、串與廣義表135

4.1多維數組的概念與存儲135

4.1.1多維數組的概念135

4.1.2多維數組的存儲表示136

4.2特殊矩陣138

4.2.1對稱矩陣的壓縮存儲138

4.2.2三對角線/多對角線矩陣的壓縮存儲140

4.3稀疏矩陣141

4.3.1稀疏矩陣及其三元組數組表示141

4.3.2稀疏矩陣的轉置145

4.3.3稀疏矩陣的相加和相乘147

4.3.4矩陣的正交鍊表表示152

4.4字元串153

4.4.1字元串的概念153

4.4.2C++有關字元串的庫函式154

4.4.3字元串的實現156

4.4.4字元串的自定義類158

4.4.5字元串操作的實現159

4.4.6字元串的模式匹配161

4.4.7字元串的存儲方法167

4.5廣義表169

4.5.1廣義表的定義與性質169

4.5.2廣義表的表示170

4.5.3廣義表存儲結構的實現170

4.5.4廣義表的遞歸算法174

4.5.5三元多項式的表示181

習題183

第5章樹186

5.1樹的基本概念186

5.1.1樹的定義和術語186

5.1.2樹的抽象數據類型188

5.2二叉樹189

5.2.1二叉樹的定義189

5.2.2二叉樹的性質190

5.2.3二叉樹的抽象數據類型191

5.3二叉樹的存儲表示192

5.3.1二叉樹的數組存儲表示192

5.3.2二叉樹的鍊表存儲表示193

5.4二叉樹遍歷及其套用198

5.4.1二叉樹遍歷的遞歸算法198

5.4.2二叉樹遍歷的套用200

5.4.3二叉樹遍歷的非遞歸算法203

5.4.4二叉樹的計數207

5.5線索二叉樹210

5.5.1線索210

5.5.2中序線索二叉樹的建立和遍歷211

5.5.3中序線索二叉樹的插入與刪除216

5.5.4前序與後序的線索化二叉樹218

5.6樹與森林220

5.6.1樹的存儲表示220

5.6.2森林與二叉樹的轉換225

5.6.3樹與二叉樹的轉換227

5.7樹與森林的遍歷及其套用227

5.7.1樹與森林的深度優先遍歷227

5.7.2樹和森林的廣度優先遍歷230

5.7.3樹遍歷算法的套用231

5.7.4其他基於遍歷序列的幾種存儲表示232

5.8堆235

5.8.1最小堆和最大堆235

5.8.2堆的建立236

5.8.3堆的插入與刪除238

5.9Huffman樹及其套用240

5.9.1路徑長度240

5.9.2Huffman樹241

5.9.3Huffman樹的套用：最優判定樹243

5.9.4Huffman樹的套用：Huffman編碼244

習題246

第6章集合與字典251

6.1集合及其表示251

6.1.1集合的基本概念251

6.1.2用位向量實現集合抽象數據類型252

6.1.3用有序鍊表實現集合的抽象數據類型257

6.2並查集與等價類262

6.2.1並查集的定義及其實現262

6.2.2並查集的套用：等價類劃分267

6.3字典268

6.3.1字典的概念269

6.3.2字典的線性表描述270

6.4跳表273

6.4.1跳表的概念273

6.4.2跳表的類定義274

6.4.3跳表的搜尋、插入和刪除276

6.5散列279

6.5.1散列表與散列方法279

6.5.2散列函式280

6.5.3處理衝突的閉散列方法282

6.5.4處理衝突的開散列方法291

6.5.5散列表分析293

習題294

第7章搜尋結構297

7.1靜態搜尋結構298

7.1.1靜態搜尋表298

7.1.2順序搜尋300

7.1.3基於有序順序表的順序搜尋和折半搜尋302

7.1.4基於有序順序表的其他搜尋方法307

7.2二叉搜尋樹308

7.2.1二叉搜尋樹的概念309

7.2.2二叉搜尋樹上的搜尋310

7.2.3二叉搜尋樹的插入311

7.2.4二叉搜尋樹的刪除313

7.2.5二叉搜尋樹的性能分析314

7.2.6最優二叉搜尋樹317

7.3AVL樹320

7.3.1AVL樹的概念321

7.3.2平衡化旋轉321

7.3.3AVL樹的插入326

7.3.4AVL樹的刪除329

7.3.5AVL樹的性能分析333

7.4伸展樹334

7.5紅黑樹337

7.5.1紅黑樹的概念和性質337

7.5.2紅黑樹的搜尋338

7.5.3紅黑樹的插入338

7.5.4紅黑樹的刪除339

習題342

第8章圖346

8.1圖的基本概念346

8.1.1與圖有關的若干概念346

8.1.2圖的抽象數據類型348

8.2圖的存儲結構349

8.2.1圖的鄰接矩陣表示350

8.2.2圖的鄰接表表示355

8.2.3圖的鄰接多重表表示361

8.3圖的遍歷363

8.3.1深度優先搜尋364

8.3.2廣度優先搜尋365

8.3.3連通分量366

8.3.4重連通分量368

8.4最小生成樹370

8.4.1Kruskal算法371

8.4.2Prim算法373

8.5最短路徑375

8.5.1非負權值的單源最短路徑376

8.5.2任意權值的單源最短路徑379

8.5.3所有頂點之間的最短路徑381

8.6用頂點表示活動的網路（AOV網路）383

8.7用邊表示活動的網路（AOE網路）388

習題392

第9章排序397

9.1排序的概念及其算法性能分析397

9.1.1排序的概念397

9.1.2排序算法的性能評估398

9.1.3排序表的類定義400

9.2插入排序401

9.2.1直接插入排序401

9.2.2折半插入排序403

9.2.3希爾排序404

9.3快速排序405

9.3.1快速排序的過程406

9.3.2快速排序的性能分析407

9.3.3快速排序的改進算法409

9.3.4三路劃分的快速排序算法412

9.4選擇排序413

9.4.1直接選擇排序413

9.4.2錦標賽排序414

9.4.3堆排序419

9.5歸併排序422

9.5.1歸併422

9.5.2歸併排序算法423

9.6基於鍊表的排序算法425

9.6.1鍊表插入排序425

9.6.2鍊表歸併排序427

9.6.3鍊表排序結果的重排428

9.7分配排序431

9.7.1桶式排序431

9.7.2基數排序432

9.7.3MSD基數排序433

9.7.4LSD基數排序435

9.8內部排序算法的分析437

9.8.1排序方法的下界437

9.8.2各種內部排序方法的比較439

習題440

第10章檔案、外部排序與搜尋444

10.1主存儲器和外存儲器444

10.1.1磁帶444

10.1.2磁碟存儲器446

10.1.3緩衝區與緩衝池448

10.2檔案組織449

10.2.1檔案的概念449

10.2.2檔案的存儲結構450

10.3外排序459

10.3.1外排序的基本過程459

10.3.2k路平衡歸併與敗者樹461

10.3.3初始歸併段的生成（rungeneration）466

10.3.4並行操作的緩衝區處理470

10.3.5最佳歸併樹473

10.4多級索引結構475

10.4.1靜態的ISAM方法475

10.4.2動態的m路搜尋樹476

10.4.3B樹478

10.4.4B樹的插入480

10.4.5B樹的刪除482

10.4.6B+樹486

10.4.7VSAM489

10.5可擴充散列490

10.5.1二叉Trie樹490

10.5.2將二叉Trie樹轉換為目錄表491

10.5.3目錄表擴充與收縮493

10.5.4性能分析494

10.6Trie樹494

10.6.1Trie樹的定義494

10.6.2Trie樹的搜尋495

10.6.3在Trie樹上的插入和刪除496

習題497

附錄A程式索引500

附錄B辭彙索引504

參考文獻512