數據結構教程（第二版）

《數據結構教程（第二版）》是2008年清華大學出版社出版的圖書。

基本介紹

• 書名：數據結構教程（第二版）
• ISBN：9787302142294
• 定價：36元
• 裝幀：平裝

出版信息

數據結構教程（第二版）

作者：李春葆
定價：36元
印次：2-4
ISBN：9787302142294
出版日期：2007.03.01
印刷日期：2008.06.24

圖書簡介

數據結構是計算機學科的必修課程。本教程是作者針對數據結構課程概念多、算法靈活和抽象性強的特點，在總結長期教學經驗的基礎上編寫而成的。全書分為14章，內容涵蓋數據結構基本概念、線性表、棧和佇列、串、數組和稀疏矩陣、遞歸、樹和二叉樹、廣義表、圖、查找、內排序、檔案和採用面向對象方法描述算法。每章後均附有練習題和上機實驗題。

本書在第1版的基礎上增加了線段樹、並查集等相關數據結構，全書內容豐富、層次清晰，講解深入淺出，可作為高等院校計算機及相關專業本科及研究生數據結構課程教材，也可供從事計算機軟體開發和套用的工程技術人員參考。

目錄

第1章 緒論 1

1.1 什麼是數據結構 1

1.1.1 數據結構的定義 1

1.1.2 邏輯結構類型 4

1.1.3 存儲結構類型 6

1.1.4 數據結構和數據類型 7

1.2 算法及其描述 11

1.2.1 什麼是算法 11

1.2.2 算法描述 12

1.3 算法分析 13

1.3.1 算法設計的目標 13

1.3.2 算法效率分析 14

1.3.3 算法存儲空間分析 17

1.4 數據結構+算法=程式 18

本章小結 24

練習題1 25

上機實驗題1 26

第2章 線性表 27

2.1 線性表及其邏輯結構 27

2.1.1 線性表的定義 27

2.1.2 線性表的抽象數據類型描述 28

2.2 線性表的順序存儲結構 29

2.2.1 線性表的順序存儲結構——順序表 29

2.2.2 順序表基本運算的實現 30

2.3 線性表的鏈式存儲結構 36

2.3.1 線性表的鏈式存儲結構——鍊表 37

2.3.2 單鍊表基本運算的實現 38

2.3.3 雙鍊表 45

2.3.4 循環鍊表 49

2.3.5 靜態鍊表 51

2.4 線性表的套用 56

2.4.1 問題描述 56

2.4.2 數據組織 57

2.4.3 設計運算算法 57

2.4.4 設計求解程式 59

2.4.5 運行結果 59

2.5 有序表 60

本章小結 64

練習題2 64

上機實驗題2 64

第3章 棧和佇列 67

3.1 棧 67

3.1.1棧的定義 67

3.1.2棧的順序存儲結構及其基本運算實現 69

3.1.3棧的鏈式存儲結構及其基本運算的實現 72

3.1.4棧的套用舉例 75

3.2佇列 84

3.2.1佇列的定義 84

3.2.2佇列的順序存儲結構及其基本運算的實現 85

3.2.3佇列的鏈式存儲結構及其基本運算的實現 89

3.2.4佇列的套用舉例 92

本章小結 97

練習題3 97

上機實驗題3 98

第4章串 101

4.1串的基本概念 101

4.2串的存儲結構 102

4.2.1串的順序存儲結構——順序串 102

4.2.2串的鏈式存儲結構——鏈串 108

4.3串的模式匹配 114

4.3.1Brute-Force算法 115

4.3.2KMP算法 117

本章小結 123

練習題4 123

上機實驗題4 124

第5章數組和稀疏矩陣 126

5.1數組 126

5.1.1數組的基本概念 126

5.1.2數組的存儲結構 127

5.1.3特殊矩陣的壓縮存儲 129

5.2稀疏矩陣 131

5.2.1稀疏矩陣的三元組表示 131

5.2.2稀疏矩陣的十字鍊表表示 136

本章小結 140

練習題5 140

上機實驗題5 140

第6章遞歸 142

6.1什麼是遞歸 142

6.1.1遞歸的定義 142

6.1.2何時使用遞歸 143

6.1.3遞歸模型 144

6.1.4遞歸與數學歸納法 145

6.2遞歸調用的實現原理 146

6.3遞歸算法的設計 148

6.3.1遞歸算法設計的步驟 148

6.3.2遞歸數據結構的遞歸算法設計 150

6.3.3遞歸求解方法的遞歸算法設計 151

6.4遞歸算法到非遞歸算法的轉換 153

6.4.1尾遞歸和單向遞歸的消除 153

6.4.2模擬系統運行時的棧消除遞歸 154

本章小結 163

練習題6 163

上機實驗題6 164

第7章樹和二叉樹 165

7.1樹的基本概念 165

7.1.1樹的定義 165

7.1.2樹的邏輯表示方法 166

7.1.3樹的基本術語 166

7.1.4樹的性質 168

7.1.5樹的基本運算 170

7.1.6樹的存儲結構 170

7.2二叉樹概念和性質 173

7.2.1二叉樹概念 173

7.2.2二叉樹性質 174

7.2.3二叉樹與樹、森林之間的轉換 175

7.3二叉樹存儲結構 177

7.3.1二叉樹的順序存儲結構 177

7.3.2二叉樹的鏈式存儲結構 179

7.4二叉樹的基本運算及其實現 180

