Data Structures and Problem Solving Using C++ (2nd Edition)

by Mark Allen Weiss (Author)

Focus Theory Implementation   Level Elementary Intermediate Advanced Language C++     Explore "Data Structures and Problem Solving Using C++ (2nd Edition)" on Amazon.com

Table of Contents

Part 1 : Objects and C++

Chapter 1		Arrays, Pointers, and Structures
1.1		What are Pointers, Arrays and Structures?
1.2		Arrays and Strings
		1.2.1 First-Class Versus Second-Class Objects
		1.2.2 Using the vector
		1.2.3 Resizing a vector
		1.2.4 push_back size and capacity
		1.2.5 Parameter-Passing Mechanisms
		1.2.6 Primitive Arrays of Constants
		1.2.7 Multidimensional Arrays
		1.2.8 The Standard Library string type
1.3		Pointer Syntax in C++
1.4		Dynamic Memory Management
		1.4.1 The new Operator
		1.4.2 Garbage Collection and delete
		1.4.3 Stale Pointers, Double Deletion, and More
1.5		Reference Variables
1.6		Structures
		1.6.1 Pointers to Structures
		1.6.2 Exogenous Versus Indigenous Data and Shallow Versus Deep Copying
		1.6.3 Noncontiguous Lists / Linked Lists
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
		References
Chapter 2		Objects and Classes
2.1		What is Object-Oriented Programming?
2.2		Basic class Syntax
		2.2.1 Class Members
		2.2.2 Extra Constructor Syntax and Accessors
		2.2.3 Separation of Interface and Implementation
		2.2.4 The Big Three: Destructor, Copy Constructor, and operator=
		2.2.5 Default Constructor
2.3		Additional C++ Features
		2.3.1 Initialization Versus Assignment in the Constructor Revisited
		2.3.2 Type Conversions
		2.3.3 Operator Overloading
		2.3.4 Input and Output and Friends
2.4		Some Common Idioms
		2.4.1 Avoiding Friends
		2.4.2 Static Class Members
		2.4.3 The enum Trick for Integer Class Constants
2.5		Exceptions
2.6		A string Class
2.7		Recap: What Gets Called and What Are the Defaults?
2.8		Composition
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
		References
Chapter 3		Templates
3.1		What Is a Template?
3.2		Function Templates
3.3		A Sorting Function Template
3.4		Class Templates
		3.4.1 A MemoryCell Template
		3.4.2 Implementing the vector Class Template
3.5		Templates of Templates: A matrix Class
		3.5.1 The Data Members, Constructor, and Basic Accessors
		3.5.2 operator []
		3.5.3 Destructor, Copy Assignment, and Copy Constructor
3.6		Fancy Templates
		3.6.1 Multiple Template Parameters
		3.6.2 Default Template Parameters
		3.6.3 The Reserved Word typename
3.7		Bugs Associated with Templates
		3.7.1 Bad Error Messages and Inconsistent Rules
		3.7.2 Template-Matching Algorithms
		3.7.3 Nested Classes in a Template
		3.7.4 Static Members in Class Templates
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
Chapter 4		Inheritance
4.1		What Is Inheritance?
4.2		Inheritance Basics
		4.2.1 Visibility Rules
		4.2.2 The Constructor and Base Class Initialization
		4.2.3 Adding Members
		4.2.4 Overriding a Method
		4.2.5 Static and Dynamic Binding
		4.2.6 The Default Constructor, Copy Constructor, Copy Assignment Operator, and Destructor
		4.2.7 Constructors and Destructors : Virtual or Non Virtual?
		4.2.8 Abstract Methods and Classes
4.3		Example: Expanding the Shape Class
4.4		Tricky C++ Details
		4.4.1 Static Binding of Parameters
		4.4.2 Default Parameters
		4.4.3 Derived Class Methods Hide Base Class Methods
		4.4.4 Compatible Return Types for Overridden Methods
		4.4.5 Private Inheritance
		4.4.6 Friends
		4.4.7 Call by Value and Polymorphism Do Not Mix
4.5		Multiple Inheritance
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
		References
Chapter 5		Design Patterns
5.1		What Is Pattern?
5.2		The Functor (Function Objects)
5.3		Adapters and Wrappers
		5.3.1 Wrapper for Pointers
		5.3.2 A Constant Reference Wrapper
		5.3.3 Adapters: Changing an Interface
