Mastering Algorithms with C Useful Techniques from Sorting to Encryption (Kyle Loudon) (Z-Library)

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 trademarks of O’Reilly Media, Inc. Mastering Algorithms with C, the image of sea horses, 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. While every precaution has been taken in the preparation of this book, the publisher assumes 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]

v 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

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

Table of Contents ix Description of Least-Squares Estimation ..................................................... 352 Interface for Least-Squares Estimation ........................................................ 353 Implementation and Analysis of Least-Squares Estimation ........................ 354 Description of the Solution of Equations ................................................... 355 Interface for the Solution of Equations ....................................................... 360 Implementation and Analysis of the Solution of Equations ...................... 360 Questions and Answers ............................................................................... 362 Related Topics .............................................................................................. 363 14. Data Compression ................................................................................ 365 Description of Bit Operations ..................................................................... 369 Interface for Bit Operations ......................................................................... 369 Implementation and Analysis of Bit Operations ........................................ 370 Description of Huffman Coding .................................................................. 375 Interface for Huffman Coding ..................................................................... 379 Implementation and Analysis of Huffman Coding ..................................... 380 Huffman Coding Example: Optimized Networking ................................... 396 Description of LZ77 ..................................................................................... 399 Interface for LZ77 ......................................................................................... 402 Implementation and Analysis of LZ77 ........................................................ 403 Questions and Answers ............................................................................... 418 Related Topics .............................................................................................. 420 15. Data Encryption ................................................................................... 422 Description of DES ....................................................................................... 425 Interface for DES .......................................................................................... 432 Implementation and Analysis of DES ......................................................... 433 DES Example: Block Cipher Modes ............................................................ 445 Description of RSA ....................................................................................... 448 Interface for RSA .......................................................................................... 452 Implementation and Analysis of RSA .......................................................... 452 Questions and Answers ............................................................................... 456 Related Topics .............................................................................................. 458 16. Graph Algorithms ................................................................................. 460 Description of Minimum Spanning Trees ................................................... 463 Interface for Minimum Spanning Trees ...................................................... 465 Implementation and Analysis of Minimum Spanning Trees ...................... 466 Description of Shortest Paths ...................................................................... 472 Interface for Shortest Paths .......................................................................... 474

x Table of Contents Implementation and Analysis of Shortest Paths ......................................... 475 Shortest Paths Example: Routing Tables ..................................................... 481 Description of the Traveling-Salesman Problem ........................................ 485 Interface for the Traveling-Salesman Problem ........................................... 487 Implementation and Analysis of the Traveling-Salesman Problem ........... 488 Questions and Answers ............................................................................... 493 Related Topics .............................................................................................. 495 17. Geometric Algorithms ......................................................................... 496 Description of Testing Whether Line Segments Intersect .......................... 499 Interface for Testing Whether Line Segments Intersect ............................. 502 Implementation and Analysis of Testing Whether Line Segments Intersect ....................................................................................... 503 Description of Convex Hulls ....................................................................... 505 Interface for Convex Hulls .......................................................................... 507 Implementation and Analysis of Convex Hulls .......................................... 507 Description of Arc Length on Spherical Surfaces ....................................... 512 Interface for Arc Length on Spherical Surfaces .......................................... 515 Implementation and Analysis of Arc Length on Spherical Surfaces .......... 515 Arc Length Example: Approximating Distances on Earth .......................... 517 Questions and Answers ............................................................................... 520 Related Topics .............................................................................................. 523 Index .................................................................................................................... 525

xi 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 algo- rithms, 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. Organization This book is divided into three parts. The first part consists of introductory mate- rial that is useful when working in the rest of the book. The second part presents a number of data structures considered fundamental in the field of computer sci- ence. The third part presents an assortment of algorithms for solving common problems. Each of these parts is described in more detail in the following sec- tions, including a summary of the chapters each part contains.

