| |

| |

| |

Software Development | |

| |

| |

| |

Problem Analysis and Specification | |

| |

| |

| |

Design | |

| |

| |

Top-Down Design | |

| |

| |

Object-Oriented Design | |

| |

| |

Design in the Small | |

| |

| |

| |

Coding | |

| |

| |

| |

Testing, Execution, and Debugging | |

| |

| |

| |

Maintenance | |

| |

| |

Quick Quiz 1.5 | |

| |

| |

Exercises 1.5 | |

| |

| |

Summary | |

| |

| |

Chapter Notes | |

| |

| |

Programming Pointers | |

| |

| |

ADT Tips | |

| |

| |

Programming Problems | |

| |

| |

| |

Introduction to Abstract Data Types | |

| |

| |

| |

A First Look at ADTs and Implementations | |

| |

| |

| |

C++'s Simple Data Types | |

| |

| |

Integer Data | |

| |

| |

Real Data | |

| |

| |

Character Data | |

| |

| |

Boolean Data | |

| |

| |

Quick Quiz 2.2 | |

| |

| |

Exercises 2.2 | |

| |

| |

| |

Programmer-Defined Data Types | |

| |

| |

Typedefs | |

| |

| |

Enumerations | |

| |

| |

Classes | |

| |

| |

Quick Quiz 2.3 | |

| |

| |

Exercises 2.3 | |

| |

| |

| |

Pointers | |

| |

| |

Declaring and Initializing Pointers | |

| |

| |

Basic Pointer Operations | |

| |

| |

Dynamic Memory Allocation--the new Operation | |

| |

| |

A Note about Reference Parameters | |

| |

| |

Quick Quiz 2.4 | |

| |

| |

Exercises 2.4 | |

| |

| |

Summary | |

| |

| |

Chapter Notes | |

| |

| |

Programming Pointers | |

| |

| |

ADT Tips | |

| |

| |

Programming Problems | |

| |

| |

| |

Data Structures and Abstract Data Types | |

| |

| |

| |

Data Structures, Abstract Data Types, and Implementations | |

| |

| |

| |

Static Arrays | |

| |

| |

One-Dimensional Static Arrays | |

| |

| |

The Subscript Operation | |

| |

| |

Arrays as Parameters | |

| |

| |

Out-of-Range Errors | |

| |

| |

Problems with Arrays | |

| |

| |

Quick Quiz 3.2 | |

| |

| |

Exercises 3.2 | |

| |

| |

| |

Multidimensional Arrays (optional) | |

| |

| |

Two-Dimensional Arrays | |

| |

| |

Higher-Dimensional Arrays | |

| |

| |

Array of Array Declarations | |

| |

| |

Multidimensional Arrays as Parameters | |

| |

| |

Quick Quiz 3.3 | |

| |

| |

Exercises 3.3 | |

| |

| |

| |

Dynamic Arrays | |

| |

| |

The new Operation--Dynamic Arrays | |

| |

| |

Other Uses of Pointers | |

| |

| |

Quick Quiz 3.4 | |

| |

| |

Exercises 3.4 | |

| |

| |

| |

C-Style Structs (optional) | |

| |

| |

Pointers to Structs | |

| |

| |

Quick Quiz 3.5 | |

| |

| |

| |

Procedural Programming | |

| |

| |

Example of Procedural Programming | |

| |

| |

Summary | |

| |

| |

Chapter Notes | |

| |

| |

Programming Pointers | |

| |

| |

ADT Tips | |

| |

| |

Programming Problems | |

| |

| |

| |

More about OOP and ADTs--Classes | |

| |

| |

| |

Procedural vs. Object-Oriented Programming | |

| |

| |

Quick Quiz 4.1 | |

| |

| |

| |

Classes | |

| |

| |

Differences between "Traditional" (C) Structs and OOP (C++) Structs and Classes | |

| |

| |

Class Declarations | |

| |

| |

Quick Quiz 4.2 | |

| |

| |

| |

Example: A First Version of a User-Defined Time Class | |

| |

| |

Why not make all class members public? | |

| |

| |

Implementation of a Class | |

| |

| |

Some Observations | |

| |

| |

| |

Class Constructors | |

| |

| |

| |

Other Class Operations | |

