數據結構——基於C++語言實現（微課版）

熊才權：

博士，三級教授，博士生導師。主要從事模型識別與智能系統、計算機應用、軟件工程等方面的研究。主講的“數據結構”課程2021年被認定為湖北省一流本科課程。主編過《軟件工程》（華中科技大學出版社，2005年）、《數據庫原理與應用》（華中科技大學出版社，2019年）等教材，出版學術專著一部《綜合集成模型方法與工具》（科學出版社，2019年）。主持國家自然科學基金面上項目和國家重點研發計劃項目子課題各一項，獲武漢市科技進步三等獎1項，湖北省教學成果二等獎2項、湖北工業大學教學成果一等獎3項、二等獎1項。

【章名目錄】

第 1章　緒論

第 2章　線性結構

第3章　樹與二叉樹

第4章　圖

第5章　查找

第6章　排序

【詳細目錄】

第 1章　緒論

1.1　數據結構概述　1

1.1.1　數據結構的基本概念與術語　1

1.1.2　數據的邏輯結構　2

1.1.3　數據的物理結構　4

1.2　算法與性能分析　5

1.2.1　算法的基本概念　5

1.2.2　描述算法的方法　6

1.2.3　算法設計的要求　7

1.2.4　算法效率分析　8

1.3　數據結構、算法及程序的關系　12

1.3.1　數據結構的作用　13

1.3.2　算法的作用　13

1.3.3　程序的作用　13

1.3.4　三者之間的關系　13

1.4　本章小結　14

練習題　14

第 2章　線性結構

2.1　問題導入：數組的局限性　16

2.2　順序表　17

2.2.1　非封裝的順序表　17

2.2.2　順序表類　23

2.2.3　順序表類模板　29

2.2.4　模仿的向量（vector）類模板　30

2.2.5　順序表的應用：Todo計劃表　36

2.3　鏈表　37

2.3.1　鏈表的基本概念　37

2.3.2　單鏈表　37

2.3.3　雙向鏈表　43

2.3.4　循環鏈表　44

2.3.5　模仿的鏈表類模板list　45

2.3.6　鏈表的應用：一元多項式相加　51

2.4　棧　52

2.4.1　棧的基本概念　52

2.4.2　順序棧　53

2.4.3　以標準模板庫的vector類為底層結構的順序棧　54

2.4.4　鏈棧　56

2.4.5　以標準模板庫的list類為底層結構的鏈棧　57

2.4.6　棧的應用：括號匹配　59

2.5　隊列　60

2.5.1　隊列的基本概念　60

2.5.2　順序隊列　60

2.5.3　以標準模板庫的vector類為底層結構的順序隊列　61

2.5.4　鏈隊列　63

2.5.5　以標準模板庫的list類為底層結構的鏈隊列　65

2.5.6　優先級隊列　65

2.5.7　隊列的應用：打印機模擬　65

2.6　串　66

2.6.1　串的基本概念　66

2.6.2　模仿的String類及其實現　66

2.6.3　模式匹配　70

2.6.4　串的應用：文本檢索　76

2.7　多維數組與特殊矩陣　77

2.7.1　多維數組的定義　77

2.7.2　多維數組的存儲方式　78

2.7.3　特殊矩陣　79

2.7.4　稀疏矩陣　81

2.8　本章小結　82

練習題　83

第3章　樹與二叉樹

3.1　樹的基本概念　85

3.1.1　樹的定義　85

3.1.2　樹的基本術語　86

3.2　二叉樹的基本概念　87

3.2.1　二叉樹的定義　87

3.2.2　二叉樹的性質　88

3.3　二叉樹的存儲結構　89

3.3.1　二叉樹的順序存儲結構　89

3.3.2　二叉樹的鏈式存儲結構　89

3.4　二叉樹遍歷　92

3.4.1　二叉樹遍歷概述　92

3.4.2　二叉樹的層次遍歷　92

3.4.3　二叉樹的先序、中序、後序遍歷遞歸算法　93

