数据结构与算法分析 C++描述 英文版【2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载】

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

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

Chapter 1 Introduction1

1.1 What’s the Book About?1

1.2 Mathematics Review2

1.2.1 Exponents3

1.2.2 Logarithms3

1.2.3 Series4

1.2.4 Modular Arithmetic5

1.2.5 The P Word6

1.3 A Brief Introduction to Recursion7

1.4 C++ Classes11

1.4.1 Basic class Syntax12

1.4.2 Extra Constructor Syntax and Accessors12

1.4.3 Separation of Interface and Implementation15

1.4.4 vector and string17

1.5 C++ Details19

1.5.1 Pointers19

1.5.2 Parameter Passing21

1.5.3 Return Passing22

1.5.4 Reference Variables23

1.5.5 The Big Three: Destructor, Copy Constructor, operator=23

1.5.6 C-style Arrays and Strings26

1.6 Templates29

1.6.1 Function Templates29

1.6.2 Class Templates30

1.6.3 Object, Comparable, and an Example32

1.6.4 Function Objects34

1.6.5 Separate Compilation of Class Templates35

1.7 Using Matrices37

1.7.1 The Data Members, Constructor, and Basic Accessors37

1.7.2 operator[]37

1.7.3 Destructor, Copy Assignment, Copy Constructor39

Summary39

Exercises39

References41

Chapter 2 Algorithm Analysis43

2.1 Mathematical Background43

2.2 Model46

2.3 What to Analyze46

2.4 Running Time Calculations49

2.4.1 A Simple Example49

2.4.2 General Rules50

2.4.3 Solutions for the Maximum Subsequence Sum Problem52

2.4.4 Logarithms in the Running Time58

2.4.5 Checking Your Analysis62

2.4.6 A Grain of Salt63

Summary63

Exercises64

References69

Chapter 3 Lists, Stacks, and Queues71

3.1 Abstract Data Types （ADTs）71

3.2 The List ADT72

3.2.1 Simple Array Implementation of Lists72

3.2.2 Simple Linked Lists73

3.3 vector and list in the STL74

3.3.1 Iterators75

3.3.2 Example: Using erase on a List77

3.3.3 const iterators77

3.4 Implementation of vector79

3.5 Implementation of list83

3.6 The Stack ADT94

3.6.1 Stack Model94

3.6.2 Implementation of Stacks95

3.6.3 Applications96

3.7 The Queue ADT104

3.7.1 Queue Model104

3.7.2 Array Implementation of Queues104

3.7.3 Applications of Queues106

Summary107

Exercises108

Chapter 4 Trees113

4.1 Preliminaries113

4.1.1 Implementation of Trees114

4.1.2 Tree Traversals with an Application115

4.2 Binary Trees119

4.2.1 Implementation120

4.2.2 An Example: Expression Trees121

4.3 The Search Tree ADT—Binary Search Trees124

4.3.1 contains125

4.3.2 findMin and findMax125

4.3.3 insert129

4.3.4 remove130

4.3.5 Destructor and Copy Assignment Operator132

4.3.6 Average-Case Analysis133

4.4 AVL Trees136

4.4.1 Single Rotation139

4.4.2 Double Rotation142

4.5 Splay Trees149

4.5.1 A Simple Idea （That Does Not Work）150

4.5.2 Splaying152

4.6 Tree Traversals （Revisited）158

4.7 B-Trees159

4.8 Sets and Maps in the Standard Library165

4.8.1 Sets165

4.8.2 Maps166

4.8.3 Implementation of set and map167

4.8.4 An Example That Uses Several Maps168

Summary174

Exercises174

References181

Chapter 5 Hashing185

5.1 General Idea185

5.2 Hash Function186

5.3 Separate Chaining188

5.4 Hash Tables Without Linked Lists192

5.4.1 Linear Probing193

5.4.2 Quadratic Probing195

5.4.3 Double Hashing199

5.5 Rehashing200

5.6 Hash Tables in the Standard Library204

5.7 Extendible Hashing204

Summary207

Exercises208

References211

Chapter 6 Priority Queues （Heaps）213

6.1 Model213

6.2 Simple Implementations214

6.3 Binary Heap215

6.3.1 Structure Property215

6.3.2 Heap-Order Property216

6.3.3 Basic Heap Operations217

6.3.4 Other Heap Operations220

6.4 Applications of Priority Queues225

6.4.1 The Selection Problem226

6.4.2 Event Simulation227

6.5 d-Heaps228

6.6 Leftist Heaps229

6.6.1 Leftist Heap Property229

6.6.2 Leftist Heap Operations230

6.7 Skew Heaps235

6.8 Binomial Queues239

6.8.1 Binomial Queue Structure240

6.8.2 Binomial Queue Operations241

6.8.3 Implementation of Binomial Queues244

6.9 Priority Queues in the Standard Library251

Summary251

Exercises251

References257

Chapter 7 Sorting261

7.1 Preliminaries261

7.2 Insertion Sort262

7.2.1 The Algorithm262

7.2.2 STL Implementation of Insertion Sort263

7.2.3 Analysis of Insertion Sort264

7.3 A Lower Bound for Simple Sorting Algorithms265