| |

| |

Copy Operations--Initialization and Assignment | |

| |

| |

Accessors and Mutators | |

| |

| |

Overloading Operators | |

| |

| |

Overloading Input/Output Operators | |

| |

| |

Other Operations: Advance and the Relational Operators | |

| |

| |

Summary and a Few Other Items | |

| |

| |

Pointers to Class Objects | |

| |

| |

The this Pointer | |

| |

| |

Quick Quiz 4.5 | |

| |

| |

Exercises 4.5 | |

| |

| |

Summary | |

| |

| |

Chapter Notes | |

| |

| |

Programming Pointers | |

| |

| |

ADT Tips | |

| |

| |

Programming Problems | |

| |

| |

| |

Standard C++ Input/Output and String Classes | |

| |

| |

| |

The C++ Standard I/O Classes | |

| |

| |

The istream Class | |

| |

| |

The ostream Class | |

| |

| |

File I/O: ifstream and ofstream Classes | |

| |

| |

The I/O Class Hierarchy | |

| |

| |

Quick Quiz 5.1 | |

| |

| |

| |

The C++ String Types | |

| |

| |

C-Style Strings | |

| |

| |

The C++ string Class | |

| |

| |

String Streams | |

| |

| |

Quick Quiz 5.2 | |

| |

| |

Exercises 5.2 | |

| |

| |

| |

Case Study: Text Editing | |

| |

| |

| |

Introduction to Pattern Matching (optional) | |

| |

| |

| |

Introduction to Data Encryption (optional) | |

| |

| |

Data Encryption Standard | |

| |

| |

Public-Key Encryption | |

| |

| |

Summary | |

| |

| |

Chapter Notes | |

| |

| |

Programming Pointers | |

| |

| |

ADT Tips | |

| |

| |

Programming Problems | |

| |

| |

| |

Lists | |

| |

| |

| |

List as an ADT | |

| |

| |

Designing and Building a List Class | |

| |

| |

| |

An Array-Based Implementation of Lists | |

| |

| |

Selecting a Storage Structure | |

| |

| |

Implementing the Operations | |

| |

| |

A List Class With Static Array Storage | |

| |

| |

| |

An Array-Based Implementation of Lists with Dynamic Allocation | |

| |

| |

Dynamic Allocation in Classes--Destructors, Copy Constructors, and Assignment | |

| |

| |

A Final Note | |

| |

| |

Quick Quiz 6.3 | |

| |

| |

Exercises 6.3 | |

| |

| |

| |

Introduction to Linked Lists | |

| |

| |

What Are They? | |

| |

| |

Implementing the Basic List Operations | |

| |

| |

Summary | |

| |

| |

Quick Quiz 6.4 | |

| |

| |

Exercises 6.4 | |

| |

| |

| |

A Pointer-Based Implementation of Linked Lists in C++ | |

| |

| |

Node Structure | |

| |

| |

Data Members for Linked-List Implementation | |

| |

| |

Function Members for Linked-List Implementation | |

| |

| |

Exercises 6.5 | |

| |

| |

| |

An Array-Based Implementation of Linked Lists (optional) | |

| |

| |

Node Structure | |

| |

| |

Organizing the Storage Pool | |

| |

| |

Exercises 6.6 | |

| |

| |

Summary | |

| |

| |

Chapter Notes | |

| |

| |

Programming Pointers | |

| |

| |

ADT Tips | |

| |

| |

Programming Problems | |

| |

| |

| |

Stacks | |

| |

| |

| |

Introduction to Stacks | |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

Designing and Building a Stack Class--Array-Based | |

| |

| |

Selecting Storage Structures | |

| |

| |

Implementing the Operations | |

| |

| |

The Complete Stack Class | |

| |

| |

Using a Dynamic Array to Store the Stack Elements | |

| |

| |

A Look Ahead | |

| |

| |

Quick Quiz 7.2 | |

| |

| |

Exercises 7.2 | |

| |

| |

| |

Linked Stacks | |

| |

| |

Selecting a Storage Structure | |

| |

| |

Implementing the Operations | |

| |

| |

The Complete Stack Class: Linked List Version | |

| |

| |

Exercises 7.3 | |

| |

| |

| |

Use of Stacks in Function Calls | |

