Mastering Algorithms with C Mastering Algorithms with C Kyle Loudon Beijing• Cambridge• Farnham• Köln• Paris• Sebastopol• Taipei• Tokyo Mastering Algorithms with C by Kyle Loudon Copyright © 1999 O’Reilly Media, Inc. All rights reserved. Printed in the United States of America. Published by O’Reilly Media, Inc., 1005 Gravenstein Highway North, Sebastopol, CA 95472. Editor: Andy Oram Production Editor: Jeffrey Liggett Printing History: August 1999: First Edition. Nutshell Handbook, the Nutshell Handbook logo, and the O’Reilly logo are registered trademarksofO’ReillyMedia,Inc.MasteringAlgorithmswithC,theimageofseahorses,and related trade dress are trademarks of O’Reilly Media, Inc. Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and O’Reilly Media, Inc. was aware of a trademark claim, the designations have been printed in caps or initial caps. Whileeveryprecautionhasbeentakeninthepreparationofthisbook,thepublisherassumes no responsibility for errors or omissions, or for damages resulting from the use of the information contained herein. This book uses RepKover™, a durable and flexible lay-flat binding. ISBN-13: 978-1-565-92453-6 [M] [5/08] Table of Contents Preface ..................................................................................................................... xi I. Preliminaries .......................................................................................... 1 1. Introduction ................................................................................................ 3 An Introduction to Data Structures ................................................................. 4 An Introduction to Algorithms ........................................................................ 5 A Bit About Software Engineering .................................................................. 8 How to Use This Book .................................................................................. 10 2. Pointer Manipulation ........................................................................... 11 Pointer Fundamentals .................................................................................... 12 Storage Allocation .......................................................................................... 12 Aggregates and Pointer Arithmetic ................................................................ 15 Pointers as Parameters to Functions ............................................................. 17 Generic Pointers and Casts ............................................................................ 21 Function Pointers ........................................................................................... 23 Questions and Answers ................................................................................. 24 Related Topics ................................................................................................ 25 3. Recursion ................................................................................................... 27 Basic Recursion .............................................................................................. 28 Tail Recursion ................................................................................................. 32 Questions and Answers ................................................................................. 34 Related Topics ................................................................................................ 37 v vi Table of Contents 4. Analysis of Algorithms .......................................................................... 38 Worst-Case Analysis ....................................................................................... 39 O-Notation ...................................................................................................... 40 Computational Complexity ............................................................................ 42 Analysis Example: Insertion Sort ................................................................... 45 Questions and Answers ................................................................................. 47 Related Topics ................................................................................................ 48 II. Data Structures .................................................................................. 49 5. Linked Lists ............................................................................................... 51 Description of Linked Lists ............................................................................ 52 Interface for Linked Lists ............................................................................... 53 Implementation and Analysis of Linked Lists ............................................... 56 Linked List Example: Frame Management .................................................... 65 Description of Doubly-Linked Lists ............................................................... 68 Interface for Doubly-Linked Lists .................................................................. 68 Implementation and Analysis of Doubly Linked Lists ................................. 72 Description of Circular Lists .......................................................................... 82 Interface for Circular Lists .............................................................................. 82 Implementation and Analysis of Circular Lists ............................................. 84 Circular List Example: Second-Chance Page Replacement .......................... 91 Questions and Answers ................................................................................. 94 Related Topics ................................................................................................ 96 6. Stacks and Queues ................................................................................. 98 Description of Stacks ..................................................................................... 99 Interface for Stacks ....................................................................................... 100 Implementation and Analysis of Stacks ...................................................... 102 Description of Queues ................................................................................. 105 Interface for Queues .................................................................................... 105 Implementation and Analysis of Queues .................................................... 107 Queue Example: Event Handling ................................................................ 110 Questions and Answers ............................................................................... 113 Related Topics .............................................................................................. 114 7. Sets .............................................................................................................. 115 Description of Sets ....................................................................................... 116 Interface for Sets .......................................................................................... 119 Table of Contents vii Implementation and Analysis of Sets .......................................................... 122 Set Example: Set Covering ........................................................................... 133 Questions and Answers ............................................................................... 138 Related Topics .............................................................................................. 140 8. Hash Tables ............................................................................................. 141 Description of Chained Hash Tables .......................................................... 143 Interface for Chained Hash Tables .............................................................. 147 Implementation and Analysis of Chained Hash Tables ............................. 149 Chained Hash Table Example: Symbol Tables ........................................... 157 Description of Open-Addressed Hash Tables ............................................ 161 Interface for Open-Addressed Hash Tables ............................................... 164 Implementation and Analysis of Open Addressed Hash Tables ............... 166 Questions and Answers ............................................................................... 176 Related Topics .............................................................................................. 177 9. Trees ........................................................................................................... 178 Description of Binary Trees ......................................................................... 180 Interface for Binary Trees ............................................................................ 183 Implementation and Analysis of Binary Trees ........................................... 187 Binary Tree Example: Expression Processing ............................................ 199 Description of Binary Search Trees ............................................................ 203 Interface for Binary Search Trees ................................................................ 204 Implementation and Analysis of Binary Search Trees ............................... 206 Questions and Answers ............................................................................... 230 Related Topics .............................................................................................. 233 10. Heaps and Priority Queues .............................................................. 235 Description of Heaps ................................................................................... 236 Interface for Heaps ...................................................................................... 237 Implementation and Analysis of Heaps ...................................................... 239 Description of Priority Queues .................................................................... 250 Interface for Priority Queues ....................................................................... 251 Implementation and Analysis of Priority Queues ...................................... 252 Priority Queue Example: Parcel Sorting ..................................................... 254 Questions and Answers ............................................................................... 256 Related Topics .............................................................................................. 258 viii Table of Contents 11. Graphs ....................................................................................................... 259 Description of Graphs ................................................................................. 261 Interface for Graphs ..................................................................................... 267 Implementation and Analysis of Graphs .................................................... 270 Graph Example: Counting Network Hops ................................................. 284 Graph Example: Topological Sorting .......................................................... 290 Questions and Answers ............................................................................... 295 Related Topics .............................................................................................. 297 III. Algorithms ........................................................................................... 299 12. Sorting and Searching ........................................................................ 301 Description of Insertion Sort ....................................................................... 303 Interface for Insertion Sort ........................................................................... 303 Implementation and Analysis of Insertion Sort .......................................... 304 Description of Quicksort ............................................................................. 307 Interface for Quicksort ................................................................................. 308 Implementation and Analysis of Quicksort ................................................ 308 Quicksort Example: Directory Listings ........................................................ 314 Description of Merge Sort ............................................................................ 317 Interface for Merge Sort ............................................................................... 318 Implementation and Analysis of Merge Sort .............................................. 318 Description of Counting Sort ....................................................................... 324 Interface for Counting Sort .......................................................................... 325 Implementation and Analysis of Counting Sort .......................................... 325 Description of Radix Sort ............................................................................. 329 Interface for Radix Sort ................................................................................ 329 Implementation and Analysis of Radix Sort ............................................... 330 Description of Binary Search ....................................................................... 333 Interface for Binary Search .......................................................................... 334 Implementation and Analysis of Binary Search ......................................... 334 Binary Search Example: Spell Checking ..................................................... 337 Questions and Answers ............................................................................... 339 Related Topics .............................................................................................. 341 13. Numerical Methods .............................................................................. 343 Description of Polynomial Interpolation .................................................... 344 Interface for Polynomial Interpolation ........................................................ 348 Implementation and Analysis of Polynomial Interpolation ....................... 349