C++:
An Introduction to Data Structures
by
Larry Nyhoff
(Scheduled for publication in November, 1998)
TABLE OF
CONTENTS
1 Software Engineering
1.1 Problem Analysis and Specification
1.2 Design
Objects
Operations
Data
Algorithms
Design of Function YearSum()
Design of Function DisplayTable()
Some Final Comments About Algorithms
1.3 Coding
1.4 Testing, Execution, and Debugging
1.5 Maintenance
Quick Quiz 1.5
Exercises 1.5
Programming Pointers
ADT Tips
Programming Problems
2 Introduction to Data Structures
and Abstract Data Types C-Style Types
2.1 Data Structures, Abstract Data Types, and Implementations
2.2 Simple Data Types
Boolean Data
Character Data
Integer Data
Real Data
Summary
Quick Quiz 2.2
Exercises 2.2
2.3 Arrays
One-Dimensional Arrays
The Subscript Operation
Arrays as Parameters
Out-of-Range Errors
Problems with Arrays
Multidimensional Arrays
Quick Quiz 2.3
Exercises 2.3
2.4 Structures
Why are Structures Needed?
C-Style Structs
Struct Operations
Unions
Structs in Memory
Quick Quiz 2.4
Exercises 2.4
2.5 Procedural Programming
Example: A Time Data Type
PP vs. OOP
Programming Pointers
ADT Tips
Programming Problems
3 More About Data Structures
and ADTs C++ Types
3.1 Classes
Differences between "traditional" (C) structs and OOP (C++) structs
and classes
Class Declarations
Example: C++'s Standard I/O Classes
3.2 Example of a User-Defined Type: A Time
Class
Implementation of a Class
Some Observations
Class Constructors
Copy Operators Initialization and Assignment
Access Functions
Input/Output Overloading Operators Friend Functions
Other Operations: Relational Operators and Advance
Summary and a Few Other Items
Quick Quiz 3.2
Exercises 3.2
3.3 Strings as ADTs
C-Style Implementation of Strings
A String Class
Exercises 3.3
3.4 The C++ string
Type
Definitions and Constructors
Storage
Input/Output
stringstreams
Modifiers
Copiers
Accessing Individual Characters
Search Operations
Comparisons
string and C-Style
Strings
Quick Quiz 3.4
Exercises 3.4
3.5 An Example: Text Editing
3.6 Data Encryption (optional)
Data Encryption Standard
Public-Key Encryption
Exercises 3.6
3.7 Pattern Matching (optional)
Programming Pointers
ADT Tips
Programming Problems
4 Stacks
4.1 Introduction to Stacks
4.2 Designing and Building a Stack
Class
Designing a Stack
Class
Implementing a Stack
Class
Selecting Data Members
Function Members
A Look Ahead
Quick Quiz 4.2
Exercises 4.2
4.3 Two Applications of Stacks: Function Calls; Reverse Polish Notation
Use of Stacks in Function Calls
Application of Stacks to Reverse Polish Notation
Quick Quiz 4.3
Exercises 4.3
Programming Pointers
ADT Tips
Programming Problems
5 Queues
5.1 Introduction to Queues
Example: Drill and Practice Problems
Examples of Scheduling Queues
5.2 Array-Based Implementation of Queues
Quick Quiz 5.2
Exercises 5.2
5.3 Application of Queues: Information Center Simulation
Problem Analysis and Specification
Design
Coding and Execution
Exercises 5.3
Programming Pointers
ADT Tips
Programming Problems
6 Improving ADTs Part
1: Templates and Standard Containers
6.1 Introduction: The Evolution of Reusability and Genericity
From Algorithms to Algorithms
From Data to Containers
6.2 Function Genericity Overloading and Templates
Overloading
Function Templates
Example: Displaying an Array
More About Function Templates
6.3 Class Genericity Templates
What's wrong with typedef?
Class Templates
A Stack Class
Template
An Alternative Version of the Stack
Class Template
The Standard C++ Container Class Templates
Quick Quiz 6.3
Exercises 6.3
6.4 The vector Container
Defining vector
Objects
Some vector Operations
A First Look Under the Hood Increasing the Capacity
A First Look at Iterators
Some vector Function
Members Involving Iterators
Wrap-up: vectors
vs. arrays
Quick Quiz 6.4
Exercises 6.4
6.5 Multidimensional vectors
Two-Dimensional vector
Objects
Two-Dimensional vector
Operations
Defining Two-Dimensional vector
Functions
Exercises 6.5
6.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 6.6
6.7 Bitsets (optional)
Declarations of bitset Objects
FONT FACE="Courier New">bitsetOperations
Implementing Sets with FONT FACE="Courier New">bitsets
Example: Finding Prime Numbers with the Sieve of Eratosthenes
Exercises 6.7
6.8 Valarrays (optional)
Declarations of valarray
Objects
valarray Operations
Slices, Masks, and Indirect Arrays
Exercises 6.8
Programming Pointers
ADT Tips
Programming Problems
7 Improving ADTs
Part 2: Recursion, Algorithm Analysis, and
Standard Algorithms
7.1 Recursion
Examples: Recursive Power and Factorial Functions
Example of Bad Recursion: Fibonacci Numbers
Example: Binary Search
Example: Palindrome Checker
Quick Quiz 7.1
Exercises 7.1
7.2 More Examples of Recursion: Towers of Hanoi; Parsing
Towers of Hanoi
Parsing
Exercises 7.2
7.3 Implementing Recursion
7.4 Algorithm Efficiency
Quick Quiz 7.4
Exercises 7.4
7.5 Standard Algorithms in C++
Example: STL's sort
Algorithm
A Sample of STL Algorithms
Algorithms from the <numeric>
Library
Example: Judging Figure Skating
Exercises 7.5
7.6 Proving Algorithms Correct
Example: Calculating the Mean
Example: Recursive Power Function
Summary
Exercises 7.6
Programming Pointers
ADT Tips
Programming Problems
8 Lists
8.1 Sequential Storage Implementation of Lists
Storage Structure
Implementing the Operations
Quick Quiz 8.1
Exercises 8.1
8.2 Introduction to Linked Lists
What Are They?
Implementing the Basic List Operations
Summary
Quick Quiz 8.2
Exercises 8.2
8.3 An Array-Based Implementation of Linked Lists
Node Structure
Organizing the Storage Pool
Exercises 8.3
8.4 Pointers in C++
Pointers
Basic Pointer Operations
A Note About Reference Parameters
Summary
Quick Quiz 8.4
Exercises 8.4
8.5 Run-Time Allocation and Deallocation
The newOperation
Run-Time Arrays
The deleteOperation
Run-Time Allocation in Classes Destructors, Copy Constructors, and
Assignment
Quick Quiz 8.5
Exercises 8.5
8.6 A Pointer-Based Implementation of Linked Lists in C++
Node Structure
Data Members for LinkedLists
Function Members for LinkedLists
Exercises 8.6
8.7 The standard list
Class Template
Comparing list
with other containers
Iterators
Basic list operations
Example: Internet Addresses
Quick Quiz 8.7
Exercises 8.7
8.8 Other Applications of Pointers
Command-Line Arguments
Functions as Arguments
Exercises 8.8
Programming Pointers
ADT Tips
Programming Problems
9 Other Linked Structures
9.1 Some Variants of Singly-Linked Lists
Linked Stacks and Queues
Linked Lists with Head Nodes and/or Trailer Nodes
Circular Linked Lists
Quick Quiz 9.1
Exercises 9.1
9.2 Linked Implementation of Sparse Polynomials
9.3 Hash Tables
Hash Functions
Collision Strategies
Improvements
Quick Quiz 9.3
Exercises 9.3
9.4 Doubly-Linked Lists and the Standard C++ list
Doubly-Linked Lists
A Look Under the Hood at C++'s list
Application: Large-Integer Arithmetic
Exercises 9.4
9.5 Other Multiply-Linked Lists
Multiply-Ordered Lists
Sparse Matrices
Generalized Lists
Exercises 9.5
Programming Pointers
ADT Tips
Programming Problems
10 Binary Trees
10.1 Review of Linear Search and Binary Search
Linear Search
Binary Search
10.2 Introduction to Binary Trees
Tree Terminology and Examples
Array Representation of Binary Trees
Linked Representation of Binary Trees
10.3 Binary Search Trees
Searching a BST
Inserting into a BST
Example: Validating Computer Logins
Problem of LopsidednessExercises 10.3
10.4 Binary Trees as Recursive Data Structures
Traversals
Recursive Searching
Recursive Insertion
Deletion
Quick Quiz 10.4
Exercises 10.4
10.5 Application of Binary Trees: Huffman Codes
Variable-Length Codes
Immediate Decodability
Huffman Codes
Exercises 10.5
Programming Pointers
ADT Tips
Programming Problems
11 Sorting
11.1 Some O(n2) Sorting Schemes
Selection Sorts
Exchange Sorts
Insertion Sorts
Evaluation of These Sorting Schemes
Quick Quiz 11.1
Exercises 11.1
11.2 Heaps and Heapsort
Heaps
Basic Heap Operations
Heapsort
Heap Algorithms in STL
Heaps and Priority Queues
Quick Quiz 11.2
Exercises 11.2
11.3 Quicksort
The Split Operation
Quicksort
Improvements
Quick Quiz 11.3
Exercises 11.3
11.4 Mergesort
Merging Files
Binary Mergesort
Natural Mergesort
Quick Quiz 11.4
Exercises 11.4
Programming Pointers
ADT Tips
Programming Problems
12 OOP and ADTs
12.1 A Brief History and Overview of OOP and ADTs
Encapsulation
Inheritance
Polymorphism and Dynamic Binding
Quick Quiz 12.1
12.2 Inheritance and Object-Oriented Design
From OCD to OOD
Example 1 of OOD: Licenses
Preferred Approach: Inheritance
The Is-a, Has-a, and Uses-a Relationships Between Classes
Example 2 of OOD: Payroll
Operations in Derived Classes
Constructors in Derived Classes
Example 3 of OOD: Restricted Stacks
Example 4 of OOD: Priority Queues
Quick Quiz 12.2
Exercises 12.2
12.3 Polymorphism, Virtual Functions, and ADTs
A Binding Problem
Virtual Functions and Dynamic Binding
Example: Stacks, Bounded Stacks, and Scrolls
Pure Virtual Functions and Abstract Classes
Quick Quiz 12.3
Exercises 12.3
12.4 Heterogeneous Data Structures
Creating Heterogeneous Data Structures
The Need for Virtual Functions
Programming Pointers
ADT Tips
Programming Problems
13 Trees
3.1 Threaded Binary Search Trees
Quick Quiz 13.1
Exercises 13.1
13.2 Tree Balancing: AVL Trees
Example: A BST of State Abbreviations
The Basic Rebalancing Rotations
Quick Quiz 13.2
Exercises 13.2
13.3 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 13.3
Exercises 13.3
13.4 Associative Containers in STL maps
Programming Pointers
ADT Tips
Programming Problems
14 Graphs and Digraphs
14.1 Directed Graphs
Adjacency-Matrix Representation
Adjacency-List Representation
Quick Quiz 14.1
Exercises 14.1
14.2 Searching and Traversing Digraphs
Depth-First Search
Breadth-First Search
Traversal and Shortest-Path Problems
Quick Quiz 14.2
Exercises 14.2
14.3 Graphs
Adjacency-Matrix and Adjacency-List Representations
Edge-List Representation
Connectedness
Quick Quiz 14.3
Exercises 14.3
APPENDIXES
A ASCII Codes
B. Number Systems
C. Basic C++
C.1 C++ Program Structure
C.2 Compiler Directives
C.3 Standard Libraries
C.4 Comments
C.5 Identifiers and Keywords
C.6 Fundamental Data Types
C.7 Literals
C.8 Declarations
C.9 Operators and Expressions
C.10 Control Structures
C.11 Functions
C.12 Object Lifetimes, Scopes, and Namespaces
C.13 Files
D. Other C++ Features
D.1 Arrays, Structs, and Unions
D.2 Stream Operations
D.3 String Operations
D.4 Exceptions
D.5 Other Applications of Pointers
E. Answers to Quick Quizzes
Index