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 Inserti