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