1. Preliminaries

   1. Chapter 1 Introduction

      1. An Introduction to Data Structures
      2. An Introduction to Algorithms
      3. A Bit About Software Engineering
      4. How to Use This Book

   2. Chapter 2 Pointer Manipulation

      1. Pointer Fundamentals
      2. Storage Allocation
      3. Aggregates and Pointer Arithmetic
      4. Pointers as Parameters to Functions
      5. Generic Pointers and Casts
      6. Function Pointers
      7. Questions and Answers
      8. Related Topics

   3. Chapter 3 Recursion

      1. Basic Recursion
      2. Tail Recursion
      3. Questions and Answers
      4. Related Topics

   4. Chapter 4 Analysis of Algorithms

      1. Worst-Case Analysis
      2. O-Notation
      3. Computational Complexity
      4. Analysis Example: Insertion Sort
      5. Questions and Answers
      6. Related Topics

2. Data Structures

   1. Chapter 5 Linked Lists

      1. Description of Linked Lists
      2. Interface for Linked Lists
      3. Implementation and Analysis of Linked Lists
      4. Linked List Example: Frame Management
      5. Description of Doubly-Linked Lists
      6. Interface for Doubly-Linked Lists
      7. Implementation and Analysis of Doubly Linked Lists
      8. Description of Circular Lists
      9. Interface for Circular Lists
      10. Implementation and Analysis of Circular Lists
      11. Circular List Example: Second-Chance Page Replacement
      12. Questions and Answers
      13. Related Topics

   2. Chapter 6 Stacks and Queues

      1. Description of Stacks
      2. Interface for Stacks
      3. Implementation and Analysis of Stacks
      4. Description of Queues
      5. Interface for Queues
      6. Implementation and Analysis of Queues
      7. Queue Example: Event Handling
      8. Questions and Answers
      9. Related Topics

   3. Chapter 7 Sets

      1. Description of Sets
      2. Interface for Sets
      3. Implementation and Analysis of Sets
      4. Set Example: Set Covering
      5. Questions and Answers
      6. Related Topics

   4. Chapter 8 Hash Tables

      1. Description of Chained Hash Tables
      2. Interface for Chained Hash Tables
      3. Implementation and Analysis of Chained Hash Tables
      4. Chained Hash Table Example: Symbol Tables
      5. Description of Open-Addressed Hash Tables
      6. Interface for Open-Addressed Hash Tables
      7. Implementation and Analysisof Open Addressed Hash Tables
      8. Questions and Answers
      9. Related Topics

   5. Chapter 9 Trees

      1. Description of Binary Trees
      2. Interface for Binary Trees
      3. Implementation and Analysis of Binary Trees
      4. Binary Tree Example: Expression Processing
      5. Description of Binary Search Trees
      6. Interface for Binary Search Trees
      7. Implementation and Analysis of Binary Search Trees
      8. Questions and Answers
      9. Related Topics

   6. Chapter 10 Heaps and Priority Queues

      1. Description of Heaps
      2. Interface for Heaps
      3. Implementation and Analysis of Heaps
      4. Description of Priority Queues
      5. Interface for Priority Queues
      6. Implementation and Analysis of Priority Queues
      7. Priority Queue Example: Parcel Sorting
      8. Questions and Answers
      9. Related Topics

   7. Chapter 11 Graphs

      1. Description of Graphs
      2. Interface for Graphs
      3. Implementation and Analysis of Graphs
      4. Graph Example: Counting Network Hops
      5. Graph Example: Topological Sorting
      6. Questions and Answers
      7. Related Topics

