数据结构与算法 C++版 第2版 影印版【2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载】

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

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

Chapter 1 Object-Oriented Programming Using C++1

1.1 Abstract Data Types1

1.2 Encapsulation1

1.3 Inheritance5

1.4 Pointers8

1.4.1 Pointers and Arrays10

1.4.2 Pointers and Copy Constructors12

1.4.3 Pointers and Destructors14

1.4.4 Pointers and Reference Variables15

1.4.5 Pointers to Functions17

1.5 Polymorphism18

1.6 C++ and Object-Oriented Programming20

1.7 The Standard Template Library21

1.7.1 Containers21

1.7.2 Iterators21

1.7.3 Algorithms22

1.7.4 Function Objects22

1.8 Vectors in the Standard Template Library24

1.9 Data Structures and Object-Oriented Programming31

1.10 Case Study： Random Access File31

1.11 Exercises42

1.12 Programming Assignments44

Chapter 2 Complexity Analysis47

2.1 Computational and Asymptotic Complexity47

2.2 Big-O Notation48

2.3 Properties of Big-O Notation50

2.4 Ω and Θ Notations51

2.5 Possible Problems52

2.6 Examples of Complexities52

2.7 Finding Asymptotic Complexity： Examples54

2.8 The Best， Average， and Worst Cases56

2.9 Amortized Complexity59

2.10 Exercises62

Chapter 3 Llinked Lis+s67

3.1 Singly Linked Lists67

3.1.1 Insertion72

3.1.2 Deletion74

3.1.3 Search79

3.2 Doubly Linked Lists79

3.3 Circular Lists83

3.4 Skip Lists85

3.5 Self-Organizing Lists89

3.6 Sparse Tables93

3.7 Lists in the Standard Template Library96

3.8 Deques in the Standard Template Library99

3.9 Concluding Remarks103

3.10 Case Study： A Library104

3.11 Exercises113

3.12 Programming Assignments115

Chapter 4 Stacks and Queues119

4.1 Stacks119

4.2 Queues126

4.3 Priority Queues132

4.4 Stacks in the Standard Template Library133

4.5 Queues in the Standard Template Library134

4.6 Priority Queues in the Standard Template Library135

4.7 Case Study： Exiting a Maze137

4.8 Exercises142

4.9 Programming Assignments144

Chapter 5 Recursion147

5.1 Recursive Definitions147

5.2 Function Calls and Recursion Implementation149

5.3 Anatomy of a Recursive Call151

5.4 Tail Recursion154

5.5 Nontail Recursion155

5.6 Indirect Recursion160

5.7 Nested Recursion162

5.8 Excessive Recursion162

5.9 Backtracking165

5.10 Concluding Remarks172

5.11 Case Study： A Recursive Descent Interpreter173

5.12 Exercises180

5.13 Programming Assignments182

Chapter 6 Binary Trees187

6.1 Trees， Binary Trees， and Binary Search Trees187

6.2 Implementing Binary Trees191

6.3 Searching a Binary Search Tree193

6.4 Tree Traversal195

6.4.1 Breadth-First Traversal196

6.4.2 Depth-First Traversal197

6.4.3 Stackless Depth-First Traversal203

6.5 Insertion208

6.6 Deletion211

6.6.1 Deletion by Merging212

6.6.2 Deletion by Copying215

6.7 Balancing a Tree217

6.7.1 The DSW Algorithm219

6.7.2 A VL Trees222

6.8 Self-Adjusting Trees226

6.8.1 Self-Restructuring Trees226

6.8.2 Splaying228

6.9 Heaps232

6.9.1 Heaps as Priority Queues233

6.9.2 Organizing Arrays as Heaps235

6.10 Polish Notation and Expression Trees238

6.11 Case Study： Computing Word Frequencies242

6.12 Exercises249

6.13 Programming Assignments252

Chapter 7 Multiway Trees257

