數據結構（C語言）慕課版 第3版

王海艷，南京郵電大學教授，博士生導師；江蘇省教學名師，江蘇高校“青藍工程”優

秀教學團隊負責人；主持國家級一流本科課程2 門，獲全國高校教師教學創新大賽三等獎、全國高校微課教學比賽三等獎；獲江蘇省教學成果獎特等獎1項、二等獎2項。

目錄

第　1章 緒論　001

1.1　數據結構概述　001

1.1.1　基本概念　001

1.1.2　數據結構的定義　002

1.2　抽象數據類型　003

1.3　算法和算法分析　004

1.3.1　算法　004

1.3.2　算法的時間復雜度　005

1.3.3　最好、最壞和平均時間復雜度　006

1.3.4　算法的空間復雜度　007

1.4　本章小結　007

習題　007

第　2章 線性表　009

2.1　線性表概述　009

2.2　線性表的順序存儲結構和實現　010

2.2.1　線性表的順序存儲結構　010

2.2.2　順序表基本運算的實現　011

2.3　線性表的鏈式存儲結構和實現　015

2.3.1　單鏈表的定義和表示　015

2.3.2　單鏈表基本運算的實現　016

2.3.3　帶表頭結點的單鏈表　020

2.3.4　單循環鏈表　022

2.3.5　雙向鏈表　023

2.4　順序表與鏈表的比較　024

2.5　線性表的應用　024

2.6　本章小結　027

習題　027

第3章　堆棧和隊列　030

3.1　堆棧　030

3.1.1　堆棧ADT　030

3.1.2　堆棧的順序表示　031

3.1.3　堆棧的鏈接表示　033

3.2　隊列　033

3.2.1　隊列ADT　033

3.2.2　隊列的順序表示　033

3.2.3　隊列的鏈接表示　036

3.3　表達式計算　036

3.3.1　中綴表達式　036

3.3.2　後綴表達式及其求值方法　037

3.3.3　中綴表達式轉換為後綴表達式　041

3.4　遞歸　045

3.4.1　遞歸的概念　045

3.4.2　遞歸的實現　046

3.5　本章小結　047

習題　047

第4章　數組和字符串　049

4.1　數組　049

4.1.1　一維數組　049

4.1.2　二維數組　050

4.1.3　多維數組　051

4.2　數組ADT及其運算實現　051

4.3　特殊矩陣　054

4.3.1　對稱矩陣　054

4.3.2　三角矩陣　055

4.4　稀疏矩陣　056

4.4.1　稀疏矩陣ADT　056

4.4.2　稀疏矩陣的轉置算法　058

4.5　字符串　060

4.5.1　字符串ADT　060

4.5.2　簡單字符串匹配算法　061

4.5.3　改進的字符串匹配算法　064

4.6　本章小結　070

習題　070

第5章　樹和二叉樹　072

5.1　樹　073

5.1.1　樹的定義　073

5.1.2　基本術語　074

5.2　二叉樹　074

5.2.1　二叉樹的定義　075

5.2.2　二叉樹的性質　075

5.2.3　二叉樹ADT　077

5.2.4　二叉樹的存儲表示　077

5.2.5　二叉樹的存儲實現和基本運算　078

5.3　二叉樹的遍歷　080

5.3.1　二叉樹遍歷的遞歸算法　080

5.3.2　二叉樹遍歷的應用實例　083

5.3.3　二叉樹遍歷的非遞歸算法　085

5.3.4　線索二叉樹的概念、構造和遍歷　086

5.4　樹和森林　090

5.4.1　森林與二叉樹的轉換　090

5.4.2　樹和森林的存儲表示　092

5.4.3　樹和森林的遍歷　094

5.5　堆和優先權隊列　095

5.5.1　堆　095

5.5.2　優先權隊列　098

5.6　哈夫曼樹和哈夫曼編碼　103

5.6.1　樹的路徑長度　103

5.6.2　哈夫曼樹和哈夫曼算法　105

5.6.3　構造哈夫曼樹　106

5.6.4　哈夫曼編碼　107

5.7　並查集及其應用　107

5.7.1　並查集ADT　108

5.7.2　並查集的存儲表示　108

5.7.3　並查集的運算　109

5.7.4　改進的Union()運算　111

5.7.5　並查集應用實例　112

5.8　本章小結　113

習題　113

