目錄
教育技術(shù)學專業(yè)主干課程系列教材總序
序
前言
第1章 概述 1
1.1 數(shù)據(jù)結(jié)構(gòu) 2
1.1.1 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)的定義 2
1.1.2 邏輯結(jié)構(gòu)、物理結(jié)構(gòu)和抽象數(shù)據(jù)類型 3
1.2 算法與算法分析 5
1.2.1 算法 5
1.2.2 算法的性質(zhì)和判斷算法優(yōu)劣的標準 5
1.2.3 算法分析 7
1.3 全國青少年信息學奧林匹克聯(lián)賽簡介 10
1.4 C STL簡介 11
習題 12
第2章 線性表 13
2.1 順序表 13
2.1.1 順序表的基本概念 13
2.1.2 順序表的實現(xiàn) 14
2.1.3 順序表操作的時間復雜度 19
2.2 C STL中順序表的用法 19
2.3 信息學競賽中順序表的應用 21
2.4 單鏈表 26
2.4.1 鏈表的基本概念 26
2.4.2 鏈表的實現(xiàn) 28
2.4.3 鏈表操作的時間復雜度 32
2.5 循環(huán)鏈表、雙向鏈表和靜態(tài)鏈表 32
2.5.1 循環(huán)鏈表 32
2.5.2 雙向鏈表 33
2.5.3 靜態(tài)鏈表 35
2.6 C STL中鏈表的用法 36
2.7 信息學競賽中鏈表的應用 37
習題 39
第3章 棧與隊列 40
3.1 棧 40
3.1.1 棧的基本概念 40
3.1.2 順序棧的實現(xiàn) 41
3.2 C STL中棧的用法 42
3.3 信息學競賽中棧的應用 42
3.4 隊列 48
3.4.1 隊列的基本概念 48
3.4.2 鏈式隊列的實現(xiàn) 51
3.5 C STL中隊列的用法 52
3.5.1 隊列queue的用法 52
3.5.2 優(yōu)先級隊列priority_queue的用法 52
3.6 信息學競賽中隊列的應用 54
習題 57
第4章 遞歸 59
4.1 基本概念與用法 59
4.1.1 遞歸的基本概念 59
4.1.2 遞歸的特點 61
4.2 遞歸與棧的關(guān)系 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 串的存儲結(jié)構(gòu) 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 二叉樹的基本概念與性質(zhì) 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 圖的基本術(shù)語 125
7.2 圖的存儲方法 127
7.2.1 鄰接矩陣存儲方法 127
7.2.2 鄰接表存儲方法 129
7.3 圖的遍歷 131
7.3.1 深度優(yōu)先搜索遍歷 131
7.3.2 廣度優(yōu)先搜索遍歷 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 比較排序算法的實質(zhì) 175
8.7 基數(shù)排序 177
8.7.1 線性時間排序算法 177
8.7.2 基數(shù)排序算法 178
8.7.3 鏈式基數(shù)排序算法 179
8.8 各種排序算法復雜度比較 181
8.9 C STL中排序算法的用法 182
8.9.1 幾種常用的STL sort算法函數(shù)簡介 182
8.9.2 sort函數(shù)使用方法 183
8.10 信息學競賽中排序的應用 184
習題 188
第9章 查找 189
9.1 二分查找法 189
9.1.1 二分查找法的實現(xiàn) 189
9.1.2 C STL中二分查找的用法 191
9.2 哈希表 193
9.2.1 哈希函數(shù) 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章 動態(tài)規(guī)劃 225
10.1 動態(tài)規(guī)劃基礎(chǔ) 225
10.2 背包問題 230
10.3 區(qū)間動態(tài)規(guī)劃 234
10.4 信息學競賽中動態(tài)規(guī)劃的應用 238
習題 244
習題參考答案或提示 245
參考文獻 248