This is the eBook of the printed book and may not include any media, website access codes, or print supplements that may come packaged with the bound book. Data Abstraction and Problem Solving with C++: Walls & Mirrors provides a firm foundation in data abstraction that emphasizes the distinction between specifications and implementation as the basis for an object-oriented approach. Software engineering principles and concepts as well as UML diagrams are used to enhance student understanding.

Table of 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 Destructor 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.1The 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 C++ 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 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 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.3 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 C++ 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.1.1 Multiple catch Blocks C3.1.2 Uncaught Exceptions C3.5 Programmer-Defined Exception Classes Chapter 7 Stack Implementations 7.1 An Array-Based Implementation 7.2 A Linked Implementation 7.3 Comparing Implementations Chapter 8 Lists 8.1 Specifying the Abstract Data Type List 8.2 Using the List Operations 8.3 Specifications of the ADT List Using Exceptions    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 Linked Implementation of the ADT List 9.2.1 The Header File 9.2.2 The Implementation File 9.2.3 Using Recursion To Process a Linked Chain 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 Order-of-Magnitude 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 Selection Sort 11.1.2 Bubble Sort 11.1.3 Insertion Sort 11.2 Faster Sorting Algorithms 11.2.1 Merge Sort 11.2.2 Quick Sort 11.2.3 Radix Sort 11.3 A Comparison of Sorting Algorithms 11.4 The Standard Template Library: 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.3 The Implementation File 12.2.3 The Efficiency of the Link-Based Implementation 12.3 Implementations That Use the ADT List 12.3.1 Composition 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 a Queue 13.2.1 Reading a String of Characters 13.2.2 Recognizing Palindromes 13.3 The ADT Priority Queue 13.4.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 Classes Overloading Operators Overloading the Stream Operators << and >> Friend Classes and Data Member Access 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 Binary Tree Operations 15.2.2 An Interface Template for the ADT Binary Tree 15.2.3 Traversals of a Binary Tree 15.3 The ADT Binary Search Tree 15.3.1 Binary Search Tree Operations 15.3.2 An Interface Template for the ADT Binary Tree 15.3.3 Searching a Binary Search Tree 15.3.4 Creating a Binary Search Tree 15.3.5 Traversals of a Binary Search Tree Chapter 16 Tree Implementations 16.1 Implementations of the ADT Binary Tree 16.1.1 A Link-Based Implementation 16.1.2 An Array-Based Implementation 16.1.3 Efficiency of Implementations 16.2 An Implementation of the ADT Binary Search Tree 16.2.1 Algorithms for Insertion, Deletion, and Traversal 16.2.2 A Link-Based Implementation 16.2.3 Efficiency of the Implementation 16.2.4 Saving a Binary Search Tree in a File C++ Interlude 6 Iterators Iterator Introduction A List Iterator and Its Use A BST Tree Iterator and Its Use Chapter 17 Heaps An Array-Based Implementation A Heap as a Priority Queue The Heap Sort Chapter 18 Dictionaries and Their Implementations Dictionaries and Key-Value Pairs Linear (Array and Linked) and Hierarchical (Tree) Implementations Hash Functions Resolving Collisions A Hashing Implementation The Efficiency of Hashing Chapter 19 Balanced Search Trees   AVL Trees 2-3 Trees 2-3-4 Trees Red-Black 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 A Sorting Data in an External File 21.3 External Searches 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 Introduction to Templates and the STL Generalizing the ADT Node and List Appendix A Review of C++ Fundamentals Appendix B Important Themes in Programming (currently Section 1.3) Appendix C The Unified Modeling Language (currently in section 1.1) Appendix D The Software Life Cycle (currently section 1.1) Appendix E Mathematical Induction (currently Appendix D) Appendix F Algorithm Verification (currently in section 1.2) Appendix G  Files Appendix H  C++ Header Files and Standard Functions (currently Appendix C) Appendix I C++ Standard Template Library (currently Appendix E) Appendix J C++ Documentation Systems (currently Appendix F) Appendix K ASCII Character Codes (currently Appendix B) Appendix L A Comparison of C++ and Java Appendix M A Comparison of C++ and Python