目　　录
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
23.11　sort和binary_search　311
23.12　adjacent_find、merge和inplace_merge　315
23.13　reverse和reverse_copy　317
23.14　rotate和rotate_copy　319
23.15　swap、iter_swap和swap_ranges　321
23.16　count和count_if　323
23.17　max_element和
min_element　324
23.18　random_shuffle　325
23.19　for_each和transform　327
23.20　includes、set_union、set_difference、set_intersection和set_symmetric_difference　329
23.21　accumulate、adjacent_difference、inner_product和partial_sum　
23.22　lambda表达式　334
23.23　新的C++11 STL算法　338
关键术语　341
章节总结　343
编程练习　345
第24章　散列　346
24.1　简介　348
24.2　散列是什么　348
24.3　散列函数和散列码　350
24.3.1　基元类型的散列码　350
24.3.2　字符串的散列码　351
24.3.3　压缩散列码　351
24.4　用开放寻址处理冲突　354
24.4.1　线性探测　354
24.4.2　平方探测　355
24.4.3　双重散列　357
24.5　用独立链处理冲突　360
24.6　负载因子和再散列　361
24.7　用散列实现映射　362
24.8　用散列实现集合　369
关键术语　374
章节总结　375
编程练习　375
第25章　AVL树　377
25.1　简介　377
25.2　再平衡树　379
25.3　设计AVL树类　382
25.4　重写insert函数　384
25.5　实现旋转　386
25.6　实现remove函数　387
25.7　AVLTree类　389
25.8　测试AVLTree类　392
25.9　AVL树的时间复杂度分析　397
关键术语　397
章节总结　398
编程练习　398
第26章　图及其应用　400
26.1　简介　400
26.2　基本图术语　402
26.3　图的表示　405
26.3.1　顶点的表示　406
26.3.2　边的表示（用于输入）：
边数组　407
26.3.3　边的表示（用于输入）：
Edge对象　408
26.3.4　边的表示：邻接矩阵　408
26.3.5　边的表示：邻接列表　409
26.4　Graph类　413
26.5　图遍历　420
26.6　深度优先搜索　422
26.6.1　深度优先搜索算法　422
26.6.2　深度优先搜索的实现　424
26.6.3　DFS的应用　426
26.7　广度优先搜索　428
26.7.1　广度优先搜索算法　428
26.7.2　广度优先搜索的实现　429
26.7.3　BFS的应用　431
26.8　案例研究：九枚硬币翻转问题　432
关键术语　440
章节总结　441
编程练习　441
第27章　加权图及其应用　445
27.1　简介　445
27.2　加权图的表示　447
27.2.1　加权边的表示：边数组　447
27.2.2　加权相邻列表　448
27.3　WeightedGraph类　450
27.4　最小生成树　457
27.4.1　最小生成树算法　457
27.5　寻找最短路径　465
27.6　案例研究：加权九枚硬币
翻转问题　472
关键术语　477
章节总结　477
编程练习　477
附录A　C++关键字　482
附录B　ASCII字符集　484
附录C　运算符优先级表　486
附录D　数字系统　487
附录E　按位运算　494
附录F　使用命令行参数　497
附录G　枚举类型　501
附录H　正则表达式　506
附录??I?　大O、大Omega和大Theta
表示法　515

