目录
目 录<br />Introduction to C++ Programming and Data Structures, Fifth Edition<br />第17章 递归 1<br />17.1 简介 1<br />17.2 案例研究：计算阶乘 2<br />17.3 案例研究：斐波那契数 8<br />17.4 使用递归解决问题 12<br />17.5 递归辅助函数 16<br />17.5.1 选择排序 18<br />17.5.2 二分查找 20<br />17.6 汉诺塔 22<br />17.7 八皇后问题 26<br />17.8 递归与迭代 30<br />17.9 尾递归 31<br />关键术语 34<br />章节总结 35<br />编程练习 35<br />第18章 开发高效算法 46<br />18.1 简介 47<br />18.2 使用大O表示法衡量算法效率 47<br />18.3 示例：确定大O 50<br />18.4 分析算法时间复杂度 56<br />18.4.1 分析二分查找 56<br />18.4.2 分析选择排序 57<br />18.4.3 分析汉诺塔问题 58<br />18.4.4 常见的递归关系 59<br />18.4.5 比较常见的增长函数 59<br />18.5 使用动态规划求斐波那契数 63<br />18.6 使用欧几里得算法求最大<br />公约数 66<br />18.7 寻找质数的高效算法 72<br />18.8 使用分治法寻找最近点对 81<br />18.9 使用回溯法解决八皇后问题 84<br /><br />18.10 案例研究：寻找凸包 88<br />18.10.1 礼品包装算法 89<br />18.10.2 Graham算法 90<br />18.11 字符串匹配 92<br />18.11.1 Boyer-Moore算法 95<br />18.11.2 Knuth-Morris-Pratt算法 98<br />关键术语 102<br />章节总结 103<br />编程练习 104<br />第19章 排序 111<br />19.1 简介 111<br />19.2 插入排序 112<br />19.3 冒泡排序 115<br />19.4 归并排序 117<br />19.5 快速排序 123<br />19.6 堆排序 127<br />19.6.1 存储堆 129<br />19.6.2 添加新节点 130<br />19.6.3 删除根 131<br />19.6.4 Heap类 134<br />19.6.5 使用Heap类进行排序 137<br />19.6.6 堆排序的时间复杂度 139<br />19.7 桶排序和基数排序 140<br />19.8 外部排序 143<br />19.8.1 实现第一阶段 145<br />19.8.2 实现第二阶段 146<br />19.8.3 合成两个阶段 149<br />19.8.4 外部排序复杂度 150<br />关键术语 151<br />章节总结 151<br />编程练习 151<br />第20章 链表、队列和优先级队列 154<br />20.1 简介 154<br />20.2 节点 155<br />20.3 LinkedList类 159<br />20.4 实现LinkedList 163<br />20.4.1 实现addFirst<br />(T element) 164<br />20.4.2 实现addLast<br />(T element) 165<br />20.4.3 实现add(int index, <br />T element) 166<br />20.4.4 实现removeFirst() 168<br />20.4.5 实现removeLast() 170<br />20.4.6 实现removeAt<br />(int index) 171<br />20.4.7 LinkedList的源代码 173<br />20.4.8 LinkedList的时间<br />复杂度 175<br />20.5 迭代器 179<br />20.6 C++11 foreach循环 184<br />20.7 链表的变体 186<br />20.8 队列 189<br />20.9 优先级队列 192<br />关键术语 196<br />章节总结 196<br />编程练习 197<br />第21章 二叉查找树 200<br />21.1 简介 200<br />21.2 二叉查找树基础知识 201<br />21.3 表示二叉查找树 202<br />21.4 访问二叉查找树中的节点 204<br />21.5 查找元素 204<br />21.6 将元素插入二叉查找树 206<br />21.7 树的遍历 208<br />21.8 BST类 210<br />21.9 删除二叉查找树中的元素 216<br />21.10 BST的迭代器 224<br />21.11 案例研究：数据压缩 227<br />关键术语 232<br />章节总结 233<br />编程练习 233<br />第22章 STL容器 236<br />22.1 简介 236<br />22.2 STL基础 237<br />22.3 STL迭代器 243<br />22.3.1 迭代器的类型 245<br />22.3.2 迭代器运算符 246<br />22.3.3 预定义迭代器 248<br />22.3.4 istream_iterator和ostream_iterator 250<br />22.4 C++11自动类型推断 252<br />22.5 序列容器 253<br />22.5.1 序列容器：vector 254<br />22.5.2 序列容器：deque 257<br />22.5.3 序列容器：list 259<br />22.6 关联容器 263<br />22.6.1 关联容器：set和<br />multiset 263<br />22.6.2 关联容器：map和<br />multimap 265<br />22.7 容器适配器 269<br />22.7.1 容器适配器：stack 269<br />22.7.2 容器适配器：queue 270<br />22.7.3 容器适配器：priority_<br />queue 272<br />关键术语 274<br />章节总结 275<br />编程练习 276<br />第23章 STL算法 280<br />23.1 简介 281<br />23.2 算法类型 282<br />23.3 copy函数 284<br />23.4 fill和fill_n 287<br />23.5 将函数作为参数传递 289<br />23.6 generate和generate_n 293<br />23.7 remove、remove_if、<br />remove_copy和<br />remove_copy_if 295<br />23.8 replace、replace_if、replace_copy和<br />replace_copy_if 299<br />23.9 find、find_if、find_end和<br />find_first_of 303<br />23.10 search和search_n 309<br />23.11 sort和binary_search 311<br />23.12 adjacent_find、merge和inplace_merge 315<br />23.13 reverse和reverse_copy 317<br />23.14 rotate和rotate_copy 319<br />23.15 swap、iter_swap和swap_ranges 321<br />23.16 count和count_if 323<br />23.17 max_element和<br />min_element 324<br />23.18 random_shuffle 325<br />23.19 for_each和transform 327<br />23.20 includes、set_union、set_difference、set_intersection和set_symmetric_difference 329<br />23.21 accumulate、adjacent_difference、inner_product和partial_sum <br />23.22 lambda表达式 334<br />23.23 新的C++11 STL算法 338<br />关键术语 341<br />章节总结 343<br />编程练习 345<br />第24章 散列 346<br />24.1 简介 348<br />24.2 散列是什么 348<br />24.3 散列函数和散列码 350<br />24.3.1 基元类型的散列码 350<br />24.3.2 字符串的散列码 351<br />24.3.3 压缩散列码 351<br />24.4 用开放寻址处理冲突 354<br />24.4.1 线性探测 354<br />24.4.2 平方探测 355<br />24.4.3 双重散列 357<br />24.5 用独立链处理冲突 360<br />24.6 负载因子和再散列 361<br />24.7 用散列实现映射 362<br />24.8 用散列实现集合 369<br />关键术语 374<br />章节总结 375<br />编程练习 375<br />第25章 AVL树 377<br />25.1 简介 377<br />25.2 再平衡树 379<br />25.3 设计AVL树类 382<br />25.4 重写insert函数 384<br />25.5 实现旋转 386<br />25.6 实现remove函数 387<br />25.7 AVLTree类 389<br />25.8 测试AVLTree类 392<br />25.9 AVL树的时间复杂度分析 397<br />关键术语 397<br />章节总结 398<br />编程练习 398<br />第26章 图及其应用 400<br />26.1 简介 400<br />26.2 基本图术语 402<br />26.3 图的表示 405<br />26.3.1 顶点的表示 406<br />26.3.2 边的表示（用于输入）：<br />边数组 407<br />26.3.3 边的表示（用于输入）：<br />Edge对象 408<br />26.3.4 边的表示：邻接矩阵 408<br />26.3.5 边的表示：邻接列表 409<br />26.4 Graph类 413<br />26.5 图遍历 420<br />26.6 深度优先搜索 422<br />26.6.1 深度优先搜索算法 422<br />26.6.2 深度优先搜索的实现 424<br />26.6.3 DFS的应用 426<br />26.7 广度优先搜索 428<br />26.7.1 广度优先搜索算法 428<br />26.7.2 广度优先搜索的实现 429<br />26.7.3 BFS的应用 431<br />26.8 案例研究：九枚硬币翻转问题 432<br />关键术语 440<br />章节总结 441<br />编程练习 441<br />第27章 加权图及其应用 445<br />27.1 简介 445<br />27.2 加权图的表示 447<br />27.2.1 加权边的表示：边数组 447<br />27.2.2 加权相邻列表 448<br />27.3 WeightedGraph类 450<br />27.4 最小生成树 457<br />27.4.1 最小生成树算法 457<br />27.5 寻找最短路径 465<br />27.6 案例研究：加权九枚硬币<br />翻转问题 472<br />关键术语 477<br />章节总结 477<br />编程练习 477<br />附录A C++关键字 482<br />附录B ASCII字符集 484<br />附录C 运算符优先级表 486<br />附录D 数字系统 487<br />附录E 按位运算 494<br />附录F 使用命令行参数 497<br />附录G 枚举类型 501<br />附录H 正则表达式 506<br />附录??I? 大O、大Omega和大Theta<br />表示法 515<br /><br />Contents<br />17: Recursion 1<br />17.1: Introduction 1<br />17.2: Case Study: Computing Factorials 2<br />17.3: Case Study: Fibonacci Numbers 8<br />17.4: Problem Solving Using Recursion 12<br />17.5: Recursive Helper Functions 16<br />17.5.1: Selection Sort 18<br />17.5.2: Binary Search 20<br />17.6: Towers of Hanoi 22<br />17.7: Eight Queens 26<br />17.8: Recursion versus Iteration 30<br />17.9: Tail Recursion 31<br />Key Terms 34<br />Chapter Summary 35<br />Programming Exercises 35<br />18: Developing Efficient <br /> Algorithms 46<br />18.1: Introduction 47<br />18.2: Measuring Algorithm Efficiency <br /> Using Big O Notation 47<br />18.3: Examples: Determining Big O 50<br />18.4: Analyzing Algorithm Time <br /> Complexity 56<br />18.4.1: Analyzing Binary Search 56<br />18.4.2: Analyzing Selection Sort 57<br />18.4.3: Analyzing the Towers of Hanoi <br /> Problem 58<br />18.4.4: Common Recurrence <br /> Relations 59<br />18.4.5: Comparing Common Growth <br /> Functions 59<br />18.5: Finding Fibonacci Numbers Using <br /> Dynamic Programming 63<br />18.6: Finding Greatest Common Divisors <br /> Using Euclid’s Algorithm 66<br />18.7: Efficient Algorithms for Finding <br /> Prime Numbers 72<br />18.8: Finding the Closest Pair of Points <br /> Using Divide-and-Conquer 81<br />18.9: Solving the Eight Queens Problem <br /> Using Backtracking 84<br />18.10: Case Studies: Finding a Convex <br /> Hull 88<br />18.10.1: Gift-Wrapping Algorithm 89<br />18.10.2: Graham’s Algorithm 90<br />18.11: String Matching 92<br />18.11.1: The Boyer-Moore Algorithm 95<br />18.11.2: The Knuth-Morris-Pratt <br /> Algorithm 98<br />Key Terms 102<br />Chapter Summary 103<br />Programming Exercises 104<br />19: Sorting 111<br />19.1: Introduction 111<br />19.2: Insertion Sort 112<br />19.3: Bubble Sort 115<br />19.4: Merge Sort 117<br />19.5: Quick Sort 123<br />19.6: Heap Sort 127<br />19.6.1: Storing a Heap 129<br />19.6.2: Adding a New Node 130<br />19.6.3: Removing the Root 131<br />19.6.4: The Heap Class 134<br />19.6.5: Sorting Using the Heap Class 137<br />19.6.6: Heap Sort Time Complexity 139<br />19.7: Bucket Sort and Radix Sort 140<br />19.8: External Sort 143<br />19.8.1: Implementing Phase I 145<br />19.8.2: Implementing Phase II 146<br />19.8.3: Combining Two Phases 149<br />19.8.4: External Sort Complexity 150<br />Key Terms 151<br />Chapter Summary 151<br />Programming Exercises 151<br />20: Linked Lists, Queues, and <br /> Priority Queues 154<br />20.1: Introduction 154<br />20.2: Nodes 155<br />20.3: The LinkedList Class 159<br />20.4: Implementing LinkedList 163<br />20.4.1: Implementing addFirst<br /> (T element) 164<br />20.4.2: Implementing addLast<br /> (T element) 165<br />20.4.3: Implementing add(int <br /> index, T element) 166<br />20.4.4: Implementing <br /> removeFirst() 168<br />20.4.5: Implementing <br /> removeLast() 170<br />20.4.6: Implementing removeAt<br /> (int index) 171<br />20.4.7: The source code for <br /> LinkedList 173<br />20.4.8: The time complexity of <br /> LinkedList 175<br />20.5: Iterators 179<br />20.6: C++11 Foreach Loop 184<br />20.7: Variations of Linked Lists 186<br />20.8: Queues 189<br />20.9: Priority Queues 192<br />Key Terms 196<br />Chapter Summary 196<br />Programming Exercises 197<br />21: Binary Search Trees 200<br />21.1: Introduction 200<br />21.2: Binary Search Trees Basics 201<br />21.3: Representing Binary Search Trees 202<br />21.4: Accessing Nodes in Binary Trees 204<br />21.5: Searching for an Element 204<br />21.6: Inserting an Element into a BST 206<br />21.7: Tree Traversal 208<br />21.8: The BST Class 210<br />21.9: Deleting Elements in a BST 216<br />21.10: Iterators for BST 224<br />21.11: Case Study: Data Compression 227<br />Key Terms 232<br />Chapter Summary 233<br />Programming Exercises 233<br />22: STL Containers 236<br />22.1: Introduction 236<br />22.2: STL Basics 237<br />22.3: STL Iterators 243<br />22.3.1: Types of Iterators 245<br />22.3.2: Iterator Operators 246<br />22.3.3: Predefined Iterators 248<br />22.3.4: istream_iterator and <br /> ostream_iterator 250<br />22.4: C++11 Auto-Type Inference 252<br />22.5: Sequence Containers 253<br />22.5.1: Sequence Container: vector 254<br />22.5.2: Sequence Container: deque 257<br />22.5.3: Sequence Container: list 259<br />22.6: Associative Containers 263<br />22.6.1: Associative Containers: set <br /> and multiset 263<br />22.6.2: Associative Containers: map <br /> and multimap 265<br />22.7: Container Adapters 269<br />22.7.1: Container Adapter: stack 269<br />22.7.2: Container Adapter: queue 270<br />22.7.3: Container Adapter: <br /> priority_queue 272<br />Key Terms 274<br />Chapter Summary 275<br />Programming Exercises 276<br />23: STL Algorithms 280<br />23.1: Introduction 281<br />23.2: Types of Algorithms 282<br />23.3: copy 284<br />23.4: fill and fill_n 287<br />23.5: Passing Functions as Parameters 289<br />23.6: generate and generate_n 293<br />23.7: remove, remove_if, remove_copy, <br /> and remove_copy_if 295<br />23.8: replace, replace_if, replace_<br /> copy, and replace_copy_if 299<br />23.9: find, find_if, find_end, and <br /> find_first_of 303<br />23.10: search and search_n 309<br />23.11: sort and binary_search 311<br />23.12: adjacent_find, merge, and <br /> inplace_merge 315<br />23.13: reverse and reverse_copy 317<br />23.14: rotate and rotate_copy 319<br />23.15: swap, iter_swap, and swap_<br /> ranges 321<br />23.16: count and count_if 323<br />23.17: max_element and <br /> min_element 324<br />23.18: random_shuffle 325<br />23.19: for_each and transform 327<br />23.20: includes, set_union, set_<br /> difference, set_intersection, <br /> and set_symmetric_<br /> difference 329<br />23.21: accumulate, adjacent_<br /> difference, inner_product, <br /> and partial_sum 334<br />23.22: Lambda Expressions 338<br />23.23: New C++11 STL Algorithms 341<br />Key Terms 343<br />Chapter Summary 345<br />Programming Exercises 346<br />24: Hashing 348<br />24.1: Introduction 348<br />24.2: What is Hashing? 348<br />24.3: Hash Functions and Hash Codes 350<br />24.3.1: Hash Codes for Primitive <br /> Types 350<br />24.3.2: Hash Codes for Strings 351<br />24.3.3: Compressing Hash Codes 351<br />24.4: Handling Collisions Using Open <br /> Addressing 354<br />24.4.1: Linear Probing 354<br />24.4.2: Quadratic Probing 355<br />24.4.3: Double Hashing 357<br />24.5: Handling Collisions Using Separate <br /> Chaining 360<br />24.6: Load Factor and Rehashing 361<br />24.7: Implementing a Map Using <br /> Hashing 362<br />24.8: Implementing Set Using Hashing 369<br />Key Terms 374<br />Chapter Summary 375<br />Programming Exercises 375<br />25: AVL Trees 377<br />25.1: Introduction 377<br />25.2: Rebalancing Trees 379<br />25.3: Designing Classes for AVL Trees 382<br />25.4: Overriding the insert Function 384<br />25.5: Implementing Rotations 386<br />25.6: Implementing the remove <br /> Function 387<br />25.7: The AVLTree Class 389<br />25.8: Testing the AVLTree Class 392<br />25.9: AVL Tree Time Complexity <br /> Analysis 397<br />Key Terms 397<br />Chapter Summary 398<br />Programming Exercises 398<br />26: Graphs and Applications 400<br />26.1: Introduction 400<br />26.2: Basic Graph Terminologies 402<br />26.3: Representing Graphs 405<br />26.3.1: Representing Vertices 406<br />26.3.2: Representing Edges (for input): <br /> Edge Array 407<br />26.3.3: Representing Edges (for input): <br /> Edge Objects 408<br />26.3.4: Representing Edges: Adjacency <br /> Matrices 408<br />26.3.5: Representing Edges: Adjacency <br /> Lists 409<br />26.4: The Graph Class 413<br />26.5: Graph Traversals 420<br />26.6: Depth-First Search 422<br />26.6.1: Depth-First Search Algorithm 422<br />26.6.2: Implementation of Depth-First <br /> Search 424<br />26.6.3: Applications of the DFS 426<br />26.7: Breadth-First Search 428<br />26.7.1: Breadth-First Search <br /> Algorithm 428<br />26.7.2: Implementation of Breadth-First <br /> Search 429<br />26.7.3: Applications of the BFS 431<br />26.8: Case Study: The Nine Tail Problem 432<br />Key Terms 440<br />Chapter Summary 441<br />Programming Exercises 441<br />27: Weighted Graphs and <br /> Applications 445<br />27.1: Introduction 445<br />27.2: Representing Weighted Graphs 447<br />27.2.1: Representing Weighted Edges: <br /> Edge Array 447<br />27.2.2: Weighted Adjacency Lists 448<br />27.3: The WeightedGraph Class 450<br />27.4: Minimum Spanning Trees 457<br />27.4.1: Minimum Spanning Tree <br /> Algorithms 457<br />27.5: Finding Shortest Paths 465<br />27.6: Case Study: The Weighted Nine Tail <br /> Problem 472<br />Key Terms 477<br />Chapter Summary 477<br />Programming Exercises 477<br />Appendix A: C++ Keywords 482<br />Appendix B: The ASCII Character <br /> Set 484<br />Appendix C: Operator Precedence <br /> Chart 486<br />Appendix D: Number Systems 487<br />Appendix E: Bitwise <br /> Operations 494<br />Appendix F: Using Command-<br /> Line Arguments 497<br />Appendix G: Enumerated <br /> Types 501<br />Appendix H: Regular <br /> Expressions 506<br />Appendix I: The Big-O, <br /> Big-Omega, <br /> and Big-Theta <br /> Notations 515<br />
