數據結構（C++描述）（第2版）

《數據結構（C++描述）（第2版）》是2015年清華大學出版社出版的圖書，作者是熊岳山。

基本介紹

• 書名：數據結構（C++描述）（第2版）
• 作者：熊岳山
• ISBN：9787302388180
• 定價：32元
• 出版社：清華大學出版社
• 出版時間：2015年2月1日

內容簡介

數據結構是計算機科學與技術、網路工程、軟體工程、信息安全等專業的重要基礎課，是這些專業的核心課程之一，是一門集技術性、理論性和實踐性於一體的課程。

本書重點介紹抽象數據類型、基本數據結構、算法性能評價、C++語言描述數據結構、數據結構的套用等內容，進一步使讀者理解數據抽象與面向對象編程實現的關係，提高使用計算機解決實際問題的能力。

本書內容包括基本數據類型、抽象數據類型、算法效率分析、順序表、鍊表、樹和二叉樹、圖、多維數組等內容。

本書結構合理，內容豐富，算法理論分析詳細，數據結構的算法描述豐富。書中用C++語言編寫的算法代碼都已調試通過，便於自學。

本書可作為高等學校計算機科學與技術、網路工程、軟體工程、信息安全等專業以及軍事院校的基礎合訓或其他相關專業的教材和參考書

圖書目錄

第1章數據結構概述

1.1基本概念

1.1.1數據、數據元素和數據對象

1.1.2數據結構

1.2數據結構的分類

1.3抽象數據類型

1.3.1兩種軟體設計方法

1.3.2數據類型

1.3.3抽象數據類型

1.4算法和算法分析

1.4.1算法的概念

1.4.2算法分析

習題

第2章順序表

2.1線性表

2.1.1線性表的抽象數據類型表示

2.1.2線性表的類表示

2.2數組

2.2.1數組的抽象數據類型

2.2.2數組元素的插入和刪除

2.2.3數組的套用

2.3棧

2.3.1棧的抽象數據類型及其實現

2.3.2棧的套用

2.4佇列

2.4.1佇列的抽象數據類型及其實現

2.4.2優先權佇列

2.4.3佇列的套用——離散事件驅動模擬

習題

第3章鍊表

3.1動態數據結構

3.2單鍊表

3.2.1基本概念

3.2.2單鍊表結點類

3.2.3單鍊表類

3.2.4棧的單鍊表實現

3.2.5鏈式佇列

3.2.6鍊表的套用舉例

3.3循環鍊表

3.4雙鍊表

習題

第4章排序

4.1基本概念

4.2插入排序

4.2.1直接插入排序

4.2.2折半插入排序

4.2.3Shell排序

4.3選擇排序

4.3.1直接選擇排序

4.3.2樹形選擇排序

4.4交換排序

4.4.1冒泡排序

4.4.2快速排序

4.5分配排序

4.5.1基本思想

4.5.2基數排序

4.6歸併排序

*4.7外部排序

4.7.1二路合併排序

4.7.2多路替代選擇合併排序

4.7.3最佳合併排序

*4.8排序算法的時間下界

習題

第5章查找

5.1基本概念

5.2順序查找

5.3折半查找

5.4分塊查找

5.5字元串的模式匹配

5.5.1樸素的模式匹配算法

5.5.2KMP匹配算法

5.5.3算法效率分析

5.6散列查找

5.6.1概述

5.6.2散列函式

5.6.3衝突的處理

5.6.4散列查找的效率

習題

第6章樹和二叉樹

6.1樹的概念

6.2二叉樹

6.2.1二叉樹的概念

6.2.2二叉樹的性質

6.2.3二叉樹的存儲方式

6.2.4樹(樹林)與二叉樹的相互轉換

6.3樹(樹林)、二叉樹的遍歷

6.3.1樹(樹林)的遍歷

6.3.2二叉樹的遍歷

6.4抽象數據類型BinaryTree以及類BinaryTree

6.4.1抽象數據類型BinaryTree

6.4.2一個完整包含類BinaryTreeNode和類BinaryTree實現的例子

6.5二叉樹的遍歷算法

6.5.1非遞歸(使用棧)的遍歷算法

6.5.2線索化二叉樹的遍歷

習題

第7章樹形結構的套用

7.1二叉排序樹

7.1.1二叉排序樹與類BinarySTree

7.1.2二叉排序樹的檢索、插入和刪除運算

