數(shù)據結構與算法（高職高專計算機技能型緊缺人才培養(yǎng)規(guī)劃教材計算機軟件技術專業(yè)）

第1章　面向對象程序設計基礎　1
1.1　C++基本特征　1
1.1.1　重載　1
1.1.2　缺省參數(shù)函數(shù)與內置函數(shù)　3
1.1.3　引用及其使用　3
1.1.4　動態(tài)內存分配　7
1.2　類和對象　8
1.2.1　聲明類和對象　9
1.2.2　在類外定義成員函數(shù)　10
1.2.3　類數(shù)組.類指針與函數(shù)的類參數(shù)　11
1.2.4　this指針　14
1.3　構造函數(shù)與析構函數(shù)　15
1.3.1　構造函數(shù)　15
1.3.2　析構函數(shù)　16
1.4　繼承與派生　17
1.4.1　建立派生類　18
1.4.2　公用派生類與私有派生類　19
1.4.3　保護成員　20
1.4.4　友元函數(shù)與友元類　20
1.5　C++模板　23
1.5.1　函數(shù)模板　23
1.5.2　類模板　25
習題　26
第2章　數(shù)據結構導論　31
2.1　數(shù)據結構的基本概念　31
2.1.1　幾個實例　31
2.1.2　數(shù)據結構的術語　33
2.1.3　抽象數(shù)據類型及其實現(xiàn)　34
2.2　算法描述　35
2.2.1　算法的特性　35
2.2.2　算法描述與通用性　35
2.2.3　類和算法的測試　38
2.3　C++標準模板庫簡介　38
2.4　算法分析初步　41
習題　44
第3章　向量　47
3.1　向量的基本知識　47
3.1.1　線性表的定義　47
3.1.2　向量的存儲結構　47
3.2　向量運算　48
3.2.1　向量運算簡介　48
3.2.2　插入算法與刪除算法　49
3.3　簡易向量類　52
3.3.1　簡易向量類及其實現(xiàn)　52
3.3.2　簡易向量類的測試　54
3.4　標準模板向量類　55
3.4.1　模板向量類的構造器及下標運算符　55
3.4.2　模板向量類的迭代器　56
3.4.3　模板向量類的成員函數(shù)　58
3.4.4　insert類算法和erase類算法分析　58
3.4.5　模板向量類的一般表示　61
3.5　模板向量容器的測試類　62
3.5.1　模板向量測試類的數(shù)據輸入　62
3.5.2　模板向量測試類的源代碼　63
3.5.3　模板向量測試類的使用　66
3.6　矩陣類　67
3.6.1　矩陣容器的描述　68
3.6.2　模板矩陣類的使用　69
習題　71
第4章　鏈表　73
4.1　鏈表存儲結構的基本知識　73
4.1.1　單鏈表與指針　73
4.1.2　單鏈表的基本運算　75
4.2　簡易的單鏈表類　79
4.2.1　單鏈表類源代碼　79
4.2.2　單鏈表類的測試　80
4.3　循環(huán)鏈表和雙向鏈表　82
4.3.1　循環(huán)鏈表　82
4.3.2　雙向鏈表　82
4.4　標準模板雙向鏈表類　83
4.4.1　模板鏈表類的一般表示　84
4.4.2　構造器　84
4.4.3　模板鏈表類的迭代器　85
4.4.4　模板鏈表類的成員函數(shù)　87
4.5　模板鏈表容器的測試類　89
4.5.1　模板鏈表測試類的數(shù)據輸入　89
4.5.2　模板鏈表測試類的源代碼　89
4.5.3　模板鏈表測試類的使用　93
習題　95
第5章　棧和隊列　97
5.1　?！?7
5.1.1　棧的定義及運算　97
5.1.2　棧的向量存儲結構　98
5.1.3　簡易向量棧類　98
5.1.4　棧的鏈表存儲結構　102
5.1.5　簡易鏈表棧類　103
5.2　模板棧容器　108
5.2.1　模板棧容器的實現(xiàn)　108
5.2.2　棧的接口　109
5.2.3　使用棧容器　110
5.3　隊列的基本知識　115
5.3.1　隊列的定義及運算　115
5.3.2　隊列的向量存儲結構　116
5.3.3　簡易的循環(huán)隊列類　117
5.3.4　隊列的鏈表存儲結構　120
5.4　模板隊列容器　124
5.4.1　deque容器　124
5.4.2　queue容器　125
習題　128
第6章　字符串　133
6.1　字符與字符串的概念　133
6.2　C風格字符串的存儲結構與運算　134
6.2.1　C風格字符串的順序存儲結構　134
6.2.2　C風格字符串的鏈表存儲結構　135
6.2.3　C風格字符串的運算　136
6.3　字符串類　138
6.3.1　字符串類對象的聲明　139
6.3.2　字符串類的構造器　140
6.3.3　字符串類的運算　141
6.4　模板容器與字符串類　144
習題　148
第7章　查找　151
7.1　查找方法概述　151
7.2　順序查找　152
7.2.1　簡單順序查找方法　152
7.2.2　一般線性表的順序查找　153
7.3　有序表的查找　156
7.3.1　有序表的建立　156
7.3.2　有序表的折半查找法　157
7.3.3　折半查找法的應用　161
7.4　標準模板庫的查找算法　164
7.4.1　STL迭代器　164
7.4.2　STL查找運算　165
7.5　哈希表及其查找　169
7.5.1　哈希表與哈希函數(shù)　169
7.5.2　設計哈希函數(shù)　171
7.5.3　閉散列方法　173
7.5.4　哈希類的向量版本　176
7.5.5　開散列方法與哈希類的鏈表版本　179
習題　183
第8章　排序　187
8.1　排序基本概念　187
8.2　3種基本的排序方法　188
8.2.1　直接插入排序　188
8.2.2　冒泡排序　189
8.2.3　選擇排序　191
8.2.4　基本排序方法的向量版本　192
8.3　高級排序方法　194
8.3.1　希爾排序　194
8.3.2　快速排序　195
8.3.3　歸并排序　198
8.3.4　基數(shù)排序　200
8.4　標準模板庫的通用排序方法　202
習題　209
第9章　樹　212
9.1　二叉樹　212
9.1.1　樹的常用術語　212
9.1.2　二叉樹的定義　213
9.1.3　二叉樹的重要性質　213
9.1.4　二叉樹的存儲結構　214
9.2　遍歷二叉樹　215
9.2.1　先根遍歷　216
9.2.2　中根遍歷　217
9.2.3　后根遍歷　218
9.2.4　按層遍歷　219
9.2.5　二叉樹遍歷算法的應用　220
9.3　二叉鏈表模板類　221
9.3.1　二叉鏈表類的輸入類　222
9.3.2　二叉鏈表類的模板結點類　222
9.3.3　二叉鏈表基類　223
9.3.4　二叉鏈表類派生的應用類　228
9.4　二叉搜索樹模板類　231
9.4.1　二叉搜索樹的基本知識　231
9.4.2　定位函數(shù)與查找算法的實現(xiàn)　235
9.4.3　二叉搜索樹類及其測試　237
9.4.4　二叉搜索樹插入算法與刪除算法的實現(xiàn)　240
9.4.5　輸出二叉樹結點表算法的實現(xiàn)　245
習題　248
第10章　圖　250
10.1　圖的基本概念和術語　250
10.1.1　圖的概念　250
10.1.2　路徑和回路　251
10.1.3　連通圖　251
10.1.4　頂點的度　252
10.2　圖的存儲結構　252
10.2.1　鄰接矩陣　252
10.2.2　基于鄰接矩陣的模板圖類　253
10.2.3　鄰接鏈表　258
10.2.4　基于鄰接鏈表的模板圖類　259
10.3　圖的遍歷及其應用　264
10.3.1　圖的深度優(yōu)先搜索遍歷　265
10.3.2　圖的廣度優(yōu)先搜索遍歷　268
10.3.3　圖遍歷的應用　269
10.3.4　圖的遍歷類　272
10.4　圖的生成樹　276
10.4.1　生成樹的概念　276
10.4.2　最小生成樹　277
10.4.3　Prim算法　280
10.4.4　Kruskal算法　284
10.5　最短路徑　288
10.5.1　單源頂點最短路徑問題求解　289
10.5.2　關于源點最短路徑的討論　292
習題　294