第6章　集合和搜索　117

6.1　集合　117

6.1.1　集合的基本概念　117

6.1.2　動態集ADT　118

6.1.3　集合的表示　118

6.2　順序搜索　119

6.2.1　無序表的順序搜索　119

6.2.2　有序表的順序搜索　120

6.3　對半搜索　120

6.3.1　對半搜索算法　120

6.3.2　二叉判定樹　123

6.4　分塊搜索　124

6.5　本章小結　126

習題　126

第7章　搜索樹　128

7.1　二叉搜索樹　129

7.1.1　二叉搜索樹的定義與性質　129

7.1.2　二叉搜索樹的搜索　129

7.1.3　二叉搜索樹的插入　130

7.1.4　二叉搜索樹的刪除　132

7.1.5　二叉搜索樹的高度　134

7.2　二叉平衡樹　134

7.2.1　二叉平衡樹的定義　134

7.2.2　二叉平衡樹的平衡調整方法　135

7.2.3　二叉平衡樹的插入　138

7.2.4　二叉平衡樹的刪除　139

7.2.5　二叉平衡樹的高度　140

7.3　紅黑樹　141

7.3.1　紅黑樹的定義　141

7.3.2　紅黑樹的性質　141

7.3.3　紅黑樹的插入　141

7.4　m叉搜索樹　143

7.4.1　m叉搜索樹的定義　143

7.4.2　m叉搜索樹的高度　145

7.5　B-樹　145

7.5.1　B-樹的定義　145

7.5.2　B-樹的高度　146

7.5.3　B-樹的搜索　146

7.5.4　B-樹的插入　147

7.5.5　B-樹的刪除　148

7.6　B+樹　151

7.6.1　B+樹的定義　151

7.6.2　B+樹的搜索、插入和刪除　151

7.7　本章小結　152

習題　152

第8章　散列表　155

8.1　散列技術簡介　155

8.2　散列函數　156

8.3　散列沖突處理　158

8.3.1　拉鏈法　158

8.3.2　開地址法　159

8.3.3　性能分析　165

8.4　本章小結　166

習題　166

第9章　圖　167

9.1　圖的基本概念　167

9.1.1　圖的定義　167

9.1.2　圖的基本術語　168

9.1.3　圖的類型定義　170

9.2　圖的存儲結構　170

9.2.1　鄰接矩陣表示法　170

9.2.2　鄰接矩陣的實現　171

9.2.3　鄰接表表示法　174

9.2.4　鄰接表的實現　174

9.2.5　十字鏈表表示法　177

9.2.6　鄰接多重表表示法　178

9.3　圖的遍歷　180

9.3.1　深度優先遍歷　180

9.3.2　寬度優先遍歷　181

9.4　拓撲排序　183

9.4.1　AOV網　183

9.4.2　AOV網的拓撲排序　184

9.5　關鍵路徑　185

9.5.1　AOE網　185

9.5.2　AOE網的關鍵路徑和關鍵活動　186

9.6　最小代價生成樹　189

9.6.1　最小代價生成樹的基本概念　189

9.6.2　普裏姆算法　189

9.6.3　克魯斯卡爾算法　191

9.7　單源最短路徑　193

9.7.1　最短路徑問題　193

9.7.2　單源最短路徑問題　194

9.8　所有頂點之間的最短路徑　197

9.9　本章小結　199

習題　199

第　10章 排序　203

10.1　排序的基本概念　203

10.2　簡單排序算法　204

10.2.1　簡單選擇排序　205

10.2.2　直接插入排序　207

10.2.3　冒泡排序　210

10.3　快速排序算法　212

10.4　兩路合並排序算法　216

10.5　堆排序算法　219

10.6　希爾排序算法　221

10.7　基數排序算法　224

10.8　外排序　226

10.8.1　預處理　226

10.8.2　多路合並　230

10.8.3　最佳合並樹　233

10.8.4　完整的外排序過程　234

10.9　本章小結　234

習題　235

附錄A　綜合實驗　238

實驗1　線性表的基本運算及多項式的算術運算　239

實驗2　二叉樹的基本操作及哈夫曼編碼/譯碼系統的實現　240

實驗3　圖的基本運算及智能交通中的最佳路徑選擇問題　241

實驗4　各種內排序算法的實現及性能比較　241

附錄B　配套慕課使用說明　243