数据结构与算法分析 C++版 第3版 英文版

Ⅰ Preliminaries 1

1 Data Structures and Algorithms 3

1.1 A Philosophy of Data Structures 4

1.1.1 The Need for Data Structures 4

1.1.2 Costs and Benefits 6

1.2 Abstract Data Types and Data Structures 8

1.3 Design Patterns 12

1.3.1 Flyweight 13

1.3.2 Visitor 13

1.3.3 Composite 14

1.3.4 Strategy 15

1.4 Problems，Algorithms，and Programs 16

1.5 Further Reading 18

1.6 Exercises 20

2 Mathematical Preliminaries 25

2.1 Sets and Relations 25

2.2 Miscellaneous Notation 29

2.3 Logarithms 31

2.4 Summations and Recurrences 32

2.5 Recursion 36

2.6 Mathematical Proof Techniques 38

2.6.1 Direct Proof 39

2.6.2 Proof by Contradiction 39

2.6.3 Proof by Mathematical Induction 40

2.7 Estimation 46

2.8 Further Reading 47

2.9 Exercises 48

3 Algorithm Analysis 55

3.1 Introduction 55

3.2 Best，Worst，and Average Cases 61

3.3 A Faster Computer，or a Faster Algorithm？ 62

3.4 Asymptotic Analysis 65

3.4.1 Upper Bounds 65

3.4.2 Lower Bounds 67

3.4.3 ？Notation 68

3.4.4 Simplifying Rules 69

3.4.5 Classifying Functions 70

3.5 Calculating the Running Time for a Program 71

3.6 Analyzing Problems 76

3.7 Common Misunderstandings 77

3.8 Multiple Parameters 79

3.9 Space Bounds 80

3.10 Speeding Up Your Programs 82

3.11 Empirical Analysis 85

3.12 Further Reading 86

3.13 Exercises 86

3.14 Projects 90

Ⅱ Fundamental Data Structures 93

4 Lists，Stacks，and Queues 95

4.1 Lists 96

4.1.1 Array-Based List Implementation 100

4.1.2 Linked Lists 103

4.1.3 Comparison of List Implementations 112

4.1.4 Element Implementations 114

4.1.5 Doubly Linked Lists 115

4.2 Stacks 120

4.2.1 Array-Based Stacks 121

4.2.2 Linked Stacks 124

4.2.3 Comparison of Array-Based and Linked Stacks 125

4.2.4 Implementing Recursion 125

4.3 Queues 129

4.3.1 Array-Based Queues 129

4.3.2 Linked Queues 134

4.3.3 Comparison of Array-Based and Linked Queues 134

4.4 Dictionaries 134

4.5 Further Reading 145

4.6 Exercises 145

4.7 Projects 149

5 Binary Trees 151

5.1 Definitions and Properties 151

5.1.1 The Full Binary Tree Theorem 153

5.1.2 A Binary Tree Node ADT 155

5.2 Binary Tree Traversals 155

5.3 Binary Tree Node Implementations 160

5.3.1 Pointer-Based Node Implementations 160

5.3.2 Space Requirements 166

5.3.3 Array Implementation for Complete Binary Trees 168

5.4 Binary Search Trees 168

5.5 Heaps and Priority Queues 178

5.6 Huffman Coding Trees 185

5.6.1 Building Huffman Coding Trees 186

5.6.2 Assigning and Using Huffman Codes 192

5.6.3 Search in Huffman Trees 195

5.7 Further Reading 196

5.8 Exercises 196

5.9 Projects 200

6 Non-Binary Trees 203

6.1 General Tree Definitions and Terminology 203

6.1.1 An ADT for General Tree Nodes 204

6.1.2 General Tree Traversals 205

6.2 The Parent Pointer Implementation 207

6.3 General Tree Implementations 213

6.3.1 List of Children 214

6.3.2 The Left-Child/Right-Sibling Implementation 215

6.3.3 Dynamic Node Implementations 215

6.3.4 Dynamic “Left-Child/Right-Sibling” Implementation 218

6.4 K-ary Trees 218

6.5 Sequential Tree Implementations 219

6.6 Further Reading 223

6.7 Exercises 223

6.8 Projects 226

Ⅲ Sorting and Searching 229

7 Internal Sorting 231

7.1 Sorting Terminology and Notation 232

7.2 Three？（n2）Sorting Algorithms 233

7.2.1 Insertion Sort 233

7.2.2 Bubble Sort 235

7.2.3 Selection Sort 237

7.2.4 The Cost of Exchange Sorting 238

7.3 Shellsort 239

7.4 Mergesort 241

7.5 Quicksort 244

7.6 Heapsort 251

7.7 Binsort and Radix Sort 252

7.8 An Empirical Comparison of Sorting Algorithms 259

7.9 Lower Bounds for Sorting 261

7.10 Further Reading 265

7.11 Exercises 265

7.12 Projects 269

8 File Processing and External Sorting 273

8.1 Primary versus Secondary Storage 273

8.2 Disk Drives 276

