Data structures and algorithm analysis in C++PDF|Epub|txt|kindle电子书版本网盘下载

Data structures and algorithm analysis in C++PDF格式电子书版下载

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

Chapter 1 Programming：A General Overview1

1.1 What’s This 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 Recursion8

1.4 C＋＋ Classes12

1.4.1 Basic class Syntax12

1.4.2 Extra Constructor Syntax and Accessors13

1.4.3 Separation of Interface and Implementation16

1.4.4 vector and stri ng19

1.5 C＋＋ Details21

1.5.1 Pointers21

1.5.2 Lvalues，Rvalues，and References23

1.5.3 Parameter Passing25

1.5.4 Return Passing27

1.5.5 std：：swap and std：：move29

1.5.6 The Big-Five：Destructor，Copy Constructor，Move Constructor，Copy Assignment operator=，Move Assignment operator=30

1.5.7 C-style Arrays and Strings35

1.6 Templates36

1.6.1 Function Templates37

1.6.2 Class Templates38

1.6.3 Object，Comparable，and an Example39

1.6.4 Function Objects41

1.6.5 Separate Compilation of Class Templates44

1.7 Using Matrices44

1.7.1 The Data Members，Constructor，and Basic Accessors44

1.7.2 operator[]45

1.7.3 Big-Five46

Summary46

Exercises46

References48

Chapter 2 Algorithm Analysis51

2.1 Mathematical Background51

2.2 Model54

2.3 What to Analyze54

2.4 Running-Time Calculations57

2.4.1A Simple Example58

2.4.2General Rules58

2.4.3Solutions for the Maximum Subsequence Sum Problem60

2.4.4Logarithms in the Running Time66

2.4.5Limitations of Worst-Case Analysis70

Summary70

Exercises71

References76

Chapter 3 Lists，Stacks，and Queues77

3.1Abstract Data Types （ADTs）77

3.2The List ADT78

3.2.1 Simple Array Implementation of Lists78

3.2.2 Simple Linked Lists79

3.3vector and l i st in the STL80

3.3.1Iterators82

3.3.2Example：Using erase on a List83

3.3.3const_iterators84

3.4Implementation of vector86

3.5Implementation of l i st91

3.6The Stack ADT103

3.6.1 Stack Model103

3.6.2 Implementation of Stacks104

3.6.3 Applications104

3.7The Queue ADT112

3.7.1 Queue Model113

3.7.2 Array Implementation of Queues113

3.7.3 Applications of Queues115

Summary116

Exercises116

Chapter 4 Trees121

4.1 Preliminaries121

4.1.1 Implementation of Trees122

4.1.2 Tree Traversals with an Application123

4.2 Binary Trees126

4.2.1 Implementation128

4.2.2 An Example：Expression Trees128

4.3 The Search Tree ADT—Binary Search Trees132

4.3.1 contains134

4.3.2 findMin and findMax135

4.3.3 insert136

4.3.4 remove139

4.3.5 Destructor and Copy Constructor141

4.3.6 Average-Case Analysis141

4.4 AVL Trees144

4.4.1 Single Rotation147

4.4.2 Double Rotation149

4.5 Splay Trees158

4.5.1 A Simple Idea （That Does Not Work）158

4.5.2 Splaying160

4.6 Tree Traversals （Revisited）166

4.7 B-Trees168

4.8 Sets and Maps in the Standard Library173

4.8.1 Sets173

4.8.2 Maps174

4.8.3 Implementation of set and map175

4.8.4 An Example That Uses Several Maps176

Summary181

Exercises182

References189

Chapter 5 Hashing193

5.1 General Idea193

5.2 Hash Function194

5.3 Separate Chaining196

5.4 Hash Tables without Linked Lists201

5.4.1 Linear Probing201

5.4.2 Quadratic Probing202

5.4.3 Double Hashing207

5.5 Rehashing208

5.6 Hash Tables in the Standard Library210

5.7 Hash Tables with Worst-Case O（1） Access212

5.7.1 Perfect Hashing213

5.7.2 Cuckoo Hashing215

5.7.3 Hopscotch Hashing227

5.8 Universal Hashing230

5.9 Extendible Hashing233

Summary236

Exercises237

References241

Chapter 6 Priority Queues （Heaps）245

6.1 Model245

6.2 Simple Implementations246

6.3 Binary Heap247

6.3.1 Structure Property247

6.3.2 Heap-Order Property248

6.3.3 Basic Heap Operations249

6.3.4 Other Heap Operations252

6.4 Applications of Priority Queues257

6.4.1 The Selection Problem258

6.4.2 Event Simulation259

6.5 d-Heaps260

6.6 Leftist Heaps261

6.6.1 Leftist Heap Property261

6.6.2 Leftist Heap Operations262

6.7 Skew Heaps269

6.8 Binomial Queues271

6.8.1 Binomial Queue Structure271

6.8.2 Binomial Queue Operations271

6.8.3 Implementation of Binomial Queues276

6.9 Priority Queues in the Standard Library282

Summary283

Exercises283

References288

Chapter 7 Sorting291

7.1 Preliminaries291

7.2 Insertion Sort292

7.2.1 The Algorithm292

