book

Data Structures and Algorithms in C++, Second Edition

Name: Data Structures and Algorithms in C++, Second Edition
ISBN: 9780470383278

by Michael T. Goodrich, Roberto Tamassia, David M. Mount

February 2011

Intermediate to advanced

736 pages

19h 35m

English

Wiley

Read now

Unlock full access

Copyright
Preface
Use as a TextbookOnline ResourcesFor the StudentFor the InstructorA Resource for Teaching Data Structures and Algorithms
Contents and Organization
PrerequisitesAbout the AuthorsAcknowledgments
1. A C++ Primer
1.1. Basic C++ Programming Elements1.1.1. A Simple C++ Program1.1.1.1. Program Elements1.1.2. Fundamental Types1.1.2.1. Characters1.1.2.2. Integers1.1.2.3. Enumerations1.1.2.4. Floating Point1.1.3. Pointers, Arrays, and Structures1.1.3.1. Pointers1.1.3.2. Arrays1.1.3.3. Pointers and Arrays1.1.3.4. Strings1.1.3.5. C-Style Structures1.1.3.6. Pointers, Dynamic Memory, and the "new" Operator1.1.3.7. Memory Leaks1.1.3.8. References1.1.4. Named Constants, Scope, and Namespaces1.1.4.1. Constants and Typedef1.1.4.2. Local and Global Scopes1.1.4.3. Namespaces1.1.4.4. The Using Statement1.2. Expressions1.2.1.1.2.1.1. Member Selection and Indexing1.2.1.2. Arithmetic Operators1.2.1.3. Increment and Decrement Operators1.2.1.4. Relational and Logical Operators1.2.1.5. Bitwise Operators1.2.1.6. Assignment Operators1.2.1.7. Other Operators1.2.1.8. Operator Precedence1.2.2. Changing Types through Casting1.2.2.1. Traditional C-Style Casting1.2.2.2. Explicit Cast Operators1.2.2.3. Static Casting1.2.2.4. Implicit Casting1.3. Control Flow1.3.1.1.3.1.1. If Statement1.3.1.2. Switch Statement1.3.1.3. While and Do-While Loops1.3.1.4. For Loop1.3.1.5. Break and Continue Statements1.4. Functions1.4.1. Argument Passing1.4.1.1. Constant References as Arguments1.4.1.2. Array Arguments1.4.2. Overloading and Inlining1.4.2.1. Function Overloading1.4.2.2. Operator Overloading1.4.2.3. In-line Functions1.5. Classes1.5.1. Class Structure1.5.1.1. Access Control1.5.1.2. Member Functions1.5.1.3. In-Class Function Definitions1.5.2. Constructors and Destructors1.5.2.1. Constructors1.5.2.2. Initializing Class Members with Initializer Lists1.5.2.3. Destructors1.5.3. Classes and Memory Allocation1.5.4. Class Friends and Class Members1.5.4.1. Nesting Classes and Types within Classes1.5.5. The Standard Template Library1.5.5.1. Templates and the STL Vector Class1.5.5.2. More on STL Strings1.6. C++ Program and File Organization1.6.1.1.6.1.1. Source Files1.6.1.2. Header Files1.6.2. An Example Program1.6.2.1. The CreditCard Class1.6.2.2. The Main Test Program1.6.2.3. Avoiding Multiple Header Expansions1.7. Writing a C++ Program1.7.1. Design1.7.2. Pseudo-Code1.7.3. Coding1.7.3.1. Readability and Style1.7.4. Testing and Debugging1.7.4.1. Testing1.7.4.2. Debugging1.8. Exercises1.8.1. Reinforcement1.8.2. Creativity1.8.3. Projects1.9. Chapter Notes
2. Object-Oriented Design
2.1. Goals, Principles, and Patterns2.1.1. Object-Oriented Design Goals2.1.1.1. Robustness2.1.1.2. Adaptability2.1.1.3. Reusability2.1.2. Object-Oriented Design Principles2.1.2.1. Abstraction2.1.2.2. Encapsulation2.1.2.3. Modularity2.1.2.4. Hierarchical Organization2.1.3. Design Patterns2.2. Inheritance and Polymorphism2.2.1. Inheritance in C++2.2.1.1. Member Functions2.2.1.2. Protected Members2.2.1.3. Illustrating Class Protection2.2.1.4. Constructors and Destructors2.2.1.5. Static Binding2.2.1.6. Dynamic Binding and Virtual Functions2.2.1.7. Virtual Destructors2.2.2. Polymorphism2.2.2.1. Specialization2.2.2.2. Extension2.2.3. Examples of Inheritance in C++2.2.3.1. Arithmetic Progression Class2.2.3.2. A Geometric Progression Class2.2.3.3. A Fibonacci Progression Class2.2.3.4. Combining the Progression Classes2.2.4. Multiple Inheritance and Class Casting2.2.4.1. Multiple and Restricted Inheritance2.2.4.2. Casting in an Inheritance Hierarchy2.2.5. Interfaces and Abstract Classes2.2.5.1. Abstract Classes2.2.5.2. Interfaces and Abstract Base Classes2.3. Templates2.3.1. Function Templates2.3.2. Class Templates2.3.2.1. Templated Arguments2.4. Exceptions2.4.1. Exception Objects2.4.1.1. Using Inheritance to Define New Exception Types2.4.2. Throwing and Catching Exceptions2.4.3. Exception Specification2.4.3.1. Generic Exception Class2.5. Exercises2.5.1. Reinforcement2.5.2. Creativity2.5.3. Projects2.6. Chapter Notes
3. Arrays, Linked Lists, and Recursion
3.1. Using Arrays3.1.1. Storing Game Entries in an Array3.1.1.1. A Class for High Scores3.1.1.2. Insertion3.1.1.3. Object Removal3.1.2. Sorting an Array3.1.3. Two-Dimensional Arrays and Positional Games3.1.3.1. Dynamic Allocation of Matrices3.1.3.2. Using STL Vectors to Implement Matrices3.1.3.3. Tic-Tac-Toe3.2. Singly Linked Lists3.2.1. Implementing a Singly Linked List3.2.2. Insertion to the Front of a Singly Linked List3.2.3. Removal from the Front of a Singly Linked List3.2.4. Implementing a Generic Singly Linked List3.3. Doubly Linked Lists3.3.1.3.3.1.1. Header and Trailer Sentinels3.3.2. Insertion into a Doubly Linked List3.3.3. Removal from a Doubly Linked List3.3.4. A C++ Implementation3.4. Circularly Linked Lists and List Reversal3.4.1. Circularly Linked Lists3.4.1.1. Maintaining a Playlist for a Digital Audio Player3.4.2. Reversing a Linked List3.5. Recursion3.5.1.3.5.1.1. The Factorial Function3.5.1.2. A Recursive Implementation of the Factorial Function3.5.1.3. Drawing an English Ruler3.5.1.4. A Recursive Approach to Ruler Drawing3.5.1.5. Illustrating Ruler Drawing using a Recursion Trace3.5.1.6. Further Illustrations of Recursion3.5.1.6.1. Example 3.13.5.1.6.2. Example 3.23.5.1.6.3. Example 3.33.5.2. Linear Recursion3.5.2.1. Summing the Elements of an Array Recursively3.5.2.2. Analyzing Recursive Algorithms using Recursion Traces3.5.2.3. Reversing an Array by Recursion3.5.2.4. Defining Problems in Ways that Facilitate Recursion3.5.2.5. Tail Recursion3.5.3. Binary Recursion3.5.3.1. Computing Fibonacci Numbers via Binary Recursion3.5.3.2. Computing Fibonacci Numbers via Linear Recursion3.5.4. Multiple Recursion3.6. Exercises3.6.1. Reinforcement3.6.2. Creativity3.6.3. Projects3.7. Chapter Notes
4. Analysis Tools
4.1. The Seven Functions Used in This Book4.1.1. The Constant Function4.1.2. The Logarithm Function4.1.2.1.4.1.2.1.1. Proposition 4.1 (Logarithm Rules)4.1.2.1.2. Example 4.24.1.3. The Linear Function4.1.4. The N-Log-N Function4.1.5. The Quadratic Function4.1.5.1. Nested Loops and the Quadratic Function4.1.6. The Cubic Function and Other Polynomials4.1.6.1. Polynomials4.1.6.2. Summations4.1.7. The Exponential Function4.1.7.1.4.1.7.1.1. Proposition 4.4 (Exponent Rules)4.1.7.2. Geometric Sums4.1.8. Comparing Growth Rates4.1.8.1. The Ceiling and Floor Functions4.2. Analysis of Algorithms4.2.1. Experimental Studies4.2.2. Primitive Operations4.2.2.1. Counting Primitive Operations4.2.2.2. Focusing on the Worst Case4.2.3. Asymptotic Notation4.2.3.1. The "Big-Oh" Notation4.2.3.2. Example 4.64.2.3.3. Characterizing Running Times using the Big-Oh Notation4.2.3.4. Some Properties of the Big-Oh Notation4.2.3.4.1. Example 4.84.2.3.4.2. Example 4.104.2.3.4.3. Example 4.114.2.3.4.4. Example 4.124.2.3.4.5. Example 4.134.2.3.4.6. Example 4.144.2.3.5. Characterizing Functions in Simplest Terms4.2.3.6. Big-Omega4.2.3.6.1. Example 4.154.2.3.7. Big-Theta4.2.3.7.1. Example 4.164.2.4. Asymptotic Analysis4.2.5. Using the Big-Oh Notation4.2.5.1. Some Words of Caution4.2.5.2. Exponential Running Times4.2.5.3. Two Examples of Asymptotic Algorithm Analysis4.2.5.4. A Quadratic-Time Algorithm4.2.5.5. A Linear-Time Algorithm4.2.6. A Recursive Algorithm for Computing Powers4.2.7. Some More Examples of Algorithm Analysis4.2.7.1. A Constant-Time Method4.2.7.2. Revisiting the Method for Finding the Maximum in an Array4.2.7.3. Further Analysis of the Maximum-Finding Algorithm4.2.7.4. Three-Way Set Disjointness4.2.7.5. Recursion Run Amok4.2.7.6. An Iterative Method for Solving the Element Uniqueness Problem4.2.7.7. Using Sorting as a Problem-Solving Tool4.3. Simple Justification Techniques4.3.1. By Example4.3.1.1.4.3.1.1.1. Example 4.174.3.2. The "Contra" Attack4.3.2.1.4.3.2.1.1. Example 4.184.3.2.2. Contradiction4.3.2.2.1. Example 4.194.3.3. Induction and Loop Invariants4.3.3.1. Induction4.3.3.2. Loop Invariants4.4. Exercises4.4.1. Reinforcement4.4.2. Creativity4.4.3. Projects4.5. Chapter Notes
5. Stacks, Queues, and Deques
5.1. Stacks5.1.1.5.1.1.1.5.1.1.1.1. Example 5.15.1.1.1.2. Example 5.25.1.2. The Stack Abstract Data Type5.1.2.1.5.1.2.1.1. Example 5.35.1.3. The STL Stack5.1.4. A C++ Stack Interface5.1.5. A Simple Array-Based Stack Implementation5.1.5.1. A C++ Implementation of a Stack5.1.5.2. Example Output5.1.6. Implementing a Stack with a Generic Linked List5.1.7. Reversing a Vector Using a Stack5.1.8. Matching Parentheses and HTML Tags5.1.8.1. An Algorithm for Parentheses Matching5.1.8.2. Matching Tags in an HTML Document5.2. Queues5.2.1. The Queue Abstract Data Type5.2.1.1.5.2.1.1.1. Example 5.45.2.2. The STL Queue5.2.3. A C++ Queue Interface5.2.4. A Simple Array-Based Implementation5.2.4.1. Using an Array in a Circular Way5.2.4.2. Using the Modulo Operator to Implement a Circular Array5.2.5. Implementing a Queue with a Circularly Linked List5.3. Double-Ended Queues5.3.1. The Deque Abstract Data Type5.3.1.1.5.3.1.1.1. Example 5.55.3.2. The STL Deque5.3.3. Implementing a Deque with a Doubly Linked List5.3.4. Adapters and the Adapter Design Pattern5.4. Exercises5.4.1. Reinforcement5.4.2. Creativity5.4.3. Projects5.5. Chapter Notes
6. List and Iterator ADTs
6.1. Vectors6.1.1. The Vector Abstract Data Type6.1.1.1.6.1.1.1.1. Example 6.16.1.2. A Simple Array-Based Implementation6.1.2.1. The Performance of a Simple Array-Based Implementation6.1.3. An Extendable Array Implementation6.1.4. STL Vectors6.2. Lists6.2.1. Node-Based Operations and Iterators6.2.1.1. Containers and Positions6.2.1.2. Iterators6.2.2. The List Abstract Data Type6.2.2.1.6.2.2.1.1. Example 6.36.2.3. Doubly Linked List Implementation6.2.4. STL Lists6.2.5. STL Containers and Iterators6.2.5.1. STL Iterators6.2.5.2. Using Iterators6.2.5.3. Const Iterators6.2.5.4. STL Iterator-Based Container Functions6.2.5.5. STL Vectors and Algorithms6.2.5.6. An Illustrative Example6.3. Sequences6.3.1. The Sequence Abstract Data Type6.3.2. Implementing a Sequence with a Doubly Linked List6.3.3. Implementing a Sequence with an Array6.4. Case Study: Bubble-Sort on a Sequence6.4.1. The Bubble-Sort Algorithm6.4.2. A Sequence-Based Analysis of Bubble-Sort6.5. Exercises6.5.1. Reinforcement6.5.2. Creativity6.5.3. Projects6.6. Chapter Notes
7. Trees
7.1. General Trees7.1.1. Tree Definitions and Properties7.1.1.1. Formal Tree Definition7.1.1.2. Other Node Relationships7.1.1.2.1. Example 7.17.1.1.3. Edges and Paths in Trees7.1.1.3.1. Example 7.27.1.1.4. Ordered Trees7.1.1.4.1. Example 7.37.1.2. Tree Functions7.1.3. A C++ Tree Interface7.1.4. A Linked Structure for General Trees7.2. Tree Traversal Algorithms7.2.1. Depth and Height7.2.2. Preorder Traversal7.2.2.1.7.2.2.1.1. Example 7.67.2.3. Postorder Traversal7.2.3.1.7.2.3.1.1. Example 7.77.2.3.2. Other Kinds of Traversals7.3. Binary Trees7.3.1.7.3.1.1.7.3.1.1.1. Example 7.87.3.1.1.2. Example 7.97.3.2.7.3.2.1. A Recursive Binary Tree Definition7.3.3. The Binary Tree ADT7.3.4. A C++ Binary Tree Interface7.3.5. Properties of Binary Trees7.3.6. A Linked Structure for Binary Trees7.3.6.1. Binary Tree Update Functions7.3.6.2. Performance of the LinkedBinaryTree Implementation7.3.7. A Vector-Based Structure for Binary Trees7.3.8. Traversals of a Binary Tree7.3.8.1. Preorder Traversal of a Binary Tree7.3.8.2. Postorder Traversal of a Binary Tree7.3.8.3. Evaluating an Arithmetic Expression7.3.8.4. Inorder Traversal of a Binary Tree7.3.8.5. Binary Search Trees7.3.8.6. Using Inorder Traversal for Tree Drawing7.3.8.7. The Euler Tour Traversal of a Binary Tree7.3.9. The Template Function Pattern7.3.9.1. Euler Tour with the Template Function Pattern7.3.9.2. Template Function Examples7.3.9.3. C++ Implementation7.3.10. Representing General Trees with Binary Trees7.4. Exercises7.4.1. Reinforcement7.4.2. Creativity7.4.3. Projects7.5. Chapter Notes

