Data Structures and Algorithms in C++, Second Edition

Contents and Organization

The chapters for this course are organized to provide a pedagogical path that starts with the basics of C++ programming and object-oriented design. We provide an early discussion of concrete structures, like arrays and linked lists, in order to provide a concrete footing to build upon when constructing other data structures. We then add foundational techniques like recursion and algorithm analysis, and, in the main portion of the book, we present fundamental data structures and algorithms, concluding with a discussion of memory management (that is, the architectural underpinnings of data structures). Specifically, the chapters for this book are organized as follows:

1. A C++ Primer

2. Object-Oriented Design

3. Arrays, Linked Lists, and Recursion

4. Analysis Tools

5. Stacks, Queues, and Deques

6. List and Iterator ADTs

7. Trees

8. Heaps and Priority Queues

9. Hash Tables, Maps, and Skip Lists

10. Search Trees

11. Sorting, Sets, and Selection

12. Strings and Dynamic Programming

13. Graph Algorithms

14. Memory Management and B-Trees

    A. Useful Mathematical Facts

A more detailed listing of the contents of this book can be found in the table of contents.

Prerequisites

We have written this book assuming that the reader comes to it with certain knowledge. We assume that the reader is at least vaguely familiar with a high-level programming language, such as C, C++, Python, or Java, and that he or she understands the main constructs from such a high-level language, including:

• Variables and expressions.

• Functions (also known as methods ...