數(shù)據(jù)結(jié)構(gòu)與算法分析：C++描述（英文版 第3版）

Chapter 1　Introduction　1
1.1　What's the Book About?　1
1.2　Mathematics Review　2
1.2.1　Exponents　3
1.2.2　kogarithms　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　C++ Classes　11
1.4.i　Basic class Syntax　12
1.4.2　Extra Constructor Syntax and Accessors　12
1.4.3　Separation of Interface and Implementation　15
1.4.4　vector and string　17
1.5　C++ Details　19
1.5.1　Pointers　19
1.5.2　Parameter Passing　21
1.5.3　Return Passing　22
1.5.4　Reference Variables　23
1.5.5　The Big Three: Destructor, Copy Constructor, operator=　23
1.5.6　C-style Arrays and Strings　26
1.6　Templates　29
1.6.1　Function Templates　29
1.6.2　Class Templates　30
1.6.3　Object, Comparable, and an Example　32
1.6.4　Function Objects　34
1.6.5　Separate Compilation of Class Templates　35
1.7　Using Matrices　37
1.7.1　The Data Members, Constructor, and Basic Accessors　37
1.7.2　operator[]　37
1.7.3　Destructor, Copy Assignment, Copy Constructor　39
Summary　39
Exercises　39
References　41
Chapter 2　Algorithm Analysis　43
2.1　Mathematical Background　43
2.2　Model　46
2.3　What to Analyze　46
2.4　Running Time Calculations　49
2.4.1　A Simple Example　49
2.4.2　General Rules　50
2.4.3　Solutions for the Maximum Subsequence Sum Problem　52
2.4.4　Logarithms in the Running Time　58
2.4.5　Checking Your Analysis　62
2.4.6　A Grain of Salt　63
Summary　63
Exercises　64
References　69
Chapter 3　Lists, Stacks, and Queues　71
3.1　Abstract Data Types (ADTs)　71
3.2　The List ADT　72
3.2.1　Simple Array Implementation of Lists　72
3.2.2　Simple Linked Lists　73
3.3　vector and list in the STL　74
3.3.1　Iterators　75
3.3.2　Example: Using erase on a List　77
3.3.3　const iterators　77
3.4　Implementation of vector　79
3.5　Implementation of list　83
3.6　The Stack ADT　94
3.6.1　Stack Model　94
3.6.2　Implementation of Stacks　95
3.6.3　Applications　96
3.7　The Queue ADT　104
3.7.1　Queue Model　104
3.7.2　Array Implementation of Queues　104
3.7.3　Applications of Queues　106
Summary　107
Exercises　108
Chapter 4　Trees　113
4.1　Preliminaries　113
4.1.1　Implementation of Trees　114
4.1.2　Tree Traversals with an Application　115
4.2　Binary Trees　119
4.2.1　Implementation　120
4.2.2　An Example: Expression Trees　121
4.3　The Search Tree ADT　Binary Search Trees　124
4.3.1　contains　125
4.3.2　findMin and findMax　125
4.3.3　insert　129
4.3.4　remove　130
4.3.5　Destructor and Copy Assignment Operator　132
4.3.6　Average-Case Analysis　133
4.4　AVL Trees　136
4.4.1　Single Rotation　139
4.4.2　Double Rotation　142
4.5　Splay Trees　149
4.5.1　A Simple Idea (That Does Not Work)　150
4.5.2　Splaying　152
4.6　Tree Traversals (Revisited)　158
4.7　B-Trees　159
4.8　Sets and Maps in the Standard Library　165
4.8.1　Sets　165
4.8.2　Maps　166
4.8.3　Implementation of set and map　167
4.8.4　An Example That Uses Several Maps　168
Summary　174
Exercises　174
References　181
Chapter 5　Hashing　185
5.1　General Idea　185
5.2　Hash Function　186
5.3　Separate Chaining　188
5.4　Hash Tables Without Linked Lists　192
5.4.1　Linear Probing　193
5.4.2　Quadratic Probing　195
5.4.3　Double Hashing　199
5.5　Rehashing　200
5.6　Hash Tables in the Standard Library　204
5.7　Extendible Hashing　204
Summary　207
Exercises　208
References　211
Chapter 6　Priority Queues (Heaps)　213
6.1　Model　213
6.2　Simple Implementations　214
6.3　Binary Heap　215
6.3.1　Structure Property　215
6.3.2　Heap-Order Property　216
6.3.3　Basic Heap Operations　217
6.3.4　Other Heap Operations　220
6.4　Applications of Priority Queues　225
6.4.1　The Selection Problem　226
6.4.2　Event Simulation　227
6.5　d-Heaps　228
6.6　Leftist Heaps　229
6.6.1　Leftist Heap Property　229
6.6.2　Leftist Heap Operations　230
6.7　Skew Heaps　235
6.8　Binomial Queues　239
6.8.1　Binomial Queue Structure　240
6.8.2　Binomial Queue Operations　241
6.8.3　Implementation of Binomial Queues　244
6.9　Priority Queues in the Standard Library　251
Summary　251
Exercises　251
References　257
Chapter 7　Sorting　261
7.1　Preliminaries　261
7.2　Insertion Sort　262
7.2.1　The Algorithm　262
7.2.2　STL Implementation of Insertion Sort　263
7.2.3　Analysis of Insertion Sort　264
7.3　A Lower Bound for Simple Sorting Algorithms　265
7.4　Shellsort　266
7.4.1　Worst-Case Analysis of Shellsort　268
7.5　Heapsort　270
7.5.1　Analysis of Heapsort　272
7.6　Mergesort　274
7.6.1　Analysis of Mergesort　276
7.7　Quicksort　279
7.7.1　Picking the Pivot　280
7.7.2　Partitioning Strategy　282
7.7.3　Small Arrays　284
7.7.4　Actual Quicksort Routines　284
7.7.5　Analysis of Quicksort　287
7.7.6　A Linear-Expected-Time Algorithm for Selection　290
7.8　Indirect Sorting　292
7.8.1　vector＜Comparable*＞ Does Not Work　295
7 8.2　Smart Pointer Class　295
7 8.3　Overloading operator＜　295
7 8.4　Dereferencing a Pointer with *　295
7 8.5　Overloading the Type Conversion Operator　295
7 8.6　Implicit Type Conversions Are Everywhere　296
7 8.7　Dual-Direction Implicit Conversions Can Cause Ambiguities　296
7 8.8　Pointer Subtraction Is Legal　297
7.9　A General Lower Bound for Sorting　297
7.9.1　Decision Trees　297
7.10　Bucket Sort　299
7.11　External Sorting　300
7 11.1　Why We Need New Algorithms　300
7 11.2　Model for External Sorting　300
7 11.3　The Simple Algorithm　301
7 11.4　Multiway Merge　302
7 11.5　Polyphase Merge　303
7 11.6　Replacement Selection　304
Summary　305
Exercises　306
References　311
Chapter 8　The Disjoint Set Class　315
8.1　Equivalence Relations　315
8.2　The Dynamic Equivalence Problem　316
8.3　Basic Data Structure　317
8.4　Smart Union Algorithms　321
8.5　Path Compression　324
8.6　Worst Case for Union-by-Rank and Path Compression　325
8.6.1　Analysis of the Union~ind Algorithm　326
8.7　An Application　331
Summary　334
Exercises　335
References　336
Chapter 9　Graph Algorithms　339
9.1　Definitions　339
9.1.1　Representation of Graphs　340
9.2　Topological Sort　342
9.3　Shortest-Path Algorithms　345
9.3.1　Unweighted Shortest Paths　347
9.3.2　Dijkstra's Algorithm　351
9.3.3　Graphs with Negative Edge Costs　360
9.3.4　Acyclic Graphs　360
9.3.5　All-Pairs Shortest Path　364
9.3.6　Shortest Path Example　365
9.4　Network Flow Problems　367
9.4.1　A Simple Maximum-Flow Algorithm　367
9.5　Minimum Spanning Tree　372
9.5.1　Prim's Algorithm　373
9.5.2　Kruskal's Algorithm　376
9.6　Applications of Depth-First Search　378
9.6.1　Undirected Graphs　379
9.6.2　Biconnectivity　381
9.6.3　Euler Circuits　385
9.6.4　Directed Graphs　388
9.6.5　Finding Strong Components　390
9.7　Introduction to NP-Completeness　392
9.7.1　Easy vs. Hard　392
9.7.2　The Class NP　393
9.7.3　NP-Complete Problems　394
Summary　396
Exercises　396
References　404
Chapter 10　Algorithm Design Techniques　409
10.1　Greedy Algorithms　409
10.1.1　A Simple Scheduling Problem　410
10.1.2　Huffman Codes　413
10.1.3　Approximate Bin Packing　419
10.2　Divide and Conquer　427
10.2.1　Running Time of Divide and Conquer Algorithms　428
10.2.2　Closest-Points Problem　430
10.2.3　The Selection Problem　435
10.2.4　Theoretical Improvements for Arithmetic Problems　438
10.3　Dynamic Programming　442
10.3.1　Using a Table Instead of Recursion　442
10.3.2　Ordering Matrix Multiplications　444
10.3.3　Optimal Binary Search Tree　447
10.3.4 All-Pairs Shortest Path　451
10.4　Randomized Algorithms　454
10.4.1　Random Number Generators　455
10.4.2 Skip Lists　459
10.4.3　Primality Testing　461
10.5　Backtracking Algorithms　464
10.5.1　The Turnpike Reconstruction Problem　465
10.5.2　Games　469
Summary　475
Exercises　475
References　485
Chapter 11　Amortized Analysis　491
11.1　An Unrelated Puzzle　492
11.2　Binomial Queues　492
11.3　Skew Heaps　497
11.4　Fibonacci Heaps　499
11.4.1　Cutting Nodes in Leftist Heaps　500
11.4.2　Lazy Merging for Binomial Queues　502
11.4.3　The Fibonacci Heap Operations　506
11.4.4　Proof of the Time Bound　506
11.5　Splay Trees　509
Summary　513
Exercises　513
References　515
Chapter 12　Advanced Data Structures and Implementation　517
12.1　Top-Down Splay Trees　517
12.2　Red-Black Trees　525
12.2.1　Bottom-Up Insertion　526
12.2.2　Top-Down Red-Black Trees　527
12.2.3　Top-Down Deletion　531
12.3　Deterministic Skip Lists　535
12.4　AA-Trees　540
12.5　Treaps　547
12.6　k-d Trees　549
12.7　Pairing Heaps　553
Summary　558
Exercises　558
References　563
Appendix A　Separate Compilation of Class Templates　567
A.1　Everything in the Header　568
A.2　Explicit Instantiation　568
A.3　The export Directive　570
Index　571