本书是国外数据结构与算法分析方面的标准教材，使用最卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。

随着计算机速度的不断增加和功能的日益强大，人们对有效编程和算法分析的要求也在增长。本书把算法分析与最有效率的Java程序的开发有机地结合起来，深入分析每种算法，内容全面、缜密严格，并细致讲解精心构造程序的方法。

本书是国外数据结构与算法分析方面的标准教材，使用最卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。

随着计算机速度的不断增加和功能的日益强大，人们对有效编程和算法分析的要求也在增长。本书把算法分析与最有效率的Java程序的开发有机地结合起来，深入分析每种算法，内容全面、缜密严格，并细致讲解精心构造程序的方法。

第2版的特色如下：

全面阐述新的Java 5.O编程语言和Java Collections库。

改进内部设计，用图和实例阐述算法的实施步骤。

第3章对表、栈和队列的讨论进行了全面修订。

用一章专门讨论摊还分析和一些高级数据结构的实现。

每章末尾的大量练习按照难易程度编排，以增强对关键概念的理解。

  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