8. Heaps and Priority Queues
8.1. The Priority Queue Abstract Data Type8.1.1. Keys, Priorities, and Total Order Relations8.1.1.1. Comparing Keys with Total Orders8.1.1.1.1. Example 8.18.1.2. Comparators8.1.2.1.8.1.2.1.1. Example 8.28.1.2.1.2. Example 8.38.1.2.2. Defining and Using Comparator Objects8.1.3. The Priority Queue ADT8.1.3.1.8.1.3.1.1. Example 8.48.1.4. A C++ Priority Queue Interface8.1.5. Sorting with a Priority Queue8.1.6. The STL priority_queue Class8.2. Implementing a Priority Queue with a List8.2.1.8.2.1.1. Implementation with an Unsorted List8.2.1.2. Implementation with a Sorted List8.2.2. A C++ Priority Queue Implementation using a List8.2.3. Selection-Sort and Insertion-Sort8.2.3.1. Selection-Sort8.2.3.2. Insertion-Sort8.3. Heaps8.3.1. The Heap Data Structure8.3.1.1. The Height of a Heap8.3.2. Complete Binary Trees and Their Representation8.3.2.1. The Complete Binary Tree ADT8.3.2.2. A Vector Representation of a Complete Binary Tree8.3.2.3. A C++ Implementation of a Complete Binary Tree8.3.3. Implementing a Priority Queue with a Heap8.3.3.1. Insertion8.3.3.2. Removal8.3.3.3. Down-Heap Bubbling after a Removal8.3.3.4. Analysis8.3.4. C++ Implementation8.3.5. Heap-Sort8.3.5.1. Implementing Heap-Sort In-Place8.3.6. Bottom-Up Heap Construction *8.3.6.1. Recursive Bottom-Up Heap Construction8.4. Adaptable Priority Queues8.4.1.8.4.1.1. Functions of the Adaptable Priority Queue ADT8.4.2. A List-Based Implementation8.4.3. Location-Aware Entries8.5. Exercises8.5.1. Reinforcement8.5.2. Creativity8.5.3. Projects8.6. Chapter Notes
9. Hash Tables, Maps, and Skip Lists
9.1. Maps9.1.1.9.1.1.1. Entries and the Composition Pattern9.1.2. The Map ADT9.1.2.1.9.1.2.1.1. Example 9.19.1.3. A C++ Map Interface9.1.4. The STL map Class9.1.5. A Simple List-Based Map Implementation9.2. Hash Tables9.2.1. Bucket Arrays9.2.2. Hash Functions9.2.3. Hash Codes9.2.3.1. Hash Codes in C++9.2.3.2. Converting to an Integer9.2.3.3. Polynomial Hash Codes9.2.3.4. Cyclic Shift Hash Codes9.2.3.5. Experimental Results9.2.3.6. Hashing Floating-Point Quantities9.2.4. Compression Functions9.2.4.1. The Division Method9.2.4.2. The MAD Method9.2.5. Collision-Handling Schemes9.2.5.1. Separate Chaining9.2.5.2. Open Addressing9.2.5.3. Linear Probing and its Variants9.2.5.4. Quadratic Probing9.2.5.5. Double Hashing9.2.6. Load Factors and Rehashing9.2.6.1. Rehashing into a New Table9.2.7. A C++ Hash Table Implementation9.2.7.1. Iterator Dereferencing and Condensed Function Definitions9.2.7.2. Definitions of the Other Iterator Member Functions9.2.7.3. Definitions of the HashMap Member Functions9.3. Ordered Maps9.3.1.9.3.1.1. Implementing an Ordered Map9.3.2. Ordered Search Tables and Binary Search9.3.2.1. Binary Search9.3.2.2. Comparing Map Implementations9.3.3. Two Applications of Ordered Maps9.3.3.1. Flight Databases9.3.3.2. Maxima Sets9.3.3.3. Maintaining a Maxima Set with an Ordered Map9.4. Skip Lists9.4.1. Search and Update Operations in a Skip List9.4.1.1. Searching in a Skip List9.4.1.2. Insertion in a Skip List9.4.1.3. Removal in a Skip List9.4.1.4. Maintaining the Top-most Level9.4.2. A Probabilistic Analysis of Skip Lists *9.4.2.1. Bounding the Height of a Skip List9.4.2.2. Analyzing Search Time in a Skip List9.4.2.3. Space Usage in a Skip List9.5. Dictionaries9.5.1. The Dictionary ADT9.5.1.1.9.5.1.1.1. Example 9.29.5.2. A C++ Dictionary Implementation9.5.3. Implementations with Location-Aware Entries9.6. Exercises9.6.1. Reinforcement9.6.2. Creativity9.6.3. Projects9.7. Chapter Notes
10. Search Trees
10.1. Binary Search Trees10.1.1.10.1.1.1. Binary Search Trees and Ordered Maps10.1.2. Searching10.1.2.1. Analysis of Binary Tree Searching10.1.3. Update Operations10.1.3.1. Insertion10.1.3.2. Removal10.1.3.3. Performance of a Binary Search Tree10.1.4. C++ Implementation of a Binary Search Tree10.2. AVL Trees10.2.1.10.2.1.1. Definition of an AVL Tree10.2.2. Update Operations10.2.2.1. Insertion10.2.2.2. Removal10.2.2.3. Performance of AVL Trees10.2.3. C++ Implementation of an AVL Tree10.3. Splay Trees10.3.1. Splaying10.3.2. When to Splay10.3.3. Amortized Analysis of Splaying *10.3.3.1. Worst-Case Time10.3.3.2. Amortized Performance of Splay Trees10.3.3.3. An Accounting Analysis of Splaying10.3.3.4. An Accounting Invariant for Splaying10.4. (2,4) Trees10.4.1. Multi-Way Search Trees10.4.1.1. Definition of a Multi-way Search Tree10.4.1.2. Searching in a Multi-Way Tree10.4.1.3. Data Structures for Representing Multi-way Search Trees10.4.1.4. Definition of a (2, 4) Tree10.4.2. Update Operations for (2,4) Trees10.4.2.1. Insertion10.4.2.2. Analysis of Insertion in a (2, 4) Tree10.4.2.3. Removal10.4.2.4. Performance of (2, 4) Trees10.5. Red-Black Trees10.5.1. Update Operations10.5.1.1. Insertion10.5.1.2. Removal10.5.1.3. Performance of Red-Black Trees10.5.2. C++ Implementation of a Red-Black Tree10.6. Exercises10.6.1. Reinforcement10.6.2. Creativity10.6.3. Projects10.7. Chapter Notes
11. Sorting, Sets, and Selection
11.1. Merge-Sort11.1.1. Divide-and-Conquer11.1.1.1. Using Divide-and-Conquer for Sorting11.1.2. Merging Arrays and Lists11.1.2.1. Merging Two Sorted Lists11.1.2.2. The Running Time for Merging11.1.3. The Running Time of Merge-Sort11.1.4. C++ Implementations of Merge-Sort11.1.5. Merge-Sort and Recurrence Equations *11.2. Quick-Sort11.2.1.11.2.1.1. High-Level Description of Quick-Sort11.2.1.2. Performing Quick-Sort on Arrays and Lists11.2.1.3. Running Time of Quick-Sort11.2.2. Randomized Quick-Sort11.2.2.1. Picking Pivots at Random11.2.3. C++ Implementations and Optimizations11.3. Studying Sorting through an Algorithmic Lens11.3.1. A Lower Bound for Sorting11.3.2. Linear-Time Sorting: Bucket-Sort and Radix-Sort11.3.2.1. Bucket-Sort11.3.2.2. Stable Sorting11.3.2.3. Radix-Sort11.3.2.3.1. Example 11.511.3.3. Comparing Sorting Algorithms11.3.3.1. Considering Running Time and Other Factors11.3.3.2. Insertion-Sort11.3.3.3. Merge-Sort11.3.3.4. Quick-Sort11.3.3.5. Heap-Sort11.3.3.6. Bucket-Sort and Radix-Sort11.4. Sets and Union/Find Structures11.4.1. The Set ADT11.4.2. Mergable Sets and the Template Method Pattern11.4.2.1.11.4.2.1.1. Example 11.711.4.2.2. Fundamental Methods of the Mergable Set ADT11.4.2.3. A Simple Mergable Set Implementation11.4.2.4. Performance of Generic Merging11.4.2.5. Generic Merging as a Template Method Pattern11.4.3. Partitions with Union-Find Operations11.4.3.1. Performance of the Sequence Implementation11.4.3.2. A Tree-Based Partition Implementation *11.5. Selection11.5.1.11.5.1.1. Defining the Selection Problem11.5.2. Prune-and-Search11.5.3. Randomized Quick-Select11.5.4. Analyzing Randomized Quick-Select11.6. Exercises11.6.1. Reinforcement11.6.2. Creativity11.6.3. Projects11.7. Chapter Notes
12. Strings and Dynamic Programming
12.1. String Operations12.1.1.12.1.1.1. Text Processing12.1.2. The STL String Class12.1.2.1.12.1.2.1.1. Example 12.112.2. Dynamic Programming12.2.1. Matrix Chain-Product12.2.1.1.12.2.1.1.1. Example 12.212.2.1.2. Defining Subproblems12.2.1.3. Characterizing Optimal Solutions12.2.1.4. Designing a Dynamic Programming Algorithm12.2.2. DNA and Text Sequence Alignment12.2.2.1. The Components of a Dynamic Programming Solution12.2.2.2. Applying Dynamic Programming to the LCS Problem12.2.2.3. The LCS Algorithm12.3. Pattern Matching Algorithms12.3.1. Brute Force12.3.1.1. Performance12.3.1.1.1. Example 12.412.3.2. The Boyer-Moore Algorithm12.3.3. The Knuth-Morris-Pratt Algorithm12.3.3.1. The Failure Function12.3.3.1.1. Example 12.512.3.3.2. Performance12.3.3.3. Constructing the KMP Failure Function12.4. Text Compression and the Greedy Method12.4.1. The Huffman-Coding Algorithm12.4.2. The Greedy Method12.5. Tries12.5.1. Standard Tries12.5.2. Compressed Tries12.5.3. Suffix Tries12.5.3.1. Saving Space12.5.3.2. Construction12.5.3.3. Using a Suffix Trie12.5.4. Search Engines12.5.4.1. Inverted Files12.6. Exercises12.6.1. Reinforcement12.6.2. Creativity12.6.3. Projects12.7. Chapter Notes
13. Graph Algorithms
13.1. Graphs13.1.1.13.1.1.1.13.1.1.1.1. Example 13.113.1.1.1.2. Example 13.213.1.1.1.3. Example 13.313.1.1.1.4. Example 13.413.1.1.1.5. Example 13.513.1.1.1.6. Example 13.913.1.1.1.7. Example 13.1013.1.2. The Graph ADT13.2. Data Structures for Graphs13.2.1. The Edge List Structure13.2.1.1. Vertex Objects13.2.1.2. Edge Objects13.2.1.3. Visualizing the Edge List Structure13.2.1.4. Performance of the Edge List Structure13.2.2. The Adjacency List Structure13.2.2.1. Performance of the Adjacency List Structure13.2.3. The Adjacency Matrix Structure13.2.3.1. Performance of the Adjacency Matrix Structure13.3. Graph Traversals13.3.1. Depth-First Search13.3.1.1. Discovery Edges and Back Edges13.3.2. Implementing Depth-First Search13.3.2.1. The Decorator Pattern13.3.2.2. Making Graph Vertices Decorable13.3.2.3. DFS Traversal using Decorable Positions13.3.3. A Generic DFS Implementation in C++13.3.3.1. Using the Template Method Pattern for DFS13.3.4. Polymorphic Objects and Decorator Values *13.3.5. Breadth-First Search13.4. Directed Graphs13.4.1.13.4.1.1. Methods Dealing with Directed Edges13.4.1.2. Reachability13.4.2. Traversing a Digraph13.4.2.1. Testing for Strong Connectivity13.4.2.2. Directed Breadth-First Search13.4.3. Transitive Closure13.4.3.1. Performance of the Floyd-Warshall Algorithm13.4.4. Directed Acyclic Graphs13.4.4.1.13.4.4.1.1. Example 13.2013.5. Shortest Paths13.5.1. Weighted Graphs13.5.1.1. Defining Shortest Paths in a Weighted Graph13.5.2. Dijkstra's Algorithm13.5.2.1. A Greedy Method for Finding Shortest Paths13.5.2.2. Edge Relaxation13.5.2.3. Why It Works13.5.2.4. The Running Time of Dijkstra's Algorithm13.6. Minimum Spanning Trees13.6.1.13.6.1.1. Problem Definition13.6.1.2. A Crucial Fact About Minimum Spanning Trees13.6.2. Kruskal's Algorithm13.6.2.1. The Running Time of Kruskal's Algorithm13.6.3. The Prim-Jarník Algorithm13.6.3.1. Analyzing the Prim-Jarník Algorithm13.6.3.2. Illustrating the Prim-Jarník Algorithm13.7. Exercises13.7.1. Reinforcement13.7.2. Creativity13.7.3. Projects13.8. Chapter Notes
14. Memory Management and B-Trees
14.1. Memory Management14.1.1.14.1.1.1. The C++ Run-Time Stack14.1.1.2. Keeping Track of the Program Counter14.1.1.3. Understanding Call-by-Value Parameter Passing14.1.1.4. Implementing Recursion14.1.2. Memory Allocation in C++14.1.2.1. The Memory Heap14.1.2.2. Memory Allocation Algorithms14.1.3. Garbage Collection14.1.3.1. Performing DFS In-place14.2. External Memory and Caching14.2.1. The Memory Hierarchy14.2.1.1. Caches and Disks14.2.2. Caching Strategies14.2.2.1. Caching and Blocking14.2.2.2. Caching Algorithms14.2.2.3. Page Replacement Algorithms14.3. External Searching and B-Trees14.3.1.14.3.1.1. Some Inefficient External-Memory Dictionaries14.3.2. (a,b) Trees14.3.2.1. Definition of an (a,b) Tree14.3.2.2. Search and Update Operations14.3.3. B-Trees14.4. External-Memory Sorting14.4.1.14.4.1.1. Multi-Way Merge-Sort14.4.2. Multi-Way Merging14.5. Exercises14.5.1. Reinforcement14.5.2. Creativity14.5.3. Projects14.6. Chapter Notes
A. Useful Mathematical Facts
A.1. Logarithms and ExponentsA.1.1.A.1.1.1. Logarithms and ExponentsA.1.1.2. Integer Functions and RelationsA.1.1.3. SummationsA.1.1.4. Basic ProbabilityA.1.1.4.1. Example A.17A.1.1.4.2. Example A.18A.1.1.4.3. Example A.20A.1.1.4.4. Example A.22A.1.1.5. Useful Mathematical Techniques
Bibliography