7.4 Shellsort266

7.4.1 Worst-Case Analysis of Shellsort268

7.5 Heapsort270

7.5.1 Analysis of Heapsort272

7.6 Mergesort274

7.6.1 Analysis of Mergesort276

7.7 Quicksort279

7.7.1 Picking the Pivot280

7.7.2 Partitioning Strategy282

7.7.3 Small Arrays284

7.7.4 Actual Quicksort Routines284

7.7.5 Analysis of Quicksort287

7.7.6 A Linear-Expected-Time Algorithm for Selection290

7.8 Indirect Sorting292

7.8.1 vector＜Comparabl e＞ Does Not Work295

7.8.2 Smart Pointer Class295

7.8.3 Overloading operator＜295

7.8.4 Dereferencing a Pointer with295

7.8.5 Overloading the Type Conversion Operator295

7.8.6 Implicit Type Conversions Are Everywhere296

7.8.7 Dual-Direction Implicit Conversions Can Cause Ambiguities296

7.8.8 Pointer Subtraction Is Legal297

7.9 A General Lower Bound for Sorting297

7.9.1 Decision Trees297

7.10 Bucket Sort299

7.11 External Sorting300

7.11.1 Why We Need New Algorithms300

7.11.2 Model for External Sorting300

7.11.3 The Simple Algorithm301

7.11.4 Multiway Merge302

7.11.5 Polyphase Merge303

7.11.6 Replacement Selection304

Summary305

Exercises306

References311

Chapter 8 The Disjoint Set Class315

8.1 Equivalence Relations315

8.2 The Dynamic Equivalence Problem316

8.3 Basic Data Structure317

8.4 Smart Union Algorithms321

8.5 Path Compression324

8.6 Worst Case for Union-by-Rank and Path Compression325

8.6.1 Analysis of the Union/Find Algorithm326

8.7 An Application331

Summary334

Exercises335

References336

Chapter 9 Graph Algorithms339

9.1 Definitions339

9.1.1 Representation of Graphs340

9.2 Topological Sort342

9.3 Shortest-Path Algorithms345

9.3.1 Unweighted Shortest Paths347

9.3.2 Dijkstra’s Algorithm351

9.3.3 Graphs with Negative Edge Costs360

9.3.4 Acyclic Graphs360

9.3.5 All-Pairs Shortest Path364

9.3.6 Shortest Path Example365

9.4 Network Flow Problems367

9.4.1 A Simple Maximum-Flow Algorithm367

9.5 Minimum Spanning Tree372

9.5.1 Prim’s Algorithm373

9.5.2 Kruskal’s Algorithm376

9.6 Applications of Depth-First Search378

9.6.1 Undirected Graphs379

9.6.2 Biconnectivity381

9.6.3 Euler Circuits385

9.6.4 Directed Graphs388

9.6.5 Finding Strong Components390

9.7 Introduction to NP-Completeness392

9.7.1 Easy vs.Hard392

9.7.2 The Class NP393

9.7.3 NP-Complete Problems394

Summary396

Exercises396

References404

Chapter 10 Algorithm Design Techniques409

10.1 Greedy Algorithms409

10.1.1 A Simple Scheduling Problem410

10.1.2 Huffman Codes413

10.1.3 Approximate Bin Packing419

10.2 Divide and Conquer427

10.2.1 Running Time of Divide and Conquer Algorithms428

10.2.2 Closest-Points Problem430

10.2.3 The Selection Problem435

10.2.4 Theoretical Improvements for Arithmetic Problems438

10.3 Dynamic Programming442

10.3.1 Using a Table Instead of Recursion442

10.3.2 Ordering Matrix Multiplications444

10.3.3 Optimal Binary Search Tree447

10.3.4 All-Pairs Shortest Path451

10.4 Randomized Algorithms454

10.4.1 Random Number Generators455

10.4.2 Skip Lists459

10.4.3 Primality Testing461

10.5 Backtracking Algorithms464

10.5.1 The Turnpike Reconstruction Problem465

10.5.2 Games469

Summary475

Exercises475

References485

Chapter 11 Amortized Analysis491

11.1 An Unrelated Puzzle492

11.2 Binomial Queues492

11.3 Skew Heaps497

11.4 Fibonacci Heaps499

11.4.1 Cutting Nodes in Leftist Heaps500

11.4.2 Lazy Merging for Binomial Queues502

11.4.3 The Fibonacci Heap Operations506

11.4.4 Proof of the Time Bound506

11.5 Splay Trees509

Summary513

Exercises513

References515

Chapter 12 Advanced Data Structures and Implementation517

12.1 Top-Down Splay Trees517

12.2 Red-Black Trees525

12.2.1 Bottom-Up Insertion526

12.2.2 Top-Down Red-Black Trees527

12.2.3 Top-Down Deletion531

12.3 Deterministic Skip Lists535

12.4 AA-Trees540

12.5 Treaps547

12.6 k-d Trees549

12.7 Pairing Heaps553

Summary558

Exercises558

References563

Appendix A Separate Compilation of Class Templates567

A.1 Everything in the Header568

A.2 Explicit Instantiation568

A.3 The export Directive570

Index571