| |
| |
| |
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 | |