Mastering Algorithms with C

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