1.1 Basic C++ Programming Elements, 3 The C++ Programming Model, 3 1.1.1 A Simple C++ Program, 4 Highlighting the C++ Elements, 4 1.1.2 Fundamental Types, 6 Characters, 6 Integers, 7 Enumerations, 7 Floating Point, 8 1.1.3 Pointers, Arrays, and Structures, 8 Pointers, 8 Arrays, 9 Pointers and Arrays, 10 Strings, 10 C-Style Structures, 11 Pointers, Dynamic Memory, and the `new' Operator, 12 Memory Leaks, 13 References, 14 1.1.4 Scope and Namespaces, 14 Constants and Typedef, 14 Local and Global Scopes, 15 Namespaces, 16 The Using Statement, 16 1.2 Expressions, 17 Member Selection and Indexing, 17 Arithmetic Operators, 17 Increment and Decrement Operators, 17 Relational and Logical Operators, 18 Bitwise Operators, 19 Assignment Operators, 19 Other Operators, 20 Operator Precedence, 21 1.2.1 Casting in Expressions, 21 Traditional C-Style Casting, 22 Explicit Cast Operators, 22 Static Casting, 23 Implicit Casting, 23 1.3 Control Flow, 24 If Statement, 24 Switch Statement, 24 While and Do-While Loops, 25 For Loop, 26 Break and Continue Statements, 27 1.4 Functions, 28 1.4.1 Argument Passing, 29 Constant References as Arguments, 30 Array Arguments, 30 1.4.2 Overloading, 31 Function Overloading, 31 Operator Overloading, 31 Using Overloading, 32 1.5 Classes, 33 1.5.1 Class Structure, 33 Access Control, 33 Member Functions, 34 In-Class Function Definition, 35 1.5.2 Constructors and Destructors, 36 Constructors, 36 Initializing Class Members with Initializer Lists, 38 Destructors, 39 1.5.3 Classes and Memory Allocation, 40 1.5.4 Class Friends and Class Members, 42 Nesting Classes and Types within Classes, 44 1.5.5 The Standard Template Library, 44 Templates and the STL Vector Class, 45 1.6 C++ Program and File Organization, 46 Source Files, 46 Header Files, 46 1.6.1 An Example Program, 47 The CreditCard Class, 47 The Main Test Program, 49 Avoiding Multiple Header Expansions, 50 1.7 Writing a C++ Program, 52 1.7.1 Design, 52 1.7.2 Coding, 53 Readability and Style, 54 1.7.3 Testing and Debugging, 55 Testing, 55 Debugging, 56 1.8 Exercises, 57
2.1 Goals and Principles, 63 2.1.1 Object-Oriented Design Goals, 63 Robustness, 63 Adaptability, 64 Reusability, 65 2.1.2 Object-Oriented Design Principles, 65 Abstraction, 66 Encapsulation, 66 Modularity, 67 2.2 Inheritance and Polymorphism, 69 2.2.1 Inheritance in C++, 69 Member Functions, 71 Protected Members, 72 Illustrating Class Protection, 73 Constructors and Destructors, 74 Static Binding, 75 Dynamic Binding and Virtual Functions, 75 Virtual Destructors, 76 2.2.2 Polymorphism, 77 Specialization, 77 Extension, 78 2.2.3 Examples of Inheritance in C++, 78 Arithmetic and Geometric Progression Classes, 80 A Fibonacci Progression Class, 81 Combining the Progression Classes, 82 2.2.4 Multiple Inheritance and Class Casting, 84 Multiple and Restricted Inheritance, 84 Casting in an Inheritance Hierarchy, 85 2.2.5 Interfaces and Abstract Classes, 86 Abstract Classes, 87 Interfaces and Abstract Base Classes, 88 2.3 Templates, 89 2.3.1 Function Templates, 89 2.3.2 Class Templates, 90 Templated Arguments, 91 Template Members, 91 2.4 Exceptions, 92 2.4.1 Exception Objects, 92 Using Inheritance to Define New Exception Types, 93 2.4.2 Throwing and Catching Exceptions, 93 2.4.3 Exception Specification, 95 Generic Exception Class, 96 2.5 Recursion and Other Design Patterns, 97 2.5.1 Recursion, 98 The Factorial Function, 98 A Recursive Implementation of the Factorial Function, 99 Drawing an English Ruler, 100 A Recursive Approach to Ruler Drawing, 100 Illustrating Ruler Drawing using a Recursion Trace, 102 2.6 Exercises, 103
3.1 Running Time and Pseudo-Code, 109 3.1.1 How Should Running Time be Measured?, 109 Requirements for a General Analysis Methodology, 110 3.1.2 Pseudo-Code, 110 A Pseudo-Code Example, 111 What Is Pseudo-Code?, 112 3.2 A Quick Mathematical Review, 113 3.2.1 Summations, 113 3.2.2 Logarithms and Exponents, 115 3.3 Justification Techniques (*), 116 3.3.1 By Example, 116 3.3.2 The `Contra' Attack, 116 3.3.3 Induction and Loop Invariants, 117 Induction, 117 Loop Invariants, 119 3.4 Analysis of Algorithms, 120 3.4.1 Primitive Operations, 120 Counting Primitive Operations, 121 3.4.2 Average-Case and Worst-Case Analysis, 122 3.5 Asymptotic Notation, 123 Simplifying the Analysis Further, 123 3.5.1 The `Big-Oh' Notation, 124 3.5.2 `Relatives' of the Big-Oh, 127 `Distant Cousins' of the Big-Oh, 128 3.6 Asymptotic Analysis, 129 The Floor and Ceiling Functions, 129 The Importance of Asymptotics, 130 3.6.1 Using the Big-Oh Notation, 131 Some Words of Caution, 131 3.6.2 Examples of Asymptotic Algorithm Analysis, 132 A Quadratic-Time Algorithm, 133 A Linear-Time Algorithm, 134 3.7 Exercises, 135
4.1 Using Recursion, 145 4.1.1 Linear Recursion, 146 Summing the Elements of an Array Recursively, 146 Analyzing Recursive Algorithms using Recursion Traces, 147 Reversing an Array by Recursion, 148 Computing Powers via Linear Recursion, 149 Tail Recursion, 150 4.1.2 Higher-Order Recursion, 151 Binary Recursion, 151 Computing Fibonacci Numbers via Binary Recursion, 152 Computing Fibonacci Numbers via Linear Recursion, 153 Multiple Recursion, 154 4.2 Stacks, 156 4.2.1 The Stack Abstract Data Type, 157 A Stack Interface, 158 Access to Elements, 159 4.2.2 A Simple Array-Based Implementation, 161 A C++ Implementation of a Stack, 162 Running Time, 165 4.2.3 Implementing Recursion and Function Calls, 166 The C++ Run-time Stack, 166 How Functions are Called, 166 Implementing Call by Value, 167 Implementing Call by Reference, 168 Implementing Recursion with a Stack, 168 4.3 Queues, 169 4.3.1 The Queue Abstract Data Type, 169 A Queue Interface, 170 Example Applications, 170 4.3.2 A Simple Array-Based Implementation, 171 Using an Array in a Circular Way, 172 Using the Modulo Operator to Implement a Circular Array, 173 4.3.3 Memory Allocation in C++, 175 4.4 Linked Lists, 176 4.4.1 Singly Linked Lists, 176 4.4.2 Implementing a Stack with a Singly Linked List, 178 Housekeeping Functions, 179 4.4.3 Implementing a Queue with a Singly Linked List, 182 4.5 Double-Ended Queues, 183 4.5.1 The Deque Abstract Data Type, 183 4.5.2 Implementing a Deque with a Doubly Linked List, 184 A C++ Deque Implementation, 186 4.5.3 The Adapter Design Pattern, 187 Defining the Adapter Design Pattern, 189 4.6 Sample Case Study Application, 190 The Stock Span Problem, 190 4.6.1 A Quadratic-Time Algorithm, 191 4.6.2 A Linear-Time Algorithm, 192 Summarizing the Running Time, 193 4.6.3 C++ Implementation, 195 4.7 Exercises, 196
5.1 Vectors, 205 5.1.1 The Vector Abstract Data Type, 206 5.1.2 A Simple Array-Based Implementation, 207 5.1.3 An Extendable Array Implementation, 209 Fixed Length Capacity Increment, 213 5.1.4 The STL vector Class, 214 5.2 Lists, 215 5.2.1 Node-Based Operations and Positions, 215 Positions, 216 5.2.2 The List Abstract Data Type, 217 5.2.3 Doubly Linked List Implementation, 220 Using Positions, 224 5.2.4 The STL list Class, 227 Similarities and Differences with Our List ADT, 227 5.3 Sequences, 228 5.3.1 The Sequence Abstract Data Type, 228 Multiple Inheritance in the Sequence ADT, 228 5.3.2 Implementing a Sequence with a Doubly Linked List, 229 5.3.3 Implementing a Sequence with an Array, 233 5.3.4 Comparing Sequence Implementations, 234 5.4 Case Study: Bubble-Sort on a Sequence, 235 5.4.1 The Bubble-Sort Algorithm, 235 5.4.2 A Sequence-Based Analysis of Bubble-Sort, 236 5.5 Iterators, 238 5.5.1 Iterator Functions, 238 STL Iterators, 239 5.5.2 More About Iterators, 240 When Iterators Become Invalid, 240 Iterators and Positions, 240 Using Iterators, 241 Implementing Iterators, 241 Forward and Backward Iterators, 241 5.6 A Hierarchy of Sequence ADTs, 242 5.6.1 Functions of a Container, 242 The Container ADT, 242 5.6.2 Inspectable Containers, 243 5.6.3 Inheritance Structure of Sequence ADTs, 244 5.7 Exercises, 245
6.1 The Tree Abstract Data Type, 255 6.1.1 Terminology and Basic Properties, 255 Ordered Trees, 257 6.1.2 Tree Functions, 259 6.1.3 A Tree Interface, 261 6.2 Basic Algorithms on Trees, 262 6.2.1 Running-Time Assumptions, 262 6.2.2 Depth and Height, 263 6.2.3 Preorder Traversal, 266 Tree Printing: An Application of Preorder Traversal, 267 Using Preorder Traversal for Representing a Tree, 268 6.2.4 Postorder Traversal, 269 An Illustrative Use of the Postorder Traversal, 270 A Postorder Algorithm for Computing Disk Usage, 272 Other Kinds of Traversals, 272 6.3 Binary Trees, 273 6.3.1 The Binary Tree ADT, 273 6.3.2 A Binary Tree Interface, 274 6.3.3 Properties of Binary Trees, 275 6.3.4 Traversals of a Binary Tree, 277 Preorder Traversal of a Binary Tree, 277 Postorder Traversal of a Binary Tree, 277 Evaluating an Arithmetic Expression, 278 Inorder Traversal of a Binary Tree, 279 Binary Search Trees, 280 Using Inorder Traversal for Tree Drawing, 281 A Unified Tree Traversal Framework, 281 The Euler Tour Traversal of a Binary Tree, 282 6.3.5 The Template Function Pattern, 284 Euler Tour with the Template Function Pattern, 284 Template Function Examples, 285 C++ Implementation, 286 6.4 Data Structures for Representing Trees, 289 6.4.1 A Vector-Based Structure for Binary Trees, 289 6.4.2 A Linked Structure for Binary Trees, 291 Nodes and Positions in a Binary Tree, 292 Binary Tree Update Functions, 294 Copying a Binary Tree, 297 6.4.3 A Linked Structure for General Trees, 298 6.4.4 Representing General Trees with Binary Trees, 299 6.5 Exercises, 301
7.1 The Priority Queue Abstract Data Type, 313 7.1.1 Keys, Priorities, and Total Order Relations, 313 Comparing Keys with Total Orders, 314 7.1.2 Sorting with a Priority Queue, 315 7.1.3 Functions of a Priority Queue, 316 Simplicity of the Priority Queue ADT, 316 7.1.4 Compositions and Comparators, 318 The Composition Pattern, 318 The Comparator Pattern, 319 Using Comparator Objects, 321 7.1.5 The STL priority_queue Class, 322 7.2 Implementing a Priority Queue with a Sequence, 323 7.2.1 Implementation with an Unsorted Sequence, 323 7.2.2 Implementation with a Sorted Sequence, 324 Comparing the Two Implementations, 324 7.2.3 Selection-Sort and Insertion-Sort, 327 Selection-Sort, 327 Insertion-Sort, 328 7.3 Heaps, 330 7.3.1 The Heap Data Structure, 330 7.3.2 Implementing a Priority Queue with a Heap, 333 The Vector Representation of a Heap, 334 Insertion, 335 Up-Heap Bubbling after an Insertion, 335 Removal, 337 Down-Heap Bubbling after a Removal, 337 Analysis, 339 7.3.3 C++ Implementation, 340 7.3.4 Heap-Sort, 343 Implementing Heap-Sort In-Place, 343 7.3.5 Bottom-Up Heap Construction (*), 345 7.4 The Locator Design Pattern, 349 Tracking Elements as they Move, 349 Defining the Locator Pattern, 349 Using Locators with Data Structures, 350 Locator Member Functions, 350 7.4.1 Locator-Based Priority Queue Functions (*), 351 Extending the Priority Queue ADT, 351 7.4.2 Implementing Locator-Based Priority Queues (*), 353 7.5 Exercises, 357
8.1 The Dictionary Abstract Data Type, 365 8.1.1 The Dictionary ADT, 366 8.1.2 Log Files, 369 Unordered Sequence Implementation, 369 Analysis of the Log File Data Structure, 370 Applications for Log Files, 370 8.2 Hash Tables, 371 8.2.1 Bucket Arrays, 371 Analysis of the Bucket Array Structure, 372 8.2.2 Hash Functions, 372 8.2.3 Hash Codes, 373 Hash Codes in C++, 373 Casting to an Integer, 373 Summing Components, 373 A Small C++ Example, 374 Polynomial Hash Codes, 374 Cyclic Shift Hash Codes, 375 Experimental Results, 376 Hashing Floating-Point Quantities, 377 8.2.4 Compression Maps, 377 The Division Method, 378 The MAD Method, 378 8.2.5 Collision-Handling Schemes, 379 Separate Chaining, 379 Open Addressing, 381 Linear Probing, 381 Quadratic Probing, 382 Double Hashing, 382 8.2.6 Load Factors and Rehashing, 383 Rehashing into a New Table, 383 8.2.7 A C++ Hash Table Implementation, 384 8.3 Ordered Dictionaries, 388 8.3.1 The Ordered Dictionary ADT, 388 8.3.2 Look-Up Tables, 388 8.3.3 Binary Search, 389 Analysis of Binary Search, 391 Using Look-Up Tables as Ordered Dictionaries, 392 Comparing Simple Ordered Dictionary Implementations, 392 8.3.4 The C++ Standard Template Library map Class, 393 8.4 Skip Lists, 394 8.4.1 Searching, 396 8.4.2 Update Operations, 397 Insertion, 397 Removal, 399 Maintaining the Top-most Level, 400 8.4.3 A Probabilistic Analysis of Skip Lists (*), 400 A Simplified Analysis, 401 Bounding the Height of a Skip List, 401 Bounding the Search Time on Each Level, 401 Space Usage, 402 Performance Summary, 402 8.5 Locator-Based Dictionary Functions (*), 403 Key-Based Containers, 404 8.6 Exercises, 405
9.1 Binary Search Trees, 414 9.1.1 Searching, 415 Analysis of Binary Tree Searching, 416 9.1.2 Update Operations, 417 Insertion, 417 Removal, 418 Best-case versus Worst-case, 420 9.1.3 C++ Implementation, 420 A Binary Search Tree in C++, 421 9.1.4 Performance, 425 9.2 AVL Trees, 426 Definition, 426 9.2.1 Update Operations, 428 Insertion, 428 Removal, 432 9.2.2 C++ Implementation, 433 9.2.3 Performance, 436 9.3 Multi-Way Search Trees, 437 Definition, 437 Searching in a Multi-Way Tree, 439 Data Structures, 439 9.4 (2,4) Trees, 441 9.4.1 Update Operations, 443 Insertion, 443 Analysis of Insertion in a $(2,4)$ Tree, 445 Removal, 446 9.4.2 Performance, 448 9.5 Red-Black Trees, 449 9.5.1 Update Operations, 451 Insertion, 451 Removal, 456 9.5.2 C++ Implementation, 463 9.5.3 Performance, 467 9.6 Locator-Based Search Trees (*), 468 9.7 External Searching (*), 470 9.7.1 $(a,b)$ Trees, 471 Update Operations, 472 9.7.2 B-Trees, 474 9.8 Exercises, 475
10.1 Merge-Sort, 485 10.1.1 Divide-and-Conquer, 485 Using Divide-and-Conquer for Sorting, 485 Merging Two Sorted Sequences, 491 The Running Time of Merge-Sort, 492 10.1.2 A C++ Implementation of Merge-Sort, 494 10.1.3 Merge-Sort and Recurrence Relations (*), 496 Confirming the Analysis via Induction, 497 10.2 The Set ADT, 498 10.2.1 A Simple Set Implementation, 499 Sets in STL, 499 Using a Sorted Sequence to Implement a Set, 499 Generic Merging as a Template Method Pattern, 500 Using Inheritence to Derive Set Operations, 502 Performance of Generic Merging, 502 10.3 Quick-Sort, 504 High-Level Description of Quick-Sort, 504 10.3.1 In-Place Quick-Sort, 509 Running Time of Quick-Sort, 512 10.3.2 Randomized Quick-Sort, 513 10.4 A Lower Bound on Comparison-Based Sorting, 515 10.5 Bucket-Sort and Radix-Sort, 517 10.5.1 Bucket-Sort, 517 Stable Sorting, 518 10.5.2 Radix-Sort, 518 10.6 Comparison of Sorting Algorithms, 520 Insertion-Sort, 520 Merge-Sort, 520 Quick-Sort, 521 Heap-Sort, 521 Bucket-Sort and Radix-Sort, 521 10.7 Selection, 522 10.7.1 Prune-and-Search, 522 10.7.2 Randomized Quick-Select, 523 10.7.3 Analyzing Randomized Quick-Select (*), 524 The Linearity of Expectation, 524 Characterizing the Expected Time for Quick-Select, 524 Obtaining a Closed Form Analysis, 525 10.8 Exercises, 526
11.1 String Operations, 535 Substrings, 535 11.1.1 The STL String Class, 536 Further Observations about STL Strings, 537 11.2 Pattern Matching Algorithms, 538 11.2.1 Brute Force, 538 Brute-Force Pattern Matching, 538 Performance, 539 11.2.2 The Boyer-Moore Algorithm, 540 11.2.3 The Knuth-Morris-Pratt Algorithm, 545 The Failure Function, 545 Performance, 547 Constructing the KMP Failure Function, 548 11.3 Tries, 550 11.3.1 Standard Tries, 550 11.3.2 Compressed Tries, 554 11.3.3 Suffix Tries, 556 Saving Space, 556 Construction, 556 Using a Suffix Trie, 557 Performance, 559 11.3.4 Search Engines, 560 Inverted Files, 560 11.4 Text Compression, 561 11.4.1 The Huffman Coding Algorithm, 562 11.4.2 The Greedy Method, 563 11.5 Text Similarity Testing, 564 11.5.1 The Longest Common Subsequence Problem, 564 Problem Definition, 564 11.5.2 Dynamic Programming, 565 11.5.3 Applying Dynamic Programming to the LCS Problem, 565 The LCS Algorithm, 567 Performance, 567 11.6 Exercises, 569
12.1 The Graph Abstract Data Type, 577 12.1.1 Graph Functions, 582 General Functions, 583 Functions Dealing with Directed Edges, 583 Functions for Updating Graphs, 584 12.2 Data Structures for Graphs, 585 12.2.1 The Edge List Structure, 585 Vertex Objects, 585 Edge Objects, 586 The Edge List, 586 Performance, 588 12.2.2 The Adjacency List Structure, 589 The Adjacency List, 589 Performance, 591 12.2.3 The Adjacency Matrix Structure, 592 Performance, 594 12.3 Graph Traversal, 595 12.3.1 Depth-First Search, 595 The Decorator Pattern, 599 Polymorphic Objects, 600 A Generic DFS Implementation in C++, 602 Using the Template Method Pattern for DFS, 602 12.3.2 Breadth-First Search, 608 12.4 Directed Graphs, 611 Comparing BFS and DFS for Directed and Undirected Graphs, 611 Reachability, 611 12.4.1 Traversing a Digraph, 613 Testing for Strong Connectivity, 615 Directed Breadth-First Search, 615 12.4.2 Transitive Closure, 615 12.4.3 Directed Acyclic Graphs, 617 Testing if a Directed Graph is Acyclic, 622 12.4.4 Application: Garbage Collection (*), 622 Determining Live Objects, 623 The Mark-Sweep Algorithm, 623 Performing DFS In-place, 624 12.5 Weighted Graphs, 625 12.6 Shortest Paths, 626 12.6.1 Dijkstra's Algorithm, 627 A Greedy Method for Finding Shortest Paths, 627 Edge Relaxation, 627 Why It Works, 630 The Running Time of Dijkstra's Algorithm, 632 An Alternative Implementation for Dijkstra's Algorithm, 633 Comparing the Two Implementations, 633 Programming Dijkstra's Algorithm in C++, 633 12.7 Minimum Spanning Trees, 637 Problem Definition, 637 A Crucial Fact about Minimum Spanning Trees, 638 12.7.1 Kruskal's Algorithm, 639 The Running Time of Kruskal's Algorithm, 642 12.7.2 The Prim-Jarnik Algorithm, 643 A Comparison of the Above MST Algorithms, 646 12.8 Exercises, 647
Logarithms and Exponents, 657 Integer Functions and Relations, 658 Summations, 659 Basic Probability, 661 Useful Mathematical Techniques, 663
Sections marked with a star (*) are optional.