| 作者 |
| 丛书名 |
| 出版社 |
| 原 McGraw-hill |
| ISBN |
| 简要 |
| 简介 |
| 内容简介书籍计算机书籍 Sartaj Sahni: Data Structures, A1gorithms, and Applications in C++. Copyright ?1998 by The McGraw-Hill Companies. Inc. All rights reserved. Jointly published by China Machine Press/McGraw-Hill. This edition may be sold in the People’s Republic of China only. This book cannot be re-exported and is not for sale outside the People’s Republic of China. |
| 目录 |
| CONTENTS PART I PRELIMINARIES CHAPTER I PROGRAMMING IN C++ 1.1 Introduction 3 1.2 Functions and Parameters 3 1.2.1 Value Parameters 3 1.2.2 Template Functions 4 1.2.3 Reference Parameters 5 1.2.4 Const Reference Parameters 6 1.2.5 Return Values 7 1.2.6 Recursive Functions 8 Fibonacci numbers Factorial Permutations 1.3 Dynamic Memory Allocation 14 1.3.1 The Operator new 14 1.3.2 One-Dimensional Arrays 15 1.3.3 Exception Handling 15 1.3.4 The Operator d e 1 e t e 16 1.3.5 Two-Dimensional Arrays 17 1.4 Classes 20 1.4.1 The Class Currency 20 1.4.2 Using a Different Representation 28 1.4.3 Operator Overloading 29 1.4.4 Throwing Exceptions 32 1.4.5 Friends and Protected Class Members 33 1.4.6 Addition of #ifndef, #define, and #endif Statements 36 1.5 Testing and Debugging 37 1.5.1 What Is Testing? 37 Roots of a quadratic 1.5.2 Designing Test Data 40 Finding the maximum element 1.5.3 Debugging 43 1.6 References and Selected Readings 44 CHAPTER 2 PROGRAM PERFORMANCE 45 2.1 Introduction 47 2.2 Space Complexity 48 2.2.1 Components of Space Complexity 48 2.2.2 Examples 54 2.3 Time Complexity 57 2.3.1 Components of Time Complexity 57 2.3.2 Operation Counts 58 Polynomial evaluation Rank sort Selection sort Bubble sort Insertion sort Sequential search 2.3.3 Step Counts 68 Matrix add, multiply, and transpose Minimum and maximum 2.4 Asymptotic Notation (0, ? q, o) 83 2.4.1 Big Oh Notation (0) 84 2.4.2 Omega Notation (? 88 2.4.3 Theta Notation (q) 89 2.4.4 Little Oh (o) 90 2.4.5 Properties 91 2.4.6 Complexity Analysis Examples 91 Binary search 2.5 Practical Complexities 98 2.6 Performance Measurement. 102 2.6.1 Choosing Instance Size 102 2.6.2 Developing the Test Data 103 2.6.3 Setting Up the Experiment 104 2.7 References and Selected Readings 110 PART Ⅱ DATA STRUCT URES CHAPTER 3 DATA REPRESENTA TION 111 3.1 Introduction 113 3.2 Linear Lists 114 3.3 Formula-Based Representation 116 3.3.1 Representation 116 3.3.2 The Exception Class NoMem 117 3.3.3 Operations 118 3.3.4 Evaluation 122 3.4 Linked Representation 129 3.4.1 The Classes ChainNode and Chain 129 3.4.2 Operations 130 3.4.3 Extensions to the Class Chain 136 3.4.4 A Chain Iterator Class 137 3.4.5 Circular List Representation 138 3.4.6 Comparison with Formula-Based Representation 139 3.4.7 Doubly Linked List Representation 140 3.4.8 Summary 142 3.5 Indirect Addressing 146 3.5.1 Representation 146 3.5.2 Operations 147 3.6 Simulating Pointers 152 3.6.1 SimSpace Operations 153 3.6.2 Chains Using Simulated Pointers 1 7 3.7 A Comparison 163 3.8 Applications 164 3.8.1 Bin Sort 164 3.8.2 Radix Sort 170 3.8.3 Equivalence Classes 173 Machine scheduling Electrical nets 3.8.4 Convex Hull 180 3.9 References and Selected Readings 188 CHAPTER 4 ARRAYS AND MATRICES 189 4.1 Arrays 191 4. 1.1 The Abstract Data Type 191 4.1.2 Indexing a C++ Array 192 4.1.3 Row- and Column-Major Mappings 192 4.1.4 The Class ArraylD 194 4.1.5 The Class Array2D 197 4.2 Matrices 204 4.2.1 Definitions and Operations 204 4 . 2.2 The Class Ma t r i x 206 4.3 Special Matrices 210 4.3.1 Definitions and Applications 210 4.3.2 Diagonal Matrices 212 4.3.3 Tridiagonal Matrix 214 4.3.4 Triangular Matrices 216 4.3.5 Symmetric Matrices 218 4.4 Sparse Matrices 221 4.4.1 Motivation 221 4.4.2 Array Representation 222 4.4.3 Linked Representation 229 CHAPTER 5 STACKS 239 5.1 The Abstract Data Type 241 5.2 Derived Classes and Inheritance 241 5.3 Formula-Based Representation 243 5.4 Linked Representation 248 5 . 5 Applications 252 5.5.1 Parenthesis Matching 252 5.5.2 Towers of Hanoi 254 5.5.3 Rearranging Railroad Cars 256 5.5.4 Switch Box Routing 263 5.5.5 Offline Equivalence Problem 264 5.5.6 Rat in a Maze 268 5.6 References and Selected Readings 281 CHAPTER 6 QUEUES 283 6.1 The Abstract Data Type 285 6.2 Formula-Based Representation 286 6.3 Linked Representation 292 6.4 Applications 297 6.4.1 Railroad Car Rearrangement 297 6.4.2 Wire Routing 299 6.4.3 Image Component Labeling 306 6.4.4 Machine Shop Simulation 309 6.5 References and Selected Readings 324 CHAPTER 7 SKIP LISTS AND HASHING 325 7.1 Dictionaries 327 7.2 Linear List Representation 328 7.3 Skip List Representation 332 7.3.1 The Ideal Case 332 7.3.2 Insertions and Deletions 334 7.3.3 Assigning Levels 335 7.3.4 The Class SkipNode 336 7.3.5 The Class SkipList 337 7.3.6 Complexity 342 7.4 Hash Table Representation 343 7.4.1 Ideal Hashing 343 7.4.2 Hashing with Linear Open Addressing 344 7.4.3 Hashing with Chains 350 7.5 An Application -Text Compression 357 7.5.1 LZW Compression 358 7.5.2 Implementation of LZW Compression 359 7.5.3 LZW Decompression 364 7.5.4 Implementation of LZW Decompression 365 7.6 References and Selected Readings 370 CHAPTER 8 BINARY AND OTHER TREES 371 8.1 Trees 373 8.2 Binary Trees 378 8.3 Properties of Binary Trees 379 8.4 Representation of Binary Trees 382 8.4.1 Formula-Based Representation 382 8.4.2 Linked Representation 383 8.5 Common Binary Tree Operations 385 8.6 Binary Tree Traversal 386 8.7 The ADT BinaryTree 391 8.8 The Class BinaryTree 391 8.9 ADT and Class Extensions 392 8.9. 1 Output 397 8.9.2 Delete 397 8.9.3 Height 397 8.9.4 Size 398 8.10 Applications 400 8.10.1 Placement of Signal Boosters 400 8.10.2 Online Equivalence Classes 405 8.11 References and Selected Readings416 CHAPTER 9 PRIORITY QUEUES 417 9.1 Introduction 419 9.2 Linear Lists 421 9.3 Heaps 421 9.3.1 Definitions 421 9.3.2 Insertion into a Max Heap 423 9.3.3 Deletion from a Max Heap 424 9.3.4 Max Heap Initialization 424 9.3.5 The Class MaxHeap 425 9.4 Leftist Trees 432 9.4.1 Height- and Weight-Biased Min and Max Leftist Trees 432 9.4.2 Insertion into a Max HBLT 435 9.4.3 Deletion from a Max HBLT 435 9.4.4 Melding Two Max HBLTs 435 9.4.5 Initialization 437 9.4.6 The Class MaxHBLT 438 9.5 Applications 444 9.5.1 Heap Sort 9.5.2 Machine Scheduling 444 9.5.3 Huffinan Codes 450 9.6 References and Selected Readings 457 CHAPTER 10 TOURNAMENT TREES 459 10. 1 Introduction 461 10.2 The ADT WinnerTree 466 10.3 The Class WinnerTree 466 10.3.1 Representation 466 10.3.2 Class Specification 467 10.3.3 Constructor, Destructor, and Winner 467 10.3.4 Initializing a Winner Tree 468 10.3.5 Replaying Matches 471 10.4 Loser Trees 472 10.5 Applications 474 10.5.1 Bin Packing Using First Fit 472 10.5.2 Bin Packing Using Next Fit 480 CHAPTER 11 SEARCH TREES 485 11.1 Binary Search Trees 488 11. 1. 1 Definition 488 11.1.2 The ADTs BSTree and IndexedBSTree 490 11.1.3 The Class BSTree 491 11.1.4 Searching 492 11.1.5 Inserting an Element 493 11.1.6 Deleting an Element 493 11.1.7 The Class DBSTree 496 11.1.8 Height of a Binary Search Tree 496 11.2 AVL Trees 500 11.2.1 Definition 500 11.2.2 Height of an AVL Tree 501 11.2.3 Representation of an AVL Tree 501 11.2.4 Searching art AVL Search Tree 502 11.2.5 Inserting into an AVL Search Tree 502 11.2.6 Deletion from an AVL Search Tree 506 11.3 Red-Black Trees 510 11.3.1 Definition 510 11.3.2 Representation of a Red-Black Tree 512 11.3.3 Searching a Red-Black Tree 512 11.3.4 Inserting into a Red-Black Tree 513 11.3.5 Deletion from a Red-Black Tree 518 11.3.6 Implementation Considerations and Complexity 521 11.4 B-Trees 524 11.4.1 Indexed Sequential Access Method 524 11.4.2 m-way Search Trees 525 11.4.3 B-Trees of Order m 528 11.4.4 Height of a B-tree 529 11.4.5 Searching a B-tree 530 11.4.6 Inserting into a B-tree 530 11.4.7 Deletion from a B-tree 533 11.4.8 Node Structure 537 11.5 Applications 539 11.5.1 Histogramming 539 11.5.2 Best-Fit Bin Packing 543 11.5.3 Crossing Distribution 546 11.6 References and Selected Readinas 553 CHAPTER 12 GRAPHS 555 12.1 Definitions 557 12.2 Applications 558 12.3 Properties 562 12.4 The ADTs Graph and Digraph 565 12.5 Representation of Graphs and Digraphs 567 12.5.1 Adjacency Matrix 567 12.5.2 Packed-Adjacency Lists 569 12.5.3 Linked-Adjacency Lists 570 12.6 Representation of Networks 573 12.7 Class Definitions 575 12.7.1 The Different Classes 575 12.7.2 Adjacency-Matrix Classes 576 12.7.3 An Extension to the Class Chain 580 12.7.4 The Class LinkedBase 580 12.7.5 Linked Classes 581 12.8 Graph Iterators 588 12.8.1 Specification 588 12.8.2 Iterator Functions for Adjacency-Matrix Representations 589 12.8.3 Iterator Functions for Linked-Adjacency Lists 589 12.9 Language Features 592 12.9.1 Virtual Functions and Polymorphism 592 12.9.2 Pure Virtual Functions and Abstract Classes 595 12.9.3 Virtual Base Classes 596 12.9.4 Abstract Classes and Abstract Data Types598. 12.10 Graph Search Methods 600 12.10.1 Breadth-First Search 600, 12.10.2 The Class Network 602 12.10.3 Implementation of Network: : BFS 602 12.10.4 Complexity Analysis of Network: : BFS 602 12.10.5 Depth-First Search 605 12.11 Applications Revisited 607 12.11.1 Finding a Path 607 12.11.2 Connected Graphs and Components 609 12.11.3 Spanning Trees 611 PART III ALGORITHM-DESIGN METHODS CHAPTER 13 THE GREEDY METHOD 615 13.1 Optimization Problems 617 13.2 The Greedy Method 618 13.3 Applications 623 13.3.1 Container Loading 623 13.3.2 0/1 Knapsack Problem 624 13.3.3 Topological Sorting 628 13.3.4 Bipartite Cover 633 13.3.5 Single-Source Shortest Paths 642 13.3.6 Minimum-Cost Spanning Trees 646 Kruskal’s Algorithm Prim’s Algorithm Sollin’s Algorithm 13.4 References and Selected Readings 659 CHAPTER 14 DIVIDE AND CONQUER 661 14.1 The Method 662 Minimum and maximum Strassen’s matrix multiply 14.2 Applications 672 14.2.1 Defective Chessboard 672 14.2.2 Merge Sort 677 14.2.3 Quick Sort 682 14-2.4 Selection 688 14.2.5 Closest Pair of Points 691 14.3 Solving Recurrence Equations 703 14.4 Lower Bounds on Complexity 705 14.4.1 Lower Bound for the Minmax Problem 706 14.4.2 Lower Bound for Sorting 708 CHAPTER 15 DYNAMIC PROGRAMMING 711 15.1 The Method 712 15.2 Applications 715 15.2.1 0/1 Knapsack Problem 715 15.2.2 Image Compression 719 15.2.3 Matrix Multiplication Chains 724 15.2.4 All Pairs Shortest Paths 731 15.2.5 Noncrossing Subset of Nets 735 15.2.6 Component Folding 740 15.3 References and Selected Readings 749 CHAPTER 16 BACKTRACKING 751 16.1 The Method 753 16.2 Applications 760 16.2.1 Container Loading 760 16.2.2 0/1 Knapsack Problem 769 16.2.3 Max Clique 772 16.2.4 Traveling Salesperson 775 16.2.5 Board Permutation 778 CHAPTER 17 BRANCH AND BOUND 787 17.1 The Method 788 17.2 Applications 792 17.2.1 Container Loading 792 17.2.2 0/1 Knapsack Problem 802 17.2.3 Max Clique 805 17.2.4 Traveling Salesperson 807 17.2.5 Board Permutation 810 INDEX 817 |