3.4.4　二叉樹的先序、中序、後序遍歷非遞歸算法　94

3.4.5　二叉樹遍歷遞歸程序轉換為非遞歸程序的一般方法　95

3.4.6　二叉樹遍歷的應用　97

3.5　堆　109

3.5.1　堆的基本概念　109

3.5.2　建堆　109

3.5.3　堆排序　111

3.5.4　小根堆Heap類　111

3.6　哈夫曼樹與哈夫曼編碼　112

3.6.1　哈夫曼樹的基本概念　112

3.6.2　哈夫曼樹構建　113

3.6.3　哈夫曼編碼與解碼　115

3.7　樹與森林　117

3.7.1　樹的存儲與Tree類　117

3.7.2　樹的遍歷　121

3.7.3　樹與二叉樹的轉換　123

3.7.4　樹的應用：八數碼問題　125

3.8　本章小結　127

練習題　128

第4章　圖

4.1　圖的基本概念　130

4.2　圖的存儲結構　132

4.2.1　鄰接矩陣　132

4.2.2　鄰接表　132

4.3　Graph類　133

4.4　圖的遍歷　138

4.4.1　廣度優先搜索算法　138

4.4.2　深度優先搜索算法　139

4.5　最小生成樹　141

4.5.1　圖的生成樹的基本概念　141

4.5.2　克魯斯卡爾算法　142

4.5.3　普裏姆算法　146

4.6　最短路徑　148

4.6.1　單源最短路徑　148

4.6.2　迪傑斯特拉算法　149

4.6.3　所有頂點之間的最短路徑　152

4.7　拓撲排序與關鍵路徑　156

4.7.1　有向無環圖　156

4.7.2　拓撲排序　157

4.7.3　關鍵路徑　158

4.8　圖的應用：迷宮求解　160

4.9　本章小結　162

練習題　162

第5章　查找

5.1　查找的基本概念　166

5.2　靜態查找　168

5.2.1　順序查找　168

5.2.2　折半查找　169

5.2.3　分塊查找　170

5.3　二叉搜索樹　170

5.3.1　二叉搜索樹的基本概念　170

5.3.2　二叉搜索樹的操作　171

5.3.3　二叉樹的遍歷疊代器　177

5.3.4　線索二叉樹　182

5.3.5　增加線索的遍歷疊代器　188

5.4　平衡二叉搜索樹　191

5.4.1　平衡二叉搜索樹的基本概念　191

5.4.2　動態平衡調整法　192

5.4.3　平衡二叉搜索樹插入節點　198

5.4.4　平衡二叉搜索樹刪除節點　199

5.4.5　平衡二叉搜索樹的應用：詞頻統計　201

5.5　B-樹　202

5.5.1　B-樹的基本概念　202

5.5.2　B-樹的查找　202

5.5.3　B-樹的插入　203

5.5.4　B-樹的刪除　205

5.5.5　B+樹　211

5.6　散列　217

5.6.1　散列的基本概念　217

5.6.2　散列函數的構造方法　218

5.6.3　處理散列沖突的方法　219

5.6.4　散列查找　223

5.7　本章小結　224

練習題　225

第6章　排序

6.1　排序的基本概念　227

6.2　插入排序　228

6.2.1　直接插入排序　228

6.2.2　折半插入排序　230

6.2.3　希爾排序　231

6.3　交換排序　233

6.3.1　冒泡排序　233

6.3.2　快速排序　235

6.4　選擇排序　236

6.4.1　直接選擇排序　236

6.4.2　堆排序　237

6.4.3　錦標賽排序　238

6.5　歸並排序　242

6.5.1　二路歸並　242

6.5.2　疊代歸並排序　243

6.5.3　遞歸歸並排序　243

6.6　基數排序　244

6.7　外排序　246

6.7.1　內排序與外排序　246

6.7.2　多路歸並排序　246

6.8　排序的應用：國際大學生程序設計競賽成績排序　248

6.9　本章小結　249

練習題　250

參考文獻