實用數據結構（第三版）

《實用數據結構（第三版）》是2014年清華大學出版社出版的圖書。

基本介紹

• 書名：實用數據結構（第三版）
• ISBN：9787302254027
• 定價：38.5元
• 出版社：清華大學出版社
• 出版時間：2014-12-19

圖書簡介

本書是高等學校學生學習“數據結構”課程而編寫的。書中介紹了數據處理領域中常用的數據結構及其主要的運算。主要內容包括： 集合、算法以及數據結構的基本概念，線性表及其順序存儲結構，線性鍊表及其運算，索引存儲結構，數組，樹與二叉樹，圖，查找技術，Hash表技術，排序技術。

本書通俗易懂，實例豐富。書中所有的算法均給出了C/C++的描述。本書可作為學習數據結構課程的教材，也可作為自學教材或各類培訓班的教材。

目錄

第1章緒論1.1集合1

1.1.1集合及其基本運算1

1.1.2自然數集與數學歸納法3

1.1.3笛卡兒積5

1.1.4二元關係5

1.2算法7

1.2.1算法的基本概念7

1.2.2算法設計基本方法8

1.2.3算法的複雜度分析13

1.3數據結構的基本概念16

1.3.1兩個例子16

1.3.2什麼是數據結構19

1.3.3數據結構的圖形表示21

1.3.4線性數據結構與非線性數據結構23

習題23第2章線性表及其順序存儲結構2.1線性表的基本概念25

2.1.1什麼是線性表25

2.1.2線性表的順序存儲結構--順序表26

2.1.3順序表的基本運算--插入與刪除28

2.1.4順序表類31

2.2棧及其套用35

2.2.1什麼是棧35

2.2.2棧的順序存儲及其運算372.2.3順序棧類39

2.2.4表達式的計算42

2.3佇列及其套用51

2.3.1什麼是佇列51

2.3.2循環佇列及其運算52

2.3.3循環佇列類55

2.3.4佇列的套用59

2.4字元串66

2.4.1字元串的基本概念66

2.4.2字元串匹配67

習題72第3章線性鍊表3.1線性鍊表的基本概念74

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

3.1.2線性鍊表的存儲結構75

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

3.2.1線性鍊表的插入79

3.2.2線性鍊表的刪除81

3.2.3線性鍊表類83

3.3帶鏈的棧88

3.3.1帶鏈棧及其基本運算88

3.3.2帶鏈棧類89

3.4帶鏈的佇列92

3.4.1帶鏈佇列及其基本運算92

3.4.2帶鏈佇列類94

3.5循環鍊表97

3.5.1循環鍊表及其基本運算97

3.5.2循環鍊表類99

3.6多項式的表示與運算102

習題110第4章線性表的索引存儲結構4.1索引存儲的概念1114.2“順序-索引-順序”存儲方式112

4.3“順序-索引-連結”存儲方式113

4.4多重索引存儲結構114

習題115第5章數組5.1數組的順序存儲結構116

5.2規則矩陣的壓縮117

5.3三列二維數組120

5.3.1稀疏矩陣的三列二維數組表示及其運算121

5.3.2三列二維數組表示的稀疏矩陣類133

5.4三元組鍊表140

5.4.1稀疏矩陣的三元組鍊表表示及其運算140

5.4.2三元組鍊表表示的稀疏矩陣類148

5.5十字鍊表154

5.5.1稀疏矩陣的十字鍊表表示154

5.5.2十字鍊表表示的稀疏矩陣類158

習題162第6章樹與二叉樹6.1樹164

6.2二叉樹及其基本性質167

6.2.1什麼是二叉樹167

6.2.2二叉樹的基本性質167

6.2.3滿二叉樹與完全二叉樹168

6.3二叉樹的存儲結構170

6.4二叉樹的遍歷173

6.5二叉鍊表類176

6.6穿線二叉樹179

6.6.1穿線二叉樹的概念179

6.6.2中序穿線二叉樹180

6.6.3前序穿線二叉樹187

6.6.4後序穿線二叉樹192

6.7表達式的線性化199

6.7.1有序樹的二叉樹表示199

6.7.2表達式的線性化200

6.8最優二叉樹及其套用201

6.8.1什麼是最優二叉樹201

6.8.2最優二叉樹的構造203

6.8.3最優二叉樹類208

6.8.4霍夫曼編碼210

習題211第7章圖7.1圖的基本概念213

7.2圖的存儲結構214

7.2.1關聯矩陣214

7.2.2求值矩陣215

7.2.3鄰接表216

7.2.4鄰接多重表220

7.3圖的遍歷221

7.3.1縱向優先搜尋法221

7.3.2橫向優先搜尋法222

7.4最短距離問題225

7.5圖的鄰接表類232

習題239第8章查找技術8.1順序查找240

8.2順序存儲的有序表240

8.2.1順序有序表的對分查找240

8.2.2順序有序表類241

8.3分塊查找246

8.4二叉排序樹247

8.4.1二叉排序樹的基本概念247

8.4.2二叉排序樹的插入248

8.4.3二叉排序樹的刪除250

8.4.4二叉排序樹的查找252

8.4.5二叉排序樹類256

8.5多層索引樹查找259

8.5.1B-樹259

8.5.2B+樹277

習題295第9章Hash表技術9.1Hash表的基本概念296

9.1.1直接查找技術296

9.1.2Hash表297

9.1.3Hash碼的構造298

9.2幾種常用的Hash表299

9.2.1線性Hash表299

9.2.2隨機Hash表305

9.2.3溢出Hash表310

9.2.4拉鏈Hash表317

9.2.5指標Hash表324

習題324第10章排序技術10.1互換類排序326

10.1.1冒泡排序326

10.1.2快速排序329

10.2插入類排序332

10.2.1簡單插入排序332

10.2.2希爾排序334

10.3選擇類排序336

10.3.1簡單選擇排序336

10.3.2堆排序338

10.4拓撲分類341

10.5其他排序方法簡介344

10.5.1歸併排序344

10.5.2基數排序347

習題348參考文獻349