數據結構基礎（C++語言版）第2版

《數據結構基礎（C++語言版）第2版》是2009年3月清華大學出版社出版的圖書，作者是Ellis Horowitz、Sartaj Sahni、Dinesh Mehta。

基本介紹

• 書名：數據結構基礎（C++語言版）第2版
• 作者：Ellis Horowitz、Sartaj Sahni、Dinesh Mehta
• ISBN：9787302187035
• 定價：49元
• 出版社：清華大學出版社
• 出版時間：2009.03.01

內容簡介

本書用C++作為描述語言，全面而生動地介紹了數據結構的有關知識，如數組、棧、佇列、鍊表、樹和圖，以及構成所有軟體基礎的排序散列技術。此外，本書還介紹了各種高級或特殊數據結構，如優先權佇列、高效二叉查找樹、多路查找樹等。本書對大多數算法都給出了計算時間在最優、最差情形下的複雜度分析。本書的更新版已涵蓋了C++語言的最新特性。

本書不僅可以作為計算機及相關專業本科生“數據結構”課程的教材，也可以作為研究生第一學年的“高等數據結構”課程的教材，同時，本書所介紹的各種算法的C++語言實現，對有關專業人員也具有很好的參考價值。

作者簡介

EllisHorowitz，是南加州大學計算機與電子工程系的教授。Horowitz博士已編著了10多本教材，並發表了大量學術論文。

SartajSahni，是佛羅里達大學計算機與信息科學系的傑出教授和講座教授。Sahni博士已發表300多篇學術研究論文，編著了15本教材。

DineshMehta，是科羅拉多礦業大學教授，數學與計算機科學系的副主任。Mehta博士已發表30多篇期刊和會議論文。

圖書目錄

第1章基本概念1

1.1概述：系統生命周期1

1.2面向對象的程式設計3

1.2.1算法分解與面向對象分解3

1.2.2基本定義和面向對象編程的概念3

1.2.3程式設計語言的演化和C++語言歷史4

1.3數據抽象和封裝4

1.4C++語言基礎8

1.4.1C++程式的組織結構8

1.4.2C++語言的作用域9

1.4.3C++的語句與操作符10

1.4.4C++語言中的數據聲明10

1.4.5C++語言的注釋11

1.4.6C++語言的輸入輸出11

1.4.7C++語言的函式13

1.4.8C++語言的參數傳遞13

1.4.9C++語言的函式名重載14

1.4.10內聯函式14

1.4.11C++語言的動態記憶體分配15

1.4.12例外15

1.5算法規範17

1.5.1概述17

1.5.2遞歸算法20

1.6標準模板庫24

1.7性能分析和度量27

1.7.1性能分析28

1.7.2性能度量45

1.7.3測試數據的生成50

1.8參考文獻和推薦讀物54第2章數組55

2.1抽象數據類型和C++類55

2.1.1C++類介紹55

2.1.2C++語言中的數據抽象和封裝56

2.1.3聲明類對象和調用成員函式56

2.1.4特別類操作57

2.1.5其他主題60

2.1.6ADT和C++類60

2.2將數組作為一種抽象數據類型62

2.3多項式抽象數據類型64

2.3.1多項式的表示65

2.3.2多項式的加法67

2.4稀疏矩陣71

2.4.1緒論71

2.4.2稀疏矩陣的表示法72

2.4.3轉置一個矩陣73

2.4.4矩陣的乘法76

2.5多維數組的表示81

2.6字元串抽象數據類型84

2.6.1一種簡單的字元串模式匹配算法85

2.6.2字元串模式匹配：Knuth-Morris-Pratt算法85

2.7參考文獻和推薦讀物89

2.8附加習題89數據結構基礎（C++語言版）（第2版）目錄第3章棧和佇列94

3.1C++模板94

3.1.1模板函式94

3.1.2用模板表示容器類96

3.2棧的抽象數據類型99

3.3佇列抽象數據類型103

3.4C++中的子類型和繼承109

3.5一個迷宮問題112

3.6計算表達式116

3.6.1表達式116

3.6.2後綴表達式118

3.6.3中綴表達式轉換成後綴表達式119

3.7附加習題122第4章鍊表124

4.1單鍊表和鏈124