| |

| |

Quick Quiz 7.4 | |

| |

| |

Exercises 7.4 | |

| |

| |

| |

Case Study: Postfix (RPN) Notation | |

| |

| |

Evaluating Postfix Expressions | |

| |

| |

Converting Infix Expressions to Postfix | |

| |

| |

Quick Quiz 7.5 | |

| |

| |

Exercises 7.5 | |

| |

| |

Summary | |

| |

| |

Chapter Notes | |

| |

| |

Programming Pointers | |

| |

| |

ADT Tips | |

| |

| |

Programming Problems | |

| |

| |

| |

Queues | |

| |

| |

| |

Introduction to Queues | |

| |

| |

Example: Drill and Practice Problems | |

| |

| |

| |

Designing and Building a Queue Class--Array-Based | |

| |

| |

Using a Static Array to Store the Queue Elements | |

| |

| |

Using a Dynamic Array to Store the Queue Elements | |

| |

| |

Quick Quiz 8.2 | |

| |

| |

Exercises 8.2 | |

| |

| |

| |

Linked Queues | |

| |

| |

A Natural Linked-List Implementation | |

| |

| |

Using a Circular Linked List | |

| |

| |

Quick Quiz 8.3 | |

| |

| |

Exercises 8.3 | |

| |

| |

| |

Application of Queues: Buffers and Scheduling | |

| |

| |

Quick Quiz 8.4 | |

| |

| |

Exercises 8.4 | |

| |

| |

| |

Case Study: Information Center Simulation | |

| |

| |

Problem Analysis and Specification | |

| |

| |

Building a Simulation Class | |

| |

| |

The Timer and Call Classes | |

| |

| |

Summary | |

| |

| |

Chapter Notes | |

| |

| |

Programming Pointers | |

| |

| |

ADT Tips | |

| |

| |

Programming Problems | |

| |

| |

| |

ADT Implementations: Templates and Standard Containers | |

| |

| |

| |

Introduction: The Evolution of Reusability and Genericity | |

| |

| |

From Algorithms to Algorithms | |

| |

| |

From Data to Containers | |

| |

| |

| |

Function Genericity--Overloading and Templates | |

| |

| |

Overloading | |

| |

| |

Function Templates | |

| |

| |

Another Example: Displaying an Array | |

| |

| |

| |

Class Genericity--Templates | |

| |

| |

What's Wrong with typedef? | |

| |

| |

Class Templates | |

| |

| |

An Alternative Version of the Stack Class Template | |

| |

| |

A Quick Peek at the Standard C++ Container Class Templates | |

| |

| |

Quick Quiz 9.3 | |

| |

| |

Exercises 9.3 | |

| |

| |

| |

The vector Container | |

| |

| |

Declaring vector Objects | |

| |

| |

Some vector Operations | |

| |

| |

A First Look Under the Hood--Increasing the Capacity | |

| |

| |

A First Look at Iterators | |

| |

| |

Some vector Methods Involving Iterators | |

| |

| |

Wrap-up: vectors versus Arrays | |

| |

| |

Quick Quiz 9.4 | |

| |

| |

Exercises 9.4 | |

| |

| |

| |

Case Study: Counting Computer Logins | |

| |

| |

| |

Multidimensional vectors (Optional) | |

| |

| |

Two-Dimensional vector Objects | |

| |

| |

Two-Dimensional vector Operations | |

| |

| |

Exercises 9.6 | |

| |

| |

| |

Other Standard Containers--deque, stack, and queue | |

| |

| |

STL's deque Class Template | |

| |

| |

A New (But Unnecessary) Version of Our Stack Class Template | |

| |

| |

STL's stack Adapter | |

| |

| |

STL's queue Adapter | |

| |

| |

Quick Quiz 9.7 | |

| |

| |

| |

Bitsets and Valarrays (optional) | |

| |

| |

Bitsets | |

| |

| |

Valarrays | |

| |

| |

Slices, Masks, and Indirect Arrays | |

| |

| |

Summary | |

| |

| |

Chapter Notes | |

| |

| |

Programming Pointers | |

| |

| |

ADT Tips | |

| |

| |

Programming Problems | |

| |

| |

| |

