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

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

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

1 Introduction l1

1.1．What's the Book About?1

1.2．Mathematics Review3

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

Summary12

Exercises12

References13

2 Algorithm Analysis15

2.1．Mathematical Background15

2.2．Model18

2.3．What to Analyze18

2.4．Running Time Calculations20

2.4.1．A Simple Example21

2.4.2．General Rules21

2.4.3．Solutions for the Maximum Subsequence Sum Problem24

2.4.4．Logarithms in the Running Time28

2.4.5．Checking Your Analysis33

2.4.6．A Grain of Salt33

Summary34

Exercises35

References39

3 Lists,Stacks,and Queues41

3.1．Abstract Data Types(ADTs)41

3.2．The List ADT42

3.2.1．Simple Array Implementation of lists43

3.2.2．Linked Lists43

3.2.3．Programming Details44

3.2.4．Common Errors49

3.2.5．Doubly Linked Lists51

3.2.6．Circularly Linked Lists52

3.2.7．Examples52

3.2.8．Cursor Implementation of Linked Lists57

3.3．The Stack ADT62

3.3.1．Stack Model62

3.3.2．Implementation of Stacks63

3.3.3．Applications71

3.4．The Queue ADT79

3.4.1．Quene Model79

3.4.2．Array Implementation of Queues79

3.4.3．Applications of Queues84

Summary85

Exercises85

4 Trees89

4.1．Preliminaries89

4.1.1．Implementation of Trees90

4.1.2．Tree Traversals with an Application91

4.2．Binary Trees95

4.2.1．Implementation96

4.2.2．Expression Trees97

4.3．The Search Tree ADT—Binary Search Trees100

4.3.1．MakeEmpty101

4.3.2．Find101

4.3.3．FindMin and FindMax103

4.3.4．Insert104

4.3.5．Delete105

4.3.6．Average-Case Analysis107

4.4．AVL Trees110

4.4.1．Single Rotation112

4.4.2．Double Rotation115

4.5．Splay Trees123

4.5.1．A Simple Idea(That Does Not Work)124

4.5.2．Splaying126

4.6．Tree Traversals(Revisited)132

4.7．B-Trees133

Summary138

Exercises139

References146

5 Hashing149

5.1．General Idea149

5.2．Hash Function150

5.3．Separate Chaining152

5.4．Open Addressing157

5.4.1．Linear Probing157

5.4.2．Quadratic Probing160

5.4.3．Double Hashing164

5.5．Rehashing165

5.6．Extendible Hashing168

Summary171

Exercises172

References175

6 Priority Queues(Heaps)177

6.1．Model177

6.2．Simple Implementations178

6.3．Binary Heap179

6.3.1．Structure Property179

6.3.2．Heap Order Property180

6.3.3．Basic Heap Operations182

6.3.4．Other Heap Operations186

6.4．Applications of Priority Queues189

6.4.1．The Selection Problem189

6.4.2．Event Simulation191

6.5．d-Heaps192

6.6．Leftist Heaps193

6.6.1．Leftist Heap Property193

6.6.2．Leftist Heap Operations194

6.7．Skew Heaps200

6.8．Binomial Queues202

6.8.1．Binomial Queue Structure202

6.8.2．Binomial Queue Operations204

6.8.3．Implementation of Binomial Queues205

Summary212

Exercises212

References216

7 Sorting219

7.1．Preliminaries219

7.2．Insertion Sort220

7.2.1．The Algorithm220

7.2.2．Analysis of Insertion Sort221

7.3．A Lower Bound for Simple Sorting Algorithms221

7.4．Shellsort222

7.4.1．Worst-Case Analysis of Shellsort224

7.5．Heapsort226

7.5.1．Analysis of Heapsort228

7.6．Mergesort230

7.6.1．Analysis of Mergesort232

7.7．Quicksort235

7.7.1．Picking the Pivot236

7.7.2．Partitioning Strategy237

7.7.3．Small Arrays240

7.7.4．Actual Quicksort Routines240