7.1.3等機率查找對應的最佳二叉排序樹

7.2平衡的二叉排序樹

7.2.1平衡的二叉排序樹與類AVLTree

7.2.2平衡二叉排序樹的插入和刪除

7.2.3類AVLTree與AVL樹高度

7.3B樹、B+樹

*7.423樹

*7.5紅黑樹

7.6Huffman最優二叉樹

7.6.1Huffman最優二叉樹概述

7.6.2樹編碼

7.7堆排序

*7.8判定樹

*7.9等價類和並查集

7.9.1等價類

7.9.2並查集

*7.10鍵樹

習題

第8章圖

8.1基本概念

8.2圖的存儲表示

8.2.1相鄰矩陣表示圖

8.2.2圖的鄰接表表示

8.2.3鄰接多重表

8.3構造Graph類

8.3.1基於鄰接表表示的Graph類

8.3.2Graph類的實現

8.4圖的遍歷

8.4.1深度優先遍歷

8.4.2廣度優先遍歷

8.5最小代價生成樹

8.6單源最短路徑問題——Dijkstra算法

8.7每一對頂點間的最短路徑問題

8.8有向無迴路圖

8.8.1DAG圖和AOV、AOE網

8.8.2AOV網的拓撲排序

8.8.3AOE網的關鍵路徑

習題

第9章多維數組

9.1多維數組的順序存儲

9.2特殊矩陣的順序存儲

9.3稀疏矩陣的存儲

9.4抽象數據類型稀疏矩陣與class SparseMatrix

習題

附錄Nodelib.h

參考文獻

C O N T E N T S

表目錄

表1.1學生情況表

表5.1四種處理衝突方法的平均查找長度

表8.1從S到其他結點的最短路徑

表8.2Dijkstra算法中dist數組的變化情況

表8.3計算機軟體專業必修課程

C O N T E N T S

圖目錄

圖1.1基本的邏輯結構

圖1.2基本的邏輯結構

圖1.3矩形游泳池

圖2.1順序存儲的棧

圖2.2中綴表達式的計值過程

圖2.3後綴表達式的計值

圖2.4中綴表達式轉換成後綴表達式的過程

圖2.5漢諾塔問題的遞歸求解過程

圖2.6活動記錄的進棧情況

圖2.7活動記錄的退棧情況

圖2.8順序存儲的佇列

圖2.9佇列的操作

圖2.10循環佇列的隊空和隊滿

圖2.11事件驅動過程

圖2.12事件優先佇列的管理

圖3.1單鍊表

圖3.2從鍊表中刪除一個結點

圖3.3往鍊表中插入一個結點

圖3.4附加頭結點的單鍊表

圖3.5一個實際的單鍊表結構

圖3.6空的循環鍊表

圖3.7雙鏈結點

圖3.8雙鍊表

圖3.9往雙鍊表中插入一個結點

圖3.10從雙鍊表中刪除一個結點

圖4.1直接插入排序過程

圖4.2折半查找過程

圖4.3Shell排序過程

圖4.4直接選擇排序

圖4.5第一次樹形選擇排序選出最小排序碼13

圖4.6第二次樹形選擇排序選出最小排序碼14

圖4.7起泡排序過程

圖4.8一趟快速排序的比較過程

圖4.9基數排序的分配和收集過程

圖4.10二路歸併過程

圖4.112路歸併排序示意

圖4.12實現5路合併敗者樹

圖4.13實現5路合併一次替代選擇後的敗者樹

圖4.14順序合併的3路合併樹

圖4.153路最佳合併樹

圖4.16三個排序碼排序過程對應的判定樹

圖5.1折半查找過程

圖5.2分塊查找過程

圖5.3第一趟比較

圖5.4第二趟比較

圖5.5樸素的模式匹配算法執行過程

圖5.6模式P="abcabcd"的next數組的計算過程

圖5.7基於KMP匹配算法的模式匹配過程

圖5.8用分離的同義詞子表解決衝突

圖5.9用結合的同義詞子表解決衝突

圖5.10幾種不同的解決碰撞方法時的平均檢索長度（橫坐標為負載因子的取值）

圖6.1家族樹

圖6.2二叉樹的五種基本形態

圖6.3表達式二叉樹

圖6.4深度為3的滿二叉樹

圖6.5特殊的二叉樹

圖6.6i與i+1在同一層的完全二叉樹