ADT Implementation: Recursion, Algorithm Analysis, and Standard Algorithms | |

| |

| |

| |

Recursion | |

| |

| |

Examples of Recursive Functions | |

| |

| |

Coding Recursive Functions | |

| |

| |

Example of Inappropriate Recursion: Fibonacci Numbers | |

| |

| |

Example: Binary Search | |

| |

| |

Example: Palindrome Checker | |

| |

| |

Quick Quiz 10.1 | |

| |

| |

Exercises 10.1 | |

| |

| |

| |

Examples of Recursion: Towers of Hanoi; Parsing | |

| |

| |

Towers of Hanoi | |

| |

| |

Parsing | |

| |

| |

Exercises 10.2 | |

| |

| |

| |

Implementing Recursion | |

| |

| |

| |

Algorithm Efficiency | |

| |

| |

Quick Quiz 10.4 | |

| |

| |

Exercises 10.4 | |

| |

| |

| |

Standard Algorithms in C++ | |

| |

| |

Example: STL's sort Algorithm | |

| |

| |

A Sample of STL Algorithms | |

| |

| |

Algorithms from the [left angle bracket]numeric[right angle bracket] Library | |

| |

| |

Example: Judging Figure Skating | |

| |

| |

Quick Quiz 10.5 | |

| |

| |

| |

Proving Algorithms Correct (optional) | |

| |

| |

Example: Calculating the Mean | |

| |

| |

Example: Recursive Power Function | |

| |

| |

Summary | |

| |

| |

Exercises 10.6 | |

| |

| |

Summary | |

| |

| |

Chapter Notes | |

| |

| |

Programming Pointers | |

| |

| |

ADT Tips | |

| |

| |

Programming Problems | |

| |

| |

| |

More Linking Up with Linked Lists | |

| |

| |

| |

Some Variants of Singly-Linked Lists | |

| |

| |

Linked Lists with Head Nodes | |

| |

| |

Circular Linked Lists | |

| |

| |

Quick Quiz 11.1 | |

| |

| |

Exercises 11.1 | |

| |

| |

| |

Linked Implementation of Sparse Polynomials | |

| |

| |

Exercises 11.2 | |

| |

| |

| |

Doubly-Linked Lists and the Standard C++ list | |

| |

| |

Doubly-Linked Lists | |

| |

| |

The Standard list Class Template | |

| |

| |

Example: Internet Addresses | |

| |

| |

A Look under the Hood at C++'s list | |

| |

| |

Exercises 11.3 | |

| |

| |

| |

Case Study: Large-Integer Arithmetic | |

| |

| |

Problem | |

| |

| |

Design | |

| |

| |

Implementation | |

| |

| |

Exercises 11.4 | |

| |

| |

| |

Other Multiply-Linked Lists | |

| |

| |

Multiply-Ordered Lists | |

| |

| |

Sparse Matrices | |

| |

| |

Generalized Lists | |

| |

| |

Exercises 11.5 | |

| |

| |

Summary | |

| |

| |

Chapter Notes | |

| |

| |

Programming Pointers | |

| |

| |

ADT Tips | |

| |

| |

Programming Problems | |

| |

| |

| |

Searching: Binary Trees and Hash Tables | |

| |

| |

| |

Review of Linear Search and Binary Search | |

| |

| |

Linear Search | |

| |

| |

Binary Search | |

| |

| |

Exercises 12.1 | |

| |

| |

| |

Introduction to Binary Trees | |

| |

| |

Tree Terminology | |

| |

| |

Some Examples of Binary Trees | |

| |

| |

Array Representation of Binary Trees | |

| |

| |

Linked Representation of Binary Trees | |

| |

| |

Quick Quiz 12.2 | |

| |

| |

Exercises 12.2 | |

| |

| |

| |

Binary Trees as Recursive Data Structures | |

| |

| |

Traversals | |

| |

| |

Quick Quiz 12.3 | |

| |

| |

Exercises 12.3 | |

| |

| |

| |

Binary Search Trees | |

| |

| |

Implementing BSTs | |

| |

| |

BST Traversals | |

| |

| |

Searching a BST | |

| |

| |

Inserting into a BST | |

| |

| |

Removing a Node from a BST | |

| |

| |

Problem of Lopsidedness | |

| |

