數據結構

《數據結構（面向信息學競賽）》是為教育技術學專業“數據結構”課程編寫的教材，《數據結構（面向信息學競賽）》詳細介紹了各類常用數據結構的概念、實現和應用，以及各種常見排序、查找和動態規劃算法。同時，針對本專業學生就業後指導中學生信息學奧林匹克競賽的實際需求，在各章節中加入了對應C++ STL的介紹，以及利用數據結構和算法知識解決信息學競賽題目的內容。《數據結構（面向信息學競賽）》使用C++語言作為代碼實現語言。 ^[3] 

教育技術學專業主幹課程系列教材總序

序

前言

第1章 概述 1

1.1 數據結構 2

1.1.1 數據與數據結構的定義 2

1.1.2 邏輯結構、物理結構和抽象數據類型 3

1.2 算法與算法分析 5

1.2.1 算法 5

1.2.2 算法的性質和判斷算法優劣的標準 5

1.2.3 算法分析 7

1.3 全國青少年信息學奧林匹克聯賽簡介 10

1.4 C++ STL簡介 11

習題 12

第2章 線性表 13

2.1 順序表 13

2.1.1 順序表的基本概念 13

2.1.2 順序表的實現 14

2.1.3 順序表操作的時間複雜度 19

2.2 C++ STL中順序表的用法 19

2.3 信息學競賽中順序表的應用 21

2.4 單鏈表 26

2.4.1 鏈表的基本概念 26

2.4.2 鏈表的實現 28

2.4.3 鏈表操作的時間複雜度 32

2.5 循環鏈表、雙向鏈表和靜態鏈表 32

2.5.1 循環鏈表 32

2.5.2 雙向鏈表 33

2.5.3 靜態鏈表 35

2.6 C++ STL中鏈表的用法 36

2.7 信息學競賽中鏈表的應用 37

習題 39

第3章 棧與隊列 40

3.1 棧 40

3.1.1 棧的基本概念 40

3.1.2 順序棧的實現 41

3.2 C++ STL中棧的用法 42

3.3 信息學競賽中棧的應用 42

3.4 隊列 48

3.4.1 隊列的基本概念 48

3.4.2 鏈式隊列的實現 51

3.5 C++ STL中隊列的用法 52

3.5.1 隊列queue的用法 52

3.5.2 優先級隊列priority_queue的用法 52

3.6 信息學競賽中隊列的應用 54

習題 57

第4章 遞歸 59

4.1 基本概念與用法 59

4.1.1 遞歸的基本概念 59

4.1.2 遞歸的特點 61

4.2 遞歸與棧的關係 61

4.3 遞歸算法 63

4.3.1 窮舉法 63

4.3.2 分治法 65

4.3.3 回溯法 70

4.4 信息學競賽中遞歸的應用 74

習題 78

第5章 串 79

5.1 串的基本概念 79

5.2 串的存儲結構 80

5.2.1 串的順序存儲 80

5.2.2 串的鏈式存儲 85

5.3 串的模式匹配算法 85

5.3.1 Brute-Force算法 85

5.3.2 KMP算法 87

5.4 C++ STL中字符串的用法 91

5.4.1 string的頭文件、定義與初始化 91

5.4.2 string的基本操作 91

5.5 信息學競賽中字符串的應用 93

習題 95

第6章 樹 97

6.1 樹的基本概念 97

6.2 二叉樹 98

6.2.1 二叉樹的基本概念與性質 98

6.2.2 二叉樹遍歷 101

6.3 哈夫曼樹 108

6.3.1 變長編碼 108

6.3.2 哈夫曼樹與哈夫曼編碼 110

6.4 樹與森林 115

6.4.1 樹與森林的表示方法 115

6.4.2 等價類問題與並查集算法 118

6.5 信息學競賽中樹的應用 121

習題 123

第7章 圖 125

7.1 圖的基本概念 125

7.1.1 圖的定義 125

7.1.2 圖的基本術語 125

7.2 圖的存儲方法 127

7.2.1 鄰接矩陣存儲方法 127

7.2.2 鄰接表存儲方法 129

7.3 圖的遍歷 131

7.3.1 深度優先搜索遍歷 131

7.3.2 廣度優先搜索遍歷 132

7.3.3 非連通圖的遍歷 133

7.4 *小生成樹問題 134

7.4.1 生成樹 134

7.4.2 *小生成樹 135

7.4.3 普里姆算法 135

7.4.4 克魯斯卡爾算法 139

7.5 *短路徑問題 140

7.5.1 單源*短路徑 140

7.5.2 任意兩點間的*短路徑 144

7.6 拓撲排序 147

7.7 信息學競賽中圖的應用 149

習題 154

第8章 排序 156

8.1 冒泡排序 156

8.1.1 冒泡排序算法 156

8.1.2 冒泡排序的時間複雜度 159

8.2 插入排序 159

8.2.1 插入排序算法 159

8.2.2 插入排序的時間複雜度 161

8.3 歸併排序 161

8.3.1 歸併排序算法 161

8.3.2 歸併排序的時間複雜度 163

8.4 快速排序 165

8.4.1 快速排序算法 165

8.4.2 快速排序的時間複雜度 167

8.5 堆排序 170

8.5.1 堆的概念與建立堆的方法 170

8.5.2 堆排序算法 174

8.5.3 堆排序的時間複雜度 175

8.6 比較排序算法的實質 175

8.7 基數排序 177

8.7.1 線性時間排序算法 177

8.7.2 基數排序算法 178

8.7.3 鏈式基數排序算法 179

8.8 各種排序算法複雜度比較 181

8.9 C++ STL中排序算法的用法 182

8.9.1 幾種常用的STL sort算法函數簡介 182

8.9.2 sort函數使用方法 183

8.10 信息學競賽中排序的應用 184

習題 188

第9章 查找 189

9.1 二分查找法 189

9.1.1 二分查找法的實現 189

9.1.2 C++ STL中二分查找的用法 191

9.2 哈希表 193

9.2.1 哈希函數 194

9.2.2 開放定址法 195

9.2.3 鏈地址法 198

9.2.4 哈希表的時間複雜度 199

9.2.5 C++ STL中哈希表的用法 201

9.3 查找樹 203

9.3.1 二叉查找樹 203

9.3.2 紅黑樹 210

9.3.3 C++ STL中二叉查找樹的用法 217

9.4 信息學競賽中查找的應用 219

習題 223

第10章 動態規劃 225

10.1 動態規劃基礎 225

10.2 揹包問題 230

10.3 區間動態規劃 234

10.4 信息學競賽中動態規劃的應用 238

習題 244

習題參考答案或提示 245

參考文獻 248 ^[3]