书籍详情

数据结构与算法分析Java语言描述(英文版·第二版)

数据结构与算法分析Java语言描述(英文版·第二版)

作者:(美)韦斯

出版社:机械工业出版社

出版时间:2007-01-01

ISBN:9787111198765

定价:¥55.00

购买这本书可以去
内容简介
  本书是国外数据结构与算法分析方面的标准教材,使用最卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。随着计算机速度的不断增加和功能的日益强大,人们对有效编程和算法分析的要求也在增长。本书把算法分析与最有效率的Java程序的开发有机地结合起来,深入分析每种算法,内容全面、缜密严格,并细致讲解精心构造程序的方法。第2版的特色如下:·全面阐述新的Java 5,0编程语言和Java Collections库。·改进内部设计,用图和实例阐述算法的实施步骤。·第3章对表、栈和队列的讨论进行了全面修订。·用一章专门讨论摊还分析和一些高级数据结构的实现。·每章末尾的大量练习按照难易程度编排,以增强对关键概念的理解。
作者简介
  MarkAllen Weiss拥有普林斯顿大学计算机科学博士学位,现在是佛罗里达国际大学计算机学院教授。他是著名的计算机教育专家,在数据结构与算法分析方面卓有建树,著有多部畅销书籍:《Data Structures and Problem Solving:LJsirlg、Java》、《Data Structures and Problem Solving:Using C++》、《数据结构与算法分析——C语言描述》等。他目前是AP(AdvancedPlacement)计算机学科委员会成员。
目录
Preface vii
Chapter 1 Introdudion
  1.1  What's the Book About?  1
  1.2 Mathematics Review  2
      1.2.1  Exponents 3
      1.2.2 Logarithms 3
      1.2.3  Series 4
      1.2.4 Modular Arithmetic 5
      1.2.5  The P Word 6
  1.3 A Brief Introduction to Recursion  7
  1.4  Implementing Generic Components Pre Java 5  11
      1.4.1  Using Object for Genericity 12
      1.4.2 Wrappers for Primitive Types 12
      1.4.3 Using Interface Types for Genericity 13
      1.4.4 Compatibility of Array Types 15
  1.5  Implementing Generic Components Using Java 5 Generics  16
      1.5.1  Simple Generic Classes and Interfaces 16
      1.5.2 Autoboxing/Unboxing 17
      1.5.3 Wildcards with Bounds 18
      1.5.4 Generic Static Methods 19
      1.5.5 Type Bounds 20
      1.5.6 Type Erasure 21
      1.5.7 RestrictiOns on Generics 22
  1.6  Function Objects  23
      Summary  25
      Exercises  25
      References  26
Chapter 2 Algorithm Analysis
  2.1  Mathematical Background  29
  2.2  Model  32
  2.3 What to Analyze  32
  2.4 Running Time Calculations  35
      2.4.1  A Simple Example 35
      2.4.2  General Rules 36
      2.4.3  Solutions for the Maximum Subsequence Sum Problem 38
      2.4.4  Logarithms in the Running Time 44
      2.4.5  Checking Your Analysis 48
      2.4.6 A Grain of Salt 48
      Summary  50
      Exercises  50
      References  55
Chapter 3 Lists, Stacks, and Queues
  3.1  Abstract Data Types (ADTs)  57
  3.2 The List ADT  58
      3.2.1  Simple Array Implementation of Lists 58
      3.2.2  Simple Linked Lists 59
  3.3  Lists in the Java Collections API  60
     3.3.1  Collection Interface 61
     3.3.2  Iterator s 62
     3.3.3  The List Interface, ArrayList, and LinkedList 63
     3.3.4  Example: Using remove on a LinkedList 65
     3.3.5  ListIterators 66
 3.4  Implementation of ArrayList  67
     3.4.1  The Basic Class 68
     3.4.2  The Iterator and Java Nested and Inner Classes 68
 3.5  Implementation of LinkedList  75
 3.6  The Stack ADT  82
     3.6.1  Stack Model 82
     3.6.2  Implementation of Stacks 83
     3.6.3 Applications 83
 3.7  The Queue ADT  91
     3.7.1  Queue Model 91
     3.7.2  Array Implementation of Queues 91
     3.7.3  Applications of Queues 94
     Summary  95
     Exercises  95
