目 录
Introduction to C++ Programming and Data Structures, Fifth Edition
第17章 递归 1
17.1 简介 1
17.2 案例研究：计算阶乘 2
17.3 案例研究：斐波那契数 8
17.4 使用递归解决问题 12
17.5 递归辅助函数 16
17.5.1 选择排序 18
17.5.2 二分查找 20
17.6 汉诺塔 22
17.7 八皇后问题 26
17.8 递归与迭代 30
17.9 尾递归 31
关键术语 34
章节总结 35
编程练习 35
第18章 开发高效算法 46
18.1 简介 47
18.2 使用大O表示法衡量算法效率 47
18.3 示例：确定大O 50
18.4 分析算法时间复杂度 56
18.4.1 分析二分查找 56
18.4.2 分析选择排序 57
18.4.3 分析汉诺塔问题 58
18.4.4 常见的递归关系 59
18.4.5 比较常见的增长函数 59
18.5 使用动态规划求斐波那契数 63
18.6 使用欧几里得算法求最大
公约数 66
18.7 寻找质数的高效算法 72
18.8 使用分治法寻找最近点对 81
18.9 使用回溯法解决八皇后问题 84
18.10 案例研究：寻找凸包 88
18.10.1 礼品包装算法 89
18.10.2 Graham算法 90
18.11 字符串匹配 92
18.11.1 Boyer-Moore算法 95
18.11.2 Knuth-Morris-Pratt算法 98
关键术语 102
章节总结 103
编程练习 104
第19章 排序 111
19.1 简介 111
19.2 插入排序 112
19.3 冒泡排序 115
19.4 归并排序 117
19.5 快速排序 123
19.6 堆排序 127
19.6.1 存储堆 129
19.6.2 添加新节点 130
19.6.3 删除根 131
19.6.4 Heap类 134
19.6.5 使用Heap类进行排序 137
19.6.6 堆排序的时间复杂度 139
19.7 桶排序和基数排序 140
19.8 外部排序 143
19.8.1 实现第一阶段 145
19.8.2 实现第二阶段 146
19.8.3 合成两个阶段 149
19.8.4 外部排序复杂度 150
关键术语 151
章节总结 151
编程练习 151
第20章 链表、队列和优先级队列 154
20.1 简介 154
20.2 节点 155
20.3 LinkedList类 159
20.4 实现LinkedList 163
20.4.1 实现addFirst
(T element) 164
20.4.2 实现addLast
(T element) 165
20.4.3 实现add(int index,
T element) 166
20.4.4 实现removeFirst() 168
20.4.5 实现removeLast() 170
20.4.6 实现removeAt
(int index) 171
20.4.7 LinkedList的源代码 173
20.4.8 LinkedList的时间
复杂度 175
20.5 迭代器 179
20.6 C++11 foreach循环 184
20.7 链表的变体 186
20.8 队列 189
20.9 优先级队列 192
关键术语 196
章节总结 196
编程练习 197
第21章 二叉查找树 200
21.1 简介 200
21.2 二叉查找树基础知识 201
21.3 表示二叉查找树 202
21.4 访问二叉查找树中的节点 204
21.5 查找元素 204
21.6 将元素插入二叉查找树 206
21.7 树的遍历 208
21.8 BST类 210
21.9 删除二叉查找树中的元素 216
21.10 BST的迭代器 224
21.11 案例研究：数据压缩 227
关键术语 232
章节总结 233
编程练习 233
第22章 STL容器 236
22.1 简介 236
22.2 STL基础 237
22.3 STL迭代器 243
22.3.1 迭代器的类型 245
22.3.2 迭代器运算符 246
22.3.3 预定义迭代器 248
22.3.4 istream_iterator和ostream_iterator 250
22.4 C++11自动类型推断 252
22.5 序列容器 253
22.5.1 序列容器：vector 254
22.5.2 序列容器：deque 257
22.5.3 序列容器：list 259
22.6 关联容器 263
22.6.1 关联容器：set和
multiset 263
22.6.2 关联容器：map和
multimap 265
22.7 容器适配器 269
22.7.1 容器适配器：stack 269
22.7.2 容器适配器：queue 270
22.7.3 容器适配器：priority_
queue 272
关键术语 274
章节总结 275
编程练习 276
第23章 STL算法 280
23.1 简介 281
23.2 算法类型 282
23.3 copy函数 284
23.4 fill和fill_n 287
23.5 将函数作为参数传递 289
23.6 generate和generate_n 293
23.7 remove、remove_if、
remove_copy和
remove_copy_if 295
23.8 replace、replace_if、replace_copy和
replace_copy_if 299
23.9 find、find_if、find_end和
find_first_of 303
23.10 search和search_n 309
鄂公网安备 42010302001612号 