數據結構與算法（C++微課版）

周建濤 ,博士，二級教授，博士生導師。現為內蒙古大學教務處處長、內蒙古大學計算機學院（軟件學院）院長，計算機科學與技術一級學科博士點負責人，學科帶頭人。“生態大數據”教育部工程研究中心主任，“蒙古文智能信息處理技術”國家地方聯合工程研究中心常務副主任，“雲計算與服務軟件”內蒙古自治區工程實驗室主任，“數據處理與社會計算”內蒙古自治區重點實驗室主任。軟件工程國家級一流本科專業建設點負責人，數據結構與算法國家級一流本科課程負責人。內蒙古自治區優秀教學團隊負責人、科技創新團隊負責人。內蒙古計算機學會理事長；ACM中國理事會呼和浩特分會主席；全國高等學校計算機教育研究會理事；教育部計算機類教指委“計算機專業開放教育體系和教材建設專家委員會”委員。獲得全國寶鋼教育獎優秀教師獎、內蒙古教學成果獎二等獎、內蒙古科技進步獎二等獎等。

目

 

錄第1章緒論1

1.1數據結構的基本概念1

1.1.1數據與數據元素1

1.1.2數據的邏輯結構2

1.1.3數據的存儲結構4

1.2抽象數據類型5

1.3算法與算法分析7

1.3.1算法定義及描述7

1.3.2算法評價8

1.3.3算法性能分析與度量9

習題13

 

第2章線性表16

2.1線性表的基本概念17

2.1.1邏輯結構及基本操作17

2.1.2抽象數據類型18

2.2線性表的順序存儲實現19

2.2.1存儲結構19

2.2.2基本操作的實現21

2.3線性表的鏈式存儲實現24

2.3.1單鏈表24

2.3.2雙鏈表30

2.3.3循環鏈表32

2.4應用33

2.4.1學生隊列合並33

2.4.2一元多項式求導問題34

習題36

 

第3章棧38

3.1棧的基本概念39

3.1.1邏輯結構及基本操作393.1.2抽象數據類型39

3.2棧的順序存儲實現40

3.2.1存儲結構40

3.2.2基本操作的實現42

3.2.3共享棧的介紹和基本操作43

3.3棧的鏈式存儲實現45

3.3.1存儲結構45

3.3.2基本操作的實現47

3.4棧和遞歸49

3.4.1函數調用棧49

3.4.2遞歸調用過程50

3.5應用51

3.5.1馬踏棋盤51

3.5.2開關盒布線54

習題56

 

第4章隊列58

4.1隊列的基本概念59

4.1.1邏輯結構及基本操作59

4.1.2抽象數據類型60

4.2隊列的順序存儲實現60

4.2.1存儲結構60

4.2.2基本操作的實現61

4.2.3循環隊列62

4.3隊列的鏈式存儲實現65

4.3.1存儲結構65

4.3.2基本操作的實現66

4.4應用68

4.4.1滑動窗口最大值68

4.4.2圖元識別71

習題74

 

第5章字符串76

5.1字符串的基本概念77

5.1.1邏輯結構及基本操作77

5.1.2抽象數據類型78

5.2字符串的存儲結構及實現78

5.2.1定長串78

5.2.2堆串81

5.2.3塊鏈串83

5.3字符串的模式匹配84

5.3.1樸素的模式匹配84

5.3.2無回溯的模式匹配86

5.4應用89

5.4.1最長公共子串89

5.4.2字符串全排列91

習題92

 

第6章數組94

6.1多維數組95

6.1.1數組的定義95

6.1.2數組的存儲95

6.2矩陣的壓縮存儲96

6.2.1對稱矩陣的壓縮存儲96

6.2.2三角矩陣的壓縮存儲97

6.2.3對角矩陣的壓縮存儲98

6.3稀疏矩陣98

6.3.1稀疏矩陣的壓縮存儲98

6.3.2稀疏矩陣的轉置運算101

6.4應用103

6.4.1九宮格103

6.4.2三子棋105

習題106

 

第7章樹與二叉樹109

7.1樹110

7.1.1樹的定義110

7.1.2樹的基本術語110

7.1.3樹的存儲結構111

