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

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

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

Ⅰ Preliminaries1

1 Data Structures and Algorithms3

1.1 A Philosophy of Data Structures4

1.1.1 The Need for Data Structures4

1.1.2 Costs and Benefits6

1.2 Abstract Data Types and Data Structures8

1.3 Design Patterns12

1.3.1 Flyweight13

1.3.2 Visitor13

1.3.3 Composite14

1.3.4 Strategy15

1.4 Problems，Algorithms，and Programs16

1.5 Further Reading18

1.6 Exercises20

2 Mathematical Preliminaries25

2.1 Sets and Relations25

2.2 Miscellaneous Notation29

2.3 Logarithms31

2.4 Summations and Recurrences32

2.5 Recursion36

2.6 Mathematical Proof Techniques38

2.6.1 Direct Proof39

2.6.2 Proof by Contradiction39

2.6.3 Proof by Mathematical Induction40

2.7 Estimation46

2.8 Further Reading47

2.9 Exercises48

3 Algorithm Analysis55

3.1 Introduction55

3.2 Best，Worst，and Average Cases61

3.3 A Faster Computer，or a Faster Algorithm？62

3.4 Asymptotic Analysis65

3.4.1 Upper Bounds65

3.4.2 Lower Bounds67

3.4.3 ？Notation68

3.4.4 Simplifying Rules69

3.4.5 Classifying Functions70

3.5 Calculating the Running Time for a Program71

3.6 Analyzing Problems76

3.7 Common Misunderstandings77

3.8 Multiple Parameters79

3.9 Space Bounds80

3.10 Speeding Up Your Programs82

3.11 Empirical Analysis85

3.12 Further Reading86

3.13 Exercises86

3.14 Projects90

Ⅱ Fundamental Data Structures93

4 Lists，Stacks，and Queues95

4.1 Lists96

4.1.1 Array-Based List Implementation100

4.1.2 Linked Lists103

4.1.3 Comparison of List Implementations112

4.1.4 Element Implementations114

4.1.5 Doubly Linked Lists115

4.2 Stacks120

4.2.1 Array-Based Stacks121

4.2.2 Linked Stacks124

4.2.3 Comparison of Array-Based and Linked Stacks125

4.2.4 Implementing Recursion125

4.3 Queues129

4.3.1 Array-Based Queues129

4.3.2 Linked Queues134

4.3.3 Comparison of Array-Based and Linked Queues134

4.4 Dictionaries134

4.5 Further Reading145

4.6 Exercises145

4.7 Projects149

5 Binary Trees151

5.1 Definitions and Properties151

5.1.1 The Full Binary Tree Theorem153

5.1.2 A Binary Tree Node ADT155

5.2 Binary Tree Traversals155

5.3 Binary Tree Node Implementations160

5.3.1 Pointer-Based Node Implementations160

5.3.2 Space Requirements166

5.3.3 Array Implementation for Complete Binary Trees168

5.4 Binary Search Trees168

5.5 Heaps and Priority Queues178

5.6 Huffman Coding Trees185

5.6.1 Building Huffman Coding Trees186

5.6.2 Assigning and Using Huffman Codes192

5.6.3 Search in Huffman Trees195

5.7 Further Reading196

5.8 Exercises196

5.9 Projects200

6 Non-Binary Trees203

6.1 General Tree Definitions and Terminology203

6.1.1 An ADT for General Tree Nodes204

6.1.2 General Tree Traversals205

6.2 The Parent Pointer Implementation207

6.3 General Tree Implementations213

6.3.1 List of Children214

6.3.2 The Left-Child/Right-Sibling Implementation215

6.3.3 Dynamic Node Implementations215

6.3.4 Dynamic “Left-Child/Right-Sibling” Implementation218

6.4 K-ary Trees218

6.5 Sequential Tree Implementations219

6.6 Further Reading223

6.7 Exercises223

6.8 Projects226

Ⅲ Sorting and Searching229

7 Internal Sorting231

7.1 Sorting Terminology and Notation232

7.2 Three？（n2）Sorting Algorithms233

7.2.1 Insertion Sort233

7.2.2 Bubble Sort235

7.2.3 Selection Sort237

7.2.4 The Cost of Exchange Sorting238

7.3 Shellsort239

7.4 Mergesort241

7.5 Quicksort244

7.6 Heapsort251

7.7 Binsort and Radix Sort252

7.8 An Empirical Comparison of Sorting Algorithms259

7.9 Lower Bounds for Sorting261

7.10 Further Reading265

7.11 Exercises265

7.12 Projects269

8 File Processing and External Sorting273

8.1 Primary versus Secondary Storage273

8.2 Disk Drives276

