第1章緒論1
1.1數據與數據結構2
1.1.1數據及其類型2
1.1.2數據結構簡介4
1.2算法6
1.2.1算法的概念6
1.2.2算法的分析8
1.2.3算法的設計12
1.3C++語言簡介18
1.3.1C++的產生與發展18
1.3.2C++與面向對象思想20
1.3.3C++中的類和對象23
1.4本章小結28
第2章C++編程基礎29
2.1開始C++編程30
2.1.1輸入輸出30
2.1.2預處理38
2.1.3名字空間44
2.2深入的類編程50
2.2.1訪問控制50
2.2.2初始化與清除53
2.2.3動態創建對象57
2.2.4友元函數60
2.2.5拷貝構造函數61
2.3豐富的C++特性65
2.3.1常量65
2.3.2函數重載68
2.3.3運算符重載71
2.3.4異常處理77
2.4代碼重用機制79
2.4.1繼承80
2.4.2多態87
2.4.3模板90
2.5標準模板庫93
2.5.1STL簡介94
2.5.2STL構成95
2.5.3STL的不同版本97
2.6本章小結98
第3章指針、數組與字符串99
3.1指針100
3.1.1指針的概念100
3.1.2指針的語法102
3.1.3函數與參數傳遞103
3.2數組108
3.2.1數組定義與初始化109
3.2.2數組與指針113
3.2.3數組的抽象數據類型116
3.2.4大整數乘法問題120
3.2.5荷蘭國旗問題121
3.3字符串124
3.3.1C++中的字符串124
3.3.2字符串抽象數據類型126
3.3.3字符串的匹配算法128
3.3.4字符串指數問題141
3.4動態內存管理142
3.4.1關鍵詞new和delete143
3.4.2避免內存錯誤146
3.5本章小結152
第4章鏈表153
4.1單向鏈表154
4.1.1單向鏈表的結構154
4.1.2單向鏈表類的實現155
4.1.3有序鏈表的合並162
4.1.4多項式加法問題163
4.2單向循環鏈表164
4.2.1單向循環鏈表的結構164
4.2.2單向循環鏈表類的實現166
4.2.3約瑟夫問題169
4.2.4魔術師發牌問題170
4.2.5拉丁方陣問題172
4.3雙向循環鏈表173
4.3.1雙向循環鏈表的結構173
4.3.2雙向循環鏈表類的實現174
4.3.3Vigenere加密問題182
4.3.4選美比賽問題184
4.4遊標類的設計與實現186
4.4.1遊標類的結構186
4.4.2遊標類的實現187
4.5STL與鏈表191
4.5.1STL中鏈表類的接口191
4.5.2遍歷194
4.5.3元素的插入與刪除196
4.6本章小結196
第5章棧與隊列197
5.1棧198
5.1.1棧的結構198
5.1.2棧的實現199
5.1.3括號匹配問題203
5.1.4停車場模擬問題204
5.2隊列208
5.2.1隊列的結構208
5.2.2隊列的實現210
5.2.3舞伴問題214
5.2.4楊輝三角形問題215
5.2.5遊程編碼問題216
5.3優先級隊列218
5.3.1優先級隊列的結構218
5.3.2優先級隊列的實現220
5.4STL中的棧與隊列222
5.4.1STL中的stack222
5.4.2STL中的queue224
5.4.3STL中的priority_queue226
5.5本章小結229
第6章遞歸231
6.1遞歸的概念232
6.1.1遞歸的定義232
6.1.2應用遞歸的原則235
6.1.3遞歸和非遞歸的轉化240
6.2分治法243
6.2.1分治法簡述243
6.2.2漢諾塔問題244
6.2.3傳染病問題246
6.3回溯法250
6.3.1回溯法簡述251
6.3.2迷宮問題251
6.3.3八皇後問題255
6.3.4騎士周遊問題258
6.4本章小結265
第7章樹267
7.1樹的概念268
7.1.1樹的定義268
7.1.2樹的術語271
7.1.3樹的抽象數據類型272
7.2二叉樹273
7.2.1二叉樹的定義273
7.2.2二叉樹的性質275
7.2.3二叉樹的實現276
7.2.4二叉樹的遍歷285
7.2.5二叉樹的線索化289
7.3樹與森林291
7.3.1樹的存儲表示291
7.3.2樹的實現294
7.3.3樹與森林的遍歷298
7.3.4森林與二叉樹的轉換300
7.4霍夫曼樹304
7.4.1霍夫曼樹的概念304
7.4.2霍夫曼樹的構造方法305
7.4.3霍夫曼編碼及其實現307
7.5堆313
7.5.1堆的概念314
7.5.2堆的建立314
7.5.3堆的操作316
7.6基於STL實現樹結構317
7.6.1STL中的vector317
7.6.2STL中的map321
7.7醫院建模問題323
7.8本章小結328
第8章圖329
8.1圖的基本概念330
8.1.1圖的定義330
8.1.2圖的術語331
8.1.3圖的運算334
8.1.4圖的抽象數據類型336
8.2圖的存儲與表示337
8.2.1圖的鄰接矩陣表示337
8.2.2圖的鄰接表表示339
8.2.3兩種表示法的比較342
8.3圖的遍歷342
8.3.1歐拉路徑與歐拉回路343
8.3.2哈密爾頓路徑與哈密爾頓回路345
8.3.3廣度優先遍歷346
8.3.4深度優先遍歷349
8.4最短路徑問題353
8.4.1固定起點最短路問題353
8.4.2非固定起點最短路問題355
8.4.3最短路徑的動態規劃解法358
8.4.4旅遊交通路線問題364
8.5最小生成樹372
8.5.1最小生成樹的定義372
8.5.2克魯斯卡爾算法373
8.5.3普裏姆算法375
8.6經典問題舉例379
8.6.1文字遊戲問題380
8.6.2道路修建問題382
8.6.3回家路線問題385
8.6.4水塘計算問題387
8.6.5棍子還原問題389
8.7本章小結392
第9章樹形搜索結構393
9.1二叉搜索樹394
9.1.1二叉搜索樹的概念394
9.1.2二叉搜索樹的操作395
9.1.3二叉搜索樹的實現397
9.1.4二叉搜索樹的分析400
9.2AVL樹403
9.2.1AVL樹的概念404
9.2.2AVL樹的旋轉405
9.2.3AVL樹的實現410
9.3紅黑樹418
9.3.1紅黑樹的概念418
9.3.2紅黑樹的操作421
9.3.3紅黑樹的實現428
9.4Trie樹433
9.4.1Trie樹的概念433
9.4.2Trie樹的表示434
9.4.3Trie樹的實現435
9.5本章小結439
第10章集合與字典441
10.1集合論基礎442
10.1.1集合的概念442
10.1.2集合的運算444
10.2集合的實現445
10.2.1位向量集合445
10.2.2鏈表集合451
10.3字典460
10.3.1字典的概念461
10.3.2搜索運算463
10.4散列467
10.4.1散列的概念467
10.4.2散列函數469
10.4.3處理散列沖突471
10.4.4散列的應用475
10.5經典問題舉例476
10.5.1拼寫檢查問題476
10.5.2無線網絡問題485
10.5.3第K個數問題488
10.6STL中的set490
10.7本章小結493
第11章排序495
11.1排序問題概述496
11.1.1基本概念和定義496
11.1.2排序算法的分類497
11.1.3排序算法分析與選擇497
11.2插入排序498
11.2.1直接插入排序498
11.2.2二分法插入排序501
11.2.3希爾排序503
11.3選擇排序506
11.3.1直接選擇排序506
11.3.2堆排序508
11.4交換排序512
11.4.1冒泡法排序512
11.4.2Shaker排序514
11.4.3快速排序517
11.5歸並排序522
11.6計數排序526
11.7本章小結531
參考文獻533
……