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
鄂公网安备 42010302001612号 