This book offers robust solutions for everyday programming tasks, providing all the necessary information to
understand and use common programming techniques. It includes implementations and real-world examples of
each data structure in the text and full source code on the accompanying website
(http://examples.oreilly.com/masteralgoc/). Intended for anyone with a basic understanding of the C language.
Preface
When I first thought about writing this book, I immediately thought of O'Reilly & Associates to publish it. They were the first publisher
I contacted, and the one I most wanted to work with because of their tradition of books covering "just the facts." This approach is not
what one normally thinks of in connection with books on data structures and algorithms. When one studies data structures and
algorithms, normally there is a fair amount of time spent on proving their correctness rigorously. Consequently, many books on this
subject have an academic feel about them, and real details such as implementation and application are left to be resolved
elsewhere. This book covers how and why certain data structures and algorithms work, real applications that use them (including
many examples), and their implementation. Mathematical rigor appears only to the extent necessary in explanations.
Naturally, I was very happy that O'Reilly & Associates saw value in a book that covered this aspect of the subject. This preface
contains some of the reasons I think you will find this book valuable as well. It also covers certain aspects of the code in the book,
defines a few conventions, and gratefully acknowledges the people who played a part in the book's creation.
Bookmarks
Main Page
Table of content
Copyright
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
index