| |

Quick Quiz 12.4 | |

| |

| |

Exercises 12.4 | |

| |

| |

| |

Case Study: Validating Computer Logins | |

| |

| |

Problem | |

| |

| |

Design | |

| |

| |

Coding | |

| |

| |

| |

Threaded Binary Search Trees (Optional) | |

| |

| |

Quick Quiz 12.6 | |

| |

| |

Exercises 12.6 | |

| |

| |

| |

Hash Tables | |

| |

| |

Hash Functions | |

| |

| |

Collision Strategies | |

| |

| |

Improvements | |

| |

| |

Quick Quiz 12.7 | |

| |

| |

Exercises 12.7 | |

| |

| |

Summary | |

| |

| |

Chapter Notes | |

| |

| |

Programming Pointers | |

| |

| |

ADT Tips | |

| |

| |

Programming Problems | |

| |

| |

| |

Sorting | |

| |

| |

| |

Some O(n[superscript 2]) Sorting Schemes | |

| |

| |

Selection Sorts | |

| |

| |

Exchange Sorts | |

| |

| |

Insertion Sorts | |

| |

| |

Evaluation of These Sorting Schemes | |

| |

| |

Indirect Sorting | |

| |

| |

Quick Quiz 13.1 | |

| |

| |

Exercises 13.1 | |

| |

| |

| |

Heaps, Heapsort, and Priority Queues | |

| |

| |

Heaps | |

| |

| |

Basic Heap Operations | |

| |

| |

Heapsort | |

| |

| |

Heap Algorithms in STL | |

| |

| |

Heaps and Priority Queues | |

| |

| |

Quick Quiz 13.2 | |

| |

| |

Exercises 13.2 | |

| |

| |

| |

Quicksort | |

| |

| |

The Split Operation | |

| |

| |

Quicksort | |

| |

| |

Improvements | |

| |

| |

Quick Quiz 13.3 | |

| |

| |

Exercises 13.3 | |

| |

| |

| |

Mergesort | |

| |

| |

Merging Lists | |

| |

| |

Binary Mergesort | |

| |

| |

Natural Mergesort | |

| |

| |

Quick Quiz 13.4 | |

| |

| |

Exercises 13.4 | |

| |

| |

| |

Radix Sort | |

| |

| |

Exercises 13.5 | |

| |

| |

Summary | |

| |

| |

Chapter Notes | |

| |

| |

Programming Pointers | |

| |

| |

ADT Tips | |

| |

| |

Programming Problems | |

| |

| |

| |

OOP and ADTs | |

| |

| |

| |

A Brief History and Overview of OOP and ADTs | |

| |

| |

Encapsulation | |

| |

| |

Inheritance | |

| |

| |

Polymorphism and Dynamic Binding | |

| |

| |

Quick Quiz 14.1 | |

| |

| |

| |

Inheritance and Object-Oriented Design | |

| |

| |

Example 1: Licenses | |

| |

| |

Public, Private, and Protected Sections | |

| |

| |

The Form of Derived Classes | |

| |

| |

The Is-a, Has-a, and Uses-a Relationships Between Classes | |

| |

| |

Quick Quiz 14.2 | |

| |

| |

Exercises 14.2 | |

| |

| |

| |

Building Derived Classes | |

| |

| |

Derived Class Constructors | |

| |

| |

Accessing Inherited Data Members | |

| |

| |

Reusing Operations | |

| |

| |

Example: Stacks and Bounded Stacks | |

| |

| |

| |

Case Study: Payroll | |

| |

| |

Problem | |

| |

| |

Design | |

| |

| |

| |

Polymorphism, Virtual Functions, and ADTs | |

| |

| |

Why Polymorphism is Needed: a Binding Problem | |

| |

| |

Virtual Functions and Dynamic Binding | |

| |

| |

| |

Using Handles | |

| |

| |

| |

Stacks and Bounded Stacks | |

| |

| |

Pure Virtual Functions and Abstract Classes | |

| |

| |

Quick Quiz 14.5 | |

| |

| |

Exercises 14.5 | |

| |

| |

| |

Case Study: A Heterogeneous Data Structure | |

| |

| |

The Need for Virtual Functions | |

| |

| |

Summary | |

| |

| |