5.4		Iterators
		5.4.1 Iterator Design 1
		5.4.2 Iterator Design 2
		5.4.3 Inheritance-Based Iterators and Factories
5.5		Composite (Pair)
5.6		Observer
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
		References

Part 2 : Algorithms and Building Blocks

Chapter 6		Algorithm Analysis
6.1		What is Algorithm Analysis?
6.2		Examples of Algorithm Running Times
6.3		The Maximum Contiguous Subsequence Sum Problem
		6.3.1 The Obvious O(N3)Algorithm
		6.3.2 An Improved O(N2) Algorithm
		6.3.3 A Linear Algorithm
6.4		General Big-Oh Rules
6.5		The Logarithm
6.6		Static Searching Problem
		6.6.1 Sequential Search
		6.6.2 Binary Search
		6.6.3 Interpolation Search
6.7		Checking an Algorithm Analysis
6.8		Limitation of Big-Oh Analysis
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
		References
Chapter 7		The Standard Template Library
7.1		Introduction
7.2		Stacks and Queues
		7.2.1 Stacks
		7.2.2 Stacks and Computer Languages
		7.2.3 Queues
7.3		Containers and Iterators
		7.3.1 Containers
		7.3.2 The iterator
7.4		STL Algorithms
		7.4.1 STL Function Objects
		7.4.2 Binary Search
		7.4.3 Sorting
7.5		Implementation of vector with an Iterator
7.6		Sequences and Linked Lists
		7.6.1 The list Class
		7.6.2 Stacks and Queues
7.7		Sets
7.8		Maps
7.9		Priority Queues
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
		References
Chapter 8		Recursion
8.1		What Is a Recursion?
8.2		Background Proofs by Mathematical Induction
8.3		Basic Recursion
		8.3.1 Printing Numbers in Any Base
		8.3.2 Why it works
		8.3.3 How It Works
		8.3.4 Too Much Recursion Can Be Dangerous
		8.3.5 Preview of Trees
		8.3.6 Additional Examples
8.4		Numerical Applications
		8.4.1 Modular Arithmetic
		8.4.2 Modular Exponentiation
		8.4.3 Greatest Common Divisor and Multiplicative Inverses
		8.4.4 The RSA Cryptosystem
8.5		Divide-and-Conquer Algorithms
		8.5.1 The Maximum Contiguous Subsequence Sum Problem
		8.5.2 Analysis of a Basic Divide-and-Conquer Recurrence
		8.5.3 A General Upper Bound for Divide-and-Conquer Running Times
8.6		Dynamic Programming
8.7		Backtracking
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
		References
Chapter 9		Sorting Algorithms
9.1		Why Is Sorting Important?
9.2		Preliminaries
9.3		Analysis of the Insertion Sort and Other Simple Sorts
9.4		Shellsort
		9.4.1 Performance of Shellsort
9.5		Mergesort
		9.5.1 Linear-Time Merging of Sorted Arrays
		9.5.2 The Mergesort Algorithm
9.6		Quicksort
		9.6.1 The Quicksort Algorithm
		9.6.2 Analysis of Quicksort
		9.6.3 Picking the Pivot
		9.6.4 A Partitioning Strategy
		9.6.5 Keys Equal to the Pivot
		9.6.6 Median-of-Three Partitioning
		9.6.7 Small Arrays
		9.6.8 C++ Quicksort Routine
9.7		Quickselect
9.8		A Lower Bound for Sorting
9.9		Indirect Sorting
		9.9.1 Using Pointers to Reduce Comparable Copies to 2N
		9.9.2 Avoiding the Extra Array
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
		References
Chapter 10		Randomization
10.1		Why Do We Need Random Numbers?
10.2		Random Number Generators
10.3		Nonuniform Random Numbers
10.4		Generating a Random Permutation
10.5		Randomized Algorithms
10.6		Randomized Primality Testing
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
		References

Part 3 : Applications

Chapter 11		Fun and Games
11.1		Word Search Puzzles
		11.1.1 Theory
		11.1.2 C++ Implementation
11.2		The Game of Tic-Tac-Toe
		11.2.1 Alpha-Beta Pruning
		11.2.2 Transposition Tables
		11.2.3 Computer Chess
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
		References