8.2.1 Disk Drive Architecture276

8.2.2 Disk Access Costs280

8.3 Buffers and Buffer Pools282

8.4 The Programmer’s View of Files290

8.5 External Sorting291

8.5.1 Simple Approaches to External Sorting294

8.5.2 Replacement Selection296

8.5.3 Multiway Merging300

8.6 Further Reading303

8.7 Exercises304

8.8 Projects307

9 Searching311

9.1 Searching Unsorted and Sorted Arrays312

9.2 Self-Organizing Lists317

9.3 Bit Vectors for Representing Sets323

9.4 Hashing324

9.4.1 Hash Functions325

9.4.2 Open Hashing330

9.4.3 Closed Hashing331

9.4.4 Analysis of Closed Hashing339

9.4.5 Deletion344

9.5 Further Reading345

9.6 Exercises345

9.7 Projects348

10 Indexing351

10.1 Linear Indexing353

10.2 ISAM356

10.3 Tree-based Indexing358

10.4 2-3 Trees360

10.5 B-Trees364

10.5.1 B＋-Trees368

10.5.2 B-Tree Analysis374

10.6 Further Reading375

10.7 Exercises375

10.8 Projects377

Ⅳ Advanced Data Structures379

11 Graphs381

11.1 Terminology and Representations382

11.2 Graph Implementations386

11.3 Graph Traversals390

11.3.1 Depth-First Search393

11.3.2 Breadth-First Search394

11.3.3 Topological Sort394

11.4 Shortest-Paths Problems399

11.4.1 Single-Source Shortest Paths400

11.5 Minimum-Cost Spanning Trees402

11.5.1 Prim’s Algorithm404

11.5.2 Kruskal’s Algorithm407

11.6 Further Reading409

11.7 Exercises409

11.8 Projects411

12 Lists and Arrays Revisited413

12.1 Multilists413

12.2 Matrix Representations416

12.3 Memory Management420

12.3.1 Dynamic Storage Allocation422

12.3.2 Failure Policies and Garbage Collection429

12.4 Further Reading433

12.5 Exercises434

12.6 Projects435

13 Advanced Tree Structures437

13.1 Tries437

13.2 Balanced Trees442

13.2.1 The AVL Tree443

13.2.2 The Splay Tree445

13.3 Spatial Data Structures448

13.3.1 The K-D Tree450

13.3.2 The PR quadtree455

13.3.3 Other Point Data Structures459

13.3.4 Other Spatial Data Structures461

13.4 Further Reading461

13.5 Exercises462

13.6 Projects463

Ⅴ Theory of Algorithms467

14 Analysis Techniques469

14.1 Summation Techniques470

14.2 Recurrence Relations475

14.2.1 Estimating Upper and Lower Bounds475

14.2.2 Expanding Recurrences478

14.2.3 Divide and Conquer Recurrences480

14.2.4 Average-Case Analysis of Quicksort482

14.3 Amortized Analysis484

14.4 Further Reading487

14.5 Exercises487

14.6 Projects491

15 Lower Bounds493

15.1 Introduction to Lower Bounds Proofs494

15.2 Lower Bounds on Searching Lists496

15.2.1 Searching in Unsorted Lists496

15.2.2 Searching in Sorted Lists498

15.3 Finding the Maximum Value499

15.4 Adversarial Lower Bounds Proofs501

15.5 State Space Lower Bounds Proofs504

15.6 Finding the ith Best Element507

15.7 Optimal Sorting509

15.8 Further Reading512

15.9 Exercises512

15.10 Projects515

16 Patterns of Algorithms517

16.1 Dynamic Programming517

16.1.1 The Knapsack Problem519

16.1.2 All-Pairs Shortest Paths521

16.2 Randomized Algorithms523

16.2.1 Randomized algorithms for finding large values523

16.2.2 Skip Lists524

16.3 Numerical Algorithms530

16.3.1 Exponentiation531

16.3.2 Largest Common Factor531

16.3.3 Matrix Multiplication532

16.3.4 Random Numbers534

16.3.5 The Fast Fourier Transform535

16.4 Further Reading540

16.5 Exercises540

16.6 Projects541

17 Limits to Computation543

17.1 Reductions544

17.2 Hard Problems549

17.2.1 The Theory of NP-Completeness551

17.2.2 NP-Completeness Proofs555

17.2.3 Coping with NP-Complete Problems560

17.3 Impossible Problems563

17.3.1 Uncountability564

17.3.2 The Halting Problem Is Unsolvable567

17.4 Further Reading569

17.5 Exercises570

17.6 Projects572

Ⅵ APPENDIX575

A Utility Functions577

Bibliography579

Index585