3. Algorithms

   1. Chapter 12 Sorting and Searching

      1. Description of Insertion Sort
      2. Interface for Insertion Sort
      3. Implementation and Analysis of Insertion Sort
      4. Description of Quicksort
      5. Interface for Quicksort
      6. Implementation and Analysis of Quicksort
      7. Quicksort Example: Directory Listings
      8. Description of Merge Sort
      9. Interface for Merge Sort
      10. Implementation and Analysis of Merge Sort
      11. Description of Counting Sort
      12. Interface for Counting Sort
      13. Implementation and Analysis of Counting Sort
      14. Description of Radix Sort
      15. Interface for Radix Sort
      16. Implementation and Analysis of Radix Sort
      17. Description of Binary Search
      18. Interface for Binary Search
      19. Implementation and Analysis of Binary Search
      20. Binary Search Example: Spell Checking
      21. Questions and Answers
      22. Related Topics

   2. Chapter 13 Numerical Methods

      1. Description of Polynomial Interpolation
      2. Interface for Polynomial Interpolation
      3. Implementation and Analysis of Polynomial Interpolation
      4. Description of Least-Squares Estimation
      5. Interface for Least-Squares Estimation
      6. Implementation and Analysis of Least-Squares Estimation
      7. Description of the Solution of Equations
      8. Interface for the Solution of Equations
      9. Implementation and Analysis of the Solution of Equations
      10. Questions and Answers
      11. Related Topics

   3. Chapter 14 Data Compression

      1. Description of Bit Operations
      2. Interface for Bit Operations
      3. Implementation and Analysis of Bit Operations
      4. Description of Huffman Coding
      5. Interface for Huffman Coding
      6. Implementation and Analysis of Huffman Coding
      7. Huffman Coding Example: Optimized Networking
      8. Description of LZ77
      9. Interface for LZ77
      10. Implementation and Analysis of LZ77
      11. Questions and Answers
      12. Related Topics

   4. Chapter 15 Data Encryption

      1. Description of DES
      2. Interface for DES
      3. Implementation and Analysis of DES
      4. DES Example: Block Cipher Modes
      5. Description of RSA
      6. Interface for RSA
      7. Implementation and Analysis of RSA
      8. Questions and Answers
      9. Related Topics

   5. Chapter 16 Graph Algorithms

      1. Description of Minimum Spanning Trees
      2. Interface for Minimum Spanning Trees
      3. Implementation and Analysis of Minimum Spanning Trees
      4. Description of Shortest Paths
      5. Interface for Shortest Paths
      6. Implementation and Analysis of Shortest Paths
      7. Shortest Paths Example: Routing Tables
      8. Description of the Traveling-Salesman Problem
      9. Interface for the Traveling-Salesman Problem
      10. Implementation and Analysis of the Traveling-Salesman Problem
      11. Questions and Answers
      12. Related Topics

   6. Chapter 17 Geometric Algorithms

      1. Description of Testing Whether Line Segments Intersect
      2. Interface for Testing Whether Line Segments Intersect
      3. Implementation and Analysis of Testing Whether Line Segments Intersect
      4. Description of Convex Hulls
      5. Interface for Convex Hulls
      6. Implementation and Analysis of Convex Hulls
      7. Description of Arc Length on Spherical Surfaces
      8. Interface for Arc Length on Spherical Surfaces
      9. Implementation and Analysis of Arc Length on Spherical Surfaces
      10. Arc Length Example: Approximating Distances on Earth
      11. Questions and Answers
      12. Related Topics

1. Colophon

Our look is the result of reader comments, our own experimentation, and feedback from distribution channels. Distinctive covers complement our distinctive approach to technical topics, breathing personality and life into potentially dry subjects. The animals on the cover of Mastering Algorithms with C are sea horses. Sea horses are of the family Syngnathidae, genus Hippocampus. The word "hippocampus" comes from the Greek for "bent horse." The sea horse's unusual-looking body is formed by 50 or so bony plates that encircle the body to create rings of armor. Within their narrow snouts are tubes through which they feed, sucking in plankton and tiny fish larvae. The male sea horse has a pouch in his belly, into which a female lays 100 or more eggs at a time. The male fertilizes the eggs in the pouch and carries them until they hatch, ten days to six weeks later, depending on the sea horse species. Sea horses are found mostly in shallow tropical and subtropical waters, although there are some ocean-dwelling sea horse species. All sea horses use their pelvic and pectoral fins for steering. They swim slowly, in an upright position, and take frequent breaks. During these breaks they wrap their prehensile tails around a piece of seaweed or coral to anchor themselves. In addition to providing a resting place, the seaweed and coral provide good camouflage for the sea horse. The largest sea horse species is the Pacific sea horse, measuring approximately 12 inches long. The smallest is the dwarf sea horse, which measures only an inch and a half long. Jeffrey Liggett was the production editor for Mastering Algorithms with C; Cindy Kogut was the copyeditor; Ellie Fountain Maden was the proofreader; Sebastian Banker provided production assistance; Claire Cloutier LeBlanc, Nancy Wolfe Kotary, and Melanie Wang provided quality control. Robert Romano and Rhon Porter created the illustrations using Adobe Photoshop 5 and Macromedia FreeHand 8. Mike Sierra provided FrameMaker technical support. William Meyers wrote the index with production assistance by Seth Maislin and Brenda Miller. Hanna Dyer designed the cover of this book based on a series design by Edie Freedman. The illustration is by Lorrie LeJeune. The cover layout was produced by Kathleen Wilson with QuarkXPress 3.32 using the ITC Garamond font. Kathleen Wilson designed the diskette label. Whenever possible, our books use RepKover, a durable and flexible lay-flat binding. If the page count exceeds RepKover's limit, perfect binding is used. The inside layout was designed by Alicia Cech based on a series design by Nancy Priest. The inside layout was implemented in FrameMaker 5.5.6 by Mike Sierra. The text and heading fonts are ITC Garamond Light and Garamond Book. This colophon was written by Clairemarie Fisher O'Leary.