Content preview from Data Structures and Algorithms in C++, Second Edition

Chapter 11. Sorting, Sets, and Selection

Contents

11.1 Merge-Sort	500
11.1.1 Divide-and-Conquer	500
11.1.2 Merging Arrays and Lists	505
11.1.3 The Running Time of Merge-Sort	508
11.1.4 C++ Implementations of Merge-Sort	509
11.1.5 Merge-Sort and Recurrence Equations *	511
11.2 Quick-Sort	513
11.2.1 Randomized Quick-Sort	521
11.2.2 C++ Implementations and Optimizations	523
11.3 Studying Sorting through an Algorithmic Lens	526
11.3.1 A Lower Bound for Sorting	526
11.3.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort	528
11.3.3 Comparing Sorting Algorithms	531
11.4 Sets and Union/Find Structures	533
11.4.1 The Set ADT	533
11.4.2 Mergable Sets and the Template Method Pattern	534
11.4.3 Partitions with Union-Find Operations	538
11.5 Selection	542
11.5.1 Prune-and-Search	542
11.5.2 Randomized Quick-Select	543
11.5.3 Analyzing Randomized Quick-Select	544
11.6 Exercises	545

Merge-Sort

In this section, we present a sorting technique, called merge-sort, which can be described in a simple and compact way using recursion.

Divide-and-Conquer

Merge-sort is based on an algorithmic design pattern called divide-and-conquer. The divide-and-conquer pattern consists of the following three steps:

Divide: If the input size is smaller than a certain threshold (say, one or two elements), solve the problem directly using a straightforward method and return the solution obtained. Otherwise, divide the input data into two or more disjoint subsets.
Recur:

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Data Structures and Algorithms in Java, 2nd Edition

Publisher Resources

ISBN: 9780470383278Purchase book

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design