目　　录
Introduction to C++ Programming and Data Structures, Fifth Edition
译者序
前言
作者简介
第17章　递归　1
17.1　简介　1
17.2　案例研究：计算阶乘　2
17.3　案例研究：斐波那契数　5
17.4　使用递归解决问题　7
17.5　递归辅助函数　9
17.5.1　选择排序　10
17.5.2　二分查找　12
17.6　汉诺塔　13
17.7　八皇后问题　16
17.8　递归与迭代　19
17.9　尾递归　19
关键术语　21
章节总结　21
编程练习　21
第18章　开发高效算法　30
18.1　简介　30
18.2　使用大O表示法衡量算法效率　30
18.3　示例：确定大O　32
18.4　分析算法时间复杂度　34
18.4.1　分析二分查找　35
18.4.2　分析选择排序　35
18.4.3　分析汉诺塔问题　35
18.4.4　常见的递归关系　36
18.4.5　比较常见的增长函数　36
18.5　使用动态规划求斐波那契数　37
18.6　使用欧几里得算法求最大
公约数　39
18.7　寻找质数的高效算法　43
18.8　使用分治法寻找最近点对　51
18.9　使用回溯法解决八皇后问题　53
18.10　案例研究：寻找凸包　56
18.10.1　礼品包装算法　57
18.10.2　Graham算法　58
18.11　字符串匹配　59
18.11.1　Boyer-Moore算法　61
18.11.2　Knuth-Morris-Pratt算法　64
关键术语　67
章节总结　68
编程练习　68
第19章　排序　74
19.1　简介　74
19.2　插入排序　74
19.3　冒泡排序　77
19.4　归并排序　79
19.5　快速排序　82
19.6　堆排序　86
19.6.1　存储堆　86
19.6.2　添加新节点　87
19.6.3　删除根　89
19.6.4　Heap类　92
19.6.5　使用Heap类进行排序　94
19.6.6　堆排序的时间复杂度　95
19.7　桶排序和基数排序　96
19.8　外部排序　97
19.8.1　实现第一阶段　99
19.8.2　实现第二阶段　100
19.8.3　合成两个阶段　102
19.8.4　外部排序复杂度　107
关键术语　107
章节总结　107
编程练习　107
第20章　链表、队列和优先级队列　109
20.1　简介　109
20.2　节点　109
20.3　LinkedList类　112
20.4　实现LinkedList　114
20.4.1　实现addFirst
(T element)　115
20.4.2　实现addLast
(T element)　116
20.4.3　实现add(int index,
T element)　118
20.4.4　实现removeFirst()　119
20.4.5　实现removeLast()　120
20.4.6　实现removeAt
(int index)　122
20.4.7　LinkedList的源代码　123
20.4.8　LinkedList的时间
复杂度　129
20.5　迭代器　130
20.6　C++11 foreach循环　133
20.7　链表的变体　135
20.8　队列　135
20.9　优先级队列　138
关键术语　141
章节总结　141
编程练习　141
第21章　二叉查找树　144
21.1　简介　144
21.2　二叉查找树基础知识　144
21.3　表示二叉查找树　145
21.4　访问二叉查找树中的节点　146
21.5　查找元素　146
21.6　将元素插入二叉查找树　146
21.7　树的遍历　148
21.8　BST类　150
21.9　删除二叉查找树中的元素　160
21.10　BST的迭代器　165
21.11　案例研究：数据压缩　167
关键术语　172
章节总结　172
编程练习　173
第22章　STL容器　174
22.1　简介　174
22.2　STL基础　174
22.3　STL迭代器　179
22.3.1　迭代器的类型　181
22.3.2　迭代器运算符　182
22.3.3　预定义迭代器　184
22.3.4　istream_iterator和ostream_iterator　185
22.4　C++11自动类型推断　187
22.5　序列容器　187
22.5.1　序列容器：vector　188
22.5.2　序列容器：deque　189
22.5.3　序列容器：list　191
22.6　关联容器　194
22.6.1　关联容器：set和
multiset　195
22.6.2　关联容器：map和
multimap　196
22.7　容器适配器　198
22.7.1　容器适配器：stack　198
22.7.2　容器适配器：queue　200
22.7.3　容器适配器：priority_
queue　201
关键术语　202
章节总结　203
编程练习　203
第23章　STL算法　207
23.1　简介　207
23.2　算法类型　208
23.3　copy函数　209
23.4　fill和fill_n　211
23.5　将函数作为参数传递　212
23.6　generate和generate_n　215
23.7　remove、remove_if、remove_copy和remove_copy_if　216
23.8　replace、replace_if、replace_
copy和replace_copy_if　220
23.9　find、find_if、find_end和
find_first_of　223
23.10　search和search_n　227
23.11　sort和binary_search　229
23.12　adjacent_find、merge和inplace_merge　231
23.13　reverse和reverse_copy　233
23.14　rotate和rotate_copy　234
23.15　swap、iter_swap和swap_ranges　236
23.16　count和count_if　237
23.17　max_element和min_
element　238
23.18　random_shuffle　239
23.19　for_each和transform　240
23.20　includes、set_union、set_difference、set_intersection和set_symmetric_difference　242
23.21　accumulate、adjacent_difference、inner_product和partial_sum　244
23.22　lambda表达式　247
23.23　新的C++11 STL算法　250
关键术语　251
章节总结　251
编程练习　252
第24章　散列　254
24.1　简介　254
24.2　散列是什么　254
24.3　散列函数和散列码　255
24.3.1　基元类型的散列码　255
24.3.2　字符串的散列码　256
24.3.3　压缩散列码　256
24.4　用开放寻址处理冲突　257
24.4.1　线性探测　257
24.4.2　平方探测　258
24.4.3　双重散列　258
24.5　用独立链处理冲突　259
24.6　负载因子和再散列　259
24.7　用散列实现映射　260
24.8　用散列实现集合　268
关键术语　275
章节总结　275
编程练习　275
第25章　AVL树　277
25.1　简介　277
25.2　再平衡树　278
25.3　设计AVL树类　279
25.4　重写insert函数　280
25.5　实现旋转　281
25.6　实现remove函数　282
25.7　AVLTree类　282
25.8　测试AVLTree类　288
25.9　AVL树的时间复杂度分析　291
关键术语　292
章节总结　292
编程练习　292
第26章　图及其应用　294
26.1　简介　294
26.2　基本图术语　295
26.3　图的表示　296
26.3.1　顶点的表示　296
26.3.2　边的表示（用于输入）：
边数组　297
26.3.3　边的表示（用于输入）：
Edge对象　298
26.3.4　边的表示：邻接矩阵　299
26.3.5　边的表示：邻接列表　299
26.4　Graph类　301
26.5　图遍历　311
26.6　深度优先搜索　314
26.6.1　深度优先搜索算法　314
26.6.2　深度优先搜索的实现　315
26.6.3　DFS的应用　318
26.7　广度优先搜索　318
26.7.1　广度优先搜索算法　318
26.7.2　广度优先搜索的实现　319
26.7.3　BFS的应用　321
26.8　案例研究：九枚硬币翻转问题　322
关键术语　328
章节总结　328
编程练习　329
第27章　加权图及其应用　332
27.1　简介　332
27.2　加权图的表示　333
27.2.1　加权边的表示：边数组　333
27.2.2　加权相邻列表　333
27.3　WeightedGraph类　335
27.4　最小生成树　341
27.4.1　最小生成树算法　342
27.5　寻找最短路径　350
27.6　案例研究：加权九枚硬币
翻转问题　359
关键术语　363
章节总结　363
编程练习　363
附录A　C++关键字　367
附录B　ASCII字符集　368
附录C　运算符优先级表　369
附录D　数字系统　371
附录E　按位运算　375
附录F　使用命令行参数　376
附录G　枚举类型　379
附录H　正则表达式　383
附录I　大O、大Omega和大Theta
表示法　390