xii Preface Part I Part I, Preliminaries, contains Chapters 1 through 4. Chapter 1, Introduction, intro- duces the concepts of data structures and algorithms and presents reasons for using them. It also presents a few topics in software engineering, which are applied throughout the rest of the book. Chapter 2, Pointer Manipulation, dis- cusses a number of topics on pointers. Pointers appear a great deal in this book, so this chapter serves as a refresher on the subject. Chapter 3, Recursion, covers recursion, a popular technique used with many data structures and algorithms. Chapter 4, Analysis of Algorithms, presents the analysis of algorithms. The tech- niques in this chapter are used to analyze algorithms throughout the book. Part II Part II, Data Structures, contains Chapters 5 through 11. Chapter 5, Linked Lists, presents various forms of linked lists, including singly-linked lists, doubly-linked lists, and circular lists. Chapter 6, Stacks and Queues, presents stacks and queues, data structures for sorting and returning data on a last-in, first-out and first-in, first- out order respectively. Chapter 7, Sets, presents sets and the fundamental mathe- matics describing sets. Chapter 8, Hash Tables, presents chained and open- addressed hash tables, including material on how to select a good hash function and how to resolve collisions. Chapter 9, Trees, presents binary and AVL trees. Chapter 9 also discusses various methods of tree traversal. Chapter 10, Heaps and Priority Queues, presents heaps and priority queues, data structures that help to quickly determine the largest or smallest element in a set of data. Chapter 11, Graphs, presents graphs and two fundamental algorithms from which many graph algorithms are derived: breadth-first and depth-first search. Part III Part III, Algorithms, contains Chapters 12 through 17. Chapter 12, Sorting and Searching, covers various algorithms for sorting, including insertion sort, quick- sort, merge sort, counting sort, and radix sort. Chapter 12 also presents binary search. Chapter 13, Numerical Methods, covers numerical methods, including algo- rithms for polynomial interpolation, least-squares estimation, and the solution of equations using Newton’s method. Chapter 14, Data Compression, presents algo- rithms for data compression, including Huffman coding and LZ77. Chapter 15, Data Encryption, discusses algorithms for DES and RSA encryption. Chapter 16, Graph Algorithms, covers graph algorithms, including Prim’s algorithm for mini- mum spanning trees, Dijkstra’s algorithm for shortest paths, and an algorithm for solving the traveling-salesman problem. Chapter 17, Geometric Algorithms, pre- sents geometric algorithms, including methods for testing whether line segments intersect, computing convex hulls, and computing arc lengths on spherical surfaces.

Preface xiii Key Features There are a number of special features that I believe together make this book a unique approach to covering the subject of data structures and algorithms: Consistent format for every chapter Every chapter (excluding those in the first part of the book) follows a consis- tent format. This format allows most of the book to be read as a textbook or a reference, whichever is needed at the moment. Clearly identified topics and applications Each chapter (except Chapter 1) begins with a brief introduction, followed by a list of clearly identified topics and their relevance to real applications. Analyses of every operation, algorithm, and example An analysis is provided for every operation of abstract datatypes, every algo- rithm in the algorithms chapters, and every example throughout the book. Each analysis uses the techniques presented in Chapter 4. Real examples, not just trivial exercises All examples are from real applications, not just trivial exercises. Examples like these are exciting and teach more than just the topic being demonstrated. Real implementations using real code All implementations are written in C, not pseudocode. The benefit of this is that when implementing many data structures and algorithms, there are con- siderable details pseudocode does not address. Questions and answers for further thought At the end of each chapter (except Chapter 1), there is a series of questions along with their answers. These emphasize important ideas from the chapter and touch on additional topics. Lists of related topics for further exploration At the end of each chapter (except Chapter 1), there is a list of related topics for further exploration. Each topic is presented with a brief description. Numerous cross references and call-outs Cross references and call-outs mark topics mentioned in one place that are introduced elsewhere. Thus, it is easy to locate additional information. Insightful organization and application of topics Many of the data structures or algorithms in one chapter use data structures and algorithms presented elsewhere in the book. Thus, they serve as exam- ples of how to use other data structures and algorithms themselves. All depen- dencies are carefully marked with a cross reference or call-out.

xiv Preface Coverage of fundamental topics, plus more This book covers the fundamental data structures and algorithms of computer science. It also covers several topics not normally addressed in books on the subject. These include numerical methods, data compression (in more detail), data encryption, and geometric algorithms. About the Code All implementations in this book are in C. C was chosen because it is still the most general-purpose language in use today. It is also one of the best languages in which to explore the details of data structures and algorithms while still working at a fairly high level. It may be helpful to note a few things about the code in this book. All code focuses on pedagogy first There is also a focus on efficiency, but the primary purpose of all code is to teach the topic it addresses in a clear manner. All code has been fully tested on four platforms The platforms used for testing were HP-UX 10.20, SunOs 5.6, Red Hat Linux 5. 1, and DOS/Windows NT/95/98. See the readme file on the accompanying disk for additional information. Headers document all public interfaces Every implementation includes a header that documents the public interface. Most headers are shown in this book. However, headers that contain only prototypes are not. (For instance, Example 12-1 includes sort.h, but this header is not shown because it contains only prototypes to various sorting functions.) Static functions are used for private functions Static functions have file scope, so this fact is used to keep private functions private. Functions specific to a data structure or algorithm’s implementation are thus kept out of its public interface. Naming conventions are applied throughout the code Defined constants appear entirely in uppercase. Datatypes and global vari- ables begin with an uppercase character. Local variables begin with a lower- case character. Operations of abstract datatypes begin with the name of the type in lowercase, followed by an underscore, then the name of the opera- tion in lowercase. All code contains numerous comments All comments are designed to let developers follow the logic of the code with- out reading much of the code itself. This is useful when trying to make con- nections between the code and explanations in the text.

