第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.3 C++語言簡介 18
1.3.1 C++的産生與發展 18
1.3.2 C++與麵嚮對象思想 20
1.3.3 C++中的類和對象 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.1 STL簡介 94
2.5.2 STL構成 95
2.5.3 STL的不同版本 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.1 C++中的字符串 124
3.3.2 字符串抽象數據類型 126
3.3.3 字符串的匹配算法 128
3.3.4 字符串指數問題 141
3.4 動態內存管理 142
3.4.1 關鍵詞new和delete 143
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.3 Vigenere加密問題 182
4.3.4 選美比賽問題 184
4.4 遊標類的設計與實現 186
4.4.1 遊標類的結構 186
4.4.2 遊標類的實現 187
4.5 STL與鏈錶 191
4.5.1 STL中鏈錶類的接口 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.4 STL中的棧與隊列 222
5.4.1 STL中的stack 222
5.4.2 STL中的queue 224
5.4.3 STL中的priority_queue 226
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.1 STL中的vector 317
7.6.2 STL中的map 321
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.2 AVL樹 403
9.2.1 AVL樹的概念 404
9.2.2 AVL樹的鏇轉 405
9.2.3 AVL樹的實現 410
9.3 紅黑樹 418
9.3.1 紅黑樹的概念 418
9.3.2 紅黑樹的操作 421
9.3.3 紅黑樹的實現 428
9.4 Trie樹 433
9.4.1 Trie樹的概念 433
9.4.2 Trie樹的錶示 434
9.4.3 Trie樹的實現 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.6 STL中的set 490
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.2 Shaker排序 514
11.4.3 快速排序 517
11.5 歸並排序 522
11.6 計數排序 526
11.7 本章小結 531
參考文獻 532
· · · · · · (收起)