C++数据结构与算法（第四版）

图书标准信息

• 作者 Adam Drozdek 著；徐丹、吴伟敏 译
• 出版社 清华大学出版社
• 出版时间 2014-10
• 版次 4
• ISBN 9787302376682
• 定价 79.80元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 610页
• 字数 1066千字
• 正文语种 简体中文
• 原版书名 Data Structures and Algorithms in C++

【内容简介】

　　这本《C++数据结构与算法(第4版)》全面系统地介绍了数据结构，并以C++语言实现相关的算法。
　　主要强调了数据结构和算法之间的联系，使用面向对象的方法介绍数据结构，其内容包括算法的复杂度分析、链表、栈、队列、递归、二叉树、图、排序和散列。本书还清晰地阐述了同类教材中较少提到的内存管理、数据压缩和字符串匹配等主题。书中包含大量的示例分析和图形，便于读者进一步理解和巩固所学的知识。

【作者简介】

　　AdamDrozdek毕业于美国莱特州立大学，现任迪尤肯大学计算机科学系副教授，出版过多部数据结构和算法方面的专业书籍，包括本书和DataStructuresandAlgorithmsinJava等。

【目录】

第1章C++面向对象程序设计1
1.1抽象数据类型1
1.2封装1
1.3继承5
1.4指针7
1.4.1指针与数组10
1.4.2指针与复制构造函数12
1.4.3指针与析构函数14
1.4.4指针和引用变量14
1.4.5函数指针17
1.5多态性18
1.6C++和面向对象程序设计20
1.7标准模板库20
1.7.1容器21
1.7.2迭代器21
1.7.3算法21
1.7.4函数对象22
1.8标准模板库中的向量24
1.9数据结构与面向对象编程29
1.10案例分析：随机访问文件30
1.11习题38
1.12编程练习40
参考书目42
第2章复杂度分析43
2.1计算复杂度以及渐近复杂度43
2.2大O表示法44
2.3大O表示法的性质46
2.4Ω表示法与Θ表示法47
2.5可能存在的问题48
2.6复杂度示例49
2.7确定渐近复杂度示例50
2.8最好、平均和最坏情况51
2.9摊销复杂度(amortizedcomplexity)54
2.10NP完整性57
2.11习题59
参考书目61
第3章链表63
3.1单向链表63
3.1.1插入68
3.1.2删除70
3.1.3查找74
3.2双向链表74
3.3循环链表78
3.4跳跃链表(skiplist)79
3.5自组织链表83
3.6稀疏表87
3.7标准模板库中的链表89
3.8小结92
3.9案例分析：图书馆93
3.10习题101
3.11编程练习102
参考书目105
第4章栈与队列107
4.1栈107
4.2队列113
4.3优先队列119
4.4标准模板库中的栈119
4.5标准模板库中的队列120
4.6标准模板库中的优先队列121
4.7标准模版库中的双端队列123
4.8案例分析：迷宫问题127
4.9习题131
4.10编程练习133
参考书目134
第5章递归135
5.1递归定义135
5.2函数调用与递归实现137
5.3分析递归调用139
5.4尾递归142
5.5非尾递归142
5.6间接递归147
5.7嵌套递归148
5.8不合理递归149
5.9回溯152
5.10小结157
5.11案例分析：递归下降解释器158
5.12习题165
5.13编程练习167
参考书目169
第6章二叉树171
6.1树、二叉树和二叉查找树171
6.2二叉树的实现174
6.3二叉查找树的查找176
6.4树的遍历179
6.4.1广度优先遍历179
6.4.2深度优先遍历180
6.4.3不使用栈的深度优先遍历186
6.5插入191
6.6删除193
6.6.1合并删除194
6.6.2复制删除196
6.7树的平衡198
6.7.1DSW算法200
6.7.2AVL树202
6.8自适应树(self-adjustingtree)207
6.8.1自重新构造树(self-restructuringtree)207
6.8.2“张开”策略(splaying)208
6.9堆212
6.9.1将堆作为优先队列213
6.9.2用数组实现堆215
6.10treap树218
6.11k-d树221
6.12波兰表示法和表达式树225
6.13案例分析：计算单词出现的频率229
6.14习题235
6.15编程练习239
参考书目242
第7章多叉树245
7.1B树家族245
7.1.1B树247
7.1.2B*树254
7.1.3B+树255
7.1.4前缀B+树257
7.1.5k-dB树259
7.1.6位树264
7.1.7R树265
7.1.82-4树267
7.1.9标准模板库中的集合(set)以及多重集合(multiset)278
7.1.10标准模板库中的映射(map)和多映射(multimap)282
7.2trie286
7.3小结292
7.4案例分析：拼写检查器292
7.5习题300
7.6编程练习301
参考书目304
第8章图307
8.1图的表示法308
8.2图的遍历309
8.3最短路径312
8.4环的检测319
8.5生成树322
8.6连通性324
8.6.1无向图中的连通性324
8.6.2有向图中的连通性326
8.7拓扑排序328
8.8网络329
8.8.1最大流329
8.8.2成本最低的最大流337
8.9匹配340
8.9.1稳定匹配问题344
8.9.2分配问题346
8.9.3非二分图中的匹配集合348
8.10欧拉(Eulerian)图与汉密尔顿(Hamiltonian)图349
8.10.1欧拉图349
8.10.2汉密尔顿图352
8.11图的上色问题356
8.12图论中的NP完整性问题359
8.12.1派系问题359
8.12.2三色问题360
8.12.3顶点覆盖问题361
8.12.4汉密尔顿环问题361
8.13案例分析：唯一代表363
8.14习题372
8.15编程练习376
参考书目377
第9章排序381
9.1基本的排序算法382
9.1.1插入排序382
9.1.2选择排序384
9.1.3冒泡排序386
9.1.4梳排序388
9.2决策树389
9.3高效排序算法392
9.3.1希尔排序392
9.3.2堆排序395
9.3.3快速排序397
9.3.4归并排序402
9.3.5基数排序405
9.3.6计数排序408
9.4标准模板库中的排序410
9.5小结414
9.6案例分析：多项式相加414
9.7习题420
9.8编程练习422
参考书目423
第10章散列427
10.1散列函数427
10.1.1除余法428
10.1.2折叠法428
10.1.3平方取中法429
10.1.4提取法429
10.1.5基数转换法429
10.1.6全域散列法429
10.2冲突解决方法430
10.2.1开放定址法430
10.2.2链接法435
10.2.3桶定址436
10.3删除437
10.4理想散列函数438
10.4.1Cichelli方法438
10.4.2FHCD算法440
10.5再散列442
10.6可扩展文件的散列函数444
10.6.1可扩展散列445
10.6.2线性散列446
10.7案例分析：使用桶的散列449
10.8习题456
10.9编程练习457
参考书目458
第11章数据压缩461
11.1数据压缩的条件461
11.2Huffman编码463
11.3Run-Length编码方式473
11.4Ziv-Lempel编码方式474
11.5案例分析：Huffman方法和Run-Length编码方式476
11.6习题485
11.7编程练习486
参考书目487
第12章内存管理489
12.1sequential-fit方法490
12.2nonsequential-fit方法491
12.3垃圾回收497
12.3.1标记和清除498
12.3.2复制方法504
12.3.3递增的垃圾回收505
12.3.4分代垃圾回收510
12.4小结513
12.5案例分析514
12.6习题521
12.7编程练习522
参考书目524
第13章字符串匹配527
13.1字符串的精确匹配527
13.1.1简单的算法527
13.1.2Knuth-Morris-Pratt算法530
13.1.3Boyer-Moore算法536
13.1.4多次搜索545
13.1.5面向位的方法546
13.1.6单词集合的匹配550
13.1.7正则表达式的匹配555
13.1.8后缀trie和树558
13.1.9后缀数组563
13.2字符串的模糊匹配564
13.2.1字符串的近似性565
13.2.2有k个错误的字符串匹配570
13.3案例分析：最长的共有子字符串573
13.4习题580
13.5编程练习581
参考书目582
附录A计算大O585
附录B标准模板库中的算法591
附录CNP完整性599