7.2二叉樹113

7.2.1二叉樹的定義113

7.2.2二叉樹的性質115

7.2.3二叉樹的存儲結構116

7.3二叉樹的遍歷118

7.3.1二叉樹遍歷的定義118

7.3.2二叉樹的遞歸遍歷119

7.3.3二叉樹的非遞歸遍歷121

7.4線索二叉樹125

7.4.1線索二叉樹的定義125

7.4.2線索二叉樹的建立126

7.4.3線索二叉樹的遍歷127

7.5樹與森林130

7.5.1樹與森林的遍歷130

7.5.2森林與二叉樹的關系130

7.6哈夫曼(Huffman)樹與編碼132

7.6.1Huffman樹132

7.6.2Huffman編碼133

7.7應用137

7.7.1二叉排序樹137

7.7.2中綴表達式138

習題140

 

第8章圖142

8.1圖的基本概念143

8.1.1圖的定義143

8.1.2圖的連通性145

8.1.3圖的抽象數據類型147

8.2圖的存儲結構149

8.2.1鄰接矩陣149

8.2.2鄰接表151

8.2.3鄰接多重表154

8.2.4十字鏈表155

8.3圖的遍歷算法156

8.3.1深度優先遍歷157

8.3.2廣度優先遍歷159

8.4最小生成樹161

8.4.1最小生成樹問題161

8.4.2普裏姆（Prim）算法162

8.4.3克魯斯卡爾(Kruskal)算法165

8.5最短路徑166

8.5.1最短路徑問題166

8.5.2迪傑斯特拉（Dijkstra）算法166

8.5.3弗洛伊德（Floyd）算法169

8.6拓撲排序和關鍵路徑171

8.6.1AOV網與拓撲排序171

8.6.2拓撲排序算法173

8.6.3AOE網與關鍵路徑175

8.6.4關鍵路徑算法176

8.7應用179

8.7.1擴大朋友圈179

8.7.2市內交通導航問題180

習題183

 

第9章查找186

9.1查找的基本概念187

9.2線性表的查找188

9.2.1順序查找188

9.2.2二分查找189

9.2.3索引順序查找192

9.3二叉查找樹193

9.3.1二叉查找樹的定義193

9.3.2二叉查找樹的基本操作194

9.3.3查找性能分析198

9.4平衡二叉樹198

9.4.1平衡二叉樹的定義199

9.4.2平衡二叉樹的建立199

9.5哈希表205

9.5.1哈希表的基本概念205

9.5.2哈希函數的構造206

9.5.3處理沖突的方法207

9.5.4查找性能分析208

9.6B樹與B+樹210

9.6.1B樹210

9.6.2B+樹216

9.7應用217

9.7.1直方圖的計算217

9.7.2鍵樹219

習題220

 

第10章排序223

10.1排序的基本概念223

10.1.1排序算法的分類224

10.1.2排序算法性能評價225

10.2插入排序226

10.2.1直接插入排序226

10.2.2折半插入排序228

10.2.3希爾（Shell）排序229

10.3選擇排序230

10.3.1直接選擇排序231

10.3.2堆排序232

10.4交換排序237

10.4.1冒泡排序237

10.4.2快速排序239

10.5歸並排序242

10.6基數排序244

10.6.1多排序碼排序244

10.6.2鏈式基數排序245

10.7各種內部排序算法的比較248

10.8外部排序250

10.8.1外部排序的基本過程250

10.8.2多路平衡歸並252

10.8.3置換—選擇排序254

10.8.4最佳歸並樹258

10.9應用260

10.9.1按文件名排序260

10.9.2數據庫數據排序261

習題263

 

第11章算法進階265

11.1分治算法265

11.1.1折半查找算法中的分治策略269

11.1.2歸並排序中的分治策略270

11.2貪心算法271

11.2.1錢幣找零問題中的貪心策略272

11.2.2背包問題中的貪心策略274

11.2.3最小生成樹問題中的貪心策略275

11.3動態規劃算法276

11.3.1最大子序列和問題的動態規劃算法278

11.3.20/1背包問題的動態規劃算法280

11.4搜索算法282

11.4.1回溯法282

11.4.2分支限界法285

習題287