7.7.5．Analysis of Quicksort241

7.7.6．A Linear-Expected-Time Algorithm for Selection245

7.8．Sorting Large Structures247

7.9．A General Lower Bound for Sorting247

7.9.1．Decision Trees247

7.10．Bucket Sort250

7.11．External Sorting250

7.11.1．Why We Need New Algorithms251

7.11.2．Model for External Sorting251

7.11.3．The Simple Algorithm251

7.11.4．Multiway Merge253

7.11.5．Polyphase Merge254

7.11.6．Replacement Selection255

Summary256

Exercises257

References261

8 The Disjoint Set ADT263

8.1．Equivalence Relations263

8.2．The Dynamic Equivalence Problem264

8.3．Basic Data Structure265

8.4．Smart Union Algorithms269

8.5．Path Compression271

8.6．Worst Case for Union-by-Rank and Path Compression273

8.6.1．Analysis of the Union/Find Algorithm273

8.7．An Application279

Summary279

Exercises280

References281

9 Graph Algorithms283

9.1．Definitions283

9.1.1．Representation of Graphs284

9.2．Topological Sort286

9.3．Shortest-Path Algorithms290

9.3.1．Unweighted Shortest Paths291

9.3.2．Dijkstra's Algorithm295

9.3.3．Graphs with Negative Edge Costs304

9.3.4．Acyclic Graphs305

9.3.5．All-Pairs Shortest Path308

9.4．Network Flow Problems308

9.4.1．A Simple Maximum-Flow Algorithm309

9.5．Minimum Spanning Tree313

9.5.1．Prim's Algorithm314

9.5.2．Kruskal's Algorithm316

9.6．Applications of Depth-First Search319

9.6.1．Undirected Graphs320

9.6.2．Biconnectivity322

9.6.3．Euler Circuits326

9.6.4．Directed Graphs329

9.6.5．Finding Strong Components331

9.7．Introduction to NP-Completeness332

9.7.1．Easy vs.Hard333

9.7.2．The Class NP334

9.7.3．NP-Complete Problems335

Summary337

Exercises337

References343

10 Algorithm Design Techniques347

10.1．Greedy Algorithms347

10.1.1．A Simple Scheduling Problem348

10.1.2．Huffman Codes351

10.1.3．Approximate Bin Packing357

10.2．Divide and Conquer365

10.2.1．Running Time of Divide and Conquer Algorithms366

10.2.2．Closest-Points Problem368

10.2.3．The Selection Problem373

10.2.4．Theoretical Improvements for Arithmetic Problems376

10.3．Dynamic Programming380

10.3.1．Using a Table Instead of Recursion380

10.3.2．Ordering Matrix Multiplications383

10.3.3．Optimal Binary Search Tree387

10.3.4．All-Pairs Shortest Path390

10.4．Randomized Algorithms392

10.4.1．Random Number Generators394

10.4.2．Skip Lists397

10.4.3．Primality Testing399

10.5．Backtracking Algorithms401

10.5.1．The Turnpike Reconstruction Problem403

10.5.2．Games407

Summary413

Exercises415

References422

11 Amortized Analysis427

11.1．An Unrelated Puzzle428

11.2．Binomial Queues428

11.3．Skew Heaps433

11.4．Fibonacci Heaps435

11.4.1．Cutting Nodes in Leftist Heaps436

11.4.2．Lazy Merging for Binomial Queues439

11.4.3．The Fibonacci Heap Operations442

11.4.4．Proof of the Time Bound443

11.5．Splay Trees445

Summary449

Exercises450

References451

12 Advanced Data Structures and Implementation453

12.1．Top-Down Splay Trees453

12.2．Red Black Trees457

12.2.1．Bottom-Up Insertion462

12.2.2．Top-Down Red Black Trees463

12.2.3．Top-Down Deletion465

12.3．Deterministic Skip Lists469

12.4．AA-Trees476

12.5．Treaps482

12.6．k-d Trees485

12.7．Pairing Heaps488

Summary494

Exercises495

References497

Index501