Chapter 4 Trees
   4.1  Preliminaries  101
       4.1.1  Implementation of Trees 102
       4.1.2  Tree Traversals with an Application 103
   4.2  Binary Trees  107
      4.2.1  Implementation 108
      4.2.2  An Example: Expression Trees 109
   4.3  The Search Tree ADT Binary Search Trees  112
      4.3.1  contains 113
      4.3.2  findMin and findMax 115
      4.3.3  insert 115
      4.3.4  remove 117
      4.3.5  Average.Case Analysis 120
  4.4  AVL Trees  123
      4.4.1  Single Rotation 125
      4.4.2  Double Rotation 128
  4.5  Splay Trees  135
      4.5.1  A Simple Idea (That Does Not Work) 135
      4.5.2  Splaying 137
  4.6  Tree Traversals (Revisited)  143
  4.7  B.Trees  145
  4.8  Sets and Maps in the Standard Library  150
      4.8.1  Sets 151
      4.8.2  Maps 151
      4.8.3 Implementation of TreeSet and TreeMap 152
     ~ 4.8.4  An Example That Uses Several Maps 152
  4.9  Summary  157
      Exercises  159
      References  165
Chapter 5 Hashing
  5.1  General Idea  169
  5.2  Hash Function 170
  5.3  Separate Chaining  172
  5.4  Hash Tables Without Linked .Lists  177
     5.4.1  Linear Probing 177
     5.4.2  Quadratic Probing 179
     5.4.3  Double Hashing 181
 5.5  Rehashing  186
  5.6  Hash Tables in the Standard Library  187
  5.7  Extendible Hashing  190
      Summary  193
      Exercises  194
      References  198
Chapter 6 Priority Queues (Heaps)
  6.1  Model  201
  6.2  Simple Implementations  202
  6.3  Binary Heap  202
      6.3.1  Structure Property 203
      6.3.2  Heap Order Property 205
      6.3.3  Basic Heap Operations 205
      6.3.4 Other Heap Operations 210
  6.4 Applications of Priority Queues  214
      6.4.1  The Selection Problem 214
      6.4.2 Event Simulation 215
  6.5  d.Heaps  216
  6.6 Leftist Heaps  217
      6.6.1  Leftist Heap Property. 217
      6.6.2  Leftist Heap Operations 218
  6.7  Skew Heaps  225
  6.8  Binomial Queues  227
      6.8.1  Binomial Queue Structure 228
      6.8.2  Binomial Queue Operations 229
      6.8.3  Implementation of Binomial Queues 232
  6.9  Priority Queues in the Standard Library  237
      Summary  237
      Exercises  239
      References  243
Chapter 7 Sorting
  7.1  Preliminaries  247
  7.2  Insertion Sort  248
      7.2.1  The Algorithm 248
      7.2.2 Analysis of Insertion Sort 248
  7.3  A Lower Bound for Simple Sorting Algorithms  249
  7:.4  Shellsort  250
      7.4.1  Worst.Case Analysis of Shellsort 252
  7.5  Heapsort  254
      7.5.1  Analysis of Heapsort 256
  7.6  Mergesort  258
      7.6.1  Analysis of Mergesort 260
  7.7  Quicksort  264
      7.7.1  Picking the Pivot 264
      7.7.2 Partitioning Strategy 266
      7.7.3  Small Arrays 268
      7.7.4 Actual Quicksort Routines 268
      7.7.5 Analysis of Quicksort 27!
      7.7.6 A Linear.Expected.Time Algorithm for Selection 274
  7.8 A General Lower Bound for Sorting  276
      7.8.1  Decision Trees 276
  7.9  Bucket Sort  278
  7.10 External Sorting  279
      7.10.1 Why We Need New Algorithms 279
      7.10.2 Model for External Sorting 279
      7.10.3 The Simple Algorithm 279
      7.10.4 Multiway Merge 281
      7.10.5 Polyphase Merge 282
      7.10.6 Replacement Selection 283
      Summary  284
      Exercises  285
      References  290
