Data Structures and Algorithms in C++: Pocket Primer

Title Page....4

Copyright....5

Contents....6

Preface....9

Acknowledgments....12

Chapter 1: C++ Review....13

1.1 The auto Keyword....13

1.2 Classes....13

1.2.1 Example: A Fraction Class....15

1.3 Pointers and Arrays....24

1.4 Inheritance....26

1.5 Templates....30

1.6 The Standard Template Library (STL)....31

1.6.1 Containers....31

1.6.2 Iterators....32

1.6.3 Algorithms....33

1.7 Putting It All Together: A Vector Class....33

1.7.1 Constructors/Destructors....34

1.7.2 Member Functions....36

1.7.3 Iterators....38

Chapter 2: Algorithm Analysis....40

2.1 Big-O Notation....41

2.1.1 Terminology....41

2.2 Efficiency of Vector Operations....43

2.3 Estimates and Comparisons....44

2.4 Fast Enough....44

Chapter 3: Linked Lists....46

3.1 The list Interface....47

3.2 List Implementation....47

3.2.1 Constructors/Destructors....49

3.2.2 Member Functions....50

3.2.3 Iterators....54

Chapter 4: Stacks and Queues....57

4.1 The stack and queue Interfaces....57

4.2 Example: Infix and Postfix....58

4.3 Stack and Queue Implementation....59

4.3.1 Constructors/Destructors....59

4.3.2 Member Functions....59

Chapter 5: Recursion....61

5.1 Recursive Definitions....63

5.2 Proof by Induction....64

5.3 Example: Binary Search....65

5.4 Example: Tower of Hanoi....66

5.5 Example: Recursive Descent Parsing....67

5.6 The Efficiency of Recursion....68

Chapter 6: Binary Trees....69

6.1 Traversals....69

6.2 Example: Expression Trees....70

6.3 Example: Binary Search Trees....71

6.4 The set and map Interfaces....75

6.5 Example: Associative Arrays....76

6.6 Example: Sparse Matrices....76

6.7 A Binary_Search_Tree Class....77

6.7.1 Constructors/Destructors....78

6.7.2 Member Functions....80

6.7.3 Iterators....84

6.8 Set and Map Implementation....85

6.8.1 Constructors/Destructors....87

6.8.2 Member Functions....87

6.8.3 Iterators....89

Chapter 7: Binary Trees (continued)....92

7.1 Height-Balanced Trees....92

7.2 General Trees....92

7.3 Heaps....93

7.4 The priority_queue Interface....96

7.5 Priority_Queue Implementation....96

7.5.1 Constructors/Destructors....97

7.5.2 Member Functions....97

Chapter 8: Sorting....100

8.1 Bubble Sort (Revised)....100

8.2 Selection Sort....101

8.3 Insertion Sort....101

8.4 Shell Sort....102

8.5 Heap Sort....102

8.6 Merge Sort....103

8.7 Quick Sort....104

8.8 The STL sort Function....106

Chapter 9: Hash Tables....107

9.1 Hash Functions....107

9.2 Collisions....108

9.2.1 Probing....108

9.2.2 Chaining....109

9.3 Load Factors and Efficiency....109

9.4 Rehashing....110

9.5 The unordered_set and unordered_map Interfaces....110

9.6 A Hash_Table Class....111

9.6.1 Constructors/Destructors....112

9.6.2 Member Functions....112

9.6.3 Iterators....116

9.7 Unordered_Set and Unordered_Map Implementation....118

9.7.1 Constructors/Destructors....119

9.7.2 Member Functions....120

9.7.3 Iterators....121

Chapter 10: Graphs....123

10.1 Graph Representations....124

10.1.1 Adjacency Matrix....124

10.1.2 Adjacency Lists....124

10.2 Traversals....125

10.2.1 Depth-First Search....125

10.2.2 Breadth-First Search....125

10.3 Example: Topological Sorting....126

10.4 Example: Shortest Path....126

10.5 A Graph Interface....129

10.6 Graph Implementation....129

10.6.1 Constructors/Destructors....130

10.6.2 Member Functions....130

Appendix A: A Programmer’s Library....134

Appendix B: STL Class Summary....136

Appendix C: Chunk Index....145

Index....148

This book takes a minimalist approach to the traditional data structures course. It covers only those topics that are absolutely essential; the more esoteric structures and algorithms are left for later study. Suitable for an introductory data structures course or self-study, this book is written from the ground up in C++ (not translated from a Java-based text), and uses features of the C++ Standard Template Library to illustrate important concepts. A unique feature of the text is its use of literate programming techniques (originally developed by Donald Knuth) to present the sample code in a way that keeps the code from overwhelming the accompanying explanations. Source code samples from the book are available on the companion files. This book is suitable for an undergraduate data structures course using C++ or for developers needing review.