Preface xv Structures have typedefs as well as names themselves The name of the structure is always the name in the typedef followed by an underscore. Naming the structure itself is necessary for self-referential struc- tures like the one used for linked list elements (see Chapter 5). This approach is applied everywhere for consistency. All void functions contain explicit returns Although not required, this helps quickly identify where a void function returns rather than having to match up braces. Conventions Most of the conventions used in this book should be recognizable to those who work with computers to any extent. However, a few require some explanation. Bold italic Nonintrinsic mathematical functions and mathematical variables appear in this font. Constant width italic Variables from programs, names of datatypes (such as structure names), and defined constants appear in this font. Italic Commands (as they would be typed in at a terminal), names of files and paths, operations of abstract datatypes, and other functions from programs appear in this font. lg x This notation is used to represent the base-2 logarithm of x, log2 x. This is the notation used commonly in computer science when discussing algorithms; therefore, it is used in this book. How to Contact Us We have tested and verified the information in this book to the best of our ability, but you may find that features have changed (or even that we have made mistakes!). Please

xvi Preface let us know about any errors you find, as well as your suggestions for future editions, by writing to: O’Reilly & Associates, Inc. 101 Morris Street Sebastopol, CA 95472 1-800-998-9938 (in the U.S. or Canada) 1-707-829-0515 (international/local) 1-707-829-0104 (FAX) You can also send us messages electronically. To be put on the mailing list or request a catalog, send email to: info@oreilly.com To ask technical questions or comment on the book, send email to: bookquestions@oreilly.com We have a web site for the book, where we’ll list examples, errata, and any plans for future editions. You can access this page at: http://www.oreilly.com/catalog/masteralgoc/ For more information about this book and others, see the O’Reilly web site: http://www.oreilly.com Acknowledgments The experience of writing a book is not without its ups and downs. On the one hand, there is excitement, but there is also exhaustion. It is only with the support of others that one can truly delight in its pleasures and overcome its perils. There are many people I would like to thank. First, I thank Andy Oram, my editor at O’Reilly & Associates, whose assistance has been exceptional in every way. I thank Andy especially for his continual patience and support. In addition, I would like to thank Tim O’Reilly and Andy together for their interest in this project when it first began. Other individuals I gratefully acknowledge at O’Reilly & Associates are Rob Romano for drafting the technical illustrations, and Lenny Muellner and Mike Sierra, members of the tools group, who were always quick to reply to my questions. I thank Jeffrey Liggett for his swift and detailed work during the production process. In addition, I would like to thank the many others I did not correspond with directly at O’Reilly & Associates but who played no less a part in the production of this book. Thank you, everyone. Several individuals gave me a great deal of feedback in the form of reviews. I owe a special debt of gratitude to Bill Greene of Intel Corporation for his enthusiasm

Preface xvii and voluntary support in reviewing numerous chapters throughout the writing pro- cess. I also would like to thank Alan Solis of Com21 for reviewing several chap- ters. I thank Alan, in addition, for the considerable knowledge he has imparted to me over the years at our weekly lunches. I thank Stephen Friedl for his meticu- lous review of the completed manuscript. I thank Shaun Flisakowski for the review she provided at the manuscript’s completion as well. In addition, I grate- fully acknowledge those who looked over chapters with me from time to time and with whom I discussed material for the book on an ongoing basis. Many individuals gave me support in countless other ways. First, I would like to thank Jeff Moore, my colleague and friend at Jeppesen, whose integrity and pur- suit of knowledge constantly inspire me. During our frequent conversations, Jeff was kind enough to indulge me often by discussing topics in the book. Thank you, Jeff. I would also like to thank Ken Sunseri, my manager at Jeppesen, for cre- ating an environment at work in which a project like this was possible. Further- more, I warmly thank all of my friends and family for their love and support throughout my writing. In particular, I thank Marc Loudon for answering so many of my questions. I thank Marc and Judy Loudon together for their constant encour- agement. I thank Shala Hruska for her patience, understanding, and support at the project’s end, which seemed to last so long. Finally, I would like to thank Robert Foerster, my teacher, for the experiences we shared on a 16K TRS-80 in 1981. I still recall those times fondly. They made a wonderful difference in my life. For giving me my start with computers, I dedicate this book to you with affection.