Data Structures & Algorithm Analysis in C++(3rd) 英文无水印pdf 第3版 pdf所有页面使用FoxitReader和PDF-XChangeViewer测试都可以打开 本资源转载自网络，如有侵权，请联系上传者或csdn删除 本资源转载自网络，如有侵权，请联系上传者或csdn删除
Contents Preliminaries 1 Data Structures and Algorithms 1. 1 A Philosophy of Data Structures 4 1.1 The Need for data structure 1.1.2 Costs and benefits 1.2 Abstract Data Types and Data Structures 8 1. 3 Design patterns 12 1.3.1 Flyweight 13 1. 3.2 Visitor 1.3.3 Composite 1. 3.4 Stra 15 1. 4 Problems. Algorithms and programs 16 1. 5 Further Reading 18 1. 6 Exercises 2 Mathematical preliminaries 25 2.1 Sets and relations 2.2 Miscellaneous notation 29 2.3 Logarithms 2. 4 Summations and recurrences 2.5 Recursion 36 2.6 Mathematical Proof Techniques 38 2.6.1 Direct Proof 39 2.6.2 Proof by Contradicti 39 2.6.3 Proof by Mathematical Induction 2. 7 Estimation 46 2.8 Further readins 47 2.9 Exercises 3 Algorithm analysis 55 3.1 Introduction 3.2 Best. Worst, and average cases 61 3.3 A Faster Computer, or a Faster Algorithm? 3.4 Asymptotic analysis 65 3.4.1 Upper bounds 3.4.2 Lower bounds 67 3.4.3 Notation 68 3.4.4 Simplifying ru 3.4.5 Classifying Functions 70 3.5 Calculating the Running Time for a Program 3.6 Analyzing Problems 76 3. 7 Common misunderstandings 3.8 Multiple Parameters 3.9 Space bounds 80 3.10 Speeding up your programs 82 3.11 Empirical analysis 3.12 Further reading 3.13 Exercises 86 3. 14 Projects I Fundamental Data Structures 93 4 Lists, Stacks, and Queues 95 4.1 Lists 96 4.1.1 Array-Based List Implementation 1.2 Linked Lists 10 4.1.3 Comparison of List Implementations 112 Contents 4.1. 4 Element Implementations 114 4. 1.5 Doubly Linked Lists 115 4.2 Stack 120 4.2.1 Array-Based Stacks 4.2.2 Linked stacks 124 4.2.3 Comparison of Array-Based and Linked Stacks 125 4.2.4 Implementing recursion 125 4.3 Queues 12 4.3.1 Array-Based Queues 129 4.3.2 Linked Queues 134 4.3.3 Comparison of Array-Based and Linked Queues 134 4. 4 Dictionaries 134 4.5 Further Reading 145 4.6 Exercises 145 4.7 Projects 149 5 Binary Trees 151 5. 1 Definitions and properties 151 5.1.1 The Full Binary Tree Theorem 153 5.1.2 A Binary Tree Node ADt 155 5.2 Binary Tree Traversals 155 5.3 Binary Tree Node Implementations 160 5.3.1 Pointer-Based Node Implementations 160 5.3.2 Space Requirements 166 5.3.3 Array Implementation for Complete Binary Trees 168 5.4 Binary Scarch Trees 5.5 Heaps and priority Queues 178 5.6 Huffman Coding trees 185 5.6.1 Building huffman Coding trees 186 5.6.2 Assigning and Using huffman Codes 192 6.3 Search in huffman trees 195 5.7 Further Reading 196 5.8 Exercises 196 5.9 Projects 200 6 Non-Binary trees 203 6.1 General Tree Definitions and Terminology 203 6.1.1 An adt for general Tree nodes 6.1.2 General tree traversals 205 6.2 The Parent Pointer Implementation 207 6.3 General Tree Implementations 213 6.3.1 List of children 214 6.3.2 The Left-Child/Right-Sibling Implementation 215 6.3. 3 Dynamic Node Implementations 215 6.3. Dynamic Left-Child/Right-Sibling"Implementation 218 6.4 K-ary Trees 218 6.5 Sequential Tree Implementations 219 6.6 Further Reading 6.7 Exercises 223 6.8 Projects 226 II Sorting and Searching 229 7 Internal Sorting 231 7. 1 Sorting Terminology and Notation 232 7.2 Three @(m)Sorting Algorithms 33 7.2.1 Insertion sort 233 2. 2 Bubble sort 235 7. 2. 3 Scle 37 7.2.4 The Cost of Exchange Sorting 238 7.3 Shells 239 7.4 Mergesort 41 7.5 Quicksort 24 7.6 Heapsort 251 7. 7 Binsort and radix sort 252 7.8 An Empirical Comparison of Sorting algorithms 59 7.9 Lower Bounds for Sorting 7. 10 Further reading 265 7.11 Exercises 265 7.12 Projects Contents 8 File processing and external sorting 273 8.1 Primary versus Secondary Storage 273 8.2 Disk drives 8.2.1 Disk Drive architecture 276 8.2.2 Disk access costs 280 8. 3 Buffers and Buffer pools 282 8.4 The Programmer's View of Files 290 8.5 External sortin 291 8.5.1 Simple Approaches to External Sorting ) 8.5.2 Replacement Selection 8.5.3 Multiway Merging 8.6 Further reading 303 8. 7 Exercises 304 8.8 Projects 307 earching 311 9.1 Searching Unsorted and sorted arrays 312 9.2 Self-Organizing Lists 317 9. 3 Bit Vectors for Representing sets 323 9.4 hashing 9. 4.1 Hash Functions 9.4.2 Hashin 330 9.4.3 Closed Hashing 331 9.4.4 Analysis of closed hashing 9.4.5 Deletion 344 9.5 Further readin 45 9.6 Exercises 345 9.7 Projects 348 10 Indexing 351 10.1 Linear indexin I02 SAM 356 10.3 Tree-based indexing 358 10.4 2-3 Trees 10.5 B-Trees 10.5.1 B+-Trees 368 VIll Contents 10.5.2 B-Tree Analysis 374 10.6 Further Reading 375 10.7 Exercises 375 10.8 Projects 377 Iv Advanced data structures 379 raphs 11.1 Terminology and representations 11.2 Graph Implementations 386 11.3 Graph Traversals 90 1.3.1 Depth-First Search 393 11.3.2 Breadth-First search 394 I1.3. 3 Topological sort 394 11. 4 Shortest-Paths Problems 11. 4.1 Single-Source shortest paths 400 11.5 Minimum-Cost Spanning trees 402 11.5.1 Prim's algorithm 11.5.2 Kruskal,s algorithm 407 11.6 Further readins 409 11.7 Exercises 409 11. 8 Projec 411 12 Lists and Arrays revisited 413 12.1 Multilist 413 12.2 Matrix Representations 416 12.3 Memory management 420 12.3.1 Dynamic Storage allocation 422 12.3.2 Failure policies and garbage collection 12.4 Further reading 433 12.5 Exercises 434 12.6 Projects 435 13 Advanced Tree structures 437 13.1 Tries 437 Contents 13.2 Balanced Trees 44 13.2.1 The AVL Tree 23 44 13.2.2 The Splay Tree 445 13. 3 Spatial Data Structures 448 13.3.1 The K-D Tree 45 13.3.2 The PR quadtree 455 13.3.3 Other Point data structures 459 13.3.4 Other Spatial Data Structures 461 13. 4 Further reading 13.5 Exercises 462 13.6 Projects v Theory of Algorithms 467 14 Analysis Techniques 469 14.1 Summation Techniques 470 14.2 Recurrence relations 475 14.2.1 Estimating Upper an ower boun 475 14.2.2 Expanding recurrences 478 14.2.3 Divide and Conquer recurrences 480 14.2.4 Average-Case Analysis of Quicksort 482 14.3 Amortized Analysis 484 14.4 Further Reading 487 14.5 Exercises 487 14.6 Projects 491 15 Lower bounds 493 15.1 Introduction to Lower Bounds proofs 494 15.2 Lower Bounds on searching lists 496 15.2. 1 Searching in Unsorted Lists 496 15.2.2 Searching in Sorted lists 498 15.3 Finding the maximum value 499 15.4 Adversarial Lower bounds proofs 15.5 State Space Lower Bounds Proofs 15.6 Finding the ith best element 507 15.7 Optimal sorting 509 15. 8 Further reading 512 15.9Eⅹ excises 512 15. 10Projec 515 16 Patterns of algorithms 517 16. 1 Dynamic Programming 517 16.1.1 The Knapsack problem 16.1.2 All-Pairs shortest paths 521 16.2 Randomized algorithms 523 16.2. 1 Randomized algorithms for finding large values 523 6.2.2 Skip lists 524 16.3 Numerical Algorithms 530 16.3.1 Exponentiation 531 16.3.2 Largest Common Factor 531 16.3.3 Matrix Multiplication 532 16.3.4 Random numbers 534 16.3.5 The Fast Fourier Transform 535 6.4 Further Reading 540 16.5 Exercises 540 16.6 Projects 541 17 Limits to Computation 543 17.1 Reductions 544 17.2 Hard Problems 549 17.2.1 The Theory ofNp-Completeness 551 17.2.2 NP-Completeness Proofs 555 17.2.3 Coping with N P-Complete Problems 560 17.3 Impossible problems 563 17.3.1 Uncountability 564 17.3.2 The halting problem Is unsolvable 567 17.4 Further reading 569 17.5Eⅹ excises 570 17.6 Projects 572