圖6.7i與i+1不在同一層的完全二叉樹

圖6.8完全二叉樹的順序存儲

圖6.9非完全二叉樹的順序存儲

圖6.10二叉樹的LeftChild-RightChild表示

圖6.11樹(樹林)與二叉樹之間相互轉換

圖6.12樹林的例

圖6.13圖6.12對應的二叉樹

圖6.14二叉樹遍歷實例

圖6.15對稱序線索樹

圖6.16在對稱序線索化二叉樹中插入新結點

圖7.1二叉排序樹

圖7.2構造二叉排序樹

圖7.3二叉排序樹中刪除一個結點

圖7.4刪除結點11後的另一種形式

圖7.5兩種不同的二叉排序樹

圖7.6兩棵擴充二叉樹

圖7.7最佳二叉排序樹的構造

圖7.8二叉樹與結點的平衡因子

圖7.9平衡的二叉排序的生成過程(帶★的點為插入後引起不平衡的點)

圖7.10二叉排序樹的平衡旋轉

圖7.11AVL二叉排序樹結點的刪除(結點中右邊數字代表平衡因子)

圖7.12一棵7階的B-樹

圖7.13圖7.12中B-樹的插入（插入3後）

圖7.14圖7.13中B-樹的插入（插入25後）

圖7.15圖7.14中刪除元素80

圖7.16圖7.14中刪除元素4

圖7.17在圖7.16中刪除元素60

圖7.18在圖7.17中刪除元素70

圖7.19一棵3階的B+-樹

圖7.20兩棵不同形式的2-3樹

圖7.212-3樹的插入

圖7.22圖7.20(b)中插入8後2-3樹的變化圖

圖7.232-3樹的刪除

圖7.24一棵階為2的紅黑樹

圖7.25紅黑樹的生長過程

圖7.26一棵2階紅黑樹

圖7.27紅黑樹中刪除元素88

圖7.28圖7.27調整後的紅黑樹

圖7.29圖7.27中刪除元素71

圖7.30圖7.29調整後的紅黑樹

圖7.31圖7.30中刪除元素63

圖7.32調整圖7.31後的紅黑樹

圖7.33一棵擴充的二叉樹

圖7.34哈夫曼最優樹的構造過程

圖7.35Huffman編碼樹

圖7.36樹T

圖7.37樹T0

圖7.38樹T1

圖7.39Huffman 編碼樹

圖7.40堆對應的完全二叉樹

圖7.41堆中插入新結點

圖7.42堆中根結點的刪除

圖7.43篩法建堆過程

圖7.44堆排序過程

圖7.45三個元素排序的判定樹

圖7.46鑑別偽幣的判定樹

圖7.47用父指針表示的樹型結構存儲的並查集

圖7.48並查集的查找、合併過程

圖7.49Union加權規則示意圖

圖7.50路徑壓縮的例子

圖7.51鍵樹示例

圖7.52由圖7.51壓縮後的鍵樹

圖7.53鍵樹中插入記錄

圖8.1無向圖和有向圖

圖8.2圖G4=(V,E)

圖8.3圖G3的強連通分量

圖8.4G1的生成樹

圖8.5G3的生成樹林

圖8.6圖G5(網路)

圖8.7圖的鄰接表表示

圖8.8G5的鄰接表表示

圖8.9圖8.7(a)的鄰接多重表表示

圖8.10圖8.7(c)的多重鍊表表示

圖8.11圖8.7(c)的十字鍊表表示

圖8.12有向圖深度優先搜尋過程

圖8.13無向圖深度方向優先遍歷

圖8.14廣度優先生成樹(樹林)

圖8.15T的變化圖

圖8.16Prim算法構造最小生成樹的過程(g,g′為兩棵最小生成樹)

圖8.17Kruskal構造最小生成樹的過程

圖8.18有向圖G

圖8.19按最短路徑長度遞增的次序找最短路徑

圖8.20含三個頂點的有向網路

圖8.21表達式樹

圖8.22共享結點後的表達式樹

圖8.23表示各課程優先關係的AOV網

圖8.24一個AOE網的例

圖8.25圖8.24的關鍵路徑為(a1,a4,a8,a11)或(a1,a4,a7,a10)

圖9.1稀疏矩陣的三元組表示

圖9.2帶輔助行向量的二元組表示

圖9.3稀疏矩陣的行鍊表表示

圖9.4稀疏矩陣的正交表表示