8.2.1 Disk Drive Architecture 276

8.2.2 Disk Access Costs 280

8.3 Buffers and Buffer Pools 282

8.4 The Programmer’s View of Files 290

8.5 External Sorting 291

8.5.1 Simple Approaches to External Sorting 294

8.5.2 Replacement Selection 296

8.5.3 Multiway Merging 300

8.6 Further Reading 303

8.7 Exercises 304

8.8 Projects 307

9 Searching 311

9.1 Searching Unsorted and Sorted Arrays 312

9.2 Self-Organizing Lists 317

9.3 Bit Vectors for Representing Sets 323

9.4 Hashing 324

9.4.1 Hash Functions 325

9.4.2 Open Hashing 330

9.4.3 Closed Hashing 331

9.4.4 Analysis of Closed Hashing 339

9.4.5 Deletion 344

9.5 Further Reading 345

9.6 Exercises 345

9.7 Projects 348

10 Indexing 351

10.1 Linear Indexing 353

10.2 ISAM 356

10.3 Tree-based Indexing 358

10.4 2-3 Trees 360

10.5 B-Trees 364

10.5.1 B＋-Trees 368

10.5.2 B-Tree Analysis 374

10.6 Further Reading 375

10.7 Exercises 375

10.8 Projects 377

Ⅳ Advanced Data Structures 379

11 Graphs 381

11.1 Terminology and Representations 382

11.2 Graph Implementations 386

11.3 Graph Traversals 390

11.3.1 Depth-First Search 393

11.3.2 Breadth-First Search 394

11.3.3 Topological Sort 394

11.4 Shortest-Paths Problems 399

11.4.1 Single-Source Shortest Paths 400

11.5 Minimum-Cost Spanning Trees 402

11.5.1 Prim’s Algorithm 404

11.5.2 Kruskal’s Algorithm 407

11.6 Further Reading 409

11.7 Exercises 409

11.8 Projects 411

12 Lists and Arrays Revisited 413

12.1 Multilists 413

12.2 Matrix Representations 416

12.3 Memory Management 420

12.3.1 Dynamic Storage Allocation 422

12.3.2 Failure Policies and Garbage Collection 429

12.4 Further Reading 433

12.5 Exercises 434

12.6 Projects 435

13 Advanced Tree Structures 437

13.1 Tries 437

13.2 Balanced Trees 442

13.2.1 The AVL Tree 443

13.2.2 The Splay Tree 445

13.3 Spatial Data Structures 448

13.3.1 The K-D Tree 450

13.3.2 The PR quadtree 455

13.3.3 Other Point Data Structures 459

13.3.4 Other Spatial Data Structures 461

13.4 Further Reading 461

13.5 Exercises 462

13.6 Projects 463

Ⅴ Theory of Algorithms 467

14 Analysis Techniques 469

14.1 Summation Techniques 470

14.2 Recurrence Relations 475

14.2.1 Estimating Upper and Lower Bounds 475

14.2.2 Expanding Recurrences 478

14.2.3 Divide and Conquer Recurrences 480

14.2.4 Average-Case Analysis of Quicksort 482

14.3 Amortized Analysis 484

14.4 Further Reading 487

14.5 Exercises 487

14.6 Projects 491

15 Lower Bounds 493

15.1 Introduction to Lower Bounds Proofs 494

15.2 Lower Bounds on Searching Lists 496

15.2.1 Searching in Unsorted Lists 496

15.2.2 Searching in Sorted Lists 498

15.3 Finding the Maximum Value 499

15.4 Adversarial Lower Bounds Proofs 501

15.5 State Space Lower Bounds Proofs 504

15.6 Finding the ith Best Element 507

15.7 Optimal Sorting 509

15.8 Further Reading 512

15.9 Exercises 512

15.10 Projects 515

16 Patterns of Algorithms 517

16.1 Dynamic Programming 517

16.1.1 The Knapsack Problem 519

16.1.2 All-Pairs Shortest Paths 521

16.2 Randomized Algorithms 523

16.2.1 Randomized algorithms for finding large values 523

16.2.2 Skip Lists 524

16.3 Numerical Algorithms 530

16.3.1 Exponentiation 531

16.3.2 Largest Common Factor 531

16.3.3 Matrix Multiplication 532

16.3.4 Random Numbers 534

16.3.5 The Fast Fourier Transform 535

16.4 Further Reading 540

16.5 Exercises 540

16.6 Projects 541

17 Limits to Computation 543

17.1 Reductions 544

17.2 Hard Problems 549

17.2.1 The Theory of NP-Completeness 551

17.2.2 NP-Completeness Proofs 555

17.2.3 Coping with NP-Complete Problems 560

17.3 Impossible Problems 563

17.3.1 Uncountability 564

17.3.2 The Halting Problem Is Unsolvable 567

17.4 Further Reading 569

17.5 Exercises 570

17.6 Projects 572

Ⅵ APPENDIX 575

A Utility Functions 577

Bibliography 579

Index 585