Data Abstraction & Problem Solving with C++: Walls and Mirrors

Cover
Title Page
Copyright Page
Acknowledgements
Contents
Chapter 1 Data Abstraction: The Walls
1.1 Object-Oriented Concepts
1.1.1 Object-Oriented Analysis and Design
1.1.2 Aspects of an Object-Oriented Solution
1.2 Achieving a Better Solution
1.2.1 Cohesion
1.2.2 Coupling
1.3 Specifications
1.3.1 Operation Contracts
1.3.2 Unusual Conditions
1.3.3 Abstraction
1.3.4 Information Hiding
1.3.5 Minimal and Complete Interfaces
1.4 Abstract Data Types
1.4.1 Designing an ADT
1.4.2 ADTs That Suggest Other ADTs
1.5 The ADT Bag
1.5.1 Identifying Behaviors
1.5.2 Specifying Data and Operations
1.5.3 An Interface Template for the ADT
1.5.4 Using the ADT Bag
C++ Interlude 1 C++ Classes
C1.1 A Problem to Solve
C1.1.1 Private Data Fields
C1.1.2 Constructors and Destructors
C1.1.3 Methods
C1.1.4 Preventing Compiler Errors
C1.2 Implementing a Solution
C1.3 Templates
C1.4 Inheritance
C1.4.1 Base Classes and Derived Classes
C1.4.2 Overriding Base-Class Methods
C1.5 Virtual Methods and Abstract Classes
C1.5.1 Virtual Methods
C1.5.2 Abstract Classes
Chapter 2 Recursion: The Mirrors
2.1 Recursive Solutions
2.2 Recursion That Returns a Value
2.2.1 A Recursive Valued Function: The Factorial of n
2.2.2 The Box Trace
2.3 Recursion That Performs an Action
2.3 .1 A Recursive Void Function: Writing a String Backward
2.4 Recursion with Arrays
2.4.1 Writing an Array’s Entries in Backward Order
2.4.2 The Binary Search
2.4.3 Finding the Largest Value in an Array
2.4.4 Finding the kth Smallest Value of an Array
2.5 Organizing Data
2.5.1 The Towers of Hanoi
2.6 More Examples
2.6.1 The Fibonacci Sequence (Multiplying Rabbits)
2.6.2 Organizing a Parade
2.6.3 Choosing k Out of n Things
2.7 Recursion and Efficiency
Chapter 3 Array-Based Implementations
3.1 The Approach
3.1.1 Core Methods
3.1.2 Using Fixed-Size Arrays
3.2 An Array-Based Implementation of the ADT Bag
3.2.1 The Header File
3.2.2 Defining the Core Methods
3.2.3 Testing the Core Methods
3.2.4 Implementing More Methods
3.2.5 Methods That Remove Entries
3.2.6 Testing
3.3 Using Recursion in the Implementation
3.3.1 The Method getIndexOf
3.3.2 The Method getFrequencyOf
Interlude 2 Pointers, Polymorphism, and Memory Allocation
C2.1 Memory Allocation for Variables and Early Binding of Methods
C2.2 A Problem to Solve
C2.3 Pointers and the Program’s Free Store
C2.3.1 Deallocating Memory
C2.3.2 Avoiding Memory Leaks
C2.3.3 Avoiding Dangling Pointers
C2.4 Virtual Methods and Polymorphism
C2.5 Dynamic Allocation of Arrays
C2.5.1 A Resizable Array-Based Bag
Chapter 4 Link-Based Implementations
4.1 Preliminaries
4.1.1 The Class Node
4.2 A Link-Based Implementation of the ADT Bag
4.2.1 The Header File
4.2.2 Defining the Core Methods
4.2.3 Implementing More Methods
4.3 Using Recursion in Link-Based Implementations
4.3.1 Recursive Definitions of Methods in LinkedBag
4.4 Testing Multiple ADT Implementations
4.5 Comparing Array-Based and Link-Based Implementations
Chapter 5 Recursion as a Problem-Solving Technique
5.1 Defining Languages
5.1.1 The Basics of Grammars
5.1.2 Two Simple Languages
5.2 Algebraic Expressions
5.2.1 Kinds of Algebraic Expressions
5.2.2 Prefix Expressions
5.2.3 Postfix Expressions
5.2.4 Fully Parenthesized Expressions
5.3 Backtracking
5.3.1 Searching for an Airline Route
5.3.2 The Eight Queens Problem
5.4 The Relationship Between Recursion and Mathematical Induction
5.4.1 The Correctness of the Recursive Factorial Function
5.4.2 The Cost of Towers of Hanoi
Chapter 6 Stacks
6.1 The Abstract Data Type Stack
6.1.1 Developing an ADT During the Design of a Solution
6.1.2 Specifications for the ADT Stack
6.2 Simple Uses of a Stack
6.2.1 Checking for Balanced Braces
6.2.2 Recognizing Strings in a Language
6.3 Using Stacks with Algebraic Expressions
6.3.1 Evaluating Postfix Expressions
6.3.2 Converting Infix Expressions to Equivalent Postfix Expressions
6.4 Using a Stack to Search a Flight Map
6.5 The Relationship Between Stacks and Recursion
Interlude 3 Exceptions
C3.1 Background
C3.1.1 A Problem to Solve
C3.2 Assertions
C3.3 Throwing Exceptions
C3.4 Handling Exceptions
C3.4.1 Multiple catch Blocks
C3.4.2 Uncaught Exceptions
C3.5 Programmer-Defined Exception Classes
Chapter 7 Stack Implementations
7.1 An Array-Based Implementation
7.2 A Link-Based implementation
7.3 Implementations That Use Exceptions
Chapter 8 Lists
8.1 Specifying the ADT List
8.2 Using the List Operations
8.3 An Interface Template for the ADT List
Chapter 9 List Implementations
9.1 An Array-Based Implementation of the ADT List
9.1.1 The Header File
9.1.2 The Implementation File
9.2 A Link-Based Implementation of the ADT List
9.2.1 The Header File
9.2.2 The Implementation File
9.2.3 Using Recursion in LinkedList Methods
9.3 Comparing Implementations
Chapter 10 Algorithm Efficiency
10.1 What Is a Good Solution?
10.2 Measuring the Efficiency of Algorithms
10.2.1 The Execution Time of Algorithms
10.2.2 Algorithm Growth Rates
10.2.3 Analysis and Big O Notation
10.2.4 Keeping Your Perspective
10.2.5 The Efficiency of Searching Algorithms
Chapter 11 Sorting Algorithms and Their Efficiency
11.1 Basic Sorting Algorithms
11.1.1 The Selection Sort
11.1.2 The Bubble Sort
11.1.3 The Insertion Sort
11.2 Faster Sorting Algorithms
11.2.1 The Merge Sort
11.2.2 The Quick Sort
11.2.3 The Radix Sort
11.3 A Comparison of Sorting Algorithms
C++ Interlude 4 Class Relationships and Reuse
C4.1 Inheritance Revisited
C4.1.1 Public, Private, and Protected Sections of a Class
C4.1.2 Public, Private, and Protected Inheritance
C4.1.3 Is-a and As-a Relationships
C4.2 Containment: Has-a Relationships
C4.3 Abstract Base Classes Revisited
Chapter 12 Sorted Lists and Their Implementations
12.1 Specifying the ADT Sorted List
12.1.1 An Interface Template for the ADT Sorted List
12.1.2 Using the Sorted List Operations
12.2 A Link-Based Implementation
12.2.1 The Header File
12.2.2 The Implementation File
12.2.3 The Efficiency of the Link-Based Implementation
12.3 Implementations That Use the ADT List
12.3.1 Containment
12.3.2 Public Inheritance
12.3.3 Private Inheritance
Chapter 13 Queues and Priority Queues
13.1 The ADT Queue
13.2 Simple Applications of the ADT Queue
13.2.1 Reading a String of Characters
13.2.2 Recognizing Palindromes
13.3 The ADT Priority Queue
13.3.1 Tracking Your Assignments
13.4 Application: Simulation
13.5 Position-Oriented and Value-Oriented ADTs
Chapter 14 Queue Implementations
14.1 Implementations of the ADT Queue
14.1.1 An Implementation That Uses the ADT List
14.1.2 A Link-Based Implementation
14.1.3 An Array-Based Implementation
14.1.4 Comparing Implementations
14.2 An Implementation of the ADT Priority Queue
C++ Interlude 5 Overloaded Operators and Friend Access
C5.1 Overloaded Operators
C5.1.1 Overloading = for Assignment
C5.1.2 Overloading + for Concatenation
C5.2 Friend Access and Overloading
Chapter 15 Trees
15.1 Terminology
15.1.1 Kinds of Trees
15.1.2 The Height of Trees
15.1.3 Full, Complete, and Balanced Binary Trees
15.1.4 The Maximum and Minimum Heights of a Binary Tree
15.2 The ADT Binary Tree
15.2.1 Traversals of a Binary Tree
15.2.2 Binary Tree Operations
15.2.3 An Interface Template for the ADT Binary Tree
15.3 The ADT Binary Search Tree
15.3.1 Binary Search Tree Operations
15.3.2 Searching a Binary Search Tree
15.3.3 Creating a Binary Search Tree
15.3.4 Traversals of a Binary Search Tree
15.3.5 The Efficiency of Binary Search Tree Operations
Chapter 16 Tree Implementations
16.1 The Nodes in a Binary Tree
16.1.1 An Array-Based Representation
16.1.2 A Link-Based Representation
16.2 A Link-Based Implementation of the ADT Binary Tree
16.2.1 The Header File
16.2.2 The Implementation
16.3 A Link-Based Implementation of the ADT Binary Search Tree
16.3.1 Algorithms for the ADT Binary Search Tree Operations
16.3.2 The Class BinarySearchTree
16.4 Saving a Binary Search Tree in a File
16.5 Tree Sort
16.6 General Trees
C++ Interlude 6 Iterators
C6.1 Iterators
C6.1.1 Common Iterator Operations
C6.1.2 Using Iterator Operations
C6.1.3 Implementing an Iterator
C6.2 Advanced Iterator Functionality
Chapter 17 Heaps
17.1 The ADT Heap
17.2 An Array-Based Implementation of a Heap
17.2.1 Algorithms for the Array-Based Heap Operations
17.2.2 The Implementation
17.3 A Heap Implementation of the ADT Priority Queue
17.4 Heap Sort
Chapter 18 Dictionaries and Their Implementations
18.1 The ADT Dictionary
18.1.1 An Interface for the ADT Dictionary
18.2 Possible Implementations
18.2.1 A Sorted Array-Based Implementation of the ADT Dictionary
18.2.2 A Binary Search Tree Implementation of the ADT Dictionary
18.3 Selecting an Implementation
18.3.1 Four Scenarios
18.4 Hashing
18.4.1 Hash Functions
18.4.2 Resolving Collisions
18.4.3 The Efficiency of Hashing
18.4.4 What Constitutes a Good Hash Function?
18.4.5 Dictionary Traversal: An Inefficient Operation Under Hashing
18.4.6 Using Hashing and Separate Chaining to Implement the ADT Dictionary
Chapter 19 Balanced Search Trees
19.1 Balanced Search Trees
19.2 2-3 Trees
19.2.1 Traversing a 2-3 Tree
19.2.2 Searching a 2-3 Tree
19.2.3 Inserting Data into a 2-3 Tree
19.2.4 Removing Data from a 2-3 Tree
19.3 2-3-4 Trees
19.3.1 Searching and Traversing a 2-3-4 Tree
19.3.2 Inserting Data into a 2-3-4 Tree
19.3.3 Removing Data from a 2-3-4 Tree
19.4 Red-Black Trees
19.4.1 Searching and Traversing a Red-Black Tree
19.4.2 Inserting into and Removing from a Red-Black Tree
19.5 AVL Trees
Chapter 20 Graphs
20.1 Terminology
20.2 Graphs as ADTs
20.2.1 Implementing Graphs
20.3 Graph Traversals
20.3.1 Depth-First Search
20.3.2 Breadth-First Search
20.4 Applications of Graphs
20.4.1 Topological Sorting
20.4.2 Spanning Trees
20.4.3 Minimum Spanning Trees
20.4.4 Shortest Paths
20.4.5 Circuits
20.4.6 Some Difficult Problems
Chapter 21 Processing Data in External Storage
21.1 A Look at External Storage
21.2 Sorting Data in an External File
21.3 External Tables
21.3.1 Indexing an External File
21.3.2 External Hashing
21.3.3 B-Trees
21.3.4 Traversals
21.3.5 Multiple Indexing
C++ Interlude 7 The Standard Template Library
C7.1 STL Containers
C7.1.1 Container Adaptors
C7.1.2 Sequence Containers
C7.1.3 Associative Containers
C7.2 STL Algorithms
Appendix A: Review of C++ Fundamentals
Appendix B: Important Themes in Programming
Appendix C: The Unified Modeling Language
Appendix D: The Software Life Cycle
Appendix E: Mathematical Induction
Appendix F: Algorithm Verification
Appendix G: Files
Appendix H: C++ Header Files and Standard Functions
Appendix I: C++ Documentation Systems
Appendix J: ASCII Character Codes
Appendix K: C++ for Java Programmers
Appendix L: C++ for Python Programmers
Index
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W