目錄
教育技術(shù)學(xué)專(zhuān)業(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ù)類(lèi)型 3
1.2 算法與算法分析 5
1.2.1 算法 5
1.2.2 算法的性質(zhì)和判斷算法優(yōu)劣的標(biāo)準(zhǔn) 5
1.2.3 算法分析 7
1.3 全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽簡(jiǎn)介 10
1.4 C STL簡(jiǎn)介 11
習(xí)題 12
第2章 線性表 13
2.1 順序表 13
2.1.1 順序表的基本概念 13
2.1.2 順序表的實(shí)現(xiàn) 14
2.1.3 順序表操作的時(shí)間復(fù)雜度 19
2.2 C STL中順序表的用法 19
2.3 信息學(xué)競(jìng)賽中順序表的應(yīng)用 21
2.4 單鏈表 26
2.4.1 鏈表的基本概念 26
2.4.2 鏈表的實(shí)現(xiàn) 28
2.4.3 鏈表操作的時(shí)間復(fù)雜度 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 信息學(xué)競(jìng)賽中鏈表的應(yīng)用 37
習(xí)題 39
第3章 棧與隊(duì)列 40
3.1 棧 40
3.1.1 棧的基本概念 40
3.1.2 順序棧的實(shí)現(xiàn) 41
3.2 C STL中棧的用法 42
3.3 信息學(xué)競(jìng)賽中棧的應(yīng)用 42
3.4 隊(duì)列 48
3.4.1 隊(duì)列的基本概念 48
3.4.2 鏈?zhǔn)疥?duì)列的實(shí)現(xiàn) 51
3.5 C STL中隊(duì)列的用法 52
3.5.1 隊(duì)列queue的用法 52
3.5.2 優(yōu)先級(jí)隊(duì)列priority_queue的用法 52
3.6 信息學(xué)競(jìng)賽中隊(duì)列的應(yīng)用 54
習(xí)題 57
第4章 遞歸 59
4.1 基本概念與用法 59
4.1.1 遞歸的基本概念 59
4.1.2 遞歸的特點(diǎn) 61
4.2 遞歸與棧的關(guān)系 61
4.3 遞歸算法 63
4.3.1 窮舉法 63
4.3.2 分治法 65
4.3.3 回溯法 70
4.4 信息學(xué)競(jìng)賽中遞歸的應(yīng)用 74
習(xí)題 78
第5章 串 79
5.1 串的基本概念 79
5.2 串的存儲(chǔ)結(jié)構(gòu) 80
5.2.1 串的順序存儲(chǔ) 80
5.2.2 串的鏈?zhǔn)酱鎯?chǔ) 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 信息學(xué)競(jìng)賽中字符串的應(yīng)用 93
習(xí)題 95
第6章 樹(shù) 97
6.1 樹(shù)的基本概念 97
6.2 二叉樹(shù) 98
6.2.1 二叉樹(shù)的基本概念與性質(zhì) 98
6.2.2 二叉樹(shù)遍歷 101
6.3 哈夫曼樹(shù) 108
6.3.1 變長(zhǎng)編碼 108
6.3.2 哈夫曼樹(shù)與哈夫曼編碼 110
6.4 樹(shù)與森林 115
6.4.1 樹(shù)與森林的表示方法 115
6.4.2 等價(jià)類(lèi)問(wèn)題與并查集算法 118
6.5 信息學(xué)競(jìng)賽中樹(shù)的應(yīng)用 121
習(xí)題 123
第7章 圖 125
7.1 圖的基本概念 125
7.1.1 圖的定義 125
7.1.2 圖的基本術(shù)語(yǔ) 125
7.2 圖的存儲(chǔ)方法 127
7.2.1 鄰接矩陣存儲(chǔ)方法 127
7.2.2 鄰接表存儲(chǔ)方法 129
7.3 圖的遍歷 131
7.3.1 深度優(yōu)先搜索遍歷 131
7.3.2 廣度優(yōu)先搜索遍歷 132
7.3.3 非連通圖的遍歷 133
7.4 小生成樹(shù)問(wèn)題 134
7.4.1 生成樹(shù) 134
7.4.2 小生成樹(shù) 135
7.4.3 普里姆算法 135
7.4.4 克魯斯卡爾算法 139
7.5 短路徑問(wèn)題 140
7.5.1 單源短路徑 140
7.5.2 任意兩點(diǎn)間的短路徑 144
7.6 拓?fù)渑判?147
7.7 信息學(xué)競(jìng)賽中圖的應(yīng)用 149
習(xí)題 154
第8章 排序 156
8.1 冒泡排序 156
8.1.1 冒泡排序算法 156
8.1.2 冒泡排序的時(shí)間復(fù)雜度 159
8.2 插入排序 159
8.2.1 插入排序算法 159
8.2.2 插入排序的時(shí)間復(fù)雜度 161
8.3 歸并排序 161
8.3.1 歸并排序算法 161
8.3.2 歸并排序的時(shí)間復(fù)雜度 163
8.4 快速排序 165
8.4.1 快速排序算法 165
8.4.2 快速排序的時(shí)間復(fù)雜度 167
8.5 堆排序 170
8.5.1 堆的概念與建立堆的方法 170
8.5.2 堆排序算法 174
8.5.3 堆排序的時(shí)間復(fù)雜度 175
8.6 比較排序算法的實(shí)質(zhì) 175
8.7 基數(shù)排序 177
8.7.1 線性時(shí)間排序算法 177
8.7.2 基數(shù)排序算法 178
8.7.3 鏈?zhǔn)交鶖?shù)排序算法 179
8.8 各種排序算法復(fù)雜度比較 181
8.9 C STL中排序算法的用法 182
8.9.1 幾種常用的STL sort算法函數(shù)簡(jiǎn)介 182
8.9.2 sort函數(shù)使用方法 183
8.10 信息學(xué)競(jìng)賽中排序的應(yīng)用 184
習(xí)題 188
第9章 查找 189
9.1 二分查找法 189
9.1.1 二分查找法的實(shí)現(xiàn) 189
9.1.2 C STL中二分查找的用法 191
9.2 哈希表 193
9.2.1 哈希函數(shù) 194
9.2.2 開(kāi)放定址法 195
9.2.3 鏈地址法 198
9.2.4 哈希表的時(shí)間復(fù)雜度 199
9.2.5 C STL中哈希表的用法 201
9.3 查找樹(shù) 203
9.3.1 二叉查找樹(shù) 203
9.3.2 紅黑樹(shù) 210
9.3.3 C STL中二叉查找樹(shù)的用法 217
9.4 信息學(xué)競(jìng)賽中查找的應(yīng)用 219
習(xí)題 223
第10章 動(dòng)態(tài)規(guī)劃 225
10.1 動(dòng)態(tài)規(guī)劃基礎(chǔ) 225
10.2 背包問(wèn)題 230
10.3 區(qū)間動(dòng)態(tài)規(guī)劃 234
10.4 信息學(xué)競(jìng)賽中動(dòng)態(tài)規(guī)劃的應(yīng)用 238
習(xí)題 244
習(xí)題參考答案或提示 245
參考文獻(xiàn) 248