数据结构与算法分析：Java语言描述（英文版）（第2版）
Preface vii
Chapter 1 Introdudion
1.1 Whats 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 Prims Algorithm 351
9.5.2 Kruskals 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
Chapter 1 Introdudion
1.1 Whats 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 Prims Algorithm 351
9.5.2 Kruskals 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
MarkAllen Weiss拥有普林斯顿大学计算机科学博士学位，现在是佛罗里达国际大学计算机学院教授。他是著名的计算机教育专家，在数据结构与算法分析方面卓有建树，著有多部畅销书籍：《Data Structures and Problem Solving：LJsirlg、Java》、《Data Structures and Problem Solving：Using C++》、《数据结构与算法分析——C语言描述》等。他目前是AP（AdvancedPlacement）计算机学科委员会成员。
本书是国外数据结构与算法分析方面的标准教材，使用最卓越的Java编程语言作为实现工具讨论了数据结构（组织大量数据的方法）和算法分析（对算法运行时间的估计）。
随着计算机速度的不断增加和功能的日益强大，人们对有效编程和算法分析的要求也在增长。本书把算法分析与最有效率的Java程序的开发有机地结合起来，深入分析每种算法，内容全面、缜密严格，并细致讲解精心构造程序的方法。
第2版的特色如下：
全面阐述新的Java 5.O编程语言和Java Collections库。
改进内部设计，用图和实例阐述算法的实施步骤。
第3章对表、栈和队列的讨论进行了全面修订。
用一章专门讨论摊还分析和一些高级数据结构的实现。
每章末尾的大量练习按照难易程度编排，以增强对关键概念的理解。
随着计算机速度的不断增加和功能的日益强大，人们对有效编程和算法分析的要求也在增长。本书把算法分析与最有效率的Java程序的开发有机地结合起来，深入分析每种算法，内容全面、缜密严格，并细致讲解精心构造程序的方法。
第2版的特色如下：
全面阐述新的Java 5.O编程语言和Java Collections库。
改进内部设计，用图和实例阐述算法的实施步骤。
第3章对表、栈和队列的讨论进行了全面修订。
用一章专门讨论摊还分析和一些高级数据结构的实现。
每章末尾的大量练习按照难易程度编排，以增强对关键概念的理解。
比价列表
公众号、微信群
缺书网微信公众号
扫码进群实时获取购书优惠