Chapter 8 The Disjoint Set Class
  8.1  Equivalence Relations  293
  8.2  The Dynamic Equivalence Problem  294
  8.3  Basic Data Structure  295
  8.4  Smart Union Algorithms  299
  8.5  Path Compression  301
 8.6 Worst Case for Union.by.Rank and Path Compression  303.
     8.6.1 Analysis of the Union/Find Algorithm 304
 8.7 An Application  309
     Summary  312
     Exercises  312
     References   314
Chapter 9 Graph Algorithms
  9.1  Definitions  317
      9.1.1  Representation of Graphs 318
  9.2  Topological Sort  320
  9.3  Shortest.Path Algorithms  323
      9.3.1  Unweighted Shortest Paths 325
      9.3.2  Dijkstra~ Algorithm 329
      9.3.3  Graphs with Negative Edge Costs 338
      9.3.4  Acyclic Graphs 338
      9.3.5 All.Pairs Shortest Path 342
      9.3.6 Shortest.Path Example 342
  9.4  Network Flow Problems  344
      9.4.1  A Simple Maximum.Flow Algorithm 344
  9.5  Minimum Spanning Tree  349
      9.5.1  Prim's Algorithm 351
      9.5.2  Kruskal's Algorithm 353
  9.6 Applications of Depth.First Search  355
      9.6.1  Undirected Graphs 357
      9.6.2  Biconnectivity 358
      9.6.3  Euler Circuits 361
      9.6.4  Directed Graphs 366
      9.6.5  Finding Strong Components 367
  9.7  Introduction to NPoCompleteness  369
      9.7.1  Easyvs. Hard 369
      9.7.2  The Class NP 370
      9.7.3  NP.Complete Problems 371
      Summary  373
      Exercises  373
      References  381
Chapter 10 Algorithm Design Techniques
  10.1 Greedy Algorithms  385
      10.1.1 A Simple Scheduling Problem 386'
      10.1.2 Huffman Codes 389
      10.1.3 Approximate Bin Packing 395
  10.2 Divide and Conquer  403
      10.2.1 Running Time of Divide and Conquer Algorithms 404
      10.2.2 Closest.Points Problem 406
      10.2.3 The Selection Problem 411
      10.2.4 Theoretical Improvements for Arithmetic Problems 414
  10.3 Dynamic Programming  418
      10.3.1 Using a Table Instead of Recursion 418
      10.3.2 Ordering Matrix Multiplications 421
      10.3.3 Optimal Binary Search Tree 424
      10.3.4 All.Pairs Shortest Path 426
  10.4 Randomized Algorithms  429
      10.4.1 Random Number Generators 431
      10.4.2 Skip Lists 435
      10.4.3 Primality Testing 437
  10.5 Backtracking Algorithms  440
      10.5.1 The Turnpike Reconstruction Problem 440
      10.5.2 Games 445
      Summary  452
      Exercises  452
      References  461
Chapter 11 Amortized Analysis
  11.1 An Unrelated Puzzle  466
  11.2 Binomial Queues  466
  11.3 Skew Heaps  471
  11.4 Fibonacci Heaps  473
      11.4.1 Cutting Nodes in Leftist Heaps 474
      11.4.2 Lazy Merging for Binomial Queues 476
      11.4.3 The Fibonacci Heap Operations 480
      11.4.4 Proof of the Time Bound 480
  11.5 Splay Trees  483
      Summary  487
      Exercises  487
      References  489
Chapter 12 Advanced Data Structures
       and Implementation
  12.1 Top.Down Splay Trees  491
  12.2 Red.Black Trees  497
      12.2.1 Bottom.Up Insertion 499
      12.2.2 Top.Down Red.Black Trees 501
      12.2.3 Top.Down Deletion 506
  12.3 Deterministic Skip Lists  508
  12.4 AA.Trees  513
12.5 Treaps  521
12.6 k.d Trees  523
12.7 Pairing Heaps  527
    Summary  532
    Exercises  534
    References  538
Index 541
猜您喜欢

读书导航