Chapter 12		Stacks and Compilers
12.1		Balanced-Symbol Checker
		12.1.1 Basic Algorithm
		12.1.2 Implementation
12.2		A Simple Calculator
		12.2.1 Postfix Machines
		12.2.2 Infix to Postfix Conversion
		12.2.3 Implementation
		12.2.4 Expression Trees
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
		References
Chapter 13		Utilities
13.1		File Compression
		13.1.1 Prefix Codes
		13.1.2 Huffman's Algorithm
		13.1.3 Implementation
13.2		A Cross-Reference Generator
		13.2.1 Basic Ideas
		13.2.2 C++ Implementation
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
		References
Chapter 14		Simulation
14.1		The Josephus Problem
		14.1.1 The Simple Solution
		14.1.2 A More Efficient Algorithm
14.2		Event-Driven Simulation
		14.2.1 Basic Ideas
		14.2.2 Example: A Modem Bank Simulation
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
Chapter 15		Graphs and Paths
15.1		Definitions
		15.1.1 Representation
15.2		Unweighted Shortest-Path Problem
		15.2.1 Theory
		15.2.2 C++ Implementation
15.3		Positive-Weighted, Shortest-Path Problem
		15.3.1 Theory: Dijkstra's Algorithm
		15.3.2 C++ Implementation
15.4		Negative-Weighted, Shortest-Path Problem
		15.4.1 Theory
		15.4.2 C++ Implementation
15.5		Path Problems in Acyclic Graphs
		15.5.1 Topological Sorting
		15.5.2 Theory of the Acyclic Shortest-Path Algorithm
		15.5.3 C++ Implementation
		15.5.4 An Application: Critical-Path Analysis
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
		References

Part 4 : Implementations

Chapter 16		Stacks and Queues
16.1		Dynamic Array Implementations
		16.1.1 Stacks
		16.1.2 Queues
16.2		Linked List Implementations
		16.2.1 Stacks
		16.2.2 Queues
16.3		Comparison of the Two Methods
16.4		The STL Stack and Queue Adapters
16.5		Double-Ended Queues
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
Chapter 17		Linked Lists
17.1		Basic Ideas
		17.1.1 Header Nodes
		17.1.2 Iterator Classes
17.2		C++ Implementation
17.3		Doubly Linked Lists and Circularly Linked Lists
17.4		Sorted Linked Lists
17.5		Implementing the STL list Class
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
Chapter 18		Trees
18.1		General Trees
		18.1.1 Definitions
		18.1.2 Implementation
		18.1.3 An Application: File Systems
18.2		Binary Trees
18.3		Recursion and Trees
18.4		Tree Traversal Iterator Classes
		18.4.1 Postorder Traversal
		18.4.2 Inorder Traversal
		18.4.3 Preorder Traversal
		18.4.4 Level-Order Traversals
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
Chapter 19		Binary Search Trees
19.1		Basic Ideas
		19.1.1 The Operations
		19.1.2 C++ Implementation
19.2		Order Statistics
		19.2.1 C++ Implementation
19.3		Analysis of Binary Search Tree Operations
19.4		AVL Trees
		19.4.1 Properties
		19.4.2 Single Rotation
		19.4.3 Double Rotation
		19.4.4 Summary of AVL Insertion
19.5		Red-Black Trees
		19.5.1 Bottom-Up Insertion
		19.5.2 Top-Down Red-Black Trees
		19.5.3 C++ Implementation
		19.5.4 Top-Down Deletion
19.6		AA-Trees
		19.6.1 Insertion
		19.6.2 Deletion
		19.6.3 C++ Implementation
19.7		Implementing the STL set and map Classes
19.8		B-Trees
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
		References
Chapter 20		Hash Tables
20.1		Basic Ideas
20.2		Hash Function
20.3		Linear Probing
		20.3.1 Naive Analysis of Linear Probing
		20.3.2 What Really Happens: Primary Clustering
		20.3.3 Analysis of the find Operation
20.4		Quadratic Probing
		20.4.1 C++ Implementation
		20.4.2 Analysis of Quadratic Probing
20.5		Separate Chaining Hashing
20.6		Hash Tables Versus Binary Search Trees
20.7		Hashing Applications
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
		References
