DATA STRUCTURES AND ALGORITHMSPDF电子书下载

Chapter 1 Design and Analysis of Algorithms 1

1.1 From Problems to Programs 1

1.2 Abstract Data Types 10

1.3 Data Types， Data Structures， and Abstract Data Types 13

1.4 The Running Time of a Program 16

1.5 Calculating the Running Time of a Program 21

1.6 Good Programming Practice 27

1.7 Super Pascal 29

Chapter 2 Basic Data Types 37

2.1 The Data Type “List 37

2.2 Implementation of Lists 40

2.3 Stacks 53

2.4 Queues 56

2.5 Mappings 61

2.6 Stacks and Recursive Procedures 64

Chapter 3 Trees 75

3.1 Basic Terminology 75

3.2 The ADT TREE 82

3.3 Implementations of Trees 84

3.4 Binary Trees 93

Chapter 4 Basic Operations on Sets 107

4.1 Introduction to Sets 107

4.2 An ADT with Union， Intersection， and Difference 109

4.3 A Bit-Vector Implementation of Sets 112

4.4 A Linked-List Implementation of Sets 115

4.5 The Dictionary 117

4.6 Simple Dictionary Implementations 119

4.7 The Hash Table Data Structure 122

4.8 Estimating the Efficiency of Hash Functions 129

4.9 Implementation of the Mapping ADT 135

4.10 Priority Queues 135

4.11 Implementations of Priority Queues 138

4.12 Some Complex Set Structures 145

Chapter 5 Advanced Set Representation Methods 155

5.1 Binary Search Trees 155

5.2 Time Analysis of Binary Search Tree Operations 160

5.3 Tries 163

5.4 Balanced Tree Implementations of Sets 169

5.5 Sets with the MERGE and FIND Operations 180

5.6 An ADT with MERGE and SPLIT 189

Chapter 6 Directed Graphs 198

6.1 Basic Definitions 198

6.2 Representations for Directed Graphs 199

6.3 The Single-Source Shortest Paths Problem 203

6.4 The All-Pairs Shortest Path Problem 208

6.5 Traversals of Directed Graphs 215

6.6 Directed Acyclic Graphs 219

6.7 Strong Components 222

Chapter 7 Undirected Graphs 230

7.1 Definitions 230

7.2 Minimum-Cost Spanning Trees 233

7.3 Traversals 239

7.4 Articulation Points and Biconnected Components 244

7.5 Graph Matching 246

Chapter 8 Sorting 253

8.1 The Internal Sorting Model 253

8.2 Some Simple Sorting Schemes 254

8.3 Quicksort 260

8.4 Heapsort 271

8.5 Bin Sorting 274

8.6 A Lower Bound for Sorting by Comparisons 282

8.7 Order Statistics 286

Chapter 9 Algorithm Analysis Techniques 293

9.1 Efficiency of Algorithms 293

9.2 Analysis of Recursive Programs 294

9.3 Solving Recurrence Equations 296

9.4 A General Solution for a Large Class of Recurrences 298

Chapter 10 Algorithm Design Techniques 306

10.1 Divide-and-Conquer Algorithms 306

10.2 Dynamic Programming 311

10.3 Greedy Algorithms 321

10.4 Backtracking 324

10.5 Local Search Algorithms 336

Chapter 11 Data Structures and Algorithms for External Storage 347

11.1 A Model of External Computation 347

11.2 External Sorting 349

11.3 Storing Information in Files 361

11.4 External Search Trees 368

Chapter 12 Memory Management 378

12.1 The Issues in Memory Management 378

12.2 Managing Equal-Sized Blocks 382

12.3 Garbage Collection Algorithms for Equal-Sized Blocks 384

12.4 Storage Allocation for Objects with Mixed Sizes 392

12.5 Buddy Systems 400

12.6 Storage Compaction 404

Bibliography 411

Index 419