數(shù)據(jù)結(jié)構(gòu)學習指導與習題解答（C++語言版）

第1章 C++復習 1
1.1 標準C++程序設計語言 1
1.2 條件語句 3
1.3 運算符 5
1.4 迭代 8
1.5 函數(shù) 10
1.6 字符串 12
1.7 文件 14
復習題 15
練習題 16
復習題答案 18
練習題答案 20
第2章 指針與數(shù)組 32
2.1 指針 32
2.2 派生類型 34
2.3 引用 35
2.4 按引用傳遞 35
2.5 空指針異常 37
2.6 new和delete運算符 38
2.7 數(shù)組 39
2.8 動態(tài)數(shù)組 40
2.9 把數(shù)組傳遞給函數(shù) 41
2.10 多維數(shù)組 42
復習題 43
練習題 44
復習題答案 46
練習題答案 47
第3章 類 60
3.1 Point類 60
3.2 實例、隱式形參和this指針 63
3.3 編譯類及其客戶程序 64
3.4 友元函數(shù) 68
3.5 Line類 68
3.6 用于隨機數(shù)的類 71
3.7 靜態(tài)成員 73
3.8 復合 75
3.9 繼承 78
復習題 81
練習題 82
復習題答案 85
練習題答案 87
第4章 遞歸 98
4.1 階乘函數(shù) 98
4.2 跟蹤遞歸調(diào)用 99
4.3 斐波納契數(shù)列 99
4.4 二項式系數(shù) 101
4.5 歐幾里得算法 102
4.6 正確性的歸納證明 103
4.7 遞歸算法的復雜度分析 104
4.8 動態(tài)程序設計 105
4.9 漢諾塔 105
4.10 相互遞歸 107
復習題 108
練習題 108
復習題答案 110
練習題答案 111
第5章 棧 119
5.1 stack接口 119
5.2 使用stack對象 119
5.3 棧的應用 121
5.4 消除遞歸 124
5.5 連續(xù)實現(xiàn) 126
5.6 鏈表實現(xiàn) 129
復習題 133
練習題 134
復習題答案 135
練習題答案 136
第6章 隊列 142
6.1 queue接口 142
6.2 使用queue對象 142
6.3 隊列的應用 144
6.4 連續(xù)實現(xiàn) 149
6.5 鏈表實現(xiàn) 153
復習題 155
練習題 156
復習題答案 157
練習題答案 157
第7章 鏈表 164
7.1 list接口 164
7.2 使用list對象 165
7.3 迭代器 166
7.4 應用 168
7.5 循環(huán)鏈表 173
7.6 有序鏈表 176
7.7 不受限制的Integer類 177
7.8 List類的實現(xiàn) 183
復習題 188
練習題 189
復習題答案 191
練習題答案 192
第8章 表 200
8.1 標準的pair類型 200
8.2 使用map類模板的應用 202
8.3 散列表 207
8.4 散列函數(shù) 212
8.5 單獨串接 215
復習題 219
練習題 219
復習題答案 219
練習題答案 220
第9章 樹 224
9.1 樹的術語 224
9.2 決策樹和轉(zhuǎn)換圖 226
9.3 樹遍歷算法 230
9.4 Tree類的接口 231
9.5 Tree類的實現(xiàn) 234
復習題 238
練習題 240
復習題答案 244
練習題答案 245
第10章 二叉樹 259
10.1 定義 259
10.2 統(tǒng)計二叉樹 261
10.3 完整二叉樹 262
10.4 恒等、相等和同構(gòu) 263
10.5 完全二叉樹 264
10.6 樹遍歷 266
10.7 表達式樹 268
10.8 森林 270
10.9 BinaryTree類的接口 271
10.10 BinaryTree類的實現(xiàn) 274
復習題 278
練習題 279
復習題答案 282
練習題答案 283
第11章 查找樹 291
11.1 二叉查找樹 291
11.2 二叉查找樹的實現(xiàn) 293
11.3 二叉查找樹的性能特征 296
11.4 AVL樹 297
復習題 300
練習題 300
復習題答案 301
練習題答案 301
第12章 堆和優(yōu)先級隊列 305
12.1 堆 305
12.2 自然映射 305
12.3 插入到堆中 307
12.4 從堆中刪除 308
12.5 優(yōu)先級隊列 309
12.6 使用priority_queue對象 309
12.7 使用堆實現(xiàn)PriorityQueue類模板 311
12.8 優(yōu)先級隊列的實現(xiàn) 313
復習題 318
練習題 318
復習題答案 319
練習題答案 319
第13章 排序 322
13.1 基礎知識 322
13.2 冒泡排序 323
13.3 選擇排序 324
13.4 插入排序 325
13.5 歸并排序 327
13.6 快速排序 330
13.7 堆 331
13.8 堆排序 332
13.9 希爾排序 337
13.10 比較排序的速度限制 338
復習題 338
練習題 338
復習題答案 340
練習題答案 340
附錄A 參考資料 344
附錄B 必要的數(shù)學知識 353
B.1 下取整函數(shù)和上取整函數(shù) 353
B.2 對數(shù) 353
B.3 數(shù)學歸納法的第一定律 354
B.4 數(shù)學歸納法的第二定律 355
B.5 幾何級數(shù) 356
B.6 求和公式 357
B.7 漸近復雜度等級 357
B.8 調(diào)和數(shù) 358
B.9 斯特靈公式 360
B.10 斐波納契數(shù)字 361
B.11 黃金分割率 361
B.12 歐幾里得算法 363
附錄C 標準容器類 365
C.1 vector類模板 365
C.2 deque類模板 372
C.3 stack類模板 372
C.4 queue類模板 372
C.5 priority_queue類模板 373
C.6 list類模板 374
C.7 map類模板 377
C.8 set類模板 379
附錄D 泛型算法 382
附錄E 示例類 417
E.1 BinaryTree類 417
E.2 BinarySearchTree類 425
E.3 Card類 427
E.4 Concordance類 430
E.5 Date類 432
E.6 Deck類 440
E.7 Hand類 441
E.8 Hash函數(shù)結(jié)構(gòu)模板 442
E.9 HashTable類模板 442
E.10 Line類 445
E.11 List類模板 447
E.12 Matrix類模板 454
E.13 OrderedList類 456
E.14 Person類 456
E.15 Point類 460
E.16 Polynomial類 463
E.17 PriorityQueue類模板 470
E.18 Purse類 472
E.19 Queue類 474
E.20 Random類 476
E.21 RandomLine類 477
E.22 RandomPoint類 477
E.23 Ratio類 478
E.24 Rational類 481
E.25 SelfOrganizingList類 484
E.26 Stack類模板 484
E.27 Tree類 486