Preface;
Organization;
Key Features;
About the Code;
Conventions;
How to Contact Us;
Acknowledgments;
Part I: Preliminaries;
Chapter 1: Introduction;
1.1 An Introduction to Data Structures;
1.2 An Introduction to Algorithms;
1.3 A Bit About Software Engineering;
1.4 How to Use This Book;
Chapter 2: Pointer Manipulation;
2.1 Pointer Fundamentals;
2.2 Storage Allocation;
2.3 Aggregates and Pointer Arithmetic;
2.4 Pointers as Parameters to Functions;
2.5 Generic Pointers and Casts;
2.6 Function Pointers;
2.7 Questions and Answers;
2.8 Related Topics;
Chapter 3: Recursion;
3.1 Basic Recursion;
3.2 Tail Recursion;
3.3 Questions and Answers;
3.4 Related Topics;
Chapter 4: Analysis of Algorithms;
4.1 Worst-Case Analysis;
4.2 O-Notation;
4.3 Computational Complexity;
4.4 Analysis Example: Insertion Sort;
4.5 Questions and Answers;
4.6 Related Topics;
Part II: Data Structures;
Chapter 5: Linked Lists;
5.1 Description of Linked Lists;
5.2 Interface for Linked Lists;
5.3 Implementation and Analysis of Linked Lists;
5.4 Linked List Example: Frame Management;
5.5 Description of Doubly-Linked Lists;
5.6 Interface for Doubly-Linked Lists;
5.7 Implementation and Analysis of Doubly Linked Lists;
5.8 Description of Circular Lists;
5.9 Interface for Circular Lists;
5.10 Implementation and Analysis of Circular Lists;
5.11 Circular List Example: Second-Chance Page Replacement;
5.12 Questions and Answers;
5.13 Related Topics;
Chapter 6: Stacks and Queues;
6.1 Description of Stacks;
6.2 Interface for Stacks;
6.3 Implementation and Analysis of Stacks;
6.4 Description of Queues;
6.5 Interface for Queues;
6.6 Implementation and Analysis of Queues;
6.7 Queue Example: Event Handling;
6.8 Questions and Answers;
6.9 Related Topics;
Chapter 7: Sets;
7.1 Description of Sets;
7.2 Interface for Sets;
7.3 Implementation and Analysis of Sets;
7.4 Set Example: Set Covering;
7.5 Questions and Answers;
7.6 Related Topics;
Chapter 8: Hash Tables;
8.1 Description of Chained Hash Tables;
8.2 Interface for Chained Hash Tables;
8.3 Implementation and Analysis of Chained Hash Tables;
8.4 Chained Hash Table Example: Symbol Tables;
8.5 Description of Open-Addressed Hash Tables;
8.6 Interface for Open-Addressed Hash Tables;
8.7 Implementation and Analysisof Open Addressed Hash Tables;
8.8 Questions and Answers;
8.9 Related Topics;
Chapter 9: Trees;
9.1 Description of Binary Trees;
9.2 Interface for Binary Trees;
9.3 Implementation and Analysis of Binary Trees;
9.4 Binary Tree Example: Expression Processing;
9.5 Description of Binary Search Trees;
9.6 Interface for Binary Search Trees;
9.7 Implementation and Analysis of Binary Search Trees;
9.8 Questions and Answers;
9.9 Related Topics;
Chapter 10: Heaps and Priority Queues;
10.1 Description of Heaps;
10.2 Interface for Heaps;
10.3 Implementation and Analysis of Heaps;
10.4 Description of Priority Queues;
10.5 Interface for Priority Queues;
10.6 Implementation and Analysis of Priority Queues;
10.7 Priority Queue Example: Parcel Sorting;
10.8 Questions and Answers;
10.9 Related Topics;
Chapter 11: Graphs;
11.1 Description of Graphs;
11.2 Interface for Graphs;
11.3 Implementation and Analysis of Graphs;
11.4 Graph Example: Counting Network Hops;
11.5 Graph Example: Topological Sorting;
11.6 Questions and Answers;
11.7 Related Topics;
Part III: Algorithms;
Chapter 12: Sorting and Searching;
12.1 Description of Insertion Sort;
12.2 Interface for Insertion Sort;
12.3 Implementation and Analysis of Insertion Sort;
12.4 Description of Quicksort;
12.5 Interface for Quicksort;
12.6 Implementation and Analysis of Quicksort;
12.7 Quicksort Example: Directory Listings;
12.8 Description of Merge Sort;
12.9 Interface for Merge Sort;
12.10 Implementation and Analysis of Merge Sort;
12.11 Description of Counting Sort;
12.12 Interface for Counting Sort;
12.13 Implementation and Analysis of Counting Sort;
12.14 Description of Radix Sort;
12.15 Interface for Radix Sort;
12.16 Implementation and Analysis of Radix Sort;
12.17 Description of Binary Search;
12.18 Interface for Binary Search;
12.19 Implementation and Analysis of Binary Search;
12.20 Binary Search Example: Spell Checking;
12.21 Questions and Answers;
12.22 Related Topics;
Chapter 13: Numerical Methods;
13.1 Description of Polynomial Interpolation;
13.2 Interface for Polynomial Interpolation;
13.3 Implementation and Analysis of Polynomial Interpolation;
13.4 Description of Least-Squares Estimation;
13.5 Interface for Least-Squares Estimation;
13.6 Implementation and Analysis of Least-Squares Estimation;
13.7 Description of the Solution of Equations;
13.8 Interface for the Solution of Equations;
13.9 Implementation and Analysis of the Solution of Equations;
13.10 Questions and Answers;
13.11 Related Topics;
Chapter 14: Data Compression;
14.1 Description of Bit Operations;
14.2 Interface for Bit Operations;
14.3 Implementation and Analysis of Bit Operations;
14.4 Description of Huffman Coding;
14.5 Interface for Huffman Coding;
14.6 Implementation and Analysis of Huffman Coding;
14.7 Huffman Coding Example: Optimized Networking;
14.8 Description of LZ77;
14.9 Interface for LZ77;
14.10 Implementation and Analysis of LZ77;
14.11 Questions and Answers;
14.12 Related Topics;
Chapter 15: Data Encryption;
15.1 Description of DES;
15.2 Interface for DES;
15.3 Implementation and Analysis of DES;
15.4 DES Example: Block Cipher Modes;
15.5 Description of RSA;
15.6 Interface for RSA;
15.7 Implementation and Analysis of RSA;
15.8 Questions and Answers;
15.9 Related Topics;
Chapter 16: Graph Algorithms;
16.1 Description of Minimum Spanning Trees;
16.2 Interface for Minimum Spanning Trees;
16.3 Implementation and Analysis of Minimum Spanning Trees;
16.4 Description of Shortest Paths;
16.5 Interface for Shortest Paths;
16.6 Implementation and Analysis of Shortest Paths;
16.7 Shortest Paths Example: Routing Tables;
16.8 Description of the Traveling-Salesman Problem;
16.9 Interface for the Traveling-Salesman Problem;
16.10 Implementation and Analysis of the Traveling-Salesman Problem;
16.11 Questions and Answers;
16.12 Related Topics;
Chapter 17: Geometric Algorithms;
17.1 Description of Testing Whether Line Segments Intersect;
17.2 Interface for Testing Whether Line Segments Intersect;
17.3 Implementation and Analysis of Testing Whether Line Segments Intersect;
17.4 Description of Convex Hulls;
17.5 Interface for Convex Hulls;
17.6 Implementation and Analysis of Convex Hulls;
17.7 Description of Arc Length on Spherical Surfaces;
17.8 Interface for Arc Length on Spherical Surfaces;
17.9 Implementation and Analysis of Arc Length on Spherical Surfaces;
17.10 Arc Length Example: Approximating Distances on Earth;
17.11 Questions and Answers;
17.12 Related Topics;
Colophon;