《C++與數據結構（第3版）》是2015年電子工業出版社出版的圖書，作者是高飛、薛艷明。
基本介紹
- 書名：C++與數據結構（第3版）
- 作者：高飛、薛艷明
- ISBN：9787121256837
- 頁數：308
- 出版社：電子工業出版社
- 出版時間：2015-03
- 開本：16(185*260)
內容簡介,目錄,
內容簡介
本書是國家級（網路教育）精品課程的教學成果，也是北京市高等教育精品教材，根據教育部計算機基礎課程教學指導委員會《計算機基礎課程教學基本要求》中，有關理工類專業“算法基礎與程式設計”課程要求組織編寫。本書內容由淺入深，案例豐富，通俗易懂，實用性強。 本書在介紹了C++語言的程式設計方法的基礎上，採用面向對象的思想和抽象數據類型的概念，用C++語言有效地組織和描述了線性表、堆疊、佇列、樹和圖等各種典型的數據結構和相關類的實現，並介紹了每種數據結構的不同存儲方法、典型操作及其套用。 全書共 10 章，包括數據結構的基本概念，數組與指針，C++編程基礎，STL 標準模版庫，線性表，堆疊、佇列和遞歸，樹與二叉樹，圖，查找與散列結構，排序等。本書各章配有習題和實驗訓練題，方便實踐教學，並為任課教師提供電子課件和示例原始碼。 本書可作為高等院校電子信息類以及其他相關專業本科生教材和教學參考書，也可供從事程式設計工程人員參考使用。
目錄
第1 章數據結構的基本概念···1
1.1 數據結構的概念和術語···1
1.2 抽象數據類型···3
1.2.1 數據類型···3
1.2.2 數據抽象與抽象數據類型···4
1.3 算法和算法分析···5
1.3.1 算法···5
1.3.2 算法設計的要求···5
1.3.3 算法效率的度量···6
1.4 面向對象概述···8
1.4.1 面向對象的思想···8
1.4.2 面向對象的基本概念···9
1.4.3 面向對象的基本特性···10
1.4.4 面向對象程式設計···12
1.4.5 面向對象的語言···12
1.5 本章小結···13
習題1 ···13
第2 章數組與指針···14
2.1 數組···14
2.1.1 一維數組···14
2.1.2 多維數組···17
2.1.3 字元數組和字元串···21
2.2 指針···24
2.2.1 指針的概念···24
2.2.2 指針變數定義···25
2.2.3 指針運算···25
2.3 指針與數組···27
2.3.1 指向數組的指針···27
2.3.2 指向字元串的指針···31
2.3.3 指針數組和指向指針的指針···31
2.4 指針與函式···34
2.4.1 指向函式的指針···34
·VI· Page
2.4.2 返回指針值的函式···36
2.5 本章小結···36
習題2 ···37
實驗訓練2···37
第3 章 C++編程基礎···39
3.1 C++語言簡介···39
3.2 類···39
3.2.1 訪問控制···40
3.2.2 成員函式···42
3.2.3 構造函式與析構函式···44
3.2.4 動態存儲···50
3.3 豐富的特性···53
3.3.1 引用···53
3.3.2 友元···59
3.3.3 重載···63
3.4 代碼重用機制···67
3.4.1 繼承···67
3.4.2 多態···72
3.4.3 模板···76
3.5 本章小結···81
習題3 ···81
實驗訓練3···82
第4 章 STL 標準模板庫···89
4.1 STL 簡介···89
4.2 序列式容器···90
4.2.1 vector 容器···90
4.2.2 使用疊代器···92
4.2.3 list 容器···93
4.3 關聯式容器···95
4.3.1 pair 類型···95
4.3.2 map 容器···97
4.3.3 set 容器···98
4.4 本章小結···100
習題4 ···101
實驗訓練4···101
第5 章線性表··· 103
5.1 線性表的定義···103
5.1.1 線性表的邏輯結構···103
5.1.2 線性表的抽象類定義···104
5.2 線性表的順序表示和實現···105
5.2.1 線性表的順序表示···105
5.2.2 順序表類的定義···105
5.2.3 順序表類的實現···106
5.3 線性表的鏈式表示和實現···110
5.3.1 線性表的鏈式表示···110
5.3.2 抽象鍊表類的定義···110
5.3.3 抽象鍊表類各成員函式的實現···112
5.4 單鍊表···113
5.4.1 單鍊表的結構···113
5.4.2 單鍊表類的定義···113
5.4.3 單鍊表的常用成員函式的實現···114
5.4.4 單鍊表舉例—一元多項式加法···117
5.5 循環鍊表···120
5.5.1 循環鍊表的定義···120
5.5.2 循環鍊表類的定義···120
5.5.3 循環鍊表常用函式的實現···121
5.5.4 循環鍊表舉例—約瑟夫問題···124
5.6 雙向鍊表···125
5.6.1 雙向鍊表的定義···125
5.6.2 雙向鍊表類的定義···126
5.6.3 雙向鍊表的常用成員函式的實現···127
5.7 本章小結···130
習題5 ···131
實驗訓練5···131
第6 章堆疊、佇列和遞歸··· 133
6.1 堆疊的概念及其運算···133
6.2 抽象堆疊類的定義···134
6.3 堆疊的定義及其實現···135
6.3.1 順序棧的定義···135
6.3.2 順序棧類的定義及典型成員函式的實現···135
6.3.3 多棧共享空間問題···138
6.3.4 鏈棧的定義···139
6.3.5 鏈式棧類的定義及典型成員函式的實現···140
6.4 堆疊的套用舉例···143
6.4.1 數制轉換···143
6.4.2 一個趣味遊戲—迷宮問題···144
6.5 佇列的概念及其運算···147
6.6 抽象佇列類的定義···148
6.7 佇列的定義及其實現···148
6.7.1 佇列的順序存儲結構···148
6.7.2 循環佇列的定義···150
6.7.3 順序循環佇列類的定義及常用成員函式的實現···150
6.7.4 鏈式佇列的定義···153
6.7.5 鏈式佇列類的定義及常用成員函式的實現···153
6.7.6 鏈式佇列的套用舉例···156
6.7.7 優先權佇列的定義···157
6.7.8 優先權佇列類的定義及常用成員函式的實現···158
6.8 遞歸···161
6.8.1 遞歸的概念···161
6.8.2 遞歸的套用···162
6.8.3 遞歸在計算機中的實現···163
6.8.4 遞歸問題的非遞歸算法···165
6.9 本章小結···168
習題6 ···168
實驗訓練6···169
第7 章樹與二叉樹··· 171
7.1 樹、二叉樹和森林的基本概念···171
7.1.1 樹···171
7.1.2 二叉樹···173
7.1.3 樹與森林的存儲結構···177
7.2 二叉樹的抽象類和樹的類···181
7.2.1 二叉樹的抽象類···181
7.2.2 樹的類···186
7.3 二叉樹的遍歷和樹的遍歷···192
7.3.1 二叉樹的遍歷···192
7.3.2 樹的遍歷···195
7.4 二叉排序樹···198
7.5 二叉樹的計數···203
7.6 哈夫曼樹及其套用···204
7.6.1 最優二叉樹（哈夫曼樹）···204
7.6.2 哈夫曼編碼···205
7.7 本章小結···206
習題7 ···206
實驗訓練7···208
第8 章圖 ··· 209
8.1 圖的基本概念···209
8.1.1 圖的定義···209
8.1.2 圖的術語···210
8.1.3 圖的基本操作···212
8.1.4 圖的存儲表示···213
8.2 圖的抽象類···217
8.2.1 圖的鄰接矩陣類···217
8.2.2 圖的鄰接表類···222
8.3 圖的遍歷···228
8.3.1 深度優先搜尋DFS···228
8.3.2 廣度（或寬度）優先搜尋BFS···229
8.4 圖的連通性與最小生成樹···230
8.4.1 無向圖的連通分量和生成樹···230
8.4.2 最小生成樹···231
8.4.3 關節點和重連通分量···235
8.5 最短路徑···237
8.5.1 圖結點的可達性···238
8.5.2 從某個源點到其餘各頂點的最短路徑···239
8.5.3 每一對頂點之間的最短路徑···241
8.6 活動網路···243
8.6.1 用頂點表示活動的網路（AOV 網路） ···243
8.6.2 用邊表示活動的網路（AOE 網路）···244
8.7 本章小結···246
習題8 ···246
實驗訓練8···248
第9 章查找與散列結構··· 250
9.1 基本概念···250
9.2 靜態查找表···251
9.2.1 順序表的查找···251
9.2.2 有序表的查找···253
9.2.3 索引順序表的查找···255
9.3 動態查找表···256
9.4 Hash 表及其查找···258
9.4.1 Hash 表···258
9.4.2 Hash 函式的構造方法···259
9.4.3 處理衝突的方法···262
9.4.4 Hash 表的查找及其分析···264
9.5 本章小結···266
習題9 ···266
實驗訓練9···267
第10 章排序··· 269
10.1 排序的基本概念···269
10.2 插入排序···271
10.2.1 直接插入排序···271
10.2.2 其他插入排序···273
10.2.3 希爾排序···276
10.3 快速排序···277
10.4 選擇排序···280
10.4.1 簡單選擇排序···280
10.4.2 錦標賽排序···281
10.4.3 堆排序···284
10.5 歸併排序···289
10.5.1 歸併···289
10.5.2 疊代的歸併排序算法···290
10.6 基數排序···291
10.6.1 多關鍵字排序···291
10.6.2 鏈式基數排序···292
10.7 本章小結···294
習題10 ···295
實驗訓練10···295
參考文獻··· 297
