logo资料库

Data Structures and Algorithms in Java.pdf

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：9.41M 资料格式：pdf 举报 版权申诉
第1页 / 共738页
第2页 / 共738页
第3页 / 共738页
第4页 / 共738页
第5页 / 共738页
第6页 / 共738页
第7页 / 共738页
第8页 / 共738页
资料共738页，剩余部分请下载后查看
    Cover
    Title Page
    Copyright
    Preface to the Sixth Edition
    Prerequisites
    Online Resources
    Use as a Textbook
    About the Authors
    Additional Books by These Authors
    Acknowledgments
    Contents
    Chapter 1: Java Primer
    1.1 Getting Started
    1.2 Classes and Objects
    1.3 Strings, Wrappers, Arrays, and Enum Types
    1.4 Expressions
    1.5 Control Flow
    1.6 Simple Input and Output
    1.7 An Example Program
    1.8 Packages and Imports
    1.9 Software Development
    1.10 Exercises
    Chapter 2: Object-Oriented Design
    2.1 Goals, Principles, and Patterns
    2.2 Inheritance
    2.3 Interfaces and Abstract Classes
    2.4 Exceptions
    2.5 Casting and Generics
    2.6 Nested Classes
    2.7 Exercises
    Chapter 3: Fundamental Data Structures
    3.1 Using Arrays
    3.2 Singly Linked Lists
    3.3 Circularly Linked Lists
    3.4 Doubly Linked Lists
    3.5 Equivalence Testing
    3.6 Cloning Data Structures
    3.7 Exercises
    Chapter 4: Algorithm Analysis
    4.1 Experimental Studies
    4.2 The Seven Functions Used in This Book
    4.3 Asymptotic Analysis
    4.4 Simple Justification Techniques
    4.5 Exercises
    Chapter 5: Recursion
    5.1 Illustrative Examples
    5.2 Analyzing Recursive Algorithms
    5.3 Further Examples of Recursion
    5.4 Designing Recursive Algorithms
    5.5 Recursion Run Amok
    5.6 Eliminating Tail Recursion
    5.7 Exercises
    Chapter 6: Stacks, Queues, and Deques
    6.1 Stacks
    6.2 Queues
    6.3 Double-Ended Queues
    6.4 Exercises
    Chapter 7: List and Iterator ADTs
    7.1 The List ADT
    7.2 Array Lists
    7.3 Positional Lists
    7.4 Iterators
    7.5 The Java Collections Framework
    7.6 Sorting a Positional List
    7.7 Case Study: Maintaining Access Frequencies
    7.8 Exercises
    Chapter 8: Trees
    8.1 General Trees
    8.2 Binary Trees
    8.3 Implementing Trees
    8.4 Tree Traversal Algorithms
    8.5 Exercises
    Chapter 9: Priority Queues
    9.1 The Priority Queue Abstract Data Type
    9.2 Implementing a Priority Queue
    9.3 Heaps
    9.4 Sorting with a Priority Queue
    9.5 Adaptable Priority Queues
    9.6 Exercises
    Chapter 10: Maps, Hash Tables, and Skip Lists
    10.1 Maps
    10.2 Hash Tables
    10.3 Sorted Maps
    10.4 Skip Lists
    10.5 Sets, Multisets, and Multimaps
    10.6 Exercises
    Chapter 11: Search Trees
    11.1 Binary Search Trees
    11.2 Balanced Search Trees
    11.3 AVL Trees
    11.4 Splay Trees
    11.5 ( 2,4) Trees
    11.6 Red-Black Trees
    11.7 Exercises
    Chapter 12: Sorting and Selection
    12.1 Merge-Sort
    12.2 Quick-Sort
    12.3 Studying Sorting through an Algorithmic Lens
    12.4 Comparing Sorting Algorithms
    12.5 Selection
    12.6 Exercises
    Chapter 13: Text Processing
    13.1 Abundance of Digitized Text
    13.2 Pattern-Matching Algorithms
    13.3 Tries
    13.4 Text Compression and the Greedy Method
    13.5 Dynamic Programming
    13.6 Exercises
    Chapter 14: Graph Algorithms
    14.1 Graphs
    14.2 Data Structures for Graphs
    14.3 Graph Traversals
    14.4 Transitive Closure
    14.5 Directed Acyclic Graphs
    14.6 Shortest Paths
    14.7 Minimum Spanning Trees
    14.8 Exercises
    Chapter 15: Memory Management and B-Trees
    15.1 Memory Management
    15.2 Memory Hierarchies and Caching
    15.3 External Searching and B-Trees
    15.4 External-Memory Sorting
    15.5 Exercises
    Bibliography
    Index
    Data Structures and Algorithms in Java™ Sixth Edition Michael T. Goodrich Department of Computer Science University of California, Irvine Roberto Tamassia Department of Computer Science Brown University Michael H. Goldwasser Department of Mathematics and Computer Science Saint Louis University
    Vice President and Executive Publisher Executive Editor Assistant Marketing Manager Sponsoring Editor Project Editor Associate Production Manager Cover Designer Don Fowley Beth Lang Golub Debbie Martin Mary O’Sullivan Ellen Keohane Joyce Poh Kenji Ngieng This book was set in LATEX by the authors, and printed and bound by RR Donnelley. The cover was printed by RR Donnelley. Trademark Acknowledgments: Java is a trademark of Oracle Corporation. Unix ® is a registered trademark in the United States and other countries, licensed through X/Open Company, Ltd. PowerPoint ® is a trademark of Microsoft Corporation. All other product names mentioned herein are the trademarks of their respective owners. This book is printed on acid free paper. Founded in 1807, John Wiley & Sons, Inc. has been a valued source of knowledge and understanding for more than 200 years, helping people around the world meet their needs and fulfill their aspirations. Our company is built on a foundation of principles that include responsibility to the communities we serve and where we live and work. In 2008, we launched a Corporate Citizenship Initiative, a global effort to address the environmental, social, economic, and ethical challenges we face in our business. Among the issues we are addressing are carbon impact, paper specifications and procurement, ethical conduct within our business and among our vendors, and community and charitable support. For more information, please visit our website: www.wiley.com/go/citizenship. Copyright © 2014, 2010 John Wiley & Sons, Inc. All rights reserved. No part of this publi- cation 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, with- out either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc. 222 Rosewood Drive, Danvers, MA 01923, website www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030-5774, (201) 748-6011, fax (201) 748-6008, website http://www.wiley.com/go/ permissions. Evaluation copies are provided to qualified academics and professionals for review pur- poses only, for use in their courses during the next academic year. These copies are licensed and may not be sold or transferred to a third party. Upon completion of the review period, please return the evaluation copy to Wiley. Return instructions and a free of charge return mailing label are available at www.wiley.com/go/returnlabel. If you have chosen to adopt this textbook for use in your course, please accept this book as your complimentary desk copy. Outside of the United States, please contact your local sales representative. ISBN: 978-1-118-77133-4 (paperback) Printed in the United States of America 10 9 8 7 6 5 4 3 2 1
    To Karen, Paul, Anna, and Jack – Michael T. Goodrich To Isabel – Roberto Tamassia To Susan, Calista, and Maya – Michael H. Goldwasser
    Preface to the Sixth Edition Data Structures and Algorithms in Java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. The major changes in this sixth edition include the following: • We redesigned the entire code base to increase clarity of presentation and consistency in style and convention, including reliance on type inference, as introduced in Java 7, to reduce clutter when instantiating generic types. • We added 38 new figures, and redesigned 144 existing figures. • We revised and expanded exercises, bringing the grand total to 794 exercises! We continue our approach of dividing them into reinforcement, creativity, and project exercises. However, we have chosen not to reset the number- ing scheme with each new category, thereby avoiding possible ambiguity between exercises such as R-7.5, C-7.5, P-7.5. • The introductory chapters contain additional examples of classes and inheri- tance, increased discussion of Java’s generics framework, and expanded cov- erage of cloning and equivalence testing in the context of data structures. • A new chapter, dedicated to the topic of recursion, provides comprehensive coverage of material that was previously divided within Chapters 3, 4, and 9 of the fifth edition, while newly introducing the use of recursion when processing file systems. • We provide a new empirical study of the efficiency of Java’s StringBuilder class relative to the repeated concatenation of strings, and then discuss the theoretical underpinnings of its amortized performance. • We provide increased discussion of iterators, contrasting between so-called lazy iterators and snapshot iterators, with examples of both styles of imple- mentation for several data structures. • We have increased the use of abstract base classes to reduce redundancy when providing multiple implementations of a common interface, and the use of nested classes to provide greater encapsulation for our data structures. • We have included complete Java implementations for many data structures and algorithms that were only described with pseudocode in earlier editions. These new implementations include both array-based and linked-list-based queue implementations, a heap-based adaptable priority queue, a bottom-up heap construction, hash tables with either separate chaining or linear probing, splay trees, dynamic programming for the least-common subsequence prob- lem, a union-find data structure with path compression, breadth-first search of a graph, the Floyd-Warshall algorithm for computing a graph’s transitive closure, topological sorting of a DAG, and both the Prim-Jarn´ık and Kruskal algorithms for computing a minimum spanning tree. v
    vi Prerequisites Preface We assume that the reader is at least vaguely familiar with a high-level program- ming language, such as C, C++, Python, or Java, and that he or she understands the main constructs from such a high-level language, including: • Variables and expressions • Methods (also known as functions or procedures) • Decision structures (such as if-statements and switch-statements) • Iteration structures (for-loops and while-loops) For readers who are familiar with these concepts, but not with how they are ex- pressed in Java, we provide a primer on the Java language in Chapter 1. Still, this book is primarily a data structures book, not a Java book; hence, it does not provide a comprehensive treatment of Java. Nevertheless, we do not assume that the reader is necessarily familiar with object-oriented design or with linked structures, such as linked lists, for these topics are covered in the core chapters of this book. In terms of mathematical background, we assume the reader is somewhat famil- iar with topics from high-school mathematics. Even so, in Chapter 4, we discuss the seven most-important functions for algorithm analysis. In fact, sections that use something other than one of these seven functions are considered optional, and are indicated with a star (⋆). Online Resources This book is accompanied by an extensive set of online resources, which can be found at the following website: www.wiley.com/college/goodrich Included on this website is a collection of educational aids that augment the topics of this book, for both students and instructors. For all readers, and especially for students, we include the following resources: • All Java source code presented in this book • An appendix of useful mathematical facts • PDF handouts of PowerPoint slides (four-per-page) • A study guide with hints to exercises, indexed by problem number For instructors using this book, we include the following additional teaching aids: • Solutions to hundreds of the book’s exercises • Color versions of all figures and illustrations from the book • Slides in PowerPoint and PDF (one-per-page) format The slides are fully editable, so as to allow an instructor using this book full free- dom in customizing his or her presentations.
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料