Preiss,_B.R._-_Data_Structures_and_Algorithms_in_C++_(2004)
[C++] Data Structures and Algorithms with OO Design Patterns
Book Companion
Front Matter PDF
Wiley Book Website
Instructor Resources Website
Student Resources
Compiler Work-arounds
Example Source Code
Example Source Code ZIP
Programmer's Guide PDF
Frequently Asked Questions
Errata
Colophon
Dedication
Preface
0.1 Goals
0.2 Approach
0.3 Outline
0.4 Suggested Course Outline
0.5 Online Course Materials
Chapter 1. Introduction
1.1 What This Book Is About
1.2 Object-Oriented Design
1.2.1 Abstraction
1.2.2 Encapsulation
1.3 Object Hierarchies and Design Patterns
1.3.1 Containers
1.3.2 Iterators
1.3.3 Visitors
1.3.4 Adapters
1.3.5 Singletons
1.4 The Features of C++ You Need to Know
1.4.1 Variables
1.4.2 Parameter Passing
1.4.3 Pointers
1.4.4 Classes and Objects
1.4.5 Inheritance
1.4.6 Other Features
1.5 How This Book Is Organized
1.5.1 Models and Asymptotic Analysis
1.5.2 Foundational Data Structures
1.5.3 Abstract Data Types and the Class Hierarchy
1.5.4 Data Structures
1.5.5 Algorithms
Chapter 2. Algorithm Analysis
2.1 A Detailed Model of the Computer
2.1.1 The Basic Axioms
2.1.2 A Simple Example-Arithmetic Series Summation
2.1.3 Array Subscripting Operations
2.1.4 Another Example-Horner's Rule
2.1.5 Analyzing Recursive Functions
2.1.5.1 Solving Recurrence Relations-Repeated Substitution
2.1.6 Yet Another Example-Finding the Largest Element of an Array
2.1.7 Average Running Times
2.1.8 About Harmonic Numbers
2.1.9 Best-Case and Worst-Case Running Times
2.1.10 The Last Axiom
2.2 A Simplified Model of the Computer
2.2.1 An Example-Geometric Series Summation
2.2.2 About Arithmetic Series Summation
2.2.3 Example-Geometric Series Summation Again
2.2.4 About Geometric Series Summation
2.2.5 Example-Computing Powers
2.2.6 Example-Geometric Series Summation Yet Again
2.3 Exercises
2.4 Projects
Chapter 3. Asymptotic Notation
3.1 An Asymptotic Upper Bound-Big Oh
3.1.1 A Simple Example
3.1.2 Big Oh Fallacies and Pitfalls
3.1.3 Properties of Big Oh
3.1.4 About Polynomials
3.1.5 About Logarithms
3.1.6 Tight Big Oh Bounds
3.1.7 More Big Oh Fallacies and Pitfalls
3.1.8 Conventions for Writing Big Oh Expressions
3.2 An Asymptotic Lower Bound-Omega
3.2.1 A Simple Example
3.2.2 About Polynomials Again
3.3 More Notation-Theta and Little Oh
3.4 Asymptotic Analysis of Algorithms
3.4.1 Rules For Big Oh Analysis of Running Time
3.4.2 Example-Prefix Sums
3.4.3 Example-Fibonacci Numbers
3.4.4 Example-Bucket Sort
3.4.5 Reality Check
3.4.6 Checking Your Analysis
3.5 Exercises
3.6 Projects
Chapter 4. Foundational Data Structures
4.1 Dynamic Arrays
4.1.1 Default Constructor
4.1.2 Array Constructor
4.1.3 Copy Constructor
4.1.4 Destructor
4.1.5 Array Member Functions
4.1.6 Array Subscripting Operator
4.1.7 Resizing an Array
4.2 Singly-Linked Lists
4.2.1 An Implementation
4.2.2 List Elements
4.2.3 Default Constructor
4.2.4 Destructor and Purge Member Function
4.2.5 Accessors
4.2.6 First and Last Functions
4.2.7 Prepend
4.2.8 Append
4.2.9 Copy Constructor and Assignment Operator
4.2.10 Extract
4.2.11 InsertAfter and InsertBefore
4.3 Multi-Dimensional Arrays
4.3.1 Array Subscript Calculations
4.3.2 Two-Dimensional Array Implementation
4.3.3 Multi-Dimensional Subscripting in C++
4.3.4 Canonical Matrix Multiplication
4.4 Exercises
4.5 Projects
Chapter 5. Data Types and Abstraction
5.1 Abstract Data Types
5.2 Design Patterns
5.2.1 Class Hierarchy
5.2.2 Objects
5.2.2.1 Implementation
5.2.3 The NullObject Singleton Class
5.2.3.1 Implementation
5.2.4 Object Wrappers for the Built-In Types
5.2.4.1 Implementation
5.2.5 Containers
5.2.6 Visitors
5.2.6.1 The IsDone Member Function
5.2.6.2 Container Class Default Put Member Function
5.2.7 Iterators
5.2.8 The NullIterator Class
5.2.9 Direct vs. Indirect Containment
5.2.10 Ownership of Contained Objects
5.2.11 Associations
5.2.11.1 Implementation
5.2.12 Searchable Containers
5.3 Exercises
5.4 Projects
Chapter 6. Stacks, Queues and Deques
6.1 Stacks
6.1.1 Array Implementation
6.1.1.1 Member Variables
6.1.1.2 Constructor and Destructor
6.1.1.3 Push, Pop, and Top Member Functions
6.1.1.4 The Accept Member Function
6.1.1.5 Iterator
6.1.2 Linked List Implementation
6.1.2.1 Member Variables
6.1.2.2 Constructor and Destructor
6.1.2.3 Push, Pop, and Top Member Functions
6.1.2.4 The Accept Member Function
6.1.2.5 Iterator
6.1.3 Applications
6.1.3.1 Evaluating Postfix Expressions
6.1.3.2 Implementation
6.2 Queues
6.2.1 Array Implementation
6.2.1.1 Member Variables
6.2.1.2 Constructor and Destructor
6.2.1.3 Head, Enqueue, and Dequeue Member Functions
6.2.2 Linked List Implementation
6.2.2.1 Member Variables
6.2.2.2 Constructor and Destructor
6.2.2.3 Head, Enqueue and Dequeue Member Functions
6.2.3 Applications
6.2.3.1 Implementation
6.3 Deques
6.3.1 Array Implementation
6.3.1.1 Tail, EnqueueHead, and DequeueTail Member Functions
6.3.2 Linked List Implementation
6.3.2.1 Tail, EnqueueHead, and DequeueTail Member Functions
6.3.3 Doubly-Linked and Circular Lists
6.4 Exercises
6.5 Projects
Chapter 7. Ordered Lists and Sorted Lists
7.1 Ordered Lists
7.1.1 Array Implementation
7.1.1.1 Member Variables
7.1.1.2 Inserting and Accessing Items in a List
7.1.1.3 Finding Items in a List
7.1.1.4 Removing Items from a List
7.1.1.5 Positions of Items in a List
7.1.1.6 Finding the Position of an Item and Accessing by Position
7.1.1.7 Inserting an Item at an Arbitrary Position
7.1.1.8 Removing Arbitrary Items by Position
7.1.2 Linked List Implementation
7.1.2.1 Member Variables
7.1.2.2 Inserting and Accessing Items in a List
7.1.2.3 Finding Items in a List
7.1.2.4 Removing Items from a List
7.1.2.5 Positions of Items in a List
7.1.2.6 Finding the Position of an Item and Accessing by Position
7.1.2.7 Inserting an Item at an Arbitrary Position
7.1.2.8 Removing Arbitrary Items by Position
7.1.3 Performance Comparison: ListAsArray vs. ListAsLinkedList
7.1.4 Applications
7.2 Sorted Lists
7.2.1 Array Implementation
7.2.1.1 Inserting Items in a Sorted List
7.2.1.2 Locating Items in an Array-Binary Search
7.2.1.3 Finding Items in a Sorted List
7.2.1.4 Removing Items from a List
7.2.2 Linked List Implementation
7.2.2.1 Inserting Items in a Sorted List
7.2.2.2 Other Operations on Sorted Lists
7.2.3 Performance Comparison: SortedListAsArray vs. SortedListAsList
7.2.4 Applications
7.2.4.1 Implementation
7.2.4.2 Analysis
7.3 Exercises
7.4 Projects
Chapter 8. Hashing, Hash Tables and Scatter Tables
8.1 Hashing-The Basic Idea
8.1.1 Example
8.1.2 Keys and Hash Functions
8.1.2.1 Avoiding Collisions
8.1.2.2 Spreading Keys Evenly
8.1.2.3 Ease of Computation
8.2 Hashing Methods
8.2.1 Division Method
8.2.2 Middle Square Method
8.2.3 Multiplication Method
8.2.4 Fibonacci Hashing
8.3 Hash Function Implementations
8.3.1 Integral Keys
8.3.2 Floating-Point Keys
8.3.3 Character String Keys
8.3.4 Hashing Objects
8.3.5 Hashing Containers
8.3.6 Using Associations
8.4 Hash Tables
8.4.1 Separate Chaining
8.4.1.1 Implementation
8.4.1.2 Constructor and Destructor
8.4.1.3 Inserting and Removing Items
8.4.1.4 Finding an Item
8.4.2 Average Case Analysis
8.5 Scatter Tables
8.5.1 Chained Scatter Table
8.5.1.1 Implementation
8.5.1.2 Constructors and Destructor
8.5.1.3 Inserting and Finding an Item
8.5.1.4 Removing Items
8.5.1.5 Worst-Case Running Time
8.5.2 Average Case Analysis
8.6 Scatter Table using Open Addressing
8.6.1 Linear Probing
8.6.2 Quadratic Probing
8.6.3 Double Hashing
8.6.4 Implementation
8.6.4.1 Constructors and Destructor
8.6.4.2 Inserting Items
8.6.4.3 Finding Items
8.6.4.4 Removing Items
8.6.5 Average Case Analysis
8.7 Applications
8.8 Exercises
8.9 Projects
Chapter 9. Trees
9.1 Basics
9.1.1 Terminology
9.1.2 More Terminology
9.1.3 Alternate Representations for Trees
9.2 N-ary Trees
9.3 Binary Trees
9.4 Tree Traversals
9.4.1 Preorder Traversal
9.4.2 Postorder Traversal
9.4.3 Inorder Traversal
9.4.4 Breadth-First Traversal
9.5 Expression Trees
9.5.1 Infix Notation
9.5.2 Prefix Notation
9.5.3 Postfix Notation
9.6 Implementing Trees
9.6.1 Tree Traversals
9.6.1.1 Depth-First Traversal
9.6.1.2 Preorder, Inorder and Postorder Traversals
9.6.1.3 Breadth-First Traversal
9.6.1.4 Accept Member Function
9.6.2 Tree Iterators
9.6.2.1 Member Variables
9.6.2.2 Constructor and Reset Member Function
9.6.2.3 Operator Member Functions
9.6.3 General Trees
9.6.3.1 Member Variables
9.6.3.2 Member Functions
9.6.3.3 Constructor, Destructor, and Purge Member Function
9.6.3.4 Key and Subtree Member Functions
9.6.3.5 AttachSubtree and DetachSubtree Member Functions
9.6.4 N-ary Trees
9.6.4.1 Member Variables
9.6.4.2 Member Functions
9.6.4.3 Constructors
9.6.4.4 IsEmpty Member Function
9.6.4.5 Key, AttachKey and DetachKey Member Functions
9.6.4.6 Subtree, AttachSubtree and DetachSubtree Member Functions
9.6.5 Binary Trees
9.6.5.1 Member Variables
9.6.5.2 Constructors
9.6.5.3 Destructor and Purge Member Functions
9.6.6 Binary Tree Traversals
9.6.7 Comparing Trees
9.6.8 Applications
9.6.8.1 Implementation
9.7 Exercises
9.8 Projects
Chapter 10. Search Trees
10.1 Basics
10.1.1 M-Way Search Trees
10.1.2 Binary Search Trees
10.2 Searching a Search Tree
10.2.1 Searching an M-way Tree
10.2.2 Searching a Binary Tree
10.3 Average Case Analysis
10.3.1 Successful Search
10.3.2 Solving The Recurrence-Telescoping
10.3.3 Unsuccessful Search
10.3.4 Traversing a Search Tree
10.4 Implementing Search Trees
10.4.1 Binary Search Trees
10.4.1.1 Member Variables
10.4.1.2 Find Member Function
10.4.1.3 FindMin Member Function
10.4.2 Inserting Items in a Binary Search Tree
10.4.2.1 Insert and AttachKey Member Functions
10.4.3 Removing Items from a Binary Search Tree
10.4.3.1 Withdraw and DetachKey Member Functions
10.5 AVL Search Trees
10.5.1 Implementing AVL Trees
10.5.1.1 Constructor
10.5.1.2 Height, AdjustHeight and BalanceFactor Member Functions
10.5.2 Inserting Items into an AVL Tree
10.5.2.1 Balancing AVL Trees
10.5.2.2 Single Rotations
10.5.2.3 Double Rotations
10.5.2.4 Implementation
10.5.3 Removing Items from an AVL Tree
10.6 M-Way Search Trees
10.6.1 Implementing M-Way Search Trees
10.6.1.1 Implementation
10.6.1.2 Member Functions
10.6.1.3 Inorder Traversal
10.6.2 Finding Items in an M-Way Search Tree
10.6.2.1 Linear Search
10.6.2.2 Binary Search
10.6.3 Inserting Items into an M-Way Search Tree
10.6.4 Removing Items from an M-Way Search Tree
10.7 B-Trees
10.7.1 Implementing B-Trees
10.7.1.1 Member Variables
10.7.1.2 Constructors
10.7.1.3 Private Member Functions
10.7.2 Inserting Items into a B-Tree
10.7.2.1 Implementation
10.7.2.2 Running Time Analysis
10.7.3 Removing Items from a B-Tree
10.8 Applications
10.9 Exercises
10.10 Projects
Chapter 11. Heaps and Priority Queues
11.1 Basics
11.2 Binary Heaps
11.2.1 Complete Trees
11.2.1.1 Complete N-ary Trees
11.2.2 Implementation
11.2.2.1 Member Variables
11.2.2.2 Constructor, Destructor and Purge Member Functions
11.2.3 Putting Items into a Binary Heap
11.2.4 Removing Items from a Binary Heap
11.3 Leftist Heaps
11.3.1 Leftist Trees
11.3.2 Implementation
11.3.2.1 Member Variables
11.3.2.2 SwapContents Member Function
11.3.3 Merging Leftist Heaps
11.3.4 Putting Items into a Leftist Heap
11.3.5 Removing Items from a Leftist Heap
11.4 Binomial Queues
11.4.1 Binomial Trees
11.4.2 Binomial Queues
11.4.3 Implementation
11.4.3.1 Heap-Ordered Binomial Trees
11.4.3.2 Binomial Queues
11.4.3.3 Member Variables
11.4.3.4 AddTree and RemoveTree
11.4.3.5 FindMinTree and FindMin Member Functions
11.4.4 Merging Binomial Queues
11.4.5 Putting Items into a Binomial Queue
11.4.6 Removing an Item from a Binomial Queue
11.5 Applications
11.5.1 Discrete Event Simulation
11.5.2 Implementation
11.6 Exercises
11.7 Projects
Chapter 12. Sets, Multisets and Partitions
12.1 Basics
12.1.1 Implementing Sets
12.2 Array and Bit-Vector Sets
12.2.1 Basic Operations
12.2.2 Union, Intersection and Difference
12.2.3 Comparing Sets
12.2.4 Bit-Vector Sets
12.2.4.1 Basic Operations
12.2.4.2 Union, Intersection and Difference
12.3 Multisets
12.3.1 Array Implementation
12.3.1.1 Basic Operations
12.3.1.2 Union, Intersection and Difference
12.3.2 Linked List Implementation
12.3.2.1 Union
12.3.2.2 Intersection
12.4 Partitions
12.4.1 Representing Partitions
12.4.2 Implementing a Partition using a Forest
12.4.2.1 Implementation
12.4.2.2 Constructors and Destructor
12.4.2.3 Find and Join Member Functions
12.4.3 Collapsing Find
12.4.4 Union by Size
12.4.5 Union by Height or Rank
12.5 Applications
12.6 Exercises
12.7 Projects
Chapter 13. Dynamic Storage Allocation: The Other Kind of Heap
13.1 Basics
13.1.1 C++ Magic
13.1.1.1 Working with Multiple Storage Pools
13.1.2 The Heap
13.2 Singly Linked Free Storage
13.2.1 Implementation
13.2.1.1 Constructor and Destructor
13.2.1.2 Acquiring an Area
13.2.1.3 Releasing an Area
13.3 Doubly Linked Free Storage
13.3.1 Implementation
13.3.1.1 Constructor and Destructor
13.3.1.2 Releasing an Area
13.3.1.3 Acquiring an Area
13.4 Buddy System for Storage Management
13.4.1 Implementation
13.4.1.1 Constructor and Destructor
13.4.1.2 Acquiring an Area
13.4.1.3 Releasing an Area
13.5 Applications
13.5.1 Implementation
13.6 Exercises
13.7 Projects
Chapter 14. Algorithmic Patterns and Problem Solvers
14.1 Brute-Force and Greedy Algorithms
14.1.1 Example-Counting Change
14.1.1.1 Brute-Force Algorithm
14.1.1.2 Greedy Algorithm
14.1.2 Example-0/1 Knapsack Problem
14.2 Backtracking Algorithms
14.2.1 Example-Balancing Scales
14.2.2 Representing the Solution Space
14.2.3 Abstract Backtracking Solvers
14.2.3.1 Depth-First Solver
14.2.3.2 Breadth-First Solver
14.2.4 Branch-and-Bound Solvers
14.2.4.1 Depth-First, Branch-and-Bound Solver
14.2.5 Example-0/1 Knapsack Problem Again
14.3 Top-Down Algorithms: Divide-and-Conquer
14.3.1 Example-Binary Search
14.3.2 Example-Computing Fibonacci Numbers
14.3.3 Example-Merge Sorting
14.3.4 Running Time of Divide-and-Conquer Algorithms
14.3.4.1 Case 1 (a > b^k)
14.3.4.2 Case 2 (a = b^k)
14.3.4.3 Case 3 (a < b^k)
14.3.4.4 Summary
14.3.5 Example-Matrix Multiplication
14.4 Bottom-Up Algorithms: Dynamic Programming
14.4.1 Example-Generalized Fibonacci Numbers
14.4.2 Example-Computing Binomial Coefficients
14.4.3 Application: Typesetting Problem
14.4.3.1 Example
14.4.3.2 Implementation
14.5 Randomized Algorithms
14.5.1 Generating Random Numbers
14.5.1.1 The Minimal Standard Random Number Generator
14.5.1.2 Implementation
14.5.2 Random Variables
14.5.2.1 Implementation
14.5.3 Monte Carlo Methods
14.5.3.1 Example-Computing pi
14.5.4 Simulated Annealing
14.5.4.1 Example-Balancing Scales
14.6 Exercises
14.7 Projects
Chapter 15. Sorting Algorithms and Sorters
15.1 Basics
15.2 Sorting and Sorters
15.2.1 Sorter Class Hierarchy
15.3 Insertion Sorting
15.3.1 Straight Insertion Sort
15.3.1.1 Implementation
15.3.2 Average Running Time
15.3.3 Binary Insertion Sort
15.4 Exchange Sorting
15.4.1 Bubble Sort
15.4.2 Quicksort
15.4.2.1 Implementation
15.4.3 Running Time Analysis
15.4.3.1 Worst-Case Running Time
15.4.3.2 Best-Case Running Time
15.4.4 Average Running Time
15.4.5 Selecting the Pivot
15.5 Selection Sorting
15.5.1 Straight Selection Sorting
15.5.1.1 Implementation
15.5.2 Sorting with a Heap
15.5.2.1 Implementation
15.5.3 Building the Heap
15.5.3.1 Running Time Analysis
15.5.3.2 The Sorting Phase
15.6 Merge Sorting
15.6.1 Implementation
15.6.2 Merging
15.6.3 Two-Way Merge Sorting
15.6.4 Running Time Analysis
15.7 A Lower Bound on Sorting
15.8 Distribution Sorting
15.8.1 Bucket Sort
15.8.1.1 Implementation
15.8.2 Radix Sort
15.8.2.1 Implementation
15.9 Performance Data
15.10 Exercises
15.11 Projects
Chapter 16. Graphs and Graph Algorithms
16.1 Basics
16.1.1 Directed Graphs
16.1.2 Terminology
16.1.3 More Terminology
16.1.4 Directed Acyclic Graphs
16.1.5 Undirected Graphs
16.1.6 Terminology
16.1.7 Labeled Graphs
16.1.8 Representing Graphs
16.1.8.1 Adjacency Matrices
16.1.8.2 Sparse vs. Dense Graphs
16.1.8.3 Adjacency Lists
16.2 Implementing Graphs
16.2.1 Implementing Vertices
16.2.2 Implementing Edges
16.2.3 Abstract Graphs and Digraphs
16.2.3.1 Accessors and Mutators
16.2.3.2 Iterators
16.2.3.3 Graph Traversals
16.2.4 Implementing Undirected Graphs
16.2.4.1 Using Adjacency Matrices
16.2.4.2 Using Adjacency Lists
16.2.5 Edge-Weighted and Vertex-Weighted Graphs
16.2.6 Comparison of Graph Representations
16.2.6.1 Space Comparison
16.2.6.2 Time Comparison
16.3 Graph Traversals
16.3.1 Depth-First Traversal
16.3.1.1 Implementation
16.3.1.2 Running Time Analysis
16.3.2 Breadth-First Traversal
16.3.2.1 Implementation
16.3.2.2 Running Time Analysis
16.3.3 Topological Sort
16.3.3.1 Implementation
16.3.3.2 Running Time Analysis
16.3.4 Graph Traversal Applications: Testing for Cycles and Connectedness
16.3.4.1 Connectedness of an Undirected Graph
16.3.4.2 Connectedness of a Directed Graph
16.3.4.3 Testing for Cycles in a Directed Graph
16.4 Shortest-Path Algorithms
16.4.1 Single-Source Shortest Path
16.4.1.1 Dijkstra's Algorithm
16.4.1.2 Data Structures for Dijkstra's Algorithm
16.4.1.3 Implementation
16.4.1.4 Running Time Analysis
16.4.2 All-Pairs Source Shortest Path
16.4.2.1 Floyd's Algorithm
16.4.2.2 Implementation
16.4.2.3 Running Time Analysis
16.5 Minimum-Cost Spanning Trees
16.5.1 Constructing Spanning Trees
16.5.2 Minimum-Cost Spanning Trees
16.5.3 Prim's Algorithm
16.5.3.1 Implementation
16.5.4 Kruskal's Algorithm
16.5.4.1 Implementation
16.5.4.2 Running Time Analysis
16.6 Application: Critical Path Analysis
16.6.1 Implementation
16.7 Exercises
16.8 Projects
Chapter 17. C++ and Object-Oriented Programming
17.1 Variables, Pointers and References
17.1.1 Pointers Are Variables
17.1.1.1 Dereferencing Pointers
17.1.2 References are Not Variables
17.2 Parameter Passing
17.2.1 Pass By Value
17.2.2 Pass By Reference
17.2.2.1 The Trade-off
17.2.2.2 Constant Parameters
17.3 Objects and Classes
17.3.1 Member Variables and Member Functions
17.3.2 Constructors and Destructors
17.3.2.1 Default Constructor
17.3.2.2 Copy Constructor
17.3.2.3 The Copy Constructor, Parameter Passing and Function Return Values
17.3.2.4 Destructors
17.3.3 Accessors and Mutators
17.3.3.1 Mutators
17.3.3.2 Member Access Control
17.4 Inheritance and Polymorphism
17.4.1 Derivation and Inheritance
17.4.1.1 Derivation and Access Control
17.4.2 Polymorphism
17.4.2.1 Virtual Member Functions
17.4.2.2 Abstract Classes and Concrete Classes
17.4.2.3 Algorithmic Abstraction
17.4.3 Multiple Inheritance
17.4.4 Run-Time Type Information and Casts
17.5 Templates
17.6 Exceptions
Class Hierarchy Diagrams
Character Codes
References
Index