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

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