4.2用C++語言表示鍊表126

4.2.1在C++語言中定義結點126

4.2.2用C++語言設計一個鍊表類127

4.2.3C++語言中的指針操作130

4.2.4鍊表的控制操作131

4.3鏈的模板類134

4.3.1用模板實現鍊表134

4.3.2鍊表疊代器135

4.3.3鍊表操作138

4.3.4類的重用140

4.4循環鍊表141

4.5可用空間鍊表143

4.6鏈式棧和鏈式佇列144

4.7多項式146

4.7.1多項式的表示146

4.7.2多項式相加147

4.7.3用循環鍊表表示多項式150

4.8等價類152

4.9稀疏矩陣157

4.9.1稀疏矩陣的表示157

4.9.2稀疏矩陣的輸入159

4.9.3刪除稀疏矩陣160

4.10雙向鍊表162

4.11廣義表165

4.11.1廣義表的表示165

4.11.2表的遞歸算法168

4.11.3引用計數、共享和遞歸表171第5章樹176

5.1概述176

5.1.1術語表176

5.1.2樹的表示178

5.2二叉樹180

5.2.1抽象數據類型180

5.2.2二叉樹的性質181

5.2.3二叉樹的表示183

5.3二叉樹的遍歷和疊代程式185

5.3.1概述185

5.3.2中序遍歷185

5.3.3先序遍歷187

5.3.4後序遍歷187

5.3.5疊代中序遍歷188

5.3.6層次遍歷190

5.3.7不使用棧的遍歷191

5.4補充的二叉樹操作193

5.4.1複製二叉樹193

5.4.2檢測相等193

5.4.3滿足性問題194

5.5線索二叉樹196

5.5.1線索196

5.5.2線索二叉樹的中序遍歷197

5.5.3線上索二叉樹上插入一個結點198

5.6堆200

5.6.1優先佇列200

5.6.2大頂堆的定義201

5.6.3大頂堆的插入202

5.6.4大頂堆的刪除203

5.7二叉查找樹205

5.7.1定義205

5.7.2二叉查找樹的查找206

5.7.3二叉查找樹的插入208

5.7.4二叉查找樹的刪除209

5.7.5二叉樹的連線和分裂210

5.7.6二叉查找樹的高度212

5.8選擇樹213

5.8.1概述213

5.8.2勝者樹213

5.8.3敗者樹214

5.9森林215

5.9.1將森林轉換成二叉樹215

5.9.2森林的遍歷216

5.10離散集合表示217

5.10.1概述217

5.10.2並和查找操作217

5.10.3等價類的套用223

5.11二叉樹計數225

5.11.1不同的二叉樹225

5.11.2棧排列226

5.11.3矩陣相乘227

5.11.4不同二叉樹的個數228

5.12參考文獻和推薦讀物229第6章圖230

6.1圖的抽象數據類型230

6.1.1概述230

6.1.2定義231

6.1.3圖的表示234

6.2圖的基本操作240

6.2.1深度優先搜尋240

6.2.2廣度優先搜尋241

6.2.3連通分量242

6.2.4生成樹243

6.2.5重連通分量244

6.3最小代價生成樹248

6.3.1克魯斯卡爾算法248

6.3.2普里姆算法251

6.3.3索林算法252

6.4最短路徑和傳遞閉包253

6.4.1單源/多目標：非負權值253

6.4.2單源/多目標：任意權值257

6.4.3多源最短路徑259

6.4.4傳遞閉包260

6.5活動網路263

6.5.1頂點表示活動的網路（AOV網）263

6.5.2用邊表示活動的網路（AOE網）267

6.5.3事件最早發生時間的計算269

6.5.4事件最遲發生時間的計算269

6.6參考文獻和推薦讀物272

6.7附加習題273第7章排序275

7.1目的275

7.2插入排序278

7.3快速排序280

7.4排序算法能夠多快283

7.5歸併排序284

7.5.1歸併284

7.5.2疊代歸併285

7.5.3遞歸歸併287

7.6堆排序289

7.7多關鍵字排序292

7.8鏈和列表排序295

7.9內部排序總結302

7.10外部排序306

7.10.1概述306

7.10.2k路歸併308

7.10.3並行操作的快取處理309

