Data Structures and Algorithms in C++, Second Edition

Data Structures and Algorithms in C++, Second Edition

Released February 2011
Publisher(s): Wiley
ISBN: 9780470383278

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

An updated, innovative approach to data structures and algorithms

Written by an author team of experts in their fields, this authoritative guide demystifies even the most difficult mathematical concepts so that you can gain a clear understanding of data structures and algorithms in C++.

The unparalleled author team incorporates the object-oriented design paradigm using C++ as the implementation language, while also providing intuition and analysis of fundamental algorithms.

  • Offers a unique multimedia format for learning the fundamentals of data structures and algorithms

  • Allows you to visualize key analytic concepts, learn about the most recent insights in the field, and do data structure design

  • Provides clear approaches for developing programs

  • Features a clear, easy-to-understand writing style that breaks down even the most difficult mathematical concepts

Building on the success of the first edition, this new version offers you an innovative approach to fundamental data structures and algorithms.

Table of contents

  1. Copyright
  2. Preface
    1. Use as a Textbook
    2. Online Resources
      1. For the Student
      2. For the Instructor
    3. A Resource for Teaching Data Structures and Algorithms
  3. Contents and Organization
    1. Prerequisites
    2. About the Authors
    3. Acknowledgments
  4. 1. A C++ Primer
    1. 1.1. Basic C++ Programming Elements
      1. 1.1.1. A Simple C++ Program
        1. 1.1.1.1. Program Elements
      2. 1.1.2. Fundamental Types
        1. 1.1.2.1. Characters
        2. 1.1.2.2. Integers
        3. 1.1.2.3. Enumerations
        4. 1.1.2.4. Floating Point
      3. 1.1.3. Pointers, Arrays, and Structures
        1. 1.1.3.1. Pointers
        2. 1.1.3.2. Arrays
        3. 1.1.3.3. Pointers and Arrays
        4. 1.1.3.4. Strings
        5. 1.1.3.5. C-Style Structures
        6. 1.1.3.6. Pointers, Dynamic Memory, and the "new" Operator
        7. 1.1.3.7. Memory Leaks
        8. 1.1.3.8. References
      4. 1.1.4. Named Constants, Scope, and Namespaces
        1. 1.1.4.1. Constants and Typedef
        2. 1.1.4.2. Local and Global Scopes
        3. 1.1.4.3. Namespaces
        4. 1.1.4.4. The Using Statement
    2. 1.2. Expressions
      1. 1.2.1.
        1. 1.2.1.1. Member Selection and Indexing
        2. 1.2.1.2. Arithmetic Operators
        3. 1.2.1.3. Increment and Decrement Operators
        4. 1.2.1.4. Relational and Logical Operators
        5. 1.2.1.5. Bitwise Operators
        6. 1.2.1.6. Assignment Operators
        7. 1.2.1.7. Other Operators
        8. 1.2.1.8. Operator Precedence
      2. 1.2.2. Changing Types through Casting
        1. 1.2.2.1. Traditional C-Style Casting
        2. 1.2.2.2. Explicit Cast Operators
        3. 1.2.2.3. Static Casting
        4. 1.2.2.4. Implicit Casting
    3. 1.3. Control Flow
      1. 1.3.1.
        1. 1.3.1.1. If Statement
        2. 1.3.1.2. Switch Statement
        3. 1.3.1.3. While and Do-While Loops
        4. 1.3.1.4. For Loop
        5. 1.3.1.5. Break and Continue Statements
    4. 1.4. Functions
      1. 1.4.1. Argument Passing
        1. 1.4.1.1. Constant References as Arguments
        2. 1.4.1.2. Array Arguments
      2. 1.4.2. Overloading and Inlining
        1. 1.4.2.1. Function Overloading
        2. 1.4.2.2. Operator Overloading
        3. 1.4.2.3. In-line Functions
    5. 1.5. Classes
      1. 1.5.1. Class Structure
        1. 1.5.1.1. Access Control
        2. 1.5.1.2. Member Functions
        3. 1.5.1.3. In-Class Function Definitions
      2. 1.5.2. Constructors and Destructors
        1. 1.5.2.1. Constructors
        2. 1.5.2.2. Initializing Class Members with Initializer Lists
        3. 1.5.2.3. Destructors
      3. 1.5.3. Classes and Memory Allocation
      4. 1.5.4. Class Friends and Class Members
        1. 1.5.4.1. Nesting Classes and Types within Classes
      5. 1.5.5. The Standard Template Library
        1. 1.5.5.1. Templates and the STL Vector Class
        2. 1.5.5.2. More on STL Strings
    6. 1.6. C++ Program and File Organization
      1. 1.6.1.
        1. 1.6.1.1. Source Files
        2. 1.6.1.2. Header Files
      2. 1.6.2. An Example Program
        1. 1.6.2.1. The CreditCard Class
        2. 1.6.2.2. The Main Test Program
        3. 1.6.2.3. Avoiding Multiple Header Expansions
    7. 1.7. Writing a C++ Program
      1. 1.7.1. Design
      2. 1.7.2. Pseudo-Code
      3. 1.7.3. Coding
        1. 1.7.3.1. Readability and Style
      4. 1.7.4. Testing and Debugging
        1. 1.7.4.1. Testing
        2. 1.7.4.2. Debugging
    8. 1.8. Exercises
      1. 1.8.1. Reinforcement
      2. 1.8.2. Creativity
      3. 1.8.3. Projects
    9. 1.9. Chapter Notes
  5. 2. Object-Oriented Design
    1. 2.1. Goals, Principles, and Patterns
      1. 2.1.1. Object-Oriented Design Goals
        1. 2.1.1.1. Robustness
        2. 2.1.1.2. Adaptability
        3. 2.1.1.3. Reusability
      2. 2.1.2. Object-Oriented Design Principles
        1. 2.1.2.1. Abstraction
        2. 2.1.2.2. Encapsulation
        3. 2.1.2.3. Modularity
        4. 2.1.2.4. Hierarchical Organization
      3. 2.1.3. Design Patterns
    2. 2.2. Inheritance and Polymorphism
      1. 2.2.1. Inheritance in C++
        1. 2.2.1.1. Member Functions
        2. 2.2.1.2. Protected Members
        3. 2.2.1.3. Illustrating Class Protection
        4. 2.2.1.4. Constructors and Destructors
        5. 2.2.1.5. Static Binding
        6. 2.2.1.6. Dynamic Binding and Virtual Functions
        7. 2.2.1.7. Virtual Destructors
      2. 2.2.2. Polymorphism
        1. 2.2.2.1. Specialization
        2. 2.2.2.2. Extension
      3. 2.2.3. Examples of Inheritance in C++
        1. 2.2.3.1. Arithmetic Progression Class
        2. 2.2.3.2. A Geometric Progression Class
        3. 2.2.3.3. A Fibonacci Progression Class
        4. 2.2.3.4. Combining the Progression Classes
      4. 2.2.4. Multiple Inheritance and Class Casting
        1. 2.2.4.1. Multiple and Restricted Inheritance
        2. 2.2.4.2. Casting in an Inheritance Hierarchy
      5. 2.2.5. Interfaces and Abstract Classes
        1. 2.2.5.1. Abstract Classes
        2. 2.2.5.2. Interfaces and Abstract Base Classes
    3. 2.3. Templates
      1. 2.3.1. Function Templates
      2. 2.3.2. Class Templates
        1. 2.3.2.1. Templated Arguments
    4. 2.4. Exceptions
      1. 2.4.1. Exception Objects
        1. 2.4.1.1. Using Inheritance to Define New Exception Types
      2. 2.4.2. Throwing and Catching Exceptions
      3. 2.4.3. Exception Specification
        1. 2.4.3.1. Generic Exception Class
    5. 2.5. Exercises
      1. 2.5.1. Reinforcement
      2. 2.5.2. Creativity
      3. 2.5.3. Projects
    6. 2.6. Chapter Notes
  6. 3. Arrays, Linked Lists, and Recursion
    1. 3.1. Using Arrays
      1. 3.1.1. Storing Game Entries in an Array
        1. 3.1.1.1. A Class for High Scores
        2. 3.1.1.2. Insertion
        3. 3.1.1.3. Object Removal
      2. 3.1.2. Sorting an Array
      3. 3.1.3. Two-Dimensional Arrays and Positional Games
        1. 3.1.3.1. Dynamic Allocation of Matrices
        2. 3.1.3.2. Using STL Vectors to Implement Matrices
        3. 3.1.3.3. Tic-Tac-Toe
    2. 3.2. Singly Linked Lists
      1. 3.2.1. Implementing a Singly Linked List
      2. 3.2.2. Insertion to the Front of a Singly Linked List
      3. 3.2.3. Removal from the Front of a Singly Linked List
      4. 3.2.4. Implementing a Generic Singly Linked List
    3. 3.3. Doubly Linked Lists
      1. 3.3.1.
        1. 3.3.1.1. Header and Trailer Sentinels
      2. 3.3.2. Insertion into a Doubly Linked List
      3. 3.3.3. Removal from a Doubly Linked List
      4. 3.3.4. A C++ Implementation
    4. 3.4. Circularly Linked Lists and List Reversal
      1. 3.4.1. Circularly Linked Lists
        1. 3.4.1.1. Maintaining a Playlist for a Digital Audio Player
      2. 3.4.2. Reversing a Linked List
    5. 3.5. Recursion
      1. 3.5.1.
        1. 3.5.1.1. The Factorial Function
        2. 3.5.1.2. A Recursive Implementation of the Factorial Function
        3. 3.5.1.3. Drawing an English Ruler
        4. 3.5.1.4. A Recursive Approach to Ruler Drawing
        5. 3.5.1.5. Illustrating Ruler Drawing using a Recursion Trace
        6. 3.5.1.6. Further Illustrations of Recursion
          1. 3.5.1.6.1. Example 3.1
          2. 3.5.1.6.2. Example 3.2
          3. 3.5.1.6.3. Example 3.3
      2. 3.5.2. Linear Recursion
        1. 3.5.2.1. Summing the Elements of an Array Recursively
        2. 3.5.2.2. Analyzing Recursive Algorithms using Recursion Traces
        3. 3.5.2.3. Reversing an Array by Recursion
        4. 3.5.2.4. Defining Problems in Ways that Facilitate Recursion
        5. 3.5.2.5. Tail Recursion
      3. 3.5.3. Binary Recursion
        1. 3.5.3.1. Computing Fibonacci Numbers via Binary Recursion
        2. 3.5.3.2. Computing Fibonacci Numbers via Linear Recursion
      4. 3.5.4. Multiple Recursion
    6. 3.6. Exercises
      1. 3.6.1. Reinforcement
      2. 3.6.2. Creativity
      3. 3.6.3. Projects
    7. 3.7. Chapter Notes
  7. 4. Analysis Tools
    1. 4.1. The Seven Functions Used in This Book
      1. 4.1.1. The Constant Function
      2. 4.1.2. The Logarithm Function
        1. 4.1.2.1.
          1. 4.1.2.1.1. Proposition 4.1 (Logarithm Rules)
          2. 4.1.2.1.2. Example 4.2
      3. 4.1.3. The Linear Function
      4. 4.1.4. The N-Log-N Function
      5. 4.1.5. The Quadratic Function
        1. 4.1.5.1. Nested Loops and the Quadratic Function
      6. 4.1.6. The Cubic Function and Other Polynomials
        1. 4.1.6.1. Polynomials
        2. 4.1.6.2. Summations
      7. 4.1.7. The Exponential Function
        1. 4.1.7.1.
          1. 4.1.7.1.1. Proposition 4.4 (Exponent Rules)
        2. 4.1.7.2. Geometric Sums
      8. 4.1.8. Comparing Growth Rates
        1. 4.1.8.1. The Ceiling and Floor Functions
    2. 4.2. Analysis of Algorithms
      1. 4.2.1. Experimental Studies
      2. 4.2.2. Primitive Operations
        1. 4.2.2.1. Counting Primitive Operations
        2. 4.2.2.2. Focusing on the Worst Case
      3. 4.2.3. Asymptotic Notation
        1. 4.2.3.1. The "Big-Oh" Notation
        2. 4.2.3.2. Example 4.6
        3. 4.2.3.3. Characterizing Running Times using the Big-Oh Notation
        4. 4.2.3.4. Some Properties of the Big-Oh Notation
          1. 4.2.3.4.1. Example 4.8
          2. 4.2.3.4.2. Example 4.10
          3. 4.2.3.4.3. Example 4.11
          4. 4.2.3.4.4. Example 4.12
          5. 4.2.3.4.5. Example 4.13
          6. 4.2.3.4.6. Example 4.14
        5. 4.2.3.5. Characterizing Functions in Simplest Terms
        6. 4.2.3.6. Big-Omega
          1. 4.2.3.6.1. Example 4.15
        7. 4.2.3.7. Big-Theta
          1. 4.2.3.7.1. Example 4.16
      4. 4.2.4. Asymptotic Analysis
      5. 4.2.5. Using the Big-Oh Notation
        1. 4.2.5.1. Some Words of Caution
        2. 4.2.5.2. Exponential Running Times
        3. 4.2.5.3. Two Examples of Asymptotic Algorithm Analysis
        4. 4.2.5.4. A Quadratic-Time Algorithm
        5. 4.2.5.5. A Linear-Time Algorithm
      6. 4.2.6. A Recursive Algorithm for Computing Powers
      7. 4.2.7. Some More Examples of Algorithm Analysis
        1. 4.2.7.1. A Constant-Time Method
        2. 4.2.7.2. Revisiting the Method for Finding the Maximum in an Array
        3. 4.2.7.3. Further Analysis of the Maximum-Finding Algorithm
        4. 4.2.7.4. Three-Way Set Disjointness
        5. 4.2.7.5. Recursion Run Amok
        6. 4.2.7.6. An Iterative Method for Solving the Element Uniqueness Problem
        7. 4.2.7.7. Using Sorting as a Problem-Solving Tool
    3. 4.3. Simple Justification Techniques
      1. 4.3.1. By Example
        1. 4.3.1.1.
          1. 4.3.1.1.1. Example 4.17
      2. 4.3.2. The "Contra" Attack
        1. 4.3.2.1.
          1. 4.3.2.1.1. Example 4.18
        2. 4.3.2.2. Contradiction
          1. 4.3.2.2.1. Example 4.19
      3. 4.3.3. Induction and Loop Invariants
        1. 4.3.3.1. Induction
        2. 4.3.3.2. Loop Invariants
    4. 4.4. Exercises
      1. 4.4.1. Reinforcement
      2. 4.4.2. Creativity
      3. 4.4.3. Projects
    5. 4.5. Chapter Notes
  8. 5. Stacks, Queues, and Deques
    1. 5.1. Stacks
      1. 5.1.1.
        1. 5.1.1.1.
          1. 5.1.1.1.1. Example 5.1
          2. 5.1.1.1.2. Example 5.2
      2. 5.1.2. The Stack Abstract Data Type
        1. 5.1.2.1.
          1. 5.1.2.1.1. Example 5.3
      3. 5.1.3. The STL Stack
      4. 5.1.4. A C++ Stack Interface
      5. 5.1.5. A Simple Array-Based Stack Implementation
        1. 5.1.5.1. A C++ Implementation of a Stack
        2. 5.1.5.2. Example Output
      6. 5.1.6. Implementing a Stack with a Generic Linked List
      7. 5.1.7. Reversing a Vector Using a Stack
      8. 5.1.8. Matching Parentheses and HTML Tags
        1. 5.1.8.1. An Algorithm for Parentheses Matching
        2. 5.1.8.2. Matching Tags in an HTML Document
    2. 5.2. Queues
      1. 5.2.1. The Queue Abstract Data Type
        1. 5.2.1.1.
          1. 5.2.1.1.1. Example 5.4
      2. 5.2.2. The STL Queue
      3. 5.2.3. A C++ Queue Interface
      4. 5.2.4. A Simple Array-Based Implementation
        1. 5.2.4.1. Using an Array in a Circular Way
        2. 5.2.4.2. Using the Modulo Operator to Implement a Circular Array
      5. 5.2.5. Implementing a Queue with a Circularly Linked List
    3. 5.3. Double-Ended Queues
      1. 5.3.1. The Deque Abstract Data Type
        1. 5.3.1.1.
          1. 5.3.1.1.1. Example 5.5
      2. 5.3.2. The STL Deque
      3. 5.3.3. Implementing a Deque with a Doubly Linked List
      4. 5.3.4. Adapters and the Adapter Design Pattern
    4. 5.4. Exercises
      1. 5.4.1. Reinforcement
      2. 5.4.2. Creativity
      3. 5.4.3. Projects
    5. 5.5. Chapter Notes
  9. 6. List and Iterator ADTs
    1. 6.1. Vectors
      1. 6.1.1. The Vector Abstract Data Type
        1. 6.1.1.1.
          1. 6.1.1.1.1. Example 6.1
      2. 6.1.2. A Simple Array-Based Implementation
        1. 6.1.2.1. The Performance of a Simple Array-Based Implementation
      3. 6.1.3. An Extendable Array Implementation
      4. 6.1.4. STL Vectors
    2. 6.2. Lists
      1. 6.2.1. Node-Based Operations and Iterators
        1. 6.2.1.1. Containers and Positions
        2. 6.2.1.2. Iterators
      2. 6.2.2. The List Abstract Data Type
        1. 6.2.2.1.
          1. 6.2.2.1.1. Example 6.3
      3. 6.2.3. Doubly Linked List Implementation
      4. 6.2.4. STL Lists
      5. 6.2.5. STL Containers and Iterators
        1. 6.2.5.1. STL Iterators
        2. 6.2.5.2. Using Iterators
        3. 6.2.5.3. Const Iterators
        4. 6.2.5.4. STL Iterator-Based Container Functions
        5. 6.2.5.5. STL Vectors and Algorithms
        6. 6.2.5.6. An Illustrative Example
    3. 6.3. Sequences
      1. 6.3.1. The Sequence Abstract Data Type
      2. 6.3.2. Implementing a Sequence with a Doubly Linked List
      3. 6.3.3. Implementing a Sequence with an Array
    4. 6.4. Case Study: Bubble-Sort on a Sequence
      1. 6.4.1. The Bubble-Sort Algorithm
      2. 6.4.2. A Sequence-Based Analysis of Bubble-Sort
    5. 6.5. Exercises
      1. 6.5.1. Reinforcement
      2. 6.5.2. Creativity
      3. 6.5.3. Projects
    6. 6.6. Chapter Notes
  10. 7. Trees
    1. 7.1. General Trees
      1. 7.1.1. Tree Definitions and Properties
        1. 7.1.1.1. Formal Tree Definition
        2. 7.1.1.2. Other Node Relationships
          1. 7.1.1.2.1. Example 7.1
        3. 7.1.1.3. Edges and Paths in Trees
          1. 7.1.1.3.1. Example 7.2
        4. 7.1.1.4. Ordered Trees
          1. 7.1.1.4.1. Example 7.3
      2. 7.1.2. Tree Functions
      3. 7.1.3. A C++ Tree Interface
      4. 7.1.4. A Linked Structure for General Trees
    2. 7.2. Tree Traversal Algorithms
      1. 7.2.1. Depth and Height
      2. 7.2.2. Preorder Traversal
        1. 7.2.2.1.
          1. 7.2.2.1.1. Example 7.6
      3. 7.2.3. Postorder Traversal
        1. 7.2.3.1.
          1. 7.2.3.1.1. Example 7.7
        2. 7.2.3.2. Other Kinds of Traversals
    3. 7.3. Binary Trees
      1. 7.3.1.
        1. 7.3.1.1.
          1. 7.3.1.1.1. Example 7.8
          2. 7.3.1.1.2. Example 7.9
      2. 7.3.2.
        1. 7.3.2.1. A Recursive Binary Tree Definition
      3. 7.3.3. The Binary Tree ADT
      4. 7.3.4. A C++ Binary Tree Interface
      5. 7.3.5. Properties of Binary Trees
      6. 7.3.6. A Linked Structure for Binary Trees
        1. 7.3.6.1. Binary Tree Update Functions
        2. 7.3.6.2. Performance of the LinkedBinaryTree Implementation
      7. 7.3.7. A Vector-Based Structure for Binary Trees
      8. 7.3.8. Traversals of a Binary Tree
        1. 7.3.8.1. Preorder Traversal of a Binary Tree
        2. 7.3.8.2. Postorder Traversal of a Binary Tree
        3. 7.3.8.3. Evaluating an Arithmetic Expression
        4. 7.3.8.4. Inorder Traversal of a Binary Tree
        5. 7.3.8.5. Binary Search Trees
        6. 7.3.8.6. Using Inorder Traversal for Tree Drawing
        7. 7.3.8.7. The Euler Tour Traversal of a Binary Tree
      9. 7.3.9. The Template Function Pattern
        1. 7.3.9.1. Euler Tour with the Template Function Pattern
        2. 7.3.9.2. Template Function Examples
        3. 7.3.9.3. C++ Implementation
      10. 7.3.10. Representing General Trees with Binary Trees
    4. 7.4. Exercises
      1. 7.4.1. Reinforcement
      2. 7.4.2. Creativity
      3. 7.4.3. Projects
    5. 7.5. Chapter Notes
  11. 8. Heaps and Priority Queues
    1. 8.1. The Priority Queue Abstract Data Type
      1. 8.1.1. Keys, Priorities, and Total Order Relations
        1. 8.1.1.1. Comparing Keys with Total Orders
          1. 8.1.1.1.1. Example 8.1
      2. 8.1.2. Comparators
        1. 8.1.2.1.
          1. 8.1.2.1.1. Example 8.2
          2. 8.1.2.1.2. Example 8.3
        2. 8.1.2.2. Defining and Using Comparator Objects
      3. 8.1.3. The Priority Queue ADT
        1. 8.1.3.1.
          1. 8.1.3.1.1. Example 8.4
      4. 8.1.4. A C++ Priority Queue Interface
      5. 8.1.5. Sorting with a Priority Queue
      6. 8.1.6. The STL priority_queue Class
    2. 8.2. Implementing a Priority Queue with a List
      1. 8.2.1.
        1. 8.2.1.1. Implementation with an Unsorted List
        2. 8.2.1.2. Implementation with a Sorted List
      2. 8.2.2. A C++ Priority Queue Implementation using a List
      3. 8.2.3. Selection-Sort and Insertion-Sort
        1. 8.2.3.1. Selection-Sort
        2. 8.2.3.2. Insertion-Sort
    3. 8.3. Heaps
      1. 8.3.1. The Heap Data Structure
        1. 8.3.1.1. The Height of a Heap
      2. 8.3.2. Complete Binary Trees and Their Representation
        1. 8.3.2.1. The Complete Binary Tree ADT
        2. 8.3.2.2. A Vector Representation of a Complete Binary Tree
        3. 8.3.2.3. A C++ Implementation of a Complete Binary Tree
      3. 8.3.3. Implementing a Priority Queue with a Heap
        1. 8.3.3.1. Insertion
        2. 8.3.3.2. Removal
        3. 8.3.3.3. Down-Heap Bubbling after a Removal
        4. 8.3.3.4. Analysis
      4. 8.3.4. C++ Implementation
      5. 8.3.5. Heap-Sort
        1. 8.3.5.1. Implementing Heap-Sort In-Place
      6. 8.3.6. Bottom-Up Heap Construction *
        1. 8.3.6.1. Recursive Bottom-Up Heap Construction
    4. 8.4. Adaptable Priority Queues
      1. 8.4.1.
        1. 8.4.1.1. Functions of the Adaptable Priority Queue ADT
      2. 8.4.2. A List-Based Implementation
      3. 8.4.3. Location-Aware Entries
    5. 8.5. Exercises
      1. 8.5.1. Reinforcement
      2. 8.5.2. Creativity
      3. 8.5.3. Projects
    6. 8.6. Chapter Notes
  12. 9. Hash Tables, Maps, and Skip Lists
    1. 9.1. Maps
      1. 9.1.1.
        1. 9.1.1.1. Entries and the Composition Pattern
      2. 9.1.2. The Map ADT
        1. 9.1.2.1.
          1. 9.1.2.1.1. Example 9.1
      3. 9.1.3. A C++ Map Interface
      4. 9.1.4. The STL map Class
      5. 9.1.5. A Simple List-Based Map Implementation
    2. 9.2. Hash Tables
      1. 9.2.1. Bucket Arrays
      2. 9.2.2. Hash Functions
      3. 9.2.3. Hash Codes
        1. 9.2.3.1. Hash Codes in C++
        2. 9.2.3.2. Converting to an Integer
        3. 9.2.3.3. Polynomial Hash Codes
        4. 9.2.3.4. Cyclic Shift Hash Codes
        5. 9.2.3.5. Experimental Results
        6. 9.2.3.6. Hashing Floating-Point Quantities
      4. 9.2.4. Compression Functions
        1. 9.2.4.1. The Division Method
        2. 9.2.4.2. The MAD Method
      5. 9.2.5. Collision-Handling Schemes
        1. 9.2.5.1. Separate Chaining
        2. 9.2.5.2. Open Addressing
        3. 9.2.5.3. Linear Probing and its Variants
        4. 9.2.5.4. Quadratic Probing
        5. 9.2.5.5. Double Hashing
      6. 9.2.6. Load Factors and Rehashing
        1. 9.2.6.1. Rehashing into a New Table
      7. 9.2.7. A C++ Hash Table Implementation
        1. 9.2.7.1. Iterator Dereferencing and Condensed Function Definitions
        2. 9.2.7.2. Definitions of the Other Iterator Member Functions
        3. 9.2.7.3. Definitions of the HashMap Member Functions
    3. 9.3. Ordered Maps
      1. 9.3.1.
        1. 9.3.1.1. Implementing an Ordered Map
      2. 9.3.2. Ordered Search Tables and Binary Search
        1. 9.3.2.1. Binary Search
        2. 9.3.2.2. Comparing Map Implementations
      3. 9.3.3. Two Applications of Ordered Maps
        1. 9.3.3.1. Flight Databases
        2. 9.3.3.2. Maxima Sets
        3. 9.3.3.3. Maintaining a Maxima Set with an Ordered Map
    4. 9.4. Skip Lists
      1. 9.4.1. Search and Update Operations in a Skip List
        1. 9.4.1.1. Searching in a Skip List
        2. 9.4.1.2. Insertion in a Skip List
        3. 9.4.1.3. Removal in a Skip List
        4. 9.4.1.4. Maintaining the Top-most Level
      2. 9.4.2. A Probabilistic Analysis of Skip Lists *
        1. 9.4.2.1. Bounding the Height of a Skip List
        2. 9.4.2.2. Analyzing Search Time in a Skip List
        3. 9.4.2.3. Space Usage in a Skip List
    5. 9.5. Dictionaries
      1. 9.5.1. The Dictionary ADT
        1. 9.5.1.1.
          1. 9.5.1.1.1. Example 9.2
      2. 9.5.2. A C++ Dictionary Implementation
      3. 9.5.3. Implementations with Location-Aware Entries
    6. 9.6. Exercises
      1. 9.6.1. Reinforcement
      2. 9.6.2. Creativity
      3. 9.6.3. Projects
    7. 9.7. Chapter Notes
  13. 10. Search Trees
    1. 10.1. Binary Search Trees
      1. 10.1.1.
        1. 10.1.1.1. Binary Search Trees and Ordered Maps
      2. 10.1.2. Searching
        1. 10.1.2.1. Analysis of Binary Tree Searching
      3. 10.1.3. Update Operations
        1. 10.1.3.1. Insertion
        2. 10.1.3.2. Removal
        3. 10.1.3.3. Performance of a Binary Search Tree
      4. 10.1.4. C++ Implementation of a Binary Search Tree
    2. 10.2. AVL Trees
      1. 10.2.1.
        1. 10.2.1.1. Definition of an AVL Tree
      2. 10.2.2. Update Operations
        1. 10.2.2.1. Insertion
        2. 10.2.2.2. Removal
        3. 10.2.2.3. Performance of AVL Trees
      3. 10.2.3. C++ Implementation of an AVL Tree
    3. 10.3. Splay Trees
      1. 10.3.1. Splaying
      2. 10.3.2. When to Splay
      3. 10.3.3. Amortized Analysis of Splaying *
        1. 10.3.3.1. Worst-Case Time
        2. 10.3.3.2. Amortized Performance of Splay Trees
        3. 10.3.3.3. An Accounting Analysis of Splaying
        4. 10.3.3.4. An Accounting Invariant for Splaying
    4. 10.4. (2,4) Trees
      1. 10.4.1. Multi-Way Search Trees
        1. 10.4.1.1. Definition of a Multi-way Search Tree
        2. 10.4.1.2. Searching in a Multi-Way Tree
        3. 10.4.1.3. Data Structures for Representing Multi-way Search Trees
        4. 10.4.1.4. Definition of a (2, 4) Tree
      2. 10.4.2. Update Operations for (2,4) Trees
        1. 10.4.2.1. Insertion
        2. 10.4.2.2. Analysis of Insertion in a (2, 4) Tree
        3. 10.4.2.3. Removal
        4. 10.4.2.4. Performance of (2, 4) Trees
    5. 10.5. Red-Black Trees
      1. 10.5.1. Update Operations
        1. 10.5.1.1. Insertion
        2. 10.5.1.2. Removal
        3. 10.5.1.3. Performance of Red-Black Trees
      2. 10.5.2. C++ Implementation of a Red-Black Tree
    6. 10.6. Exercises
      1. 10.6.1. Reinforcement
      2. 10.6.2. Creativity
      3. 10.6.3. Projects
    7. 10.7. Chapter Notes
  14. 11. Sorting, Sets, and Selection
    1. 11.1. Merge-Sort
      1. 11.1.1. Divide-and-Conquer
        1. 11.1.1.1. Using Divide-and-Conquer for Sorting
      2. 11.1.2. Merging Arrays and Lists
        1. 11.1.2.1. Merging Two Sorted Lists
        2. 11.1.2.2. The Running Time for Merging
      3. 11.1.3. The Running Time of Merge-Sort
      4. 11.1.4. C++ Implementations of Merge-Sort
      5. 11.1.5. Merge-Sort and Recurrence Equations *
    2. 11.2. Quick-Sort
      1. 11.2.1.
        1. 11.2.1.1. High-Level Description of Quick-Sort
        2. 11.2.1.2. Performing Quick-Sort on Arrays and Lists
        3. 11.2.1.3. Running Time of Quick-Sort
      2. 11.2.2. Randomized Quick-Sort
        1. 11.2.2.1. Picking Pivots at Random
      3. 11.2.3. C++ Implementations and Optimizations
    3. 11.3. Studying Sorting through an Algorithmic Lens
      1. 11.3.1. A Lower Bound for Sorting
      2. 11.3.2. Linear-Time Sorting: Bucket-Sort and Radix-Sort
        1. 11.3.2.1. Bucket-Sort
        2. 11.3.2.2. Stable Sorting
        3. 11.3.2.3. Radix-Sort
          1. 11.3.2.3.1. Example 11.5
      3. 11.3.3. Comparing Sorting Algorithms
        1. 11.3.3.1. Considering Running Time and Other Factors
        2. 11.3.3.2. Insertion-Sort
        3. 11.3.3.3. Merge-Sort
        4. 11.3.3.4. Quick-Sort
        5. 11.3.3.5. Heap-Sort
        6. 11.3.3.6. Bucket-Sort and Radix-Sort
    4. 11.4. Sets and Union/Find Structures
      1. 11.4.1. The Set ADT
      2. 11.4.2. Mergable Sets and the Template Method Pattern
        1. 11.4.2.1.
          1. 11.4.2.1.1. Example 11.7
        2. 11.4.2.2. Fundamental Methods of the Mergable Set ADT
        3. 11.4.2.3. A Simple Mergable Set Implementation
        4. 11.4.2.4. Performance of Generic Merging
        5. 11.4.2.5. Generic Merging as a Template Method Pattern
      3. 11.4.3. Partitions with Union-Find Operations
        1. 11.4.3.1. Performance of the Sequence Implementation
        2. 11.4.3.2. A Tree-Based Partition Implementation *
    5. 11.5. Selection
      1. 11.5.1.
        1. 11.5.1.1. Defining the Selection Problem
      2. 11.5.2. Prune-and-Search
      3. 11.5.3. Randomized Quick-Select
      4. 11.5.4. Analyzing Randomized Quick-Select
    6. 11.6. Exercises
      1. 11.6.1. Reinforcement
      2. 11.6.2. Creativity
      3. 11.6.3. Projects
    7. 11.7. Chapter Notes
  15. 12. Strings and Dynamic Programming
    1. 12.1. String Operations
      1. 12.1.1.
        1. 12.1.1.1. Text Processing
      2. 12.1.2. The STL String Class
        1. 12.1.2.1.
          1. 12.1.2.1.1. Example 12.1
    2. 12.2. Dynamic Programming
      1. 12.2.1. Matrix Chain-Product
        1. 12.2.1.1.
          1. 12.2.1.1.1. Example 12.2
        2. 12.2.1.2. Defining Subproblems
        3. 12.2.1.3. Characterizing Optimal Solutions
        4. 12.2.1.4. Designing a Dynamic Programming Algorithm
      2. 12.2.2. DNA and Text Sequence Alignment
        1. 12.2.2.1. The Components of a Dynamic Programming Solution
        2. 12.2.2.2. Applying Dynamic Programming to the LCS Problem
        3. 12.2.2.3. The LCS Algorithm
    3. 12.3. Pattern Matching Algorithms
      1. 12.3.1. Brute Force
        1. 12.3.1.1. Performance
          1. 12.3.1.1.1. Example 12.4
      2. 12.3.2. The Boyer-Moore Algorithm
      3. 12.3.3. The Knuth-Morris-Pratt Algorithm
        1. 12.3.3.1. The Failure Function
          1. 12.3.3.1.1. Example 12.5
        2. 12.3.3.2. Performance
        3. 12.3.3.3. Constructing the KMP Failure Function
    4. 12.4. Text Compression and the Greedy Method
      1. 12.4.1. The Huffman-Coding Algorithm
      2. 12.4.2. The Greedy Method
    5. 12.5. Tries
      1. 12.5.1. Standard Tries
      2. 12.5.2. Compressed Tries
      3. 12.5.3. Suffix Tries
        1. 12.5.3.1. Saving Space
        2. 12.5.3.2. Construction
        3. 12.5.3.3. Using a Suffix Trie
      4. 12.5.4. Search Engines
        1. 12.5.4.1. Inverted Files
    6. 12.6. Exercises
      1. 12.6.1. Reinforcement
      2. 12.6.2. Creativity
      3. 12.6.3. Projects
    7. 12.7. Chapter Notes
  16. 13. Graph Algorithms
    1. 13.1. Graphs
      1. 13.1.1.
        1. 13.1.1.1.
          1. 13.1.1.1.1. Example 13.1
          2. 13.1.1.1.2. Example 13.2
          3. 13.1.1.1.3. Example 13.3
          4. 13.1.1.1.4. Example 13.4
          5. 13.1.1.1.5. Example 13.5
          6. 13.1.1.1.6. Example 13.9
          7. 13.1.1.1.7. Example 13.10
      2. 13.1.2. The Graph ADT
    2. 13.2. Data Structures for Graphs
      1. 13.2.1. The Edge List Structure
        1. 13.2.1.1. Vertex Objects
        2. 13.2.1.2. Edge Objects
        3. 13.2.1.3. Visualizing the Edge List Structure
        4. 13.2.1.4. Performance of the Edge List Structure
      2. 13.2.2. The Adjacency List Structure
        1. 13.2.2.1. Performance of the Adjacency List Structure
      3. 13.2.3. The Adjacency Matrix Structure
        1. 13.2.3.1. Performance of the Adjacency Matrix Structure
    3. 13.3. Graph Traversals
      1. 13.3.1. Depth-First Search
        1. 13.3.1.1. Discovery Edges and Back Edges
      2. 13.3.2. Implementing Depth-First Search
        1. 13.3.2.1. The Decorator Pattern
        2. 13.3.2.2. Making Graph Vertices Decorable
        3. 13.3.2.3. DFS Traversal using Decorable Positions
      3. 13.3.3. A Generic DFS Implementation in C++
        1. 13.3.3.1. Using the Template Method Pattern for DFS
      4. 13.3.4. Polymorphic Objects and Decorator Values *
      5. 13.3.5. Breadth-First Search
    4. 13.4. Directed Graphs
      1. 13.4.1.
        1. 13.4.1.1. Methods Dealing with Directed Edges
        2. 13.4.1.2. Reachability
      2. 13.4.2. Traversing a Digraph
        1. 13.4.2.1. Testing for Strong Connectivity
        2. 13.4.2.2. Directed Breadth-First Search
      3. 13.4.3. Transitive Closure
        1. 13.4.3.1. Performance of the Floyd-Warshall Algorithm
      4. 13.4.4. Directed Acyclic Graphs
        1. 13.4.4.1.
          1. 13.4.4.1.1. Example 13.20
    5. 13.5. Shortest Paths
      1. 13.5.1. Weighted Graphs
        1. 13.5.1.1. Defining Shortest Paths in a Weighted Graph
      2. 13.5.2. Dijkstra's Algorithm
        1. 13.5.2.1. A Greedy Method for Finding Shortest Paths
        2. 13.5.2.2. Edge Relaxation
        3. 13.5.2.3. Why It Works
        4. 13.5.2.4. The Running Time of Dijkstra's Algorithm
    6. 13.6. Minimum Spanning Trees
      1. 13.6.1.
        1. 13.6.1.1. Problem Definition
        2. 13.6.1.2. A Crucial Fact About Minimum Spanning Trees
      2. 13.6.2. Kruskal's Algorithm
        1. 13.6.2.1. The Running Time of Kruskal's Algorithm
      3. 13.6.3. The Prim-Jarník Algorithm
        1. 13.6.3.1. Analyzing the Prim-Jarník Algorithm
        2. 13.6.3.2. Illustrating the Prim-Jarník Algorithm
    7. 13.7. Exercises
      1. 13.7.1. Reinforcement
      2. 13.7.2. Creativity
      3. 13.7.3. Projects
    8. 13.8. Chapter Notes
  17. 14. Memory Management and B-Trees
    1. 14.1. Memory Management
      1. 14.1.1.
        1. 14.1.1.1. The C++ Run-Time Stack
        2. 14.1.1.2. Keeping Track of the Program Counter
        3. 14.1.1.3. Understanding Call-by-Value Parameter Passing
        4. 14.1.1.4. Implementing Recursion
      2. 14.1.2. Memory Allocation in C++
        1. 14.1.2.1. The Memory Heap
        2. 14.1.2.2. Memory Allocation Algorithms
      3. 14.1.3. Garbage Collection
        1. 14.1.3.1. Performing DFS In-place
    2. 14.2. External Memory and Caching
      1. 14.2.1. The Memory Hierarchy
        1. 14.2.1.1. Caches and Disks
      2. 14.2.2. Caching Strategies
        1. 14.2.2.1. Caching and Blocking
        2. 14.2.2.2. Caching Algorithms
        3. 14.2.2.3. Page Replacement Algorithms
    3. 14.3. External Searching and B-Trees
      1. 14.3.1.
        1. 14.3.1.1. Some Inefficient External-Memory Dictionaries
      2. 14.3.2. (a,b) Trees
        1. 14.3.2.1. Definition of an (a,b) Tree
        2. 14.3.2.2. Search and Update Operations
      3. 14.3.3. B-Trees
    4. 14.4. External-Memory Sorting
      1. 14.4.1.
        1. 14.4.1.1. Multi-Way Merge-Sort
      2. 14.4.2. Multi-Way Merging
    5. 14.5. Exercises
      1. 14.5.1. Reinforcement
      2. 14.5.2. Creativity
      3. 14.5.3. Projects
    6. 14.6. Chapter Notes
  18. A. Useful Mathematical Facts
    1. A.1. Logarithms and Exponents
      1. A.1.1.
        1. A.1.1.1. Logarithms and Exponents
        2. A.1.1.2. Integer Functions and Relations
        3. A.1.1.3. Summations
        4. A.1.1.4. Basic Probability
          1. A.1.1.4.1. Example A.17
          2. A.1.1.4.2. Example A.18
          3. A.1.1.4.3. Example A.20
          4. A.1.1.4.4. Example A.22
        5. A.1.1.5. Useful Mathematical Techniques
  19. Bibliography

Product information

  • Title: Data Structures and Algorithms in C++, Second Edition
  • Author(s):
  • Release date: February 2011
  • Publisher(s): Wiley
  • ISBN: 9780470383278