Algorithms 4th Edition

5星(超过95%的资源)
所需积分/C币:10 2013-12-24 12:12:53 12.83MB PDF
16
收藏 收藏
举报

普林斯顿大学经典算法课参考资料,软件开发人员必备
Algorithms FOURTH EDITION Robert Sedgewick and Kevin wayne Princeton university A Addison-Wesley 、 pper Saddle river,NJ· Boston· Indianapolis· San francisco New york· Toronto· Montreal· London· Munich· Paris· Madrid Capetown Sydney Tokyo· Singapore· Mexico city 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 the publisher was aware of a trademark claim, the designations have been printed with initial capital letters or in all capitals The authors and publisher have taken care in the preparation of this book, but make no expressed or im lied warranty of any kind and assume no responsibility for errors or omissions. no liability is assumed for incidental or consequential damages in connection with or arising out of the use of the information or programs contained herein The publisher offers excellent discounts on this book when ordered in quantity for bulk purchases or special sales, which may include electronic versions and/or custom covers and content particular to your business, training goals, marketing focuS, and branding interests. For more information, please contact U.S. Corporate and government sale (800)382-3419 corpsalesapearsontechgroup.com For sales outside the United States, please contact International sales international@pearson.com Visit us on the Web: informit. com/aw Cataloging-in-Publication Data is on file with the Library of Congress Copyright O 2011 Pearson Education, Inc All rights reserved. Printed in the United States of America. This publication is protected by copyright, and permission must be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. For information regarding permissions, write to Pearson education, Inc Rights and Contracts Department 501 Boylston Street, Suite 900 Boston MA 02116 Fax:(617)671-3447 ISBN-13:978-0-321-57351-3 ISBN-10:0-321-57351-X Text printed in the United States on recycled paper at Courier in Westford, Massachusetts First printing, March 2011 To Adam, Andrew, brett, robbie and especially linda To Jackie and alex CONTENTS P reface 1 Fundamentals 1.1 Basic Programming Model 8 1.2 Data Abstraction 64 1.3 Bags, Queues, and Stacks 120 1. 4 Analysis of algorithms 172 1.5 Case Study: Union-Find 216 2 Sorting 243 2.1 Elementary Sorts 244 2.2 Mergesort 270 2.3 Quicksort 288 2. 4 Priority queues 308 2.5 Applications 336 3 Searching 361 3.1 Symbol tables 362 3. 2 Binary Search Trees 396 3.3 Balanced Search trees 424 3.4 Hash tables 458 3.5 Applications 486 4 Graphs ,,,515 4.1 Undirected graphs 518 4.2 Directed Graphs 566 4.3 Minimum Spanning Trees 604 4.4 Shortest paths 638 5 Strings 695 5.1 String Sorts 702 5.2 Tries 730 5.3 Substring Search 758 5.4 Regular expressions 788 5.5 Data Compression 810 6 Context 853 Index .933 algorithms Clients 955 PREFACE his book is intended to survey the most important computer algorithms in use today, and to teach fundamental techniques to the growing number of people in need of knowing them. It is intended for use as a textbook for a second course in computer science, after students have acquired basic programming skills and familiarity with computer systems. The book also may be useful for self-study or as a reference for people engaged in the development of computer systems or applications programs, since it contains implemen tations of useful algorithms and detailed information on performance characteristics and clients. The broad perspective taken makes the book an appropriate introduction to the field THE STUDY OF ALGORITHMS AND DATA STRUCTURES is fundamental to any computer- science curriculum, but it is not just for programmers and computer-science students. every one who uses a computer wants it to run faster or to solve larger problems. The algorithms in this book represent a body of knowledge developed over the last 50 years that has become indispensable. From N-body simulation problems in physics to genetic-sequencing problems in molecular biology, the basic methods described here have become essential in scientific research; from architectural modeling systems to aircraft simulation, they have become es sential tools in engineering; and from database systems to internet search engines, they have become essential parts of modern software systems. And these are but a few examples-as the scope of computer applications continues to grow, so grows the impact of the basic methods covered here Before developing our fundamental approach to studying algorithms, we develop data types for stacks, queues, and other low-level abstractions that we use throughout the book Then we survey fundamental algorithms for sorting, searching, graphs, and strings. The last chapter is an overview placing the rest of the material in the book in a larger context Distinctive features The orientation of the book is to study algorithms likely to be of practical use. The book teaches a broad variety of algorithms and data structures and pro- vides sufficient information about them that readers can confidently implement, debug, and put them to work in any computational environment. The approach involves Algorithms. Our descriptions of algorithms are based on complete implementations and on a discussion of the operations of these programs on a consistent set of examples. Instead of presenting pseudo-code, we work with real code, so that the programs can quickly be put to practical use. Our programs are written in Java, but in a style such that most of our code can be reused to develop implementations in other modern programming languages Data types. We use a modern programming style based on data abstraction, so that algo- rithms and their data structures are encapsulated together Applications. Each chapter has a detailed description of applications where the algorithms described play a critical role. These range from applications in physics and molecular biology to engineering computers and systems, to familiar tasks such as data compression and search ing on the web A scientific approach. We emphasize developing mathematical models for describing the performance of algorithms, using the models to develop hypotheses about performance, and then testing the hypotheses by running the algorithms in realistic contexts Breadth of coverage. We cover basic abstract data types, sorting algorithms, searching al- gorithms, graph processing, and string processing. We keep the material in algorithmic con text, describing data structures, algorithm design paradigms, reduction, and problem-solving models. We cover classic methods that have been taught since the 1960s and new methods hat have been invented in recent years Our primary goal is to introduce the most important algorithms in use today to as wide an audience as possible. These algorithms are generally ingenious creations that, remarkably, can each be expressed in just a dozen or two lines of code. As a group, they represent problem solving power of amazing scope. They have enabled the construction of computational ar tifacts, the solution of scientific problems, and the development of commercial applications that would not have been feasible without them

...展开详情
立即下载 身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
snakeqian 浅显易懂,好书
2015-07-31
回复
怪梦侠 浅显易懂的算法书,值得阅读
2015-06-03
回复
daohu 很好的算法书,很不错
2015-05-26
回复
tianjianshan 非常好,英文原版,文字版,很清晰
2015-03-24
回复
陽昊棠 只能说,相见恨晚,整理原来臃肿的知识和思路的一本减肥健美书。
2015-03-02
回复
towersxu 好书,非常清晰。
2015-01-28
回复
zhiyu5770 非常不错,在coursera上看到的以这本书base的网络教程,配合起来读有帮助,感谢分享
2015-01-09
回复
wadexmy Very good book,Just what I need.
2015-01-08
回复
wang73ying 很好 很清晰
2014-11-20
回复
u011137396 本书格式,字体都非常清晰,内容也是以java语言为主,容易上手
2014-11-10
回复
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
上传资源赚钱or赚积分
最新推荐
Algorithms 4th Edition 10积分/C币 立即下载
1/0