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:
A C++ Primer
Arrays, Linked Lists, and Recursion
Stacks, Queues, and Deques
List and Iterator ADTs
Heaps and Priority Queues
Hash Tables, Maps, and Skip Lists
Sorting, Sets, and Selection
Strings and Dynamic Programming
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.
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 ...