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

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