| |
| |
Preface | |
| |
| |
| |
Preliminaries | |
| |
| |
| |
Introduction | |
| |
| |
An Introduction to Data Structures | |
| |
| |
An Introduction to Algorithms | |
| |
| |
A Bit About Software Engineering | |
| |
| |
How to Use This Book | |
| |
| |
| |
Pointer Manipulation | |
| |
| |
Pointer Fundamentals | |
| |
| |
Storage Allocation | |
| |
| |
Aggregates and Pointer Arithmetic | |
| |
| |
Pointers as Parameters to Functions | |
| |
| |
Generic Pointers and Casts | |
| |
| |
Function Pointers | |
| |
| |
Questions and Answers | |
| |
| |
Related Topics | |
| |
| |
| |
Recursion | |
| |
| |
Basic Recursion | |
| |
| |
Tail Recursion | |
| |
| |
Questions and Answers | |
| |
| |
Related Topics | |
| |
| |
| |
Analysis of Algorithms | |
| |
| |
Worst-Case Analysis | |
| |
| |
O-Notation | |
| |
| |
Computational Complexity | |
| |
| |
Analysis Example: Insertion Sort | |
| |
| |
Questions and Answers | |
| |
| |
Related Topics | |
| |
| |
| |
Data Structures | |
| |
| |
| |
Linked Lists | |
| |
| |
Description of Linked Lists | |
| |
| |
Interface for Linked Lists | |
| |
| |
Implementation and Analysis of Linked Lists | |
| |
| |
Linked List Example: Frame Management | |
| |
| |
Description of Doubly-Linked Lists | |
| |
| |
Interface for Doubly-Linked Lists | |
| |
| |
Implementation and Analysis of Doubly Linked Lists | |
| |
| |
Description of Circular Lists | |
| |
| |
Interface for Circular Lists | |
| |
| |
Implementation and Analysis of Circular Lists | |
| |
| |
Circular List Example: Second-Chance Page Replacement | |
| |
| |
Questions and Answers | |
| |
| |
Related Topics | |
| |
| |
| |
Stacks and Queues | |
| |
| |
Description of Stacks | |
| |
| |
Interface for Stacks | |
| |
| |
Implementation and Analysis of Stacks | |
| |
| |
Description of Queues | |
| |
| |
Interface for Queues | |
| |
| |
Implementation and Analysis of Queues | |
| |
| |
Queue Example: Event Handling | |
| |
| |
Questions and Answers | |
| |
| |
Related Topics | |
| |
| |
| |
Sets | |
| |
| |
Description of Sets | |
| |
| |
Interface for Sets | |
| |
| |
Implementation and Analysis of Sets | |
| |
| |
Set Example: Set Covering | |
| |
| |
Questions and Answers | |
| |
| |
Related Topics | |
| |
| |
| |
Hash Tables | |
| |
| |
Description of Chained Hash Tables | |
| |
| |
Interface for Chained Hash Tables | |
| |
| |
Implementation and Analysis of Chained Hash Tables | |
| |
| |
Chained Hash Table Example: Symbol Tables | |
| |
| |
Description of Open-Addressed Hash Tables | |
| |
| |
Interface for Open-Addressed Hash Tables | |
| |
| |
Implementation and Analysis of Open Addressed Hash Tables | |
| |
| |
Questions and Answers | |
| |
| |
Related Topics | |
| |
| |
| |
Trees | |
| |
| |
Description of Binary Trees | |
| |
| |
Interface for Binary Trees | |
| |
| |
Implementation and Analysis of Binary Trees | |
| |
| |
Binary Tree Example: Expression Processing | |
| |
| |
Description of Binary Search Trees | |
| |
| |
Interface for Binary Search Trees | |
| |
| |
Implementation and Analysis of Binary Search Trees | |
| |
| |
Questions and Answers | |
| |
| |
Related Topics | |
| |
| |
| |
Heaps and Priority Queues | |
| |
| |
Description of Heaps | |
| |
| |
Interface for Heaps | |
| |
| |
Implementation and Analysis of Heaps | |
| |
| |
Description of Priority Queues | |
| |
| |
Interface for Priority Queues | |
| |
| |
Implementation and Analysis of Priority Queues | |
| |
| |
Priority Queue Example: Parcel Sorting | |
| |
| |
Questions and Answers | |
| |
| |
Related Topics | |
| |
| |
| |
Graphs | |
| |
| |
Description of Graphs | |
| |
| |
Interface for Graphs | |
| |
| |
Implementation and Analysis of Graphs | |
| |
| |
Graph Example: Counting Network Hops | |
| |
| |
Graph Example: Topological Sorting | |
| |
| |
Questions and Answers | |
| |
| |
Related Topics | |
| |
| |
| |
Algorithms | |
| |
| |
| |
Sorting and Searching | |
| |
| |
Description of Insertion Sort | |
| |
| |
Interface for Insertion Sort | |
| |
| |
Implementation and Analysis of Insertion Sort | |
| |
| |
Description of Quicksort | |
| |
| |
Interface for Quicksort | |
| |
| |
Implementation and Analysis of Quicksort | |
| |
| |
Quicksort Example: Directory Listings | |
| |
| |
Description of Merge Sort | |
| |
| |
Interface for Merge Sort | |
| |
| |
Implementation and Analysis of Merge Sort | |
| |
| |
Description of Counting Sort | |
| |
| |
Interface for Counting Sort | |
| |
| |
Implementation and Analysis of Counting Sort | |
| |
| |
Description of Radix Sort | |
| |
| |
Interface for Radix Sort | |
| |
| |
Implementation and Analysis of Radix Sort | |
| |
| |
Description of Binary Search | |
| |
| |
Interface for Binary Search | |
| |
| |
Implementation and Analysis of Binary Search | |
| |
| |
Binary Search Example: Spell Checking | |
| |
| |
Questions and Answers | |
| |
| |
Related Topics | |
| |
| |
| |
Numerical Methods | |
| |
| |
Description of Polynomial Interpolation | |
| |
| |
Interface for Polynomial Interpolation | |
| |
| |
Implementation and Analysis of Polynomial Interpolation | |
| |
| |
Description of Least-Squares Estimation | |
| |
| |
Interface for Least-Squares Estimation | |
| |
| |
Implementation and Analysis of Least-Squares Estimation | |
| |
| |
Description of the Solution of Equations | |
| |
| |
Interface for the Solution of Equations | |
| |
| |
Implementation and Analysis of the Solution of Equations | |
| |
| |
Questions and Answers | |
| |
| |
Related Topics | |
| |
| |
| |
Data Compression | |
| |
| |
Description of Bit Operations | |
| |
| |
Interface for Bit Operations | |
| |
| |
Implementation and Analysis of Bit Operations | |
| |
| |
Description of Huffman Coding | |
| |
| |
Interface for Huffman Coding | |
| |
| |
Implementation and Analysis of Huffman Coding | |
| |
| |
Huffman Coding Example: Optimized Networking | |
| |
| |
Description of LZ77 | |
| |
| |
Interface for LZ77 | |
| |
| |
Implementation and Analysis of LZ77 | |
| |
| |
Questions and Answers | |
| |
| |
Related Topics | |
| |
| |
| |
Data Encryption | |
| |
| |
Description of DES | |
| |
| |
Interface for DES | |
| |
| |
Implementation and Analysis of DES | |
| |
| |
DES Example: Block Cipher Modes | |
| |
| |
Description of RSA | |
| |
| |
Interface for RSA | |
| |
| |
Implementation and Analysis of RSA | |
| |
| |
Questions and Answers | |
| |
| |
Related Topics | |
| |
| |
| |
Graph Algorithms | |
| |
| |
Description of Minimum Spanning Trees | |
| |
| |
Interface for Minimum Spanning Trees | |
| |
| |
Implementation and Analysis of Minimum Spanning Trees | |
| |
| |
Description of Shortest Paths | |
| |
| |
Interface for Shortest Paths | |
| |
| |
Implementation and Analysis of Shortest Paths | |
| |
| |
Shortest Paths Example: Routing Tables | |
| |
| |
Description of the Traveling-Salesman Problem | |
| |
| |
Interface for the Traveling-Salesman Problem | |
| |
| |
Implementation and Analysis of the Traveling-Salesman Problem | |
| |
| |
Questions and Answers | |
| |
| |
Related Topics | |
| |
| |
| |
Geometric Algorithms | |
| |
| |
Description of Testing Whether Line Segments Intersect | |
| |
| |
Interface for Testing Whether Line Segments Intersect | |
| |
| |
Implementation and Analysis of Testing Whether Line Segments Intersect | |
| |
| |
Description of Convex Hulls | |
| |
| |
Interface for Convex Hulls | |
| |
| |
Implementation and Analysis of Convex Hulls | |
| |
| |
Description of Arc Length on Spherical Surfaces | |
| |
| |
Interface for Arc Length on Spherical Surfaces | |
| |
| |
Implementation and Analysis of Arc Length on Spherical Surfaces | |
| |
| |
Arc Length Example: Approximating Distances on Earth | |
| |
| |
Questions and Answers | |
| |
| |
Related Topics | |
| |
| |
Index | |