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
About the Author :
Frank M. Carrano is a professor emeritus of computer science at the University of Rhode Island. He received the Ph.D. degree in computer science from Syracuse University in 1969. His interests include data structures, computer science education, social issues in computing, and numerical computation. Professor Carrano is particularly interested in the design and delivery of undergraduate courses in computer science. He has authored several well-known computer science textbooks for undergraduates.
Frank’s Making it Real blog http://frank-m-carrano.com/blog/ extends his textbooks and lectures to a lively discussion with instructors and students about teaching and learning computer science.
Follow Frank on Twitter: http://twitter.com/Frank_M_Carrano
Find him on Facebook: https://www.facebook.com/makingitreal
For nearly thirty years, Dr. Timothy M. Henry, PMP, has been teaching computer science concepts along with managing information technology projects for the U. S. Coast Guard and IT consulting companies. His professional expertise encompasses many areas of information technology - design, development, implementation, testing and security. Many of the projects managed by Dr. Henry have successfully used cutting edge secure communication and 3D interactive technologies in novel ways. He has over fifteen years experience teaching computer science and is currently a member of the Computer Science and Statistics faculty at the University of Rhode Island.
He earned his M. S. in Computer Science from Old Dominion University while serving as the IT Director at the Coast Guard's Reserve Training Center in Yorktown, VA. He received his Ph.D. in Applied Mathematics from the University of Rhode Island in 2001.
