Support us


to write
more tutorials




to create new
visualizers




to keep sharing
free knowledge
for you


every dollar helps
Need help with a programming assignment? Get affordable programming homework help.

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

by Mark Allen Weiss (Author)

Data Structures and Problem Solving Using C++ (2nd Edition) Cover
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