Tài liệu Wrox beginning algorithms nov 2005

TEAM LinG Beginning Algorithms Beginning Algorithms Simon Harris and James Ross Beginning Algorithms Published by Wiley Publishing, Inc. 10475 Crosspoint Boulevard Indianapolis, IN 46256 www.wiley.com Published 2006 by Wiley Publishing, Inc., Indianapolis, Indiana Published simultaneously in Canada ISBN-13: 978-0-7645- 9674-2 ISBN-10: 0-7645-9674-8 Manufactured in the United States of America 10 9 8 7 6 5 4 3 2 1 1MA/RS/RQ/QV/IN Library of Congress Cataloging-in-Publication Data: Harris, Simon, 1972Beginning algorithms / Simon Harris and James Ross. p. cm. Includes index. ISBN-13: 978-0-7645-9674-2 (paper/website) ISBN-10: 0-7645-9674-8 (paper/website) 1. Computer algorithms. I. Ross, James, 1968- II. Title. QA76.9.A43H376 2005 005.1--dc22 2005022374 No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 646-8600. Requests to the Publisher for permission should be addressed to the Legal Department, Wiley Publishing, Inc., 10475 Crosspoint Blvd., Indianapolis, IN 46256, (317) 572-3447, fax (317) 572-4355, or online at http://www.wiley.com/go/permissions. LIMIT OF LIABILITY/DISCLAIMER OF WARRANTY: THE PUBLISHER AND THE AUTHOR MAKE NO REPRESENTATIONS OR WARRANTIES WITH RESPECT TO THE ACCURACY OR COMPLETENESS OF THE CONTENTS OF THIS WORK AND SPECIFICALLY DISCLAIM ALL WARRANTIES, INCLUDING WITHOUT LIMITATION WARRANTIES OF FITNESS FOR A PARTICULAR PURPOSE. NO WARRANTY MAY BE CREATED OR EXTENDED BY SALES OR PROMOTIONAL MATERIALS. THE ADVICE AND STRATEGIES CONTAINED HEREIN MAY NOT BE SUITABLE FOR EVERY SITUATION. THIS WORK IS SOLD WITH THE UNDERSTANDING THAT THE PUBLISHER IS NOT ENGAGED IN RENDERING LEGAL, ACCOUNTING, OR OTHER PROFESSIONAL SERVICES. IF PROFESSIONAL ASSISTANCE IS REQUIRED, THE SERVICES OF A COMPETENT PROFESSIONAL PERSON SHOULD BE SOUGHT. NEITHER THE PUBLISHER NOR THE AUTHOR SHALL BE LIABLE FOR DAMAGES ARISING HEREFROM. THE FACT THAT AN ORGANIZATION OR WEBSITE IS REFERRED TO IN THIS WORK AS A CITATION AND/OR A POTENTIAL SOURCE OF FURTHER INFORMATION DOES NOT MEAN THAT THE AUTHOR OR THE PUBLISHER ENDORSES THE INFORMATION THE ORGANIZATION OR WEBSITE MAY PROVIDE OR RECOMMENDATIONS IT MAY MAKE. FURTHER, READERS SHOULD BE AWARE THAT INTERNET WEBSITES LISTED IN THIS WORK MAY HAVE CHANGED OR DISAPPEARED BETWEEN WHEN THIS WORK WAS WRITTEN AND WHEN IT IS READ. For general information on our other products and services please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002. Trademarks: Wiley, the Wiley logo, Wrox, the Wrox logo, Programmer to Programmer, and related trade dress are trademarks or registered trademarks of John Wiley & Sons, Inc. and/or its affiliates, in the United States and other countries, and may not be used without written permission. All other trademarks are the property of their respective owners. Wiley Publishing, Inc., is not associated with any product or vendor mentioned in this book. Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books. Credits Executive Editor Project Coordinators Carol Long Erin Smith Ryan Steffen Consulting Editor Jon Eaves Media Development Specialists Development Editors Angela Denny Kit Malone Travis Silvers Ami Frank Sullivan Sydney Jones Graphics and Production Specialists Mary Beth Wakefield Jonelle Burns Lauren Goddard Denny Hager Joyce Haughey Jennifer Heleine Barbara Moore Melanee Prendergast Alicia South Production Manager Quality Control Technicians Tim Tate John Greenough Leeann Harney Production Editor William A. Barton Copy Editor Luann Rouff Editorial Manager Vice President & Executive Group Publisher Richard Swadley Proofreading TECHBOOKS Production Services Vice President and Executive Publisher Joseph B. Wikert Indexing Valerie Haynes Perry About the Authors Simon Harris started writing animated sprites on a Commodore 64 in primary school. After a break of many years, he taught himself 80x86 and IBM System/370 assembler and started working professionally. Since then he has moved from assembler to C, C++, and, of course, Java. He believes a fundamental understanding and appreciation of algorithms is essential to developing good software; and since starting his own company, RedHill Consulting, he has managed to make a living discussing and demonstrating software development practices and techniques to anyone who will listen. In his more than 15 years of development experience, James Ross has ranged from building packaged products to large enterprise systems to research into compilers and languages. In recent years, he has become a code quality fanatic and agile methods specialist, particularly with test-driven development. He works as a consultant for ThoughtWorks, the world’s leading agile software development company. He is currently leading the development of a large J2EE project in the insurance industry in Melbourne, Australia. He lives with his wife and family in Melbourne. Acknowledgments From Simon Harris: First and foremost, a mighty big thank-you to Jon Eaves for handing us this opportunity, and to James, whose skill and professionalism never cease to amaze me. I certainly couldn’t have finished this book without either of you. Many thanks also to all those who read the draft chapters and provided feedback: Andrew Harris, Andy Trigg, Peter Barry, Michael Melia, and Darrell Deboer (I’m sure I’ve missed some). I hope you find the final product does justice to your efforts. I also want to acknowledge my brother Tim for listening to my ranting at all hours of the night and day, and Kerri Rusnak and her family for feeding me waffles and cups of tea, not to mention my Aikido students for continuing to turn up and practice during my various absences. Finally, I’d like to extend my sincerest gratitude to everyone at Wiley who persisted with the book and to all of my other friends and family who continued to prod and encourage me, especially when I thought the sky was falling. It’s certainly been a learning experience. From James Ross: First of all, I’d like to thank Simon for letting me come along for the ride on his first book. It was a great opportunity to write seriously for the first time and it’s always a pleasure and an education to work with Simon. We heard a lot of stories about author teams who destroy their relationship while collaborating on a book, but I’m glad to say we avoided that trap. I’d also like to thank all the folks at Wiley who were extremely understanding with two newbie authors and guided us unerringly towards the goal—especially Ami Sullivan and Carol Long. It is much appreciated. To all the supergeeks at ThoughtWorks who have made my professional life such a pleasure over the past few years, especially Andy Trigg, who’s been my programming pal since we wrote our first unit tests together, and who reviewed all the chapters I wrote with incredible attention to detail and insight, and Jon Eaves, the technical editor on this book, who never fails to make me laugh and teach me something. Simon Stewart also helped with great feedback on early drafts, and Gregor Hohpe and Martin Fowler provided the encouragement and inspiration to actually keep typing all those long nights. Speaking of the long nights, I can honestly say that this book would not have been possible (at least my chapters!) without the love and understanding of the ladies in my life—Catherine, who is the sun in our little solar system; Jessica; Ruby; and little Ella, who was six months old when I signed on for this project and who slept at least 12 hours every single night while it was being written. You may never read it, baby, but I’ll always think of you when I pick it up! Contents Acknowledgments Introduction Chapter 1: Getting Started Defining Algorithms Understanding Complexity in Relation to Algorithms Understanding Big-O Notation Constant Time: O(1) Linear Time: O(N) Quadratic Time: O(N2) Logarithmic Time: O(log N) and O(N log N) Factorial Time: O(N!) Unit Testing What Is Unit Testing? Why Unit Testing Is Important A JUnit Primer Test-Driven Development Summary Chapter 2: Iteration and Recursion Performing Calculations Processing Arrays Using Iterators to Overcome Array-based Problems Iterator Operations The Iterator Interface The Iterable Interface Iterator Idioms Standard Iterators Recursion Recursive Directory Tree Printer Example Anatomy of a Recursive Algorithm The Base Case The General Case Summary Exercises ix xix 1 1 3 4 6 6 6 8 8 9 9 11 11 14 14 15 16 18 18 19 20 20 21 21 35 37 40 40 41 41 41 Contents Chapter 3: Lists Understanding Lists Testing Lists Implementing Lists An Array List A Linked List Summary Exercises Chapter 4: Queues 43 43 46 58 59 66 74 74 75 Understanding Queues 75 Queue Operations The Queue Interface 76 77 A First-In-First-Out Queue Implementing the FIFO Queue Blocking Queues Example: A Call Center Simulator Running the Application Summary Exercises Chapter 5: Stacks Stacks The Tests Implementation Example: Implementing Undo/Redo Testing Undo/Redo Summary Chapter 6: Basic Sorting 77 81 82 86 95 96 96 97 97 99 102 105 106 114 115 The Importance of Sorting Sorting Fundamentals Understanding Comparators 115 116 116 Comparator Operations The Comparator Interface Some Standard Comparators 117 117 117 Working with the Natural Comparator Working with the Reverse Comparator Understanding Bubble Sort xii 117 119 121 Contents The ListSorter Interface Testing AbstractListSorter 124 124 Working with a Selection Sort Understanding Insertion Sort Understanding Stability Comparing the Basic Sorting Algorithms 128 133 138 139 CallCountingListComparator ListSorterCallCountingTest Understanding the Algorithm Comparison 139 140 143 Summary Exercises 144 144 Chapter 7: Advanced Sorting Understanding Understanding Understanding Understanding the Shellsort Algorithm Quicksort the Compound Comparator and Stability the Mergesort Algorithm Merging The mergesort Algorithm Comparing the Advanced Sorting Algorithms Summary Exercises Chapter 8: Priority Queues Understanding Priority Queues A Simple Priority Queue Example Working with Priority Queues Understanding the Unsorted List Priority Queue Understanding the Sorted List Priority Queue Understanding Heap-ordered Priority Queues Sink or Swim Comparing the Priority Queue Implementations Summary Exercises Chapter 9: Binary Searching and Insertion Understanding Binary Searching 145 145 151 157 160 160 162 169 172 172 173 174 174 179 182 184 186 188 194 198 198 199 199 Binary Search Approaches A List Searcher 202 202 Recursive Binary Searcher 205 xiii Contents Iterative Binary Searcher Assessing the List Searcher’s Performance 208 210 Linear Searching for Comparison Tests for Performance 210 212 Understanding Binary Insertion 216 A List Inserter Assessing Performance Summary Chapter 10: Binary Search Trees Understanding Binary Search Trees Minimum Maximum Successor Predecessor Search Insertion Deletion In-order Traversal Pre-order Traversal Post-order Traversal Balancing Testing and Implementing a Binary Search Tree Assessing Binary Search Tree Performance Summary Exercises Chapter 11: Hashing Understanding Hashing Working with Hashing Linear Probing Bucketing Assessing Performance Summary Exercises Chapter 12: Sets Understanding Sets Testing Set Implementations xiv 217 220 224 225 226 227 227 227 227 228 230 232 235 235 235 236 238 261 264 264 265 265 272 275 281 285 291 292 293 293 297 Contents A List Set A Hash Set A Tree Set Summary Exercises Chapter 13: Maps 303 305 309 315 316 317 Understanding Maps Testing Map Implementations A List Map A Hash Map A Tree Map Summary Exercises 317 322 329 333 337 343 344 Chapter 14: Ternary Search Trees 345 Understanding Ternary Search Trees Searching for a Word Inserting a Word Prefix Searching Pattern Matching Putting Ternary Search Trees into Practice Crossword Helper Example Summary Exercise Chapter 15: B-Trees 345 346 350 351 353 357 370 374 374 375 Understanding B-Trees Putting B-Trees into Practice Summary Exercises 375 381 392 393 Chapter 16: String Searching 395 A Generic String Searcher Interface A Generic Test Suite A Brute-Force Algorithm The Boyer-Moore Algorithm Creating the Tests Implementing the Algorithm 395 397 400 402 404 404 xv Contents A String Match Iterator Comparing the Performance Measuring Performance How They Compare Summary Chapter 17: String Matching Understanding Soundex Understanding Levenshtein Word Distance Summary Chapter 18: Computational Geometry A Quick Geometry Refresher Coordinates and Points Lines Triangles Finding the Intersection of Two Lines Slope Crossing the y Axis 408 409 409 413 413 415 415 426 435 437 437 437 438 439 440 441 442 Finding the Intersection Point Finding the Closest Pair of Points Summary Exercises 443 457 467 467 Chapter 19: Pragmatic Optimization 469 Where Optimization Fits In Understanding Profiling The FileSortingHelper Example Program Profiling with hprof Profiling with JMP Understanding Optimization Putting Optimization into Practice Summary 469 470 471 475 477 479 480 487 Appendix A: Further Reading 489 Appendix B: Resources 491 xvi Contents Appendix C: Bibliography 493 Appendix D: Answers to Exercises 495 Index 541 xvii Introduction Welcome to Beginning Algorithms, a step-by-step introduction to computing algorithms for the real world. Developers use algorithms and data structures every day of their working lives. Having a good understanding of these algorithms and knowledge of when to apply them is essential to producing software that not only works correctly, but also performs efficiently. This book aims to explain those algorithms and data structures most commonly encountered in day-today software development, while remaining at all times practical, concise, and to the point, with little or no verbiage to distract from the core concepts and examples. Who Should Read This Book The ideal reader of this book is someone who develops applications, or is just starting to do so, and who wants to understand algorithms and data structures. This might include programmers; developers; software engineering students; information systems students; and computer science students. While this book assumes you have an understanding of computer programming in general, it is also hoped that if you took away the code, you could still read the book cover to cover and follow along— albeit at a largely conceptual level. For this reason, team leaders, architects, and even business analysts might also benefit. Prerequisite Knowledge As the code examples are all written in the Java programming language, a working knowledge of Java is likely necessary, as is a familiarity with the standard Java libraries—and with the java.lang package in particular. Also necessary is an understanding of arrays, loops, and so on, and, of course, how to create, compile, and run Java classes. Over and above the prerequisites mentioned, there is no particular requirement that you have any knowledge of the data structures or the algorithms contained herein. What You Will Learn In these pages, you will find detailed explanations, some implementations, example uses, and exercises, all designed to build your understanding to a point where you can use this knowledge in the real world. The examples given are rarely, if ever, academic in nature. Very careful consideration has been given in each chapter to present you with code that, in most cases, could be used in real-world applications, immediately.