7.1 The Family of B-Trees257

7.1.1 B-Trees259

7.1.2 B-Trees267

7.1.3 B+-Trees268

7.1.4 Prefiix B+-Trees270

7.1.5 Bit-Trees272

7.1.6 R-Trees273

7.1.7 2-4 Trees275

7.1.8 Sets and Multisets in the Standard Template Library281

7.1.9 Maps and Multimaps in the Standard Template Library286

7.2 Tries290

7.3 Concluding Remarks297

7.4 Case Study： Spell Checker297

7.5 Exercises307

7.6 Programming Assignments308

Chapter 8 Graphs313

8.1 Graph Representation314

8.2 Graph Traversals316

8.3 Shortest Paths319

8.4 Cycle Detection327

8.5 Spanning Trees329

8.5.1 Boruvka’s Algorithm330

8.5.2 Kruskal’s Algorithm332

8.5.3 Jarnik-Prim’s Algorithm333

8.5.4 Dijkstra’s Method333

8.6 Connectivity334

8.6.1 Connectivity in Undirected Graphs334

8.6.2 Connectivity in Directed Graphs336

8.7 Topological Sort338

8.8 Networks340

8.8.1 Maximum Flows340

8.8.2 Maximum Flows of Minimum Cost349

8.9 Matching353

8.9.1 Assignment Problem357

8.9.2 Matching in Nonbipartite Graphs359

8.10 Eulerian and Hamiltonian Graphs361

8.10.1 Eulerian Graphs361

8.10.2 HamiltonianGraphs362

8.11 Case Study： Distinct Representatives365

8.12 Exercises375

8.13 Programming Assignments377

Chapter 9 Sorting381

9.1 Elementary Sorting Algorithms382

9.1.1 Insertion Sort382

9.1.2 Selection Sort384

9.1.3 Bubble Sort386

9.2 Decision Trees388

9.3 Effiicient Sorting Algorithms391

9.3.1 Shell Sort391

9.3.2 Heap Sort394

9.3.3 Quicksort397

9.3.4 Mergesort402

9.3.5 Radix Sort405

9.4 Sorting in the Standard Template Library409

9.5 Concluding Remarks412

9.6 Case Study： Adding Polynomials413

9.7 Exercises420

9.8 Programming Assignments421

Chapter 10 Hashing425

10.1 Hash Functions425

10.1.1 Division426

10.1.2 Folding426

10.1.3 Mid-Square Function427

10.1.4 Extraction427

10.1.5 Radix Transformation427

10.2 Collision Resolution427

10.2.1 Open Addressing428

10.2.2 Chaining433

10.2.3 Bucket Addressing435

10.3 Deletion436

10.4 Perfect Hash Functions437

10.4.1 Cichelli’s Method437

10.4.2 The FHCD Algorithm439

10.5 Hash Functions for Extendible Files441

10.5.1 Extendible Hashing442

10.5.2 Linear Hashing444

10.6 Case Study：Hashing with Buckets446

10.7 Exercises454

10.8 Programming Assignments455

Chapter 11 Data Compression459

11.1 Conditions for Data Compression459

11.2 Huffman Coding461

11.3 Shannon-Fano Code473

11.4 Run-Length Encoding473

11.5 Ziv-Lempel Code475

11.6 Case Study： Huffman Method with Run-Length Encoding477

11.7 Exercises487

11.8 Programming Assignments488

Chapter 12 Memory Management491

12.1 The Sequential-Fit Methods492

12.2 The Nonsequential-Fit Methods493

12.3 Garbage Collection500

12.3.1 Mark-and-Sweep501

12.3.2 Copying Methods507

12.3.3 incremental Garbage Collection509

12.4 Concluding Remarks515

12.5 Case Study： An In-Place Garbage Collector516

12.6 Exercises523

12.7 Programming Assignments524

Appendix A Computing Big-O529

Appendix B Algorithms in the Standard Template Library535