Data abstraction & problem solving with C++ : walls and mirrors

✍ Scribed by Frank M. Carrano, Timothy Henry

• Publisher: Pearson
• Year: 2017
• Tongue: English
• Leaves: 867
• Edition: 7
• Category: Library

✦ Synopsis

Concepts of Data Structures and Abstraction for C++ Programmers

The Seventh Edition of Data Abstraction & Problem Solving with C++: Walls and Mirrors introduces fundamental computer science concepts related to the study of data structures. The text explores problem solving and the efficient access and manipulation of data and is intended for students who already have a basic understanding of programming, preferably in C++.

The “walls and mirrors” mentioned in the title represent problem-solving techniques that appear throughout the text. Data abstraction hides the details of a module from the rest of the program, whereas recursion is a repetitive technique that solves a problem by solving smaller versions of the same problems, much as images in facing mirrors grow smaller with each reflection. Along with general changes to improve clarity and correctness, this Seventh Edition features new notes, programming tips, examples, and programming problems, as well as C++11 and C++14 features–including safe memory management using smart pointers–and safe and secure coding techniques.

✦ Table of Contents

Cover
C++ Reserved Keywords
Title Page
Copyright Page
Acknowledgments
Contents
VideoNotes Directory
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.2.1. Initializers
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. Searching a Sorted Array: The Binary Search
2.4.3. Finding the Largest Value in a Sorted or Unsorted Array
2.4.4. Finding the kth Smallest Value of an Unsorted 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
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’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
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.4.1. Multiple catch Blocks
C3.4.2. Uncaught Exceptions
C3.4.3. Where to Handle Exceptions
C3.5. Programmer-Defined Exception Classes
Chapter 7: Implementations of the ADT Stack
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
C++ Interlude 4: Safe Memory Management Using Smart Pointers
C4.1. Raw Pointers
C4.2. Smart Pointers
C4.2.1. Using Shared Pointers
C4.2.2. Revised Node and LinkedList Classes
C4.2.3. Using Unique Pointers
C4.2.4. Using Weak Pointers
C4.3. Other Smart Pointer Features
C4.3.1. A Method Common to All Smart Pointers
C4.3.2. A Method Common to All Shared and Unique Pointers
C4.3.3. Methods Exclusive to Shared Pointers
C4.3.4. A Method Exclusive to Unique Pointers
C4.3.5. Unique Pointers with Arrays
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 5: Class Relationships and Reuse
C5.1. Inheritance Revisited
C5.1.1. Public, Private, and Protected Sections of a Class
C5.1.2. Public, Private, and Protected Inheritance
C5.1.3. Is-a and As-a Relationships
C5.2. Containment: Has-a Relationships
C5.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 and Priority 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 6: Overloaded Operators and Friend Access
C6.1. Overloaded Operators
C6.1.1. Overloading = for Assignment
C6.1.2. Overloading + for Concatenation
C6.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
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
C++ Interlude 7: Iterators
C7.1. Iterators
C7.1.1. Common Iterator Operations
C7.1.2. Using Iterator Operations
C7.1.3. Implementing an Iterator
C7.2. Advanced Iterator Functionality
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. Three Scenarios
18.4. Hashing as a Dictionary Implementation
18.4.1. Hash Functions
18.4.2. Resolving Collisions Using Open Addressing
18.4.3. Resolving Collisions By Restructuring the Hash Table
18.4.4. The Efficiency of Hashing
18.4.5. What Constitutes a Good Hash Function?
18.4.6. Dictionary Traversal: An Inefficient Operation Under Hashing
18.4.7. Using Hashing and Separate Chaining to Implement the ADT Dictionary
Chapter 19: Balanced Search Trees
19.1. Balanced Search Trees
19.2. AVL Trees
19.3. 2-3 Trees
19.3.1. Traversing a 2-3 Tree
19.3.2. Searching a 2-3 Tree
19.3.3. Adding Data to a 2-3 Tree
19.3.4. Removing Data from a 2-3 Tree
19.4. 2-3-4 Trees
19.4.1. Searching and Traversing a 2-3-4 Tree
19.4.2. Adding Data to a 2-3-4 Tree
19.4.3. Removing Data from a 2-3-4 Tree
19.5. Red-Black Trees
19.5.1. Searching and Traversing a Red-Black Tree
19.5.2. Adding to and Removing from a Red-Black Tree
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. Working with External Data
21.2.1. Sorting Data in an External File
21.2.2. Basic Data Management Operations
21.2.3. Indexing an External File
21.2.4. External Hashing
21.2.5. B-Trees
21.2.6. Traversals
21.2.7. Multiple Indexing
C++ Interlude 8: The Standard Template Library
C8.1. STL Container
C8.1.1. STL Container Adapters
C8.1.2. Sequence Containers
C8.1.3. Associative Containers
C8.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: C++ File Fundamentals
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
C++ Operators
Back Cover