Chapter l Introduction l.l. What''s the Book Aboat l.2. Mathematics Review l.2.l. Exponents l.2.2. Logarithms l.2.3. Series l.2.4. Modular Arithmetic l.2.5. The P Word l.3. A Brief Introduction to Recursion l.4. C Classes l.4.l. Basic class Syntax l.4.2. Extra Constractor Syntax and Accessors l.4.3. Separation of Interface and Implementation l.4.4. vector and string l.5. C Details l.5.l. Pointers 1.5.2. Parameter Passing l.5.3. Return Passing l.5.4. Reference Variables l.5.5. The Big Three: Destructor, Copy Constructor, operator= l.5.6. The World of C l.6. Templates l.6.l. Function Templates l.6.2. Class Templates l.6.3. Object, Comparable, and an Example 1.7. Using Matrices l.7.l. The Data Members, Constructor, and Basic Accessors l.7.2. operator[] l.7.3. Destructor, Copy Assignment, Copy Constructor Summary Exercises References Chapter 2 Algorithm Analysis 2.l. Mathematical Background 2.2. Model 2.3. What to Analyze 2.4. Running Time Calculations 2.4.l. A Simple Example 2.4.2. General Rules 2.4.3. Solutions for the Maximum Subsequence Sum Problem 2.4.4. Logarithms in the Running Time 2.4.5. Checking Your Analysis 2.4.6. A GraLin of SaLlt Summary Exercises References Chapter 3 Lists, Stacks, and Queues 3.1. Abstract Data Types AOTS 3.2. The List ADT 3.2.1 . Simple Array Implementation of Lists 3.2.2. Linked Lists 3.2.3. Programming Details 3.2.4. Memory Reclamation and the Big Three 3.2.5. Doubly Linked Lists 3.2.6. Circular Linked Lists 3.2.7. Examples 3.2.8. Cursor Implementation of Linked Lists 3.3. The Stack ADT 3.3.l. Stack Model 3.3.2. Implementation of Stacks 3.3.3. Applications 3.4. The Queue ADT 3.4.l. Queue Model 3.4.2. Array Implementation of Queues 3.4.3. Applications of Queues Summary Exercises Chapter 4 Trees 4.l. Preliminaries 4.1.l. Implementation of Trees 4.l.2. Tree Traversals with an Application 4.2. Binary Trees 4.2.l. Implementation 4.2.2. An Example: Expression Trees 4.3. The Search Tree ADT-Binary Search Trees 4.3.l. find 4.3.2. findMin and findMax 4.3.3. insert 4.3.4. remove 4.3.5. Destructor and Copy Assignment Operator 4.3.6. Average-Case Analysis 4.4. AVL Trees 4.4.l. Single Rotation 4.4.2. Double Rotation 4.5. Splay Trees 4.5.l. A Simple Idea That Does Not Work 4.5.2. Splaying 4.6. Tree Traversals Revisited 4.7. B-Trees Summary Exercises References Chapter 5 Hashing 5.l. General Idea 5.2. Hash Function 5.3. Separate Chaining 5.4. Open Addressing 5.4.l. Linear Probing 5.4.2. Quadratic Probing 5.4.3. Double Hashing 5.5. Rehashing 5.6. Extendible Hashing Summary Eexercises References Chapter 6 Priority Queues Heaps 6.l. Model 6.2. Simple Implementations 6.3. Binary Heap 6.3.l . Structure Property 6.3.2. Heap-Order Property 6.3.3. Basic Heap Operations 6.3.4. Other Heap Operations 6.4. Applications of Priority Queues 6.4.l. The Selection Problem 6.4.2. Event Simulation 6.5. d-Heaps 6.6. Leftist Heaps 6.6.l. Leftist Heap Property 6.6.2. Leftist Heap Operations 6.7. Skew Heaps 6.8. Binomial Queues 6.8.l. Binomial Queue Structure 6.8.2. Binomial Queue Operations 6.8.3. Implementation of Binomial Queues Summary Exercises References Chapter 7 Sorting 7.l. Preliminaries 7.2. Insertion Son 7.2.l. The Algorithm 7.2.2. Analysis of Insenion SOH 7.3. A Lower Bound for Simple Soning Algorithms 7.4. Shellson 7.4.1 . Worst-Case Analysis of Shellsort 7.5. Heapsort 7.5.l . Analysis of Heapson 7.6. MergesoH 7.6. l . Analysis of Mergesort 7.7. QoicksoH 7.7.l. Picking the Pivot 7.7.2. Partitioning Strategy 7.7.3. Small Arrays 7.7.4. Actual Quickson Routines 7.7.5. Analysis of Quickson 7.7.6. A Linear-Expected-Time Algorithm for Seleaion 7.8. Indirect Sorting 7.8.l. vector<Comparable ''> Does Not Work 7.8.2. Sman Pointer Class 7.8.3. Overloading operator< 7.8.4. Dereferencing a Pointer with 7.8.5. Overloading the Type Conversion Operator 7.8.6. Implicit Type Conversions Are Everywhere 7.8.7. Daal-Direction Implicit Conversions Can Cause Ambiguities 7.8.8. Pointer Subtraction Is Legal 7.9. A General Lower Bound for Soning 7.9.l. Decision Trees 7.1O. Bucket Sort 288 7.l1 . External Soaing 7.ll.I. Whv We Need New Algorithms 7.ll.2. Model for External SoHing 7.Il.3. The Simple Algorithm 7.ll.4. Multiway Merge 7.1l.5. Polyphase Merge 7.ll.6. Replacement Selection Summary Exercises References Chapter 8 The Disioint Set ADT 8.l. Equivalence Relations 8.2. The Dynamic Equivalence Problem 8.3. Basic Data Structure 8.4. Smart Union Algorithms 8.5. Path Compression 8.6. Worst Case for Union-by-Rank and Path Compression 8.6. l . Analysis of the Union/Find Algorithm 8.7. An Application Summary Exercises References Chapter 9 Graph Algorithms 9.l. Definitions 9.l .l . Representation of Graphs 9.2. Topological Sort 9.3. Shortest-Path Algorithms 9.3.l . Unweighted Shortest Paths 9.3.2. Diikstra''s Algorithm 9.3.3. Graphs with Negative Edge Costs 9.3.4. Acyclic Graphs 9.3.5. AII-Pairs Shortest Path 9.4. Network Flow Problems 9.4.l . A Simple Maximum-Flow Algorithm 9.5. Minimum Spanning Tree 9.5.l. Prim''s Algorithm 9.5.2. Kruskal''s Algorithm 9.6. Applications of Depth-First Search 9.6.I . Undirected Graphs 9.6.2. Biconnectivity 9.6.3. Euler Circuits 9.6.4. Directed Graphs 9.6.5. Finding Strong Components 9.7. Introduction to NP-Completeness 9.7.l. Easy vs. Hard 9.7.2. The Class NP 9.7.3. NP-Complete Problems Summary Exercises References Chapter 1O Algorithm Design Techniques 1O. l . Greedy Algorithms 1O.l.l. A Simple Scheduling Problem 1O.l.2. Huffman Codes 1O.l.3. Approximate Bin Packing 1O.2. Divide and Conquer 1O.2.l. Running Time of Divide and Conquer Algorithms 1O.2.2. Closest-Points Problem 1O.2.3. The Selection Problem 1O.2.4. Theoretical Improvements for Arithmetic Problems 1O.3. Dynamic Programming 1O.3.l. Using a Table Instead of Recursion 1O.3.2. Ordering Matrix Multiplications . 1O.3.3. Optimal Binary Search Tree 1O.3.4. AII-Pairs Shortest Path 1O.4. Randomized Algorithms 1O.4.l. Random Number Generators 1O.4.2. Skip Lists 10.4.3. Primality Testing l0.5. packtracking Algorithms 1O.5. l . The Turnpike Reconstruction Problem 1O.5.2. Games Summary
鄂公網(wǎng)安備 42010302001612號 