Chapter 21		A Priority Queue: The Binary Heap
21.1		Basic Ideas
		21.1.1 Structure Property
		21.1.2 Heap-Order Property
		21.1.3 Allowed Operations
21.2		Implementation of the Basic Operations
		21.2.1 The insert Operation
		21.2.2 The deleteMin Operation
21.3		The buildHeap Operation: Linear-Time Heap Construction
21.4		STL priority_queue Imlementation
21.5		Advanced Operations: decreaseKey and merge
21.6		Internal Sorting: HeapSort
21.7		External Sorting
		21.7.1 Why We Need New Algorithms
		21.7.2 Model for External Sorting
		21.7.3 The Simple Algorithm
		21.7.4 Multiway Merge
		21.7.5 Polyphase Merge
		21.7.6 Replacement Selection
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
		References

Part 5 : Advanced Data Structures

Chapter 22		Splay Trees
22.1		Self-Adjustment and Amortized Analysis
		22.1.1 Amortized Time Bounds
		22.1.2 A Simple Self-Adjusting Strategy (That Does Not Work)
22.2		The Basic Bottom-Up Splay Tree
22.3		Basic Splay Tree Operations
22.4		Analysis of Bottom-Up Splaying
		22.4.1 Proof of the Splaying Bound
22.5		Top-Down Splay Trees
22.6		Implementation of Top-Down Splay Trees
22.7		Comparison of the Splay Tree with Other Search Trees
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
		References
Chapter 23		Merging Priority Queues
23.1		The Skew Heap
		23.1.1 Merging Is Fundamental
		23.1.2 Simplistic Merging of Heap-Ordered Trees
		23.1.3 The Skew Heap: A Simple Modification
		23.1.4 Analysis of the Skew Heap
23.2		The Pairing Heap
		23.2.1 Pairing Heap Operations
		23.2.2 Implementation of the Pairing Heap
		23.2.3 Application: Dijkstra's Shortest Weighted Path Algorithm
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
		References
Chapter 24		The Disjoint Set Class
24.1		Equivalence Relations
24.2		Dynamic Equivalence and Two Applications
		24.2.1 Application: Generating Mazes
		24.2.2 Application: Minimum Spanning Trees
		24.2.3 Application: The Nearest Common Ancestor Problem
24.3		The Quick-Find Algorithm
24.4		The Quick-Union Algorithms
		24.4.1 Smart Union Algorithms
		24.4.2 Path Compression
24.5		C++ Implementation
24.6		Worst Case for Union-by-Rank and Path Compression
		24.6.1 Analysis of the Union/Find Algorithm
		Summary
		Objects of the Game
		Common Errors
		On the Internet
		Exercises
		References

Appendices

Appendix A		Miscellaneous C++ Details
A.1		None of the Compilers Implement the Standard
A.2		Unusual C++ Operators
		A.2.1 Autoincrement and Autodecrement Operators
		A.2.2 Type Conversions
		A.2.3 Bitwise Operators
		A.2.4 The Conditional Operator
A.3		Command-Line Arguments
A.4		Input and Output
		A.4.1 Basic Stream Operations
		A.4.2 Sequential Files
		A.4.3 String Streams
A.5		Namespaces
A.6		New C++ Features
		Common C++ Errors
Appendix B		Operators
Appendix C		Some Library Routines
C.1		Routines Declared in <ctype.h> and <cctype.h>
C.2		Constants Declared in <limits.h> and <climits>
C.3		Routines Declared in <math.h> and <cmath>
C.4		Routines Declared in <stdlib.h> and <catdlib>
Appendix D		Primitive Arrays in C++
D.1		Primitive Arrays
		D.1.1 The C++ Implementation: An Array Name Is a Pointer
		D.1.2 Multidimensional Arrays
		D.1.3 The char * Type, const Pointers, and Constant Strings
D.2		Dynamic Allocation of Arrays: new [ ]and delete [ ]
D.3		Pointer Arithmetic, Pointer Hopping, and Primitive Iteration
		D.3.1 Implications of the Precedence of *,& and [ ]
		D.3.2 What Pointer Arithmetic Means
		D.3.3 A Pointer Hopping Example
		D.3.4 Is Pointer Hopping Worthwhile?
		Common C++ Errors
		On the Internet
		Index