7.10.4順串產生313

7.10.5順串的最佳歸併315

7.11參考文獻和推薦讀物318第8章散列319

8.1緒論319

8.2靜態散列319

8.2.1哈希表319

8.2.2哈希函式320

8.2.3安全哈希函式323

8.2.4溢出處理325

8.2.5溢出技術的理論分析329

8.3動態散列331

8.3.1動態散列的目的331

8.3.2使用目錄的動態散列332

8.3.3不使用目錄的動態散列334

8.4布隆過濾器335

8.4.1勘誤檔案的套用335

8.4.2設計布隆過濾器337

8.5參考文獻和推薦讀物338第9章優先佇列340

9.1單端和雙端優先佇列340

9.2左偏樹342

9.2.1高度左偏樹342

9.2.2重量左偏樹346

9.3二項式堆349

9.3.1代價分攤349

9.3.2二項式堆的定義350

9.3.3二項式堆的插入操作351

9.3.4合併兩個二項式堆352

9.3.5刪除最小元素352

9.3.6分析354

9.4斐波那契堆356

9.4.1定義356

9.4.2從斐波那契堆中刪除元素356

9.4.3減小鍵值357

9.4.4級聯剪下357

9.4.5分析358

9.4.6在最短路徑問題上的套用360

9.5配對堆361

9.5.1定義361

9.5.2合併和插入操作362

9.5.3減小鍵值363

9.5.4刪除最小元素363

9.5.5刪除任意元素365

9.5.6實現問題365

9.5.7複雜度366

9.6對稱最小-最大堆366

9.6.1定義及性質366

9.6.2SMMH的表示367

9.6.3插入操作368

9.6.4刪除操作371

9.7區間堆373

9.7.1定義及性質373

9.7.2區間堆的插入操作374

9.7.3刪除最小元素376

9.7.4初始化區間堆377

9.7.5區間堆操作的複雜度377

9.7.6互補範圍搜尋問題377

9.8參考文獻和推薦讀物379第10章高效二叉查找樹382

10.1最優二叉查找樹382

10.2AVL樹388

10.3紅黑樹398

10.3.1定義398

10.3.2紅黑樹的表示399

10.3.3查找400

10.3.4插入400

10.3.5刪除403

10.3.6紅黑樹的合併403

10.3.7紅黑樹的分裂404

10.4伸展樹406

10.4.1自底向上的伸展樹406

10.4.2自頂向下的伸展樹409

10.5參考文獻和推薦讀物413第11章多路查找樹415

11.1m路查找樹415

11.1.1定義和性質415

11.1.2對m路查找樹進行查找416

11.2B-樹417

11.2.1定義和性質417

11.2.2B-樹的元素個數417

11.2.3插入418

11.2.4刪除420

11.3B+樹427

11.3.1定義427

11.3.2查找428

11.3.3插入428

11.3.4刪除429

11.4參考文獻和推薦讀物433第12章數字查找結構434

12.1數字查找樹434

12.1.1定義434

12.1.2查找、插入和刪除434

12.2二叉Trie樹和Patricia樹435

12.2.1二叉Trie樹435

12.2.2壓縮二叉Trie樹436

12.2.3Patricia樹436

12.3多路Trie樹440

12.3.1定義440

12.3.2查找Trie樹442

12.3.3抽樣策略442

12.3.4插入Trie樹444

12.3.5從Trie樹中刪除444

12.3.6不同長度的關鍵字444

12.3.7Trie樹的高度445

12.3.8空間需求與其他結點結構445

12.3.9前綴查找和套用448

12.3.10壓縮Trie樹449

12.3.11帶跳過欄位的壓縮Trie樹451

12.3.12帶標號邊的壓縮Trie樹452

12.3.13壓縮Trie樹需要的空間453

12.4後綴樹454

12.4.1你是否見過這個字元串454

12.4.2後綴樹數據結構455

12.4.3查找子串(查找後綴樹)457

12.4.4後綴樹上的其他技巧458

12.5Trie樹和Internet包轉發460

12.5.1IP路由460

12.5.21-比特Trie樹460

12.5.3固定跨度Trie樹461

12.5.4可變跨度Trie樹463

12.6參考文獻和推薦讀物465術語表466

ⅩVII