数据结构与算法分析 C++描述 英文版PDF电子书下载

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 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 C++ Classes 11

1.4.1 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＜Comparabl e＞ 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/Find 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