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

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.

Author Notes

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.

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.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

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

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 QueueThe 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

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents