数据结构与算法 C++版 第2版 影印版PDF电子书下载

Chapter 1 Object-Oriented Programming Using C++ 1

1.1 Abstract Data Types 1

1.2 Encapsulation 1

1.3 Inheritance 5

1.4 Pointers 8

1.4.1 Pointers and Arrays 10

1.4.2 Pointers and Copy Constructors 12

1.4.3 Pointers and Destructors 14

1.4.4 Pointers and Reference Variables 15

1.4.5 Pointers to Functions 17

1.5 Polymorphism 18

1.6 C++ and Object-Oriented Programming 20

1.7 The Standard Template Library 21

1.7.1 Containers 21

1.7.2 Iterators 21

1.7.3 Algorithms 22

1.7.4 Function Objects 22

1.8 Vectors in the Standard Template Library 24

1.9 Data Structures and Object-Oriented Programming 31

1.10 Case Study： Random Access File 31

1.11 Exercises 42

1.12 Programming Assignments 44

Chapter 2 Complexity Analysis 47

2.1 Computational and Asymptotic Complexity 47

2.2 Big-O Notation 48

2.3 Properties of Big-O Notation 50

2.4 Ω and Θ Notations 51

2.5 Possible Problems 52

2.6 Examples of Complexities 52

2.7 Finding Asymptotic Complexity： Examples 54

2.8 The Best， Average， and Worst Cases 56

2.9 Amortized Complexity 59

2.10 Exercises 62

Chapter 3 Llinked Lis+s 67

3.1 Singly Linked Lists 67

3.1.1 Insertion 72

3.1.2 Deletion 74

3.1.3 Search 79

3.2 Doubly Linked Lists 79

3.3 Circular Lists 83

3.4 Skip Lists 85

3.5 Self-Organizing Lists 89

3.6 Sparse Tables 93

3.7 Lists in the Standard Template Library 96

3.8 Deques in the Standard Template Library 99

3.9 Concluding Remarks 103

3.10 Case Study： A Library 104

3.11 Exercises 113

3.12 Programming Assignments 115

Chapter 4 Stacks and Queues 119

4.1 Stacks 119

4.2 Queues 126

4.3 Priority Queues 132

4.4 Stacks in the Standard Template Library 133

4.5 Queues in the Standard Template Library 134

4.6 Priority Queues in the Standard Template Library 135

4.7 Case Study： Exiting a Maze 137

4.8 Exercises 142

4.9 Programming Assignments 144

Chapter 5 Recursion 147

5.1 Recursive Definitions 147

5.2 Function Calls and Recursion Implementation 149

5.3 Anatomy of a Recursive Call 151

5.4 Tail Recursion 154

5.5 Nontail Recursion 155

5.6 Indirect Recursion 160

5.7 Nested Recursion 162

5.8 Excessive Recursion 162

5.9 Backtracking 165

5.10 Concluding Remarks 172

5.11 Case Study： A Recursive Descent Interpreter 173

5.12 Exercises 180

5.13 Programming Assignments 182

Chapter 6 Binary Trees 187

6.1 Trees， Binary Trees， and Binary Search Trees 187

6.2 Implementing Binary Trees 191

6.3 Searching a Binary Search Tree 193

6.4 Tree Traversal 195

6.4.1 Breadth-First Traversal 196

6.4.2 Depth-First Traversal 197

6.4.3 Stackless Depth-First Traversal 203

6.5 Insertion 208

6.6 Deletion 211

6.6.1 Deletion by Merging 212

6.6.2 Deletion by Copying 215

6.7 Balancing a Tree 217

6.7.1 The DSW Algorithm 219

6.7.2 A VL Trees 222

6.8 Self-Adjusting Trees 226

6.8.1 Self-Restructuring Trees 226

6.8.2 Splaying 228

6.9 Heaps 232

6.9.1 Heaps as Priority Queues 233

6.9.2 Organizing Arrays as Heaps 235

6.10 Polish Notation and Expression Trees 238

6.11 Case Study： Computing Word Frequencies 242

6.12 Exercises 249

6.13 Programming Assignments 252

Chapter 7 Multiway Trees 257

7.1 The Family of B-Trees 257

7.1.1 B-Trees 259

7.1.2 B-Trees 267

7.1.3 B+-Trees 268

7.1.4 Prefiix B+-Trees 270

7.1.5 Bit-Trees 272

7.1.6 R-Trees 273

7.1.7 2-4 Trees 275

7.1.8 Sets and Multisets in the Standard Template Library 281

7.1.9 Maps and Multimaps in the Standard Template Library 286

7.2 Tries 290

7.3 Concluding Remarks 297

7.4 Case Study： Spell Checker 297

7.5 Exercises 307

7.6 Programming Assignments 308

Chapter 8 Graphs 313

8.1 Graph Representation 314

8.2 Graph Traversals 316

8.3 Shortest Paths 319

8.4 Cycle Detection 327

8.5 Spanning Trees 329

8.5.1 Boruvka’s Algorithm 330

8.5.2 Kruskal’s Algorithm 332

8.5.3 Jarnik-Prim’s Algorithm 333

8.5.4 Dijkstra’s Method 333

8.6 Connectivity 334

8.6.1 Connectivity in Undirected Graphs 334

8.6.2 Connectivity in Directed Graphs 336

8.7 Topological Sort 338

8.8 Networks 340

8.8.1 Maximum Flows 340

8.8.2 Maximum Flows of Minimum Cost 349

8.9 Matching 353

8.9.1 Assignment Problem 357

8.9.2 Matching in Nonbipartite Graphs 359

8.10 Eulerian and Hamiltonian Graphs 361

8.10.1 Eulerian Graphs 361

8.10.2 HamiltonianGraphs 362

8.11 Case Study： Distinct Representatives 365

8.12 Exercises 375

8.13 Programming Assignments 377

Chapter 9 Sorting 381

9.1 Elementary Sorting Algorithms 382

9.1.1 Insertion Sort 382

9.1.2 Selection Sort 384

9.1.3 Bubble Sort 386

9.2 Decision Trees 388

9.3 Effiicient Sorting Algorithms 391

9.3.1 Shell Sort 391

9.3.2 Heap Sort 394

9.3.3 Quicksort 397

9.3.4 Mergesort 402

9.3.5 Radix Sort 405

9.4 Sorting in the Standard Template Library 409

9.5 Concluding Remarks 412

9.6 Case Study： Adding Polynomials 413

9.7 Exercises 420

9.8 Programming Assignments 421

Chapter 10 Hashing 425

10.1 Hash Functions 425

10.1.1 Division 426

10.1.2 Folding 426

10.1.3 Mid-Square Function 427

10.1.4 Extraction 427

10.1.5 Radix Transformation 427

10.2 Collision Resolution 427

10.2.1 Open Addressing 428

10.2.2 Chaining 433

10.2.3 Bucket Addressing 435

10.3 Deletion 436

10.4 Perfect Hash Functions 437

10.4.1 Cichelli’s Method 437

10.4.2 The FHCD Algorithm 439

10.5 Hash Functions for Extendible Files 441

10.5.1 Extendible Hashing 442

10.5.2 Linear Hashing 444

10.6 Case Study：Hashing with Buckets 446

10.7 Exercises 454

10.8 Programming Assignments 455

Chapter 11 Data Compression 459

11.1 Conditions for Data Compression 459

11.2 Huffman Coding 461

11.3 Shannon-Fano Code 473

11.4 Run-Length Encoding 473

11.5 Ziv-Lempel Code 475

11.6 Case Study： Huffman Method with Run-Length Encoding 477

11.7 Exercises 487

11.8 Programming Assignments 488

Chapter 12 Memory Management 491

12.1 The Sequential-Fit Methods 492

12.2 The Nonsequential-Fit Methods 493

12.3 Garbage Collection 500

12.3.1 Mark-and-Sweep 501

12.3.2 Copying Methods 507

12.3.3 incremental Garbage Collection 509

12.4 Concluding Remarks 515

12.5 Case Study： An In-Place Garbage Collector 516

12.6 Exercises 523

12.7 Programming Assignments 524

Appendix A Computing Big-O 529

Appendix B Algorithms in the Standard Template Library 535