Most books on data structures are filled with so many technical details (and lack thorough explanations) that the reading becomes difficult. This accessible, conversational presentation explores data structures concepts in clear language. Assumes a basic knowledge of C++. Focuses on the client for all programs, classes, and data structures. Offers meaningful, relevant examples and worked examples throughout. Includes thoroughly tested code. Provides code for all examples. A useful reference for anyone interested in learning more about programming.

Chapter 1 Structs and Classes 1

1.1 Structs

1.2 Basic Class Concepts

1.3 Class Implementation

1.4 Testing a Class

1.5 Placing Function Definitions in the Class Definition (and Why We Shouldn’t Do It)

1.6 Commenting a Class

1.7 The Differences Between a Struct and a Class

Summary

Exercises

Chapter 2 Overloaded Operators, Class Templates, and Abstraction

2.1 Overloaded Operators

2.2 Using a Check Struct in the Checkbook Class

2.3 Class Templates

2.4 Classes and Abstraction

Summary

Exercises

Chapter 3 More about Classes

3.1 The const Specifier

3.2 Constructors

3.3 Class Modification

3.4 Modifying the Checkbook Class to Keep a History of Checks

Summary

Exercises

Chapter 4 Pointers and Dynamic Arrays

4.1 Pointers

4.2 The [ ] Operator

v

vi Contents

4.3 Dynamically Allocated Memory

4.4 Dynamic Arrays

4.5 The Delete Operator

4.6 Pointers to Objects

4.7 Running out of Heap Memory

4.8 Adjustable Arrays

Summary

Exercises

Chapter 5 An Array Class

5.1 Array Class Template

5.2 Using the Array Class

5.3 Destructors

5.4 The Copy Constructor 107

5.5 The Overloaded Assignment Operator Function

5.6 An Example 117

5.7 Advantages and Disadvantages of an Array Class

5.8 The Standard Template Library

Summary

Exercises

Chapter 6 Introduction to Object-Oriented Programming

6.1 Composition

*6.2 Inheritance

*6.3 Polymorphism

Summary

Exercises

Chapter 7 Methods for Making Data Structures

7.1 Using Arrays in Data Structures

7.2 Introduction to Linked Structures

7.3 Writing Code for Linked Lists

7.4 Arrays vs. Linked Lists

Summary

Exercises

Chapter 8 Stacks and Queues

8.1 The Stack ADT

8.2 Array Implementation of a Stack

8.3 Linked-List Implementation of a Stack

8.4 The Queue ADT

8.5 The Linked-List Implementation of a Queue

8.6 Other Linked-List Implementations of Queues

*8.7 Array Implementation of a Queue

Summary

Exercises

Contents vii

Chapter 9 Introduction to Time Complexities

9.1 Time Complexity Basics

9.2 The Constant Time Complexity

9.3 Big-Oh Notation

9.4 The Logarithmic Time Complexity

9.5 The Binary Search Algorithm

9.6 Computer Speed: Where Does It Really Come From?

9.7 Time Complexities of Data Structure Functions

*9.8 Amortized Analysis of Array Expansion and Contraction

Summary

Exercises

Chapter 10 The Linked List as a Data Structure

10.1 The List ADT

10.2 Using Key Values in Records of Information

10.3 Linked-List Implementation

10.4 Other Implementations

Summary

Exercises

Chapter 11 Hash Tables

11.1 The Hash Table ADT

11.2 Hash Functions and Hash Table Design

11.3 Implementation Issues for a Hash Table

11.4 Pointers to Functions

11.5 A Hash Table Implementation

11.6 Using the Hash Table Implementation

11.7 A Hash Table Implementation of a Doubly Linked List

Summary

Exercises

Chapter 12 Priority Queues, Trees, and Heaps

12.1 Priority Queue ADT

12.2 Priority Queue Design

12.3 Trees

12.4 Heaps

12.5 Using a One-Assignment Swap

12.6 A Heap Implementation of a Priority Queue (Array-Based)

*12.7 The Design of a Linked (Embedded) Heap

*12.8 A Linked (Embedded) Heap Implementation of a Priority Queue

Summary

Exercises

Chapter 13 Recursion

13.1 A Recursive Factorial Function

13.2 Guidelines for Writing Recursive Functions

ChilFMff.qxd 6/29/07 4:32 PM Page vii

viii Contents

13.3 Using Recursion on Linked Structures

13.4 Time Complexities of Recursive Functions

Summary

Exercises

Chapter 14 Introduction to Sorting Algorithms

14.1 Heapsort

14.2 Insertion Sort

14.3 Quicksort

14.4 Counting Sort

14.5 Sorting a Linked List

Summary

Exercises

Chapter 15 Other Data Structures

15.1 Binary Search Trees

15.2 Comparison of the BST with Other Data Structures

15.3 Graphs

15.4 Comparing Adjacency Matrices with Adjacency Lists

Summary

Exercises

Appendix A How to Compile and Work with Multiple-File Programs

Microsoft Visual Studio 2005 C++ Compiler

Compiling and Running Code Using Classes (Not Class Templates)

Compiling and Running Code Using Class Templates

Writing Code Using Microsoft Visual Studio 2005

Opening a Project in Microsoft Visual Studio 2005 That You Have Already Created

When Things Really Get Screwed Up

UNIX compilers

Index