Contents
17: Recursion　1
17.1: Introduction　1
17.2: Case Study: Computing Factorials　2
17.3: Case Study: Fibonacci Numbers　8
17.4: Problem Solving Using Recursion　12
17.5: Recursive Helper Functions　16
17.5.1: Selection Sort　18
17.5.2: Binary Search　20
17.6: Towers of Hanoi　22
17.7: Eight Queens　26
17.8: Recursion versus Iteration　30
17.9: Tail Recursion　31
Key Terms　34
Chapter Summary　35
Programming Exercises　35
18: Developing Efficient
Algorithms　46
18.1: Introduction　47
18.2: Measuring Algorithm Efficiency
Using Big O Notation　47
18.3: Examples: Determining Big O　50
18.4: Analyzing Algorithm Time
Complexity　56
18.4.1: Analyzing Binary Search　56
18.4.2: Analyzing Selection Sort　57
18.4.3: Analyzing the Towers of Hanoi
Problem　58
18.4.4: Common Recurrence
Relations　59
18.4.5: Comparing Common Growth
Functions　59
18.5: Finding Fibonacci Numbers Using
Dynamic Programming　63
18.6: Finding Greatest Common Divisors
Using Euclid’s Algorithm　66
18.7: Efficient Algorithms for Finding
Prime Numbers　72
18.8: Finding the Closest Pair of Points
Using Divide-and-Conquer　81
18.9: Solving the Eight Queens Problem
Using Backtracking　84
18.10: Case Studies: Finding a Convex
Hull　88
18.10.1: Gift-Wrapping Algorithm　89
18.10.2: Graham’s Algorithm　90
18.11: String Matching　92
18.11.1: The Boyer-Moore Algorithm　95
18.11.2: The Knuth-Morris-Pratt
Algorithm　98
Key Terms　102
Chapter Summary　103
Programming Exercises　104
19: Sorting　111
19.1: Introduction　111
19.2: Insertion Sort　112
19.3: Bubble Sort　115
19.4: Merge Sort　117
19.5: Quick Sort　123
19.6: Heap Sort　127
19.6.1: Storing a Heap　129
19.6.2: Adding a New Node　130
19.6.3: Removing the Root　131
19.6.4: The Heap Class　134
19.6.5: Sorting Using the Heap Class　137
19.6.6: Heap Sort Time Complexity　139
19.7: Bucket Sort and Radix Sort　140
19.8: External Sort　143
19.8.1: Implementing Phase I　145
19.8.2: Implementing Phase II　146
19.8.3: Combining Two Phases　149
19.8.4: External Sort Complexity　150
Key Terms　151
Chapter Summary　151
Programming Exercises　151
20: Linked Lists, Queues, and
Priority Queues　154
20.1: Introduction　154
20.2: Nodes　155
20.3: The LinkedList Class　159
20.4: Implementing LinkedList　163
20.4.1: Implementing addFirst
(T element)　164
20.4.2: Implementing addLast
(T element)　165
20.4.3: Implementing add(int
index, T element)　166
20.4.4: Implementing
removeFirst()　168
20.4.5: Implementing
removeLast()　170
20.4.6: Implementing removeAt
(int index)　171
20.4.7: The source code for
LinkedList　173
20.4.8: The time complexity of
LinkedList　175
20.5: Iterators　179
20.6: C++11 Foreach Loop　184
20.7: Variations of Linked Lists　186
20.8: Queues　189
20.9: Priority Queues　192
Key Terms　196
Chapter Summary　196
Programming Exercises　197
21: Binary Search Trees　200
21.1: Introduction　200
21.2: Binary Search Trees Basics　201
21.3: Representing Binary Search Trees　202
21.4: Accessing Nodes in Binary Trees　204
21.5: Searching for an Element　204
21.6: Inserting an Element into a BST　206
21.7: Tree Traversal　208
21.8: The BST Class　210
21.9: Deleting Elements in a BST　216
21.10: Iterators for BST　224
21.11: Case Study: Data Compression　227
Key Terms　232
Chapter Summary　233
Programming Exercises　233
22: STL Containers　236
22.1: Introduction　236
22.2: STL Basics　237
22.3: STL Iterators　243
22.3.1: Types of Iterators　245
22.3.2: Iterator Operators　246
22.3.3: Predefined Iterators　248
22.3.4: istream_iterator and
ostream_iterator　250
22.4: C++11 Auto-Type Inference　252
22.5: Sequence Containers　253
22.5.1: Sequence Container: vector　254
22.5.2: Sequence Container: deque　257
22.5.3: Sequence Container: list　259
22.6: Associative Containers　263
22.6.1: Associative Containers: set
and multiset　263
22.6.2: Associative Containers: map
and multimap　265
22.7: Container Adapters　269
22.7.1: Container Adapter: stack　269
22.7.2: Container Adapter: queue　270
22.7.3: Container Adapter:
priority_queue　272
Key Terms　274
Chapter Summary　275
Programming Exercises　276
23: STL Algorithms　280
23.1: Introduction　281
23.2: Types of Algorithms　282
23.3: copy　284
23.4: fill and fill_n　287
23.5: Passing Functions as Parameters　289
23.6: generate and generate_n　293
23.7: remove, remove_if, remove_copy,
and remove_copy_if　295
23.8: replace, replace_if, replace_
copy, and replace_copy_if　299
23.9: find, find_if, find_end, and
find_first_of　303
23.10: search and search_n　309
23.11: sort and binary_search　311
23.12: adjacent_find, merge, and
inplace_merge　315
23.13: reverse and reverse_copy　317
23.14: rotate and rotate_copy　319
23.15: swap, iter_swap, and swap_
ranges　321
23.16: count and count_if　323
23.17: max_element and
min_element　324
23.18: random_shuffle　325
23.19: for_each and transform　327
23.20: includes, set_union, set_
difference, set_intersection,
and set_symmetric_
difference　329
23.21: accumulate, adjacent_
difference, inner_product,
and partial_sum　334
23.22: Lambda Expressions　338
23.23: New C++11 STL Algorithms　341
Key Terms　343
Chapter Summary　345
Programming Exercises　346
24: Hashing　348
24.1: Introduction　348
24.2: What is Hashing?　348
24.3: Hash Functions and Hash Codes　350
24.3.1: Hash Codes for Primitive
Types　350
24.3.2: Hash Codes for Strings　351
24.3.3: Compressing Hash Codes　351
24.4: Handling Collisions Using Open
Addressing　354
24.4.1: Linear Probing　354
24.4.2: Quadratic Probing　355
24.4.3: Double Hashing　357
24.5: Handling Collisions Using Separate
Chaining　360
24.6: Load Factor and Rehashing　361
24.7: Implementing a Map Using
Hashing　362
24.8: Implementing Set Using Hashing　369
Key Terms　374
Chapter Summary　375
Programming Exercises　375
25: AVL Trees　377
25.1: Introduction　377
25.2: Rebalancing Trees　379
25.3: Designing Classes for AVL Trees　382
25.4: Overriding the insert Function　384
25.5: Implementing Rotations　386
25.6: Implementing the remove
Function　387
25.7: The AVLTree Class　389
25.8: Testing the AVLTree Class　392
25.9: AVL Tree Time Complexity
Analysis　397
Key Terms　397
Chapter Summary　398
Programming Exercises　398
26: Graphs and Applications　400
26.1: Introduction　400
26.2: Basic Graph Terminologies　402
26.3: Representing Graphs　405
26.3.1: Representing Vertices　406
26.3.2: Representing Edges (for input):
Edge Array　407
26.3.3: Representing Edges (for input):
Edge Objects　408
26.3.4: Representing Edges: Adjacency
Matrices　408
26.3.5: Representing Edges: Adjacency
Lists　409
26.4: The Graph Class　413
26.5: Graph Traversals　420
26.6: Depth-First Search　422
26.6.1: Depth-First Search Algorithm　422
26.6.2: Implementation of Depth-First
Search　424
26.6.3: Applications of the DFS　426
26.7: Breadth-First Search　428
26.7.1: Breadth-First Search
Algorithm　428
26.7.2: Implementation of Breadth-First
Search　429
26.7.3: Applications of the BFS　431
26.8: Case Study: The Nine Tail Problem　432
Key Terms　440
Chapter Summary　441
Programming Exercises　441
27: Weighted Graphs and
Applications　445
27.1: Introduction　445
27.2: Representing Weighted Graphs　447
27.2.1: Representing Weighted Edges:
Edge Array　447
27.2.2: Weighted Adjacency Lists　448
27.3: The WeightedGraph Class　450
27.4: Minimum Spanning Trees　457
27.4.1: Minimum Spanning Tree
Algorithms　457
27.5: Finding Shortest Paths　465
27.6: Case Study: The Weighted Nine Tail
Problem　472
Key Terms　477
Chapter Summary　477
Programming Exercises　477
Appendix A: C++ Keywords　482
Appendix B: The ASCII Character
Set　484
Appendix C: Operator Precedence
Chart　486
Appendix D: Number Systems　487
Appendix E: Bitwise
Operations　494
Appendix F: Using Command-
Line Arguments　497
Appendix G: Enumerated
Types　501
Appendix H: Regular
Expressions　506
Appendix I: The Big-O,
Big-Omega,
and Big-Theta
Notations　515