作者：Robert Sedgewick
出版日期：July 23, 1998
出版社：Addison Wesley
页数：752
ISBN：ISBN-10: 0201350882 ISBN-13: 978-0201350883
文件格式：CHM

Product Description
Robert Sedgewick has thoroughly rewritten and substantially expandedandupdated his popular work to provide current and comprehensivecoverage ofimportant algorithms and data structures. Christopher VanWyk and Sedgewickhave developed new C++ implementations that bothexpress the methods in aconcise and direct manner, and also provideprogrammers with the practicalmeans to test them on real applications.Many new algorithms are presented, and the explanations of eachalgorithmare much more detailed than in previous editions. A new textdesign anddetailed, innovative figures, with accompanying commentary,greatly enhancethe presentation. The third edition retains thesuccessful blend of theory andpractice that has made Sedgewick’s workan invaluable resource for more than250,000 programmers! Thisparticular book, Parts 1-4, represents the essential first half ofSedgewick’scomplete work. It provides extensive coverage of fundamentaldata structuresand algorithms for sorting, searching, and relatedapplications. Although thesubstance of the book applies to programmingin any language, theimplementations by Van Wyk and Sedgewick alsoexploit the natural matchbetween C++ classes and ADT implementations.Highlights
Expanded coverage of arrays, linked lists, strings, trees, and other basic
data structures Greater emphasis on abstract data types (ADTs),modular programming, object-oriented programming, and C++ classes thanin previous editions
Over 100 algorithms for sorting, selection, priority queue ADT implementations, and symbol table ADT (searching) implementations
New implementations of binomial queues, multiway radix sorting,randomized BSTs, splay trees, skip lists, multiway tries, B trees,extendible hashing, and much more Increased quantitative informationabout the algorithms, giving you a
basis for comparing them Over 1000 new exercises to help you learnthe properties of algorithms Whether you are learning the algorithmsfor the first time or wish to have up-to-date reference material thatincorporates new programming styles with classic and new algorithms,you will find a wealth of useful information in this book.
From the Inside Flap
This book is intended to survey the most important computeralgorithms in use today, and to teach fundamental techniques to thegrowing number of people in need of knowing them. It can be used as atextbook for a second, third, or fourth course in computer science,after students have acquired basic programming skills and familiaritywith computer systems, but before they have taken specialized coursesin advanced areas of computer science or computer applications. Thebook also may be useful for self-study or as a reference for peopleengaged in the development of computer systems or applicationsprograms, since it contains implementations of useful algorithms anddetailed information on these algorithms’ performance characteristics.The broad perspective taken makes the book an appropriate introductionto the field.
I have completely rewritten the text for this new edition, and Ihave added more than a thousand new exercises, more than a hundred newfigures, and dozens of new programs. I have also added detailedcommentary on all the figures and programs. This new material providesboth coverage of new topics and fuller explanations of many of theclassic algorithms. A new emphasis on abstract data types throughoutthe book makes the programs more broadly useful and relevant in modernprogramming environments. People who have read old editions of the bookwill find a wealth of new information throughout; all readers will finda wealth of pedagogical material that provides effective access toessential concepts.
Due to the large amount of new material, we have split the newedition into two volumes (each about the size of the old edition) ofwhich this is the first. This volume covers fundamental concepts, datastructures, sorting algorithms, and searching algorithms; the secondvolume covers advanced algorithms and applications, building on thebasic abstractions and methods developed here. Nearly all the materialon fundamentals and data structures in this edition is new.
This book is not just for programmers and computer-science students.Nearly everyone who uses a computer wants it to run faster or to solvelarger problems. The algorithms in this book represent a body ofknowledge developed over the last 50 years that has becomeindispensible in the efficient use of the computer, for a broad varietyof applications. From N-body simulation problems in physics togenetic-sequencing problems in molecular biology, the basic methodsdescribed here have become essential in scientific research; and fromdatabase systems to Internet search engines, they have become essentialparts of modern software systems. As the scope of computer applicationsbecomes more widespread, so grows the impact of many of the basicmethods covered here. The goal of this book is to serve as a resourcefor students and professionals interested in knowing and makingintelligent use of these fundamental algorithms as basic tools forwhatever computer application they might undertake. Scope
The book contains 16 chapters grouped into four major parts:fundamentals, data structures, sorting, and searching. The descriptionshere are intended to give readers an understanding of the basicproperties of as broad a range of fundamental algorithms as possible.The algorithms described here have found widespread use for years, andrepresent an essential body of knowledge for both the practicingprogrammer and the computer-science student. Ingenious methods rangingfrom binomial queues to patricia tries are described, all related tobasic paradigms at the heart of computer science. The second volumeconsists of four additional parts that cover strings, geometry, graphs,and advanced topics. My primary goal in developing these books has beento bring together the fundamental methods from these diverse areas, toprovide access to the best methods known for solving problems bycomputer.
You will most appreciate the material in this book if you have hadone or two previous courses in computer science or have had equivalentprogramming experience: one course in programming in a high-levellanguage such as C++, Java, or C, and perhaps another course thatteaches fundamental concepts of programming systems. This book is thusintended for anyone conversant with a modern programming ivlanguage andwith the basic features of modern computer systems. References thatmight help to fill in gaps in your background are suggested in the text.
Most of the mathematical material supporting the analytic results isself-contained (or is labeled as beyond the scope of this book), solittle specific preparation in mathematics is required for the bulk ofthe book, although mathematical maturity is definitely helpful. Use inthe Curriculum
There is a great deal of flexibility in how the material here can betaught, depending on the taste of the instructor and the preparation ofthe students. There is sufficient coverage of basic material for thebook to be used to teach data structures to beginners, and there issufficient detail and coverage of advanced material for the book to beused to teach the design and analysis of algorithms to upper-levelstudents. Some instructors may wish to emphasize implementations andpractical concerns; others may wish to emphasize analysis andtheoretical concepts.
I am developing a variety of course materials for use with thisbook, including slide masters for use in lectures, programmingassignments, homework assignments and sample exams, and interactiveexercises for students.
An elementary course on data structures and algorithms mightemphasize the basic data structures in Part 2 and their use in theimplementations in Parts 3 and 4. A course on design and analysis ofalgorithms might emphasize the fundamental material in Part 1 andChapter 5, then study the ways in which the algorithms in Parts 3 and 4achieve good asymptotic performance. A course on software engineeringmight omit the mathematical and advanced algorithmic material, andemphasize how to integrate the implementations given here into largeprograms or systems. A course on algorithms might take a surveyapproach and introduce concepts from all these areas.
Earlier editions of this book have been used in recent years atscores of colleges and universities around the world as a text for thesecond or third course in computer science and as supplemental readingfor other courses. At Princeton, our experience has been that thebreadth of coverage of material in this book provides our majors withan introduction to computer science that can be expanded upon in latercourses on analysis of algorithms, systems programming and theoreticalcomputer science, while providing the growing group of students fromother disciplines with a large set of techniques that these people canimmediately put to good use.
The exercises–most of which are new to this edition–fall intoseveral types. Some are intended to test understanding of material inthe text, and simply ask readers to work through an example or to applyconcepts described in the text. Others involve implementing and puttingtogether the algorithms, or running empirical studies to comparevariants of the algorithms and to learn their properties. Still othersare a repository for important information at a level of detail that isnot appropriate for the text. Reading and thinking about the exerciseswill pay dividends for every reader. Algorithms of Practical Use
Anyone wanting to use a computer more effectively can use this bookfor reference or for self-study. People with programming experience canfind information on specific topics throughout the book. To a largeextent, you can read the individual chapters in the book independentlyof the others, although, in some cases, algorithms in one chapter makeuse of methods from a previous chapter.
The orientation of the book is to study algorithms likely to be ofpractical use. The book provides information about the tools of thetrade to the point that readers can confidently implement, debug, andput to work algorithms to solve a problem or to provide functionalityin an application. Full implementations of the methods discussed areincluded, as are descriptions of the operations of these programs on aconsistent set of examples.
Because we work with real code, rather than write pseudo-code, youcan put the programs to practical use quickly. Program listings areavailable from the book’s home page. You can use these working programsin many ways to help you study algorithms. Read them to check yourunderstanding of the details of an algorithm, or to see one way tohandle initializations, boundary conditions, and other awkwardsituations that often pose programming challenges. Run vithem to seethe algorithms in action, to study performance empirically and checkyour results against the tables in the book, or to try your ownmodifications.
When appropriate, empirical and analytic results are presented toillustrate why certain algorithms are preferred. When interesting, therelationship of the practical algorithms being discussed t