DATA ABSTRACTION & PROBLEM SOLVING WITH C++

This classic, best selling data structures text 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.

The sixth edition of Data Abstraction and Problem Solving with C++: Walls & Mirrors welcomes Associate Professor Timothy Henry of the University of Rhode Island as a co-author with Frank Carrano. The 6th edition is a significant revision of the previous edition with these goals:
- to place greater emphasis on data abstraction as a problem solving tool;
- to emphasize C++ as an implementation tool;
- to reduce the interdependency of chapters to allow more flexibility for instructors;
- to demonstrate safe and secure programming practices,
- to add VideoNotes
- to include a transition guide from Python to C++

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