7.4.1二叉樹的基本運算概述 180

7.4.2二叉樹的基本運算算法實現 180

7.5二叉樹的遍歷 183

7.5.1二叉樹遍歷的概念 183

7.5.2二叉樹遍歷遞歸算法 184

7.5.3二叉樹遍歷非遞歸算法 188

7.5.4層次遍歷算法 197

7.6二叉樹的構造 199

7.7線索二叉樹 205

7.7.1線索二叉樹的概念 205

7.7.2線索化二叉樹 206

7.7.3遍歷線索化二叉樹 208

7.8哈夫曼樹 209

7.8.1哈夫曼樹概述 209

7.8.2哈夫曼樹的構造算法 210

7.8.3哈夫曼編碼 212

7.9線段樹 214

7.9.1線段樹的定義 214

7.9.2線段樹的存儲結構 215

7.9.3線段樹基本運算的實現算法 215

7.10並查集 220

7.10.1什麼叫並查集 221

7.10.2並查集的算法實現 222

本章小結 225

練習題7 225

上機實驗題7 226

第8章廣義表 228

8.1廣義表的定義 228

8.2廣義表的存儲結構 230

8.3廣義表的運算 232

8.3.1求廣義表的長度 232

8.3.2求廣義表的深度 232

8.3.3建立廣義表的鏈式存儲結構 233

8.3.4輸出廣義表 234

8.3.5廣義表的複製 235

本章小結 240

練習題8 240

上機實驗題8 240

第9章圖 242

9.1圖的基本概念 242

9.1.1圖的定義 242

9.1.2圖的基本術語 243

9.2圖的存儲結構 245

9.2.1鄰接矩陣存儲方法 245

9.2.2鄰接表存儲方法 247

9.2.3十字鄰接表存儲方法 250

9.2.4鄰接多重表存儲方法 251

9.3圖的遍歷 252

9.3.1圖的遍歷的概念 252

9.3.2深度優先搜尋遍歷 252

9.3.3廣度優先搜尋遍歷 253

9.3.4非連通圖的遍歷 254

9.3.5圖遍歷算法的套用 255

9.4生成樹和最小生成樹 259

9.4.1生成樹的概念 259

9.4.2無向圖的連通分量和生成樹 260

9.4.3有向圖的強連通分量 261

9.4.4普里姆算法 262

9.4.5克魯斯卡爾算法 264

9.5最短路徑 268

9.5.1路徑的概念 268

9.5.2從一個頂點到其餘各頂點的最短路徑 268

9.5.3每對頂點之間的最短路徑 274

9.6拓撲排序 278

9.7AOE網與關鍵路徑 280

本章小結 285

練習題9 285

上機實驗題9 285

第10章查找 288

10.1查找的基本概念 288

10.2線性表的查找 289

10.2.1順序查找 289

10.2.2二分查找 290

10.2.3分塊查找 292

10.3樹表的查找 295

10.3.1二叉排序樹 295

10.3.2平衡二叉樹 303

10.3.3B-樹 320

10.3.4B+樹 331

10.3.52-3-4樹 333

10.3.6紅黑樹 335

10.4哈希表查找 338

10.4.1哈希表的基本概念 338

10.4.2哈希函式構造方法 339

10.4.3哈希衝突解決方法 340

10.4.4哈希表上的運算 343

本章小結 347

練習題10 347

上機實驗題10 347

第11章內排序 349

11.1排序的基本概念 349

11.2插入排序 350

11.2.1直接插入排序 350

11.2.2希爾排序 352

11.3交換排序 354

11.3.1冒泡排序 354

11.3.2快速排序 356

11.4選擇排序 360

11.4.1直接選擇排序 360

11.4.2堆排序 362

11.5歸併排序 365

11.6基數排序 369

11.7各種內排序方法的比較和選擇 371

本章小結 373

練習題11 373

上機實驗題11 374

第12章外排序 375

12.1外排序概述 375

12.2磁碟排序 376

12.2.1磁碟排序過程 376

12.2.2多路平衡歸併 377

12.2.3初始歸併段的生成 379

12.2.4最佳歸併樹 381

12.3磁帶排序 384

12.3.1多路平衡歸併排序 384

12.3.2多階段歸併排序 385

本章小結 386

練習題12 387

上機實驗題12 387

第13章檔案 388

13.1檔案的基本概念 388

13.1.1什麼是檔案 388

13.1.2檔案的邏輯結構及操作 389

13.1.3檔案的存儲結構 389

13.2順序檔案 390

13.3索引檔案 390

13.3.1ISAM檔案 391

13.3.2VSAM檔案 394

13.4哈希檔案 396

13.5多關鍵字檔案 397

13.5.1多重表檔案 397

13.5.2倒排檔案 398

本章小結 399

練習題13 399

上機實驗題13 400

第14章採用面向對象的方法描述算法 401

14.1面向對象的概念 401

14.1.1重要概念 401

14.1.2主要優點 402

14.2用C++描述面向對象的程式 403

14.2.1類 403

14.2.2類對象 405

14.2.3構造函式和析構函式 407

14.2.4派生類 410

14.3用C++描述數據結構算法 413

14.3.1順序表類 413

14.3.2鏈棧類 416

14.3.3二叉樹類 418

附錄A綜合實驗題 424

附錄B實驗報告格式 426

附錄C書中部分算法清單 427

參考文獻 430