7.2.2 STL Implementation of Insertion Sort293

7.2.3 Analysis of Insertion Sort294

7.3 A Lower Bound for Simple Sorting Algorithms295

7.4 Shellsort296

7.4.1 Worst-Case Analysis of Shellsort297

7.5 Heapsort300

7.5.1 Analysis of Heapsort301

7.6 Mergesort304

7.6.1 Analysis of Mergesort306

7.7 Quicksort309

7.7.1 Picking the Pivot311

7.7.2 Partitioning Strategy313

7.7.3 Small Arrays315

7.7.4 Actual Quicksort Routines315

7.7.5 Analysis of Quicksort318

7.7.6 A Linear-Expected-Time Algorithm for Selection321

7.8 A General Lower Bound for Sorting323

7.8.1 Decision Trees323

7.9 Decision-Tree Lower Bounds for Selection Problems325

7.10 Adversary Lower Bounds328

7.11 Linear-Time Sorts：Bucket Sort and Radix Sort331

7.12 External Sorting336

7.12.1 Why We Need New Algorithms336

7.12.2 Model for External Sorting336

7.12.3 The Simple Algorithm337

7.12.4 Multiway Merge338

7.12.5 Polyphase Merge339

7.12.6 Replacement Selection340

Summary341

Exercises341

References347

Chapter 8 The Disjoint Sets Class351

8.1 Equivalence Relations351

8.2 The Dynamic Equivalence Problem352

8.3 Basic Data Structure353

8.4 Smart Union Algorithms357

8.5 Path Compression360

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

8.6.1 Slowly Growing Functions362

8.6.2 An Analysis by Recursive Decomposition362

8.6.3 An O（M log * N） Bound369

8.6.4 An O（M α（M，N）） Bound370

8.7 An Application372

Summary374

Exercises375

References376

Chapter 9 Graph Algorithms379

9.1 Definitions379

9.1.1 Representation of Graphs380

9.2 Topological Sort382

9.3 Shortest-Path Algorithms386

9.3.1 Unweighted Shortest Paths387

9.3.2 Dijkstra’s Algorithm391

9.3.3 Graphs with Negative Edge Costs400

9.3.4 Acyclic Graphs400

9.3.5 All-Pairs Shortest Path404

9.3.6 Shortest Path Example404

9.4 Network Flow Problems406

9.4.1 A Simple Maximum-Flow Algorithm408

9.5 Minimum Spanning Tree413

9.5.1 Prim’s Algorithm414

9.5.2 Kruskal’s Algorithm417

9.6 Applications of Depth-First Search419

9.6.1 Undirected Graphs420

9.6.2 Biconnectivity421

9.6.3 Euler Circuits425

9.6.4 Directed Graphs429

9.6.5 Finding Strong Components431

9.7 Introduction to NP-Completeness432

9.7.1 Easy vs.Hard433

9.7.2 The Class NP434

9.7.3 NP-Complete Problems434

Summary437

Exercises437

References445

Chapter 10 Algorithm Design Techniques449

10.1 Greedy Algorithms449

10.1.1 A Simple Scheduling Problem450

10.1.2 Huffman Codes453

10.1.3 Approximate Bin Packing459

10.2 Divide and Conquer467

10.2.1 Running Time of Divide-and-Conquer Algorithms468

10.2.2 Closest-Points Problem470

10.2.3 The Selection Problem475

10.2.4 Theoretical Improvements for Arithmetic Problems478

10.3 Dynamic Programming482

10.3.1 Using a Table Instead of Recursion483

10.3.2 Ordering Matrix Multiplications485

10.3.3 Optimal Binary Search Tree487

10.3.4 All-Pairs Shortest Path491

10.4 Randomized Algorithms494

10.4.1 Random-Number Generators495

10.4.2 Skip Lists500

10.4.3 Primality Testing503

10.5 Backtracking Algorithms506

10.5.1 The Turnpike Reconstruction Problem506

10.5.2 Games511

Summary518

Exercises518

References527

Chapter 11 Amortized Analysis533

11.1 An Unrelated Puzzle534

11.2 Binomial Queues534

11.3 Skew Heaps539

11.4 Fibonacci Heaps541

11.4.1 Cutting Nodes in Leftist Heaps542

11.4.2 Lazy Merging for Binomial Queues544

11.4.3 The Fibonacci Heap Operations548

11.4.4 Proof of the Time Bound549

11.5 Splay Trees551

Summary555

Exercises556

References557

Chapter 12 Advanced Data Structures and Implementation559

12.1 Top-Down Splay Trees559

12.2 Red-Black Trees566

12.2.1 Bottom-Up Insertion567

12.2.2 Top-Down Red-Black Trees568

12.2.3 Top-Down Deletion570

12.3 Treaps576

12.4 Suffix Arrays and Suffix Trees579

12.4.1 Suffix Arrays580

12.4.2 Suffix Trees583

12.4.3 Linear-Time Construction of Suffix Arrays and Suffix Trees586

12.5 k-d Trees596

12.6 Pairing Heaps602

Summary606

Exercises608

References612

Appendix A Separate Compilation of Class Templates615

A.1 Everything in the Header616

A.2 Explicit Instantiation616

Index619