本書是ford和topp兩位教授于1996年出版的名著data structures with c++的第2版，新版中引入了在ansi c 1998中正式規(guī)定的標(biāo)準(zhǔn)模板庫(kù)（stl）來(lái)講授數(shù)據(jù)結(jié)構(gòu)，在全球范圍內(nèi)已經(jīng)有數(shù)以萬(wàn)計(jì)的學(xué)生從中受益。 作者將c++語(yǔ)言作為算法描述語(yǔ)言，應(yīng)用包含規(guī)范化的數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)模板庫(kù)，集中講述了數(shù)組、向量、表、關(guān)聯(lián)樹容器，以及集合、映射、堆、哈希表和圖等數(shù)據(jù)結(jié)構(gòu)及其算法，重點(diǎn)討論了如何高效地存儲(chǔ)大型數(shù)據(jù)集合，涵蓋了數(shù)據(jù)結(jié)構(gòu)初級(jí)和高級(jí)教程的最新內(nèi)容。書中各章章前提出學(xué)習(xí)目標(biāo)，章后附有豐富的練習(xí)題、答案以及書面練習(xí)和上機(jī)編程練習(xí)，指導(dǎo)讀者迅速、全面地掌握核心知識(shí)點(diǎn)和編程技巧。 本書可作為計(jì)算機(jī)及相關(guān)專業(yè)數(shù)據(jù)結(jié)構(gòu)課程的核心教材，對(duì)于廣大研發(fā)人員，也是一本數(shù)據(jù)結(jié)構(gòu)與面向?qū)ο蠹夹g(shù)完整結(jié)合的全新技術(shù)參考用書。
目錄
第1章 數(shù)據(jù)結(jié)構(gòu)入門 1
1.1 本書主要內(nèi)容 1
數(shù)據(jù)結(jié)構(gòu)和算法 4
1.2 數(shù)據(jù)結(jié)構(gòu)的抽象形式 4
time24 adt 5
1.3 作為類的adt 6
1.3.1 c++類 6
1.3.2 private 和 public部分 7
1.3.3 封裝和信息隱藏 7
1.3.4 time24類 7
1.4 實(shí)現(xiàn)c++類 10
1.5 聲明和使用對(duì)象 14
1.6 使用嵌入碼實(shí)現(xiàn)類 16
1.7 應(yīng)用程序編程接口（api） 18
1.7.1 隨機(jī)數(shù) 19
1.7.2 randomnumber api 19
1.7.3 應(yīng)用程序：擲骰子游戲 21
1.8 字符串 23
1.8.1 字符串類 24
1.8.2 附加字符串函數(shù)和操作 25
.1.9 本章小結(jié) 29
1.10 本章使用的類和庫(kù) 30
1.11 復(fù)習(xí)題 31
1.12 書面作業(yè) 35
1.13 上機(jī)題 41
1.14 項(xiàng)目設(shè)計(jì) 44
第2章 對(duì)象設(shè)計(jì)技術(shù) 46
2.1 軟件設(shè)計(jì) 47
2.1.1 需求和問(wèn)題分析 48
2.1.2 程序設(shè)計(jì) 48
2.1.3 設(shè)計(jì)日歷類 49
2.1.4 程序?qū)崿F(xiàn) 52
2.1.5 實(shí)現(xiàn)日歷類 52
2.1.6 程序測(cè)試與調(diào)試 54
2.1.7 程序維護(hù) 57
2.2 處理運(yùn)行時(shí)錯(cuò)誤 57
2.2.1 終止程序 57
2.2.2 設(shè)置標(biāo)志 58
2.2.3 c++異常 59
2.3 對(duì)象復(fù)合 62
2.3.1 timecard類 63
2.3.2 實(shí)現(xiàn)timecard類 64
2.4 運(yùn)算符重載 68
2.4.1 運(yùn)算符函數(shù) 71
2.4.2 自由函數(shù)的運(yùn)算符重載 72
2.4.3 友元函數(shù)的運(yùn)算符重載 72
2.4.4 重載數(shù)據(jù)流i/o運(yùn)算符 75
2.4.5 成員函數(shù)重載 78
2.5 本章小結(jié) 81
2.6 本章使用的類和庫(kù) 82
2.7 復(fù)習(xí)題 82
2.8 書面作業(yè) 86
2.9 上機(jī)題 90
2.10 項(xiàng)目設(shè)計(jì) 91
第3章 算法概述 96
3.1 選擇排序 97
3.2 簡(jiǎn)單查找算法 101
3.2.1 順序查找 101
3.2.2 二分查找 103
3.3 算法分析 108
3.3.1 系統(tǒng)/內(nèi)存性能標(biāo)準(zhǔn) 108
3.3.2 算法性能標(biāo)準(zhǔn)：時(shí)間復(fù)雜度分析 108
3.3.3 大ο符號(hào) 111
3.3.4 常見(jiàn)數(shù)量級(jí) 112
3.4 分析查找算法 114
3.4.1 二分查找時(shí)間復(fù)雜度 114
3.4.2 查找算法比較 115
3.5 算法的通用性 118
3.5.1 模板語(yǔ)法 119
3.5.2 運(yùn)行時(shí)模板擴(kuò)展 120
3.5.3 基于模板的查找函數(shù) 122
3.6 遞歸的概念 123
3.6.1 實(shí)現(xiàn)遞歸函數(shù) 125
3.6.2 遞歸的工作方式 127
3.6.3 應(yīng)用：多進(jìn)制輸出 129
3.7 用遞歸解決問(wèn)題 131
3.7.1 漢諾塔 131
3.7.2 數(shù)論：最大公約數(shù) 134
3.7.3 gcd的應(yīng)用：有理數(shù) 136
3.7.4 計(jì)算遞歸式 139
3.8 本章小結(jié) 142
3.9 本章使用的類和庫(kù) 143
3.10 復(fù)習(xí)題 143
3.11 書面作業(yè) 147
3.12 上機(jī)題 153
3.13 項(xiàng)目設(shè)計(jì) 156
第4章 向量容器 157
4.1 stl容器類概述 158
4.2 模板類 161
4.2.1 構(gòu)造模板類 161
4.2.2 聲明模板類對(duì)象 163
4.3 向量類 164
4.3.1 向量容器入門 166
4.3.2 向量api 171
4.4 向量應(yīng)用 173
4.4.1 合并向量 173
4.4.2 插入排序 173
4.5 本章小結(jié) 177
4.6 本章使用的類和庫(kù) 178
4.7 復(fù) 習(xí) 題 178
4.8 書面作業(yè) 181
4.9 上機(jī)題 186
4.10 項(xiàng)目設(shè)計(jì) 187
第5章 指針和動(dòng)態(tài)內(nèi)存 188
5.1 c++指針 189
5.1.1 聲明指針變量 190
5.1.2 指針賦值 190
5.1.3 用指針訪問(wèn)數(shù)據(jù) 191
5.1.4 數(shù)組和指針 192
5.1.5 指針和類類型 194
5.2 動(dòng)態(tài)內(nèi)存 196
5.2.1 內(nèi)存分配運(yùn)算符new 196
5.2.2 動(dòng)態(tài)數(shù)組分配 198
5.2.3 內(nèi)存釋放運(yùn)算符delete 199
5.3 使用動(dòng)態(tài)內(nèi)存的類 200
5.3.1 dynamicclass類 200
5.3.2 析構(gòu)函數(shù) 202
5.4 賦值和初始化 204
5.4.1 賦值問(wèn)題 205
5.4.2 重載的賦值運(yùn)算符 206
5.4.3 指針 this 207
5.4.4 初始化問(wèn)題 207
5.4.5 創(chuàng)建復(fù)制構(gòu)造函數(shù) 208
5.5 minivector類 211
5.5.1 minivector類的設(shè)計(jì) 212
5.5.2 分配更多的容量 214
5.5.3 minivector的構(gòu)造函數(shù)、析構(gòu)函數(shù)和賦值 215
5.5.4 從minivector對(duì)象中增加和刪除元素 217
5.5.5 重載下標(biāo)運(yùn)算符 220
5.6 矩陣類 222
5.6.1 描述矩陣容器 223
5.6.2 實(shí)現(xiàn)矩陣函數(shù) 226
5.7 本章小結(jié) 227
5.8 本章中的類和庫(kù) 227
5.9 復(fù)習(xí)題 228
5.10 書面作業(yè) 231
5.11 上機(jī)題 238
5.12 項(xiàng)目設(shè)計(jì) 239
第6章 表容器和迭代器 241
6.1 表容器 242
6.1.1 表 adt 243
6.1.2 表api 245
6.1.3 應(yīng)用：表回文 246
6.2 迭代器 248
6.2.1 迭代器的概念 248
6.2.2 常量迭代器 251
6.2.3 順序查找表 252
6.2.4 應(yīng)用：詞的出現(xiàn)頻率 255
6.3 表插入和刪除操作 258
6.3.1 有序表 260
6.3.2 刪除重復(fù)項(xiàng) 262
6.3.3 合并兩個(gè)表 264
6.4 實(shí)例研究：畢業(yè)生表 265
6.4.1 問(wèn)題分析 265
6.4.2 程序設(shè)計(jì) 265
6.4.3 程序?qū)崿F(xiàn) 266
6.5 本章小結(jié) 269
6.6 本章使用的類和庫(kù) 270
6.7 復(fù)習(xí)題 270
6.8 書面作業(yè) 273
6.9 上機(jī)題 276
6.10 項(xiàng)目設(shè)計(jì) 279
第7章 棧 281
7.1 棧adt 282
7.1.1 多進(jìn)制輸出 285
7.1.2 分解棧元素 288
7.2 遞歸代碼和運(yùn)行棧 291
7.3 棧 的 實(shí) 現(xiàn) 294
7.3.1 ministack類的實(shí)現(xiàn) 296
7.3.2 stl stack類的實(shí)現(xiàn)（選學(xué)） 297
7.4 后綴表達(dá)式 298
7.4.1 后綴計(jì)算 299
7.4.2 postfixeval類 300
7.5 實(shí)例研究：中綴表達(dá)式計(jì)算 306
7.5.1 中綴表達(dá)式的特征 307
7.5.2 中綴到后綴的轉(zhuǎn)換：算法設(shè)計(jì) 308
7.5.3 中綴轉(zhuǎn)換為后綴：對(duì)象設(shè)計(jì) 311
7.5.3 中綴轉(zhuǎn)換為后綴：對(duì)象設(shè)計(jì) 312
7.5.4 infix2postfix類的實(shí)現(xiàn) 314
7.6 本章小結(jié) 318
7.7 本章使用的類 319
7.8 復(fù)習(xí)題 319
7.9 書面作業(yè) 323
7.10 上機(jī)題 327
7.11 項(xiàng)目設(shè)計(jì) 328
第8章 隊(duì)列和優(yōu)先級(jí)隊(duì)列 330
8.1 隊(duì)列adt 331
8.2 基數(shù)排序 335
8.3 實(shí)現(xiàn)miniqueue類 339
8.4 實(shí)例研究：時(shí)間驅(qū)動(dòng)的模擬 343
8.4.1 模擬程序設(shè)計(jì) 343
8.4.2 模擬程序的具體實(shí)現(xiàn) 344
8.5 用數(shù)組實(shí)現(xiàn)隊(duì)列 349
8.5.1 設(shè)計(jì)有界隊(duì)列 351
8.5.2 有界隊(duì)列的實(shí)現(xiàn) 353
8.6 優(yōu)先級(jí)隊(duì)列 354
8.6.1 優(yōu)先級(jí)隊(duì)列adt 355
8.6.2 優(yōu)先級(jí)隊(duì)列排序 357
8.6.3 公司內(nèi)的支持服務(wù) 358
8.7 本章小結(jié) 362
8.8 本章使用的類和庫(kù) 363
8.9 復(fù)習(xí)題 363
8.10 書面作業(yè) 367
8.11 上機(jī)題 371
8.12 項(xiàng)目設(shè)計(jì) 373
第9章 鏈表 376
9.1 鏈表結(jié)點(diǎn) 378
9.1.1 鏈表結(jié)點(diǎn)類 378
9.1.2 添加和刪除結(jié)點(diǎn) 381
9.2 建立鏈表 382
9.2.1 定義單向鏈表 382
9.2.2 在鏈表表頭插入結(jié)點(diǎn) 384
9.2.3 在鏈表表頭刪除結(jié)點(diǎn) 385
9.2.4 刪除特定的結(jié)點(diǎn) 386
9.3 處理鏈表表尾 389
9.4 用鏈表實(shí)現(xiàn)隊(duì)列 393
9.4.1 linkedqueue類 393
9.4.2 實(shí)現(xiàn)linkedqueue類 395
9.5 雙向鏈表 398
9.5.1 dnode對(duì)象 399
9.5.2 雙向循環(huán)鏈表 401
9.6 更新雙向鏈表 403
9.6.1 insert()函數(shù) 404
9.6.2 erase()函數(shù) 405
9.7 約瑟夫問(wèn)題 409
9.8 minilist類 411
9.8.1 minilist類的私有成員 412
9.8.2 minilist類的構(gòu)造函數(shù)和析構(gòu)函數(shù) 413
9.8.3 處理表兩端元素的函數(shù) 414
9.8.4 minilist的迭代器 415
9.8.5 minilist類成員函數(shù)begin()和end() 417
9.8.6 minilist類的通用插入函數(shù) 418
9.9 選擇順序容器 419
9.10 本 章 小 結(jié) 419
9.11 本章使用的類和庫(kù) 421
9.12 復(fù) 習(xí) 題 421
復(fù)習(xí)題答案 425
9.13 書 面 作 業(yè) 427
9.14 上 機(jī) 題 430
9.15 項(xiàng) 目 設(shè) 計(jì) 431
第10章 二叉樹 434
10.1 樹結(jié)構(gòu) 435
10.1.1 術(shù)語(yǔ) 436
10.1.2 二叉樹 437
10.2 二叉樹結(jié)點(diǎn) 440
建立二叉樹 441
10.3 二叉樹遍歷算法 443
10.3.1 遞歸的樹遍歷 443
10.3.2 迭代層次遍歷 446
10.4 使用樹遍歷算法 450
10.4.1 葉結(jié)點(diǎn)計(jì)數(shù) 450
10.4.2 計(jì)算樹的深度 450
10.4.3 復(fù)制二叉樹 453
10.4.4 刪除樹結(jié)點(diǎn) 456
10.4.5 顯示二叉樹 457
10.5 二叉搜索樹 458
10.5.1 二叉搜索樹概述 459
10.5.2 創(chuàng)建二叉搜索樹 459
10.5.3 二叉搜索樹中的數(shù)據(jù)查找 460
10.5.4 二叉搜索樹的刪除 461
10.5.5 二叉搜索樹類 462
10.5.6 訪問(wèn)和更新操作 463
10.6 二叉搜索樹的應(yīng)用 467
10.6.1 應(yīng)用：消除重復(fù)項(xiàng) 467
10.6.2 應(yīng)用：錄像帶商店 469
10.7 stree類的實(shí)現(xiàn) 474
10.7.1 stree類數(shù)據(jù)成員 475
10.7.2 構(gòu)造函數(shù)、析構(gòu)函數(shù)和賦值運(yùn)算符 475
10.7.3 更新操作 476
10.7.4 二叉搜索樹的算法復(fù)雜度 483
10.8 stree迭代器（選學(xué)） 483
10.9 本章小結(jié) 488
10.10 本章使用的類和庫(kù) 489
10.11 復(fù)習(xí)題 489
10.12 書面作業(yè) 494
10.13 上機(jī)題 497
10.14 項(xiàng)目設(shè)計(jì) 499
第11章 關(guān)聯(lián)容器 503
11.1 關(guān)聯(lián)容器概述 503
11.1.1 關(guān)聯(lián)容器的種類 504
11.1.2 stl關(guān)聯(lián)容器 506
11.1.3 實(shí)現(xiàn)關(guān)聯(lián)容器 506
11.2 集合 507
11.2.1 使用迭代器顯示容器元素 508
11.2.2 集合的訪問(wèn)和更新函數(shù) 508
11.2.3 簡(jiǎn)單的拼寫檢查程序 511
11.2.4 應(yīng)用：埃拉托斯特尼篩法 514
11.2.5 集合運(yùn)算 517
11.2.6 應(yīng)用：更新計(jì)算機(jī)賬號(hào) 520
11.3 映射 522
11.3.1 map類接口 523
11.3.2 映射的操作函數(shù) 525
11.3.3 映射的下標(biāo)運(yùn)算符 526
11.3.4 實(shí)例學(xué)習(xí)：?jiǎn)卧~統(tǒng)計(jì) 529
11.4 多重集 534
11.5 實(shí)現(xiàn)集合和映射 538
11.5.1 實(shí)現(xiàn)miniset的操作函數(shù) 539
11.5.2 minimap類 540
11.5.3 實(shí)現(xiàn)minimap類 542
11.5.4 minimap的下標(biāo)運(yùn)算符 543
11.6 本章小結(jié) 543
11.7 本章使用的類和庫(kù) 544
11.8 復(fù)習(xí)題 545
11.9 書面作業(yè) 548
11.10 上 機(jī) 題 551
11.11 項(xiàng) 目 設(shè) 計(jì) 552
第12章 高級(jí)關(guān)聯(lián)結(jié)構(gòu) 555
12.1 哈 希 法 557
使用哈希函數(shù) 557
12.2 設(shè)計(jì)哈希函數(shù) 559
12.2.1 函數(shù)對(duì)象 559
12.2.2 函數(shù)對(duì)象舉例 561
12.2.3 整型哈希函數(shù) 563
12.2.4 字符串哈希函數(shù) 564
12.2.5 定制哈希函數(shù) 565
12.3 哈希表 566
12.3.1 線性探測(cè)開(kāi)放尋址法 566
12.3.2 獨(dú)立表鏈地址法 568
12.4 hash類 569
12.4.1 應(yīng)用：使用哈希表 571
12.4.2 hash類的實(shí)現(xiàn) 574
12.4.3 實(shí)現(xiàn)哈希迭代器 577
12.4.4 無(wú)序關(guān)聯(lián)容器 580
12.5 哈希表的性能 581
12.6 2-3-4樹 586
12.6.1 2-3-4樹的插入算法 588
12.6.2 2-3-4樹操作函數(shù)的時(shí)間復(fù)雜度 591
12.7 紅黑樹 592
12.7.1 紅黑樹的屬性 593
12.7.2 向紅黑樹中添加結(jié)點(diǎn) 595
12.7.3 構(gòu)造紅黑樹 599
12.7.4 查找算法的時(shí)間復(fù)雜度（選學(xué)） 601
12.7.5 從紅黑樹中刪除結(jié)點(diǎn) 602
12.8 rbtree類 603
12.8.1 rbtree類的私有部分 606
12.8.2 拆分4-結(jié)點(diǎn) 606
12.8.3 insert()操作函數(shù) 608
12.9 本章小結(jié) 609
12.10 本章用到的類和庫(kù) 610
12.11 復(fù)習(xí)題 610
12.12 書面作業(yè) 615
12.13 上機(jī)題 621
12.14 項(xiàng)目設(shè)計(jì) 623
第13章 繼承和抽象類 625
13.1 c++中的繼承 626
13.1.1 聲明員工層次關(guān)系 628
13.1.2 派生類的構(gòu)造函數(shù) 631
13.1.3 實(shí)現(xiàn)成員函數(shù) 632
13.2 圖形層次 635
13.2.1 circleshape類 637
13.2.2 其他圖形類和文本類 639
13.2.3 polyshape類的實(shí)現(xiàn) 641
13.3 圖形系統(tǒng) 644
13.4 安全向量 647
13.5 有序表 649
13.6 多態(tài)屬性和虛函數(shù) 651
13.6.1 動(dòng)態(tài)綁定 653
13.6.2 應(yīng)用：用多態(tài)性機(jī)制編寫支付員工薪金的程序 655
13.6.3 c++的多態(tài)實(shí)現(xiàn) 657
13.6.4 虛函數(shù)和析構(gòu)函數(shù) 659
13.7 抽象類 661
13.7.1 抽象類接口 662
13.7.2 棧接口 662
13.8 本章小結(jié) 663
13.9 本章使用的類和庫(kù) 664
13.10 復(fù)習(xí)題 664
13.11 書面作業(yè) 669
13.12 上機(jī)題 675
13.13 項(xiàng)目設(shè)計(jì) 677
第14章 堆、二進(jìn)制文件和位組 679
14.1 基于數(shù)組的二叉樹 680
14.2 堆 681
14.2.1 堆的插入操作 682
14.2.2 從堆中刪除元素 684
14.2.3 堆排序 688
14.2.4 向量堆化 691
14.3 優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn) 693
minipq類的實(shí)現(xiàn) 695
14.4 二進(jìn)制文件 696
14.4.1 文件結(jié)構(gòu) 696
14.4.2 直接讀寫文件 697
14.4.3 讀寫二進(jìn)制文件 698
14.4.4 應(yīng)用：銀行賬戶記錄 698
14.5 位組 702
14.5.1 bitvector類 703
14.5.2 實(shí)現(xiàn)bitvector類 706
14.6 實(shí)例研究：霍夫曼壓縮 709
14.6.1 創(chuàng)建霍夫曼樹 712
14.6.2 霍夫曼壓縮的實(shí)現(xiàn) 714
14.6.3 霍夫曼解壓縮 720
14.7 本章小結(jié) 722
14.8 本章使用的類和庫(kù) 724
14.9 復(fù)習(xí)題 724
14.10 書面作業(yè) 728
14.11 上機(jī)題 735
14.12 項(xiàng)目設(shè)計(jì) 738
第15章 遞歸算法 740
15.1 分而治之算法 741
15.1.1 創(chuàng)建標(biāo)尺 741
15.1.2 歸并排序 743
15.1.3 快速排序 750
15.1.4 排序算法的比較 758
15.1.5 應(yīng)用：搜索第k大的元素 760
15.2 組合學(xué) 762
15.2.1 查找所有子集 763
15.2.2 排列 766
15.3 動(dòng)態(tài)編程 769
15.3.1 自頂向下的動(dòng)態(tài)編程 770
15.3.2 應(yīng)用：組合 772
15.3.3 自底向上動(dòng)態(tài)編程 774
15.3.4 背包問(wèn)題 775
15.4 回溯法：八皇后問(wèn)題 782
15.4.1 問(wèn)題分析 783
15.4.2 程序設(shè)計(jì) 785
15.4.3 顯示棋盤 788
15.4.4 八皇后問(wèn)題實(shí)例分析 789
15.5 本章小結(jié) 790
15.6 本章使用的類和庫(kù) 791
15.7 復(fù)習(xí)題 792
15.8 書面作業(yè) 797
15.9 上機(jī)題 800
15.10 項(xiàng)目設(shè)計(jì) 804
第16章 圖 807
16.1 圖論術(shù)語(yǔ) 808
16.1.1 有向圖 809
16.1.2 加權(quán)圖 810
16.2 圖類 810
16.2.1 圖的api清單 810
16.2.2 圖的表示 815
16.3 圖類設(shè)計(jì) 816
16.3.1 頂點(diǎn)信息表示 817
16.3.2 頂點(diǎn)映射和vinfo表 818
16.3.3 圖類聲明 821
16.3.4 圖類的實(shí)現(xiàn) 822
16.4 圖的遍歷算法 826
16.4.1 廣度優(yōu)先搜索算法 827
16.4.2 深度優(yōu)先訪問(wèn)算法 830
16.4.3 深度優(yōu)先搜索 834
16.5 圖遍歷的應(yīng)用 835
16.5.1 無(wú)環(huán)圖 835
16.5.2 拓?fù)渑判?838
16.5.3 強(qiáng)連通分量 841
16.6 圖的最小化算法 845
16.6.1 最短路徑算法 845
16.6.2 dijkstra最小路徑算法 849
16.6.3 最小生成樹 855
16.7 本章小結(jié) 862
16.8 本章使用的類和庫(kù) 862
16.9 復(fù)習(xí)題 863
16.10 書面作業(yè) 865
16.11 上機(jī)題 873
16.12 項(xiàng)目設(shè)計(jì) 874