| |
| |
| |
| Preliminaries | |
| |
| |
| |
| Data Structures and Algorithms | |
| |
| |
| A Philosophy of Data Structures | |
| |
| |
| Abstract Data Types and Data Structures | |
| |
| |
| Problems, Algorithms, and Programs | |
| |
| |
| |
| Mathematical Preliminaries | |
| |
| |
| Sets and Relations | |
| |
| |
| Miscellaneous Notation | |
| |
| |
| Logarithms | |
| |
| |
| Recursion | |
| |
| |
| Summations and Recurrences | |
| |
| |
| Mathematical Proof Techniques | |
| |
| |
| Estimating | |
| |
| |
| |
| Algorithm Analysis | |
| |
| |
| Introduction | |
| |
| |
| Best, Worst, and Average Cases | |
| |
| |
| A Faster Computer, or a Faster Algorithm? | |
| |
| |
| Asymptotic Analysis | |
| |
| |
| Calculating the Running Time of a Program | |
| |
| |
| Analyzing Problems | |
| |
| |
| Common Misunderstandings | |
| |
| |
| Multiple Parameters | |
| |
| |
| Space Bounds | |
| |
| |
| Some Practical Considerations | |
| |
| |
| |
| Fundamental Data Structures | |
| |
| |
| |
| Lists, Stacks, and Queues | |
| |
| |
| Lists | |
| |
| |
| The Dictionary ADT | |
| |
| |
| Stacks | |
| |
| |
| Queues | |
| |
| |
| |
| Binary Trees | |
| |
| |
| Definitions and Properties | |
| |
| |
| Binary Tree Traversals | |
| |
| |
| Binary Tree Node Implementations | |
| |
| |
| Binary Search Trees | |
| |
| |
| Heaps and Priority Queues | |
| |
| |
| Huffman Coding Trees | |
| |
| |
| |
| Non-Binary Trees | |
| |
| |
| General Tree Definitions and Terminology | |
| |
| |
| The Parent Pointer Implementation | |
| |
| |
| General Tree Implementations.K-ary Trees | |
| |
| |
| Sequential Tree Implementations | |
| |
| |
| |
| Sorting and Searching | |
| |
| |
| |
| Internal Sorting | |
| |
| |
| Sorting Terminology and Notation | |
| |
| |
| Three Q(n^2) Sorting Algorithms | |
| |
| |
| Shellsort | |
| |
| |
| Quicksort | |
| |
| |
| Mergesort | |
| |
| |
| Heapsort | |
| |
| |
| Binsort and Radix Sort | |
| |
| |
| An Empirical Comparison of Sorting Algorithms | |
| |
| |
| Lower Bounds for Sorting | |
| |
| |
| |
| File Processing and External Sorting | |
| |
| |
| Primary versus Secondary Storage | |
| |
| |
| Disk Drives | |
| |
| |
| Buffers and Buffer Pools | |
| |
| |
| The Programmer's View of Files | |
| |
| |
| External Sorting | |
| |
| |
| Simple Approaches to External Sorting | |
| |
| |
| Replacement Selection | |
| |
| |
| Multiway Merging | |
| |
| |
| |
| Searching | |
| |
| |
| Searching Sorted Arrays | |
| |
| |
| Self-Organizing Lists | |
| |
| |
| Searching in Sets | |
| |
| |
| Hashing | |
| |
| |
| |
| Indexing | |
| |
| |
| Linear Indexing | |
| |
| |
| ISAM | |
| |
| |
| Tree Indexing | |
| |
| |
| 2-3 Trees | |
| |
| |
| B-Trees | |
| |
| |
| |
| Applications and Advanced Topics | |
| |
| |
| |
| Graphs | |
| |
| |
| Terminology and Representations | |
| |
| |
| Graph Implementations | |
| |
| |
| Graph Traversals | |
| |
| |
| Shortest-Paths Problems | |
| |
| |
| Minimum-Cost Spanning Trees | |
| |
| |
| |
| Lists and Arrays Revisited | |
| |
| |
| Skip Lists | |
| |
| |
| Multilists | |
| |
| |
| Matrix Representations | |
| |
| |
| Memory Management | |
| |
| |
| |
| Advanced Tree Structures | |
| |
| |
| Tries | |
| |
| |
| Balanced Trees | |
| |
| |
| Spatial Data Structures | |
| |
| |
| |
| Analysis Techniques | |
| |
| |
| Summation Techniques | |
| |
| |
| Recurrence Relations | |
| |
| |
| Amortized Analysis | |
| |
| |
| |
| Limits to Computation | |
| |
| |
| Reductions | |
| |
| |
| Hard Problems | |
| |
| |
| Impossible Problems | |
| |
| |
| |
| Appendix | |
| |
| |
| Utility Functions | |
| |
| |
| Bibliography | |
| |
| |
| Index | |