Chapter Notes | |

| |

| |

Programming Pointers | |

| |

| |

ADT Tips | |

| |

| |

Programming Problems | |

| |

| |

| |

Trees | |

| |

| |

| |

Case Study: Huffman Codes | |

| |

| |

Variable-Length Codes | |

| |

| |

Immediate Decodability | |

| |

| |

Huffman Codes | |

| |

| |

Exercises 15.1 | |

| |

| |

| |

Tree Balancing: AVL Trees | |

| |

| |

Example: A BST of State Abbreviations | |

| |

| |

The Basic Rebalancing Rotations | |

| |

| |

Quick Quiz 15.2 | |

| |

| |

Exercises 15.2 | |

| |

| |

| |

2-3-4 Trees, Red-Black Trees, B-Trees, and Other Trees | |

| |

| |

2-3-4 Trees | |

| |

| |

Red-Black Trees | |

| |

| |

B-Trees | |

| |

| |

Representing Trees and Forests as Binary Trees | |

| |

| |

Quick Quiz 15.3 | |

| |

| |

Exercises 15.3 | |

| |

| |

| |

Associative Containers in STL--maps (optional) | |

| |

| |

Quick Quiz 15.4 | |

| |

| |

Summary | |

| |

| |

Chapter Notes | |

| |

| |

Programming Pointers | |

| |

| |

ADT Tips | |

| |

| |

Programming Problems | |

| |

| |

| |

Graphs and Digraphs | |

| |

| |

| |

Directed Graphs | |

| |

| |

Adjacency-Matrix Representation | |

| |

| |

Adjacency-List Representation | |

| |

| |

Quick Quiz 16.1 | |

| |

| |

Exercises 16.1 | |

| |

| |

| |

Searching and Traversing Digraphs | |

| |

| |

Depth-First Search | |

| |

| |

Breadth-First Search | |

| |

| |

Traversal and Shortest-Path Problems | |

| |

| |

NP-Complete Problems | |

| |

| |

Quick Quiz 16.2 | |

| |

| |

Exercises 16.2 | |

| |

| |

| |

Graphs | |

| |

| |

Adjacency-Matrix and Adjacency-List Representations | |

| |

| |

Edge-List Representation | |

| |

| |

Connectedness | |

| |

| |

Quick Quiz 16.3 | |

| |

| |

Exercises 16.3 | |

| |

| |

Summary | |

| |

| |

Chapter Notes | |

| |

| |

Programming Pointers | |

| |

| |

ADT Tips | |

| |

| |

Programming Problems | |

| |

| |

Appendixes | |

| |

| |

| |

ASCII Character Set | |

| |

| |

| |

Number Systems | |

| |

| |

| |

Basic C++ | |

| |

| |

| |

C++ Program Structure | |

| |

| |

| |

Compiler Directives | |

| |

| |

| |

Standard Libraries | |

| |

| |

| |

Comments | |

| |

| |

| |

Identifiers and Keywords | |

| |

| |

| |

Fundamental Data Types | |

| |

| |

| |

Literals | |

| |

| |

| |

Declarations | |

| |

| |

| |

Operators and Expressions | |

| |

| |

| |

Control Structures | |

| |

| |

| |

Functions | |

| |

| |

| |

Lifetimes, Scopes, and Namespaces | |

| |

| |

| |

Files | |

| |

| |

| |

Other C++ Features | |

| |

| |

| |

Stream Operations | |

| |

| |

| |

String Operations | |

| |

| |

| |

Exceptions | |

| |

| |

| |

More About Function Templates | |

| |

| |

| |

Other Applications of Pointers | |

| |

| |

| |

From Java to C++ | |

| |

| |

| |

Program Structure | |

| |

| |

| |

Using and Compiler Directives | |

| |

| |

| |

Input and Output ([section]C.9, [section]C.13, & [section]D.1) | |

| |

| |

| |

Data Types | |

| |

| |

| |

Variables and Constants | |

| |

| |

| |

Functions | |

| |

| |

| |

Operator Overloading | |

| |

| |

| |

Things the Same in Both C++ and Java | |

| |

| |

| |

More Differences Between C++ and Java | |

| |

| |

| |

Answers to Quick Quizzes | |

| |

| |

Index | |