Data Structures and Problem Solving Using C++

Throughout this edition, Mark Allen Weiss has included the latest features of the C++ programming language-making prevalent use of the Standard Template Library (STL) wherever appropriate. He has also included a new chapter covering Patterns, as well as new material on templates, vectors and push_back.

C++ allows the programmer to write the interface and implementation separately, to place them in separate files and compile separately, and to hide the implementation details. This book goes a step further: The interface and implementation are discussed in separate parts of the book. Part I (Objects and C++), Part II (Algorithms and Building Blocks), and Part III (Applications) lay the groundwork by discussing basic concepts and tools and providing some practical examples, but implementation of data structures are not shown until Part IV (Implementations). This separation of interface and implementation promotes abstract thinking. Class interfaces are written and used before the implementation is known, forcing the reader to think about the functionality and potential efficiency of the various data structures (e.g. hash tables are written well before the hash table is implemented).

Table of contents

Part I: Objects and C++

Chapter 1: Arrays, Pointers and Structures

Chapter 2: Objects and Classes

Chapter 3: Templates

Chapter 4: Inheritance

Chapter 5: Design Patterns

Part II: Algorithms and Building Blocks

Chapter 6: Algorithm Analysis

Chapter 7: The Standard Template Library

Chapter 8: Recursion

Chapter 9: Sorting Algorithms

Chapter 10: Randomization

Part III: Applications

Chapter 11: Fun and Games

Chapter 12: Stacks and Compliers

Chapter 13: Utilities

Chapter 14: Simulation

Chapter 15: Graphs and Paths

Part IV: Implementations

Chapter 16: Stacks and Queues

Chapter 17: Linked Lists

Chapter 18: Trees

Chapter 19: Binary Search Trees

Chapter 20: Hash Tables

Chapter 21: A Priority Queue: The Binary Heap

Part V: Advanced Data Structures

Chapter 22: Splay Trees

Chapter 23: Merging Priority Queues

Chapter 24: The Disjoint Set Class

Appendices

Appendix A: Miscellaneous C++ Details

Appendix B: Operators

Appendix C: Some Library

Appendix D: Primitive Arrays in C++

Index