實用數據結構（C++描述）（第二版）

成書過程

該教材由徐士良、葛兵編著。2006年10月1日，該教材由清華大學出版社出版。

出版社工作人員

組稿編輯	文稿編輯
焦虹	張為民

內容簡介

該教材介紹了數據處理領域中常用的數據結構及其主要的運算，所有的算法均給出了C++的描述。全書共8章，主要內容包括：數據結構與算法的基本概念、線性表及其順序存儲結構、線性鍊表及其運算、數組、樹與二叉樹、圖、查找技術、Hash表技術、排序技術。每章後面都有習題。

教材目錄

第1章緒論

1.1數據結構的基本概念1

1.1.1兩個例子1

1.1.2什麼是數據結構4

1.1.3數據結構的圖形表示7

1.1.4線性數據結構與非線性數據結構8

1.2算法方面的考慮9

1.2.1什麼是算法9

1.2.2算法的複雜度10

習題12

第2章線性表及其順序存儲結構

2.1線性表的基本概念14

2.1.1什麼是線性表14

2.1.2線性表的順序存儲結構——順序表15

2.1.3順序表的基本運算——插入與刪除16

2.1.4順序表類20

2.2棧及其套用24

2.2.1什麼是棧24

2.2.2棧的順序存儲及其運算26

2.2.3順序棧類28

2.2.4表達式的計算31

2.3佇列及其套用37

2.3.1什麼是佇列37

2.3.2循環佇列及其運算37

2.3.3循環佇列類40

2.3.4佇列的套用44

2.4字元串49

2.4.1字元串的基本概念49

2.4.2字元串匹配50

習題55

第3章線性鍊表

3.1線性鍊表的基本概念57

3.1.1線性表順序存儲的問題57

3.1.2線性鍊表的存儲結構58

3.1.3線性鍊表類62

3.1.4帶鏈的棧65

3.1.5帶鏈的佇列68

3.2線性鍊表的插入與刪除72

3.3循環鍊表77

3.4多項式的表示與運算80

習題88

第4章數組

4.1數組的順序存儲結構90

4.2規則矩陣的壓縮91

4.3一般稀疏矩陣的表示94

4.3.1稀疏矩陣的三列二維數組表示95

4.3.2稀疏矩陣的線性鍊表表示108

4.3.3十字鍊表117

習題121

第5章樹與二叉樹

5.1樹123

5.2二叉樹及其基本性質126

5.2.1什麼是二叉樹126

5.2.2二叉樹的基本性質127

5.2.3滿二叉樹與完全二叉樹128

5.3二叉樹的遍歷129

5.4二叉樹的存儲結構131

5.4.1二叉鍊表131

5.4.2二叉鍊表類133

5.5穿線二叉樹137

5.5.1穿線二叉樹的概念137

5.5.2中序穿線二叉樹137

5.5.3前序穿線二叉樹142

5.5.4後序穿線二叉樹145

5.6表達式的線性化149

5.6.1有序樹的二叉樹表示149

5.6.2如何對表達式進行線性化151

5.7最優二叉樹及其套用151

5.7.1什麼是最優二叉樹151

5.7.2最優二叉樹的構造153

5.7.3霍夫曼編碼158

習題159

第6章圖

6.1圖的基本概念161

6.2圖的存儲結構162

6.2.1關聯矩陣162

6.2.2求值矩陣163

6.2.3鄰接表164

6.2.4鄰接多重表166

6.3圖的遍歷166

6.3.1縱向優先搜尋法167

6.3.2橫向優先搜尋法167

6.4圖鄰接表類167

6.5最短距離問題173

習題179

第7章查找技術

7.1順序查找180

7.2有序表的對分查找180

7.3分塊查找185

7.4二叉排序樹查找186

7.4.1二叉排序樹的基本概念187

7.4.2二叉排序樹的插入188

7.4.3二叉排序樹的刪除190

7.4.4二叉排序樹查找192

7.5多層索引樹查找195

7.5.1B－樹195

7.5.2B+樹205

習題215

第8章Hash表技術

8.1Hash表的基本概念217

8.1.1直接查找技術217

8.1.2Hash表218

8.1.3Hash碼的構造218

8.2幾種常用的Hash表220

8.2.1線性Hash表220

8.2.2隨機Hash表224

8.2.3溢出Hash表229

8.2.4拉鏈Hash表234

8.2.5指標Hash表239

習題239

第9章排序技術

9.1互換類排序241

9.1.1冒泡排序241

9.1.2快速排序243

9.2插入類排序246

9.2.1簡單插入排序247

9.2.2希爾排序249

9.3選擇類排序251

9.3.1簡單選擇排序251

9.3.2堆排序252

9.4拓撲分類255

9.5其他排序方法簡介258

9.5.1歸併排序258

9.5.2基數排序261

習題262

參考文獻263

（註：目錄排版順序為從左列至右列）

教學資源

配套教材

該教材有配套教材——《實用數據結構（C++描述）（第二版）習題解答》。

書名	書號	出版社	出版時間	作者
《實用數據結構（C++描述）（第二版）習題解答》	9787302150824	清華大學出版社	2007.06.01	徐士良、葛兵

課程資源

該教材提供電子課件、原始碼。

教材特色

該教材內容的表現形式實用，書中所有的算法均採用C++語言描述，由於C++語言既可用於面向過程的程式設計，又支持面向對象的程式設計，因此，作者在對算法進行描述時，儘量採用合適的程式設計方法。例如，對於基本的數據結構（如順序存儲與鏈式存儲的線性表、棧、佇列等）採用面向對象的方法，將數據與運算封裝成類，以便在其他應用程式中直接使用；而對於同一批數據進行同類操作的各種算法（如對線性表的各種排序方法）採用面向過程的方法，將各種不同的算法用普通函式來描述。這樣，書中的所有算法就可以直接在實際套用中使用。

作者簡介

徐士良，清華大學信息認知與智慧型系統研究所老師，已經退休。