Java數(shù)據(jù)結構與算法分析（影印版）

Contents                  
 Chapter 1  Introduction                  
 1.1. What's the Book About?                  
 1.2. Mathematics Review                  
 1.2.1. Exponents                  
 1.2.2. Logarithms                  
 1.2.3. Series                  
 1.2.4. Modular Arithmetic                  
 1.2.5. The P Word                  
 1.3. A Brief Introduction to Recursion                  
 1.4. Genetic Objects in Java                  
 1.4.1. The IntCell Class                  
 1.4.2. The MemoryCell Class                  
 1.4.3. Implementing Genetic findMax                  
 1.5. Exceptions                  
 1.6. Input and Output                  
 1.6.1. Basic Stream Operations                  
 1.6.2. The StringTokenizer Object                  
 1.6.3. Sequential Files                  
 1.7. Code Organization                  
 1.7.1. Packages                  
 1.7.2. The MyInteger Class                  
 1.7.3. Efficiency Considerations                  
 Summary                  
 Exercises                  
 References                  
 Chapter 2 Algorithm Analysis                  
 2.1. Mathematical Background                  
 2.2. Model                  
 2.3. What to Analyze                  
 2.4. Running Time Calculations                  
 2.4.1. 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 Grain of Salt                  
 Summary                  
 Exercises                  
 References                  
 Chapter 3 Lists, Stacks, and Queues                  
 3.1. Abstract Data Types (ADTS)                  
 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. Doubly Linked Lists                  
 3.2.5. Circular Linked Lists                  
 3.2.6. Examples                  
 3.2.7. Cursor Implementation of Linked Lists                  
 3.3. The Stack ADT                  
 3.3.1. Stack Model                  
 3.3.2. Implementation of Stacks                  
 3.3.3. Applications                  
 3.4. The Queue ADT                  
 3.4.1. Queue Model                  
 3.4.2. Array Implementation of Queues                  
 3.4.3. Applications of Queues                  
 Summary                  
 Exercises                  
 Chapter 4 Trees                  
 4.1. Preliminaries                  
 4.1.1. Implementation of Trees                  
 4.1.2. Tree Traversals with an Application                  
 4.2. Binary Trees                  
 4.2.1. Implementation                  
 4.2.2. An Example: Expression Trees                  
 4.3. The Search Tree ADT--Binary Search Trees                  
 4.3.1. find                  
 4.3.2. findMin and findMax                  
 4.3.3. insert                  
 4.3.4. remove                  
 4.3.5. Average-Case Analysis                  
 4.4. AVL Trees                  
 4.4.1. Single Rotation                  
 4.4.2. Double Rotation                  
 4.5. Splay Trees                  
 4.5.1. 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.1. General Idea                  
 5.2. Hash Function                  
 5.3. Separate Chaining                  
 5.4. Open Addressing                  
 5.4.1. Linear Probing                  
 5.4.2. Quadratic Probing                  
 5.4.3. Double Hashing                  
 5.5. Rehashing                  
 5.6. Extendible Hashing                  
 Summary                  
 Exercises                  
 References                  
 Chapter 6 Priority Queues (Heaps)                  
 6.1. Model                  
 6.2. Simple Implementations                  
 6.3. Binary Heap                  
 6.3.1. 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.1. The Selection Problem                  
 6.4.2. Event Simulation                  
 6.5. d-Heaps                  
 6.6. Leftist Heaps                  
 6.6.1. Leftist Heap Property                  
 6.6.2. Leftist Heap Operations                  
 6.7. Skew Heaps                  
 6.8. Binomial Queues                  
 6.8.1. Binomial Queue Structure                  
 6.8.2. Binomial Queue Operations                  
 6.8.3. Implementation of Binomial Queues                  
 Summary                  
 Exercises                  
 References                  
 Chapter 7 Sorting                  
 7.2. Insertion Sort                  
 7.2.1. The Algorithm                  
 7.2.2. Analysis of Insertion Sort                  
 7.3. A Lower Bound for Simple Sorting Algorithms                  
 7.4. Shellsort                  
 7.4.1. Worst-Case Analysis of Shellsort                  
 7.5. Heapsort                  
 7.5.1. Analysis of Heapsort                  
 7.6. Mergesort                  
 7.6.1. Analysis of Mergesort                  
 7.7. Quicksort                  
 7.7.1. Picking the Pivot                  
 7.7.2. Partitioning Strategy                  
 7.7.3. Small Arrays                  
 7.7.4. Actual Quicksort Routines                  
 7.7.5. Analysis of Quicksort                  
 7.7.6. A Linear-Expected-Time Algorithm for Selection                  
 7.8. A General Lower Bound for Sorting                  
 7.8.1. Decision Trees                  
 7.9. Bucket Sort                  
 7.10. External Sorting                  
 7.10.1. Why We Need New Algorithms                  
 7.10.2. Model for External Sorting                  
 7.10.3. The Simple Algorithm                  
 7.10.4. Multiway Merge                  
 7.10.5. Polyphase Merge                  
 7.10.6. Replacement Selection                  
 Summary                  
 Exercises                  
 References                  
 Chapter 8 The Disjoint Set ADT                  
 8.1. 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.1. Analysis of the Union/Find Algorithm                  
 8.7. An Application                  
 Summary                  
 Exercises                  
 References                  
 Chapter 9 Graph Algorithms                  
 9.1. Definitions                  
 9.1.1. Representation of Graphs                  
 9.2. Topological Sort                  
 9.3. Shortest-Path Algorithms                  
 9.3.1. Unweighted Shortest Paths                  
 9.3.2. Dijkstra's Algorithm                  
 9.3.3. Graphs with Negative Edge Costs                  
 9.3.4. Acyclic Graphs                  
 9.3.5. All-Pairs Shortest Path                  
 9.4. Network Flow Problems                  
 9.4.1. A Simple Maximum-Flow Algorithm                  
 9.5. Minimum Spanning Tree                  
 9.5.1. Prim's Algorithm                  
 9.5.2. Kruskal's Algorithm                  
 9.6. Applications of Depth-First Search                  
 9.6.1. Undirected Graphs                  
 9.6.5. Biconnectivity                  
 9.6.3. Euler Circuits                  
 9.6.5. Finding Strong Components                  
 9.7. Introduction to NP-Completeness                  
 9.7.1. Easy vs. Hard                  
 9.7.2. The Class NP                  
 9.7.3. NP-Complete Problems                  
 Summary                  
 Exercises                  
 References                  
 Chapter 10 Algorithm Design Techniques                  
 10.1. Greedy Algorithms                  
 10.1.1. A Simple Scheduling Problem                  
 10.1.2. Huffman Codes                  
 10.1.3. Approximate Bin Packing                  
 10.2. Divide and Conquer                  
 10.2.1. Running Time of Divide                  
 and Conquer Algorithms                  
 10.2.2. Closest-Points Problem                  
 10.2.3. The Selection Problem                  
 10.2.4. Theoretical Improvements                  
 for Arithmetic Problems                  
 10.3. Dynamic Programming                  
 10.3.1. Using a Table Instead of Recursion                  
 10.3.2. Ordering Matrix Multiplications                  
 10.3.3. Optimal Binary Search Tree                  
 10.3.4. All-Pairs Shortest Path                  
 10.4. Randomized Algorithms                  
 10.4.1. Random Number Generators                  
 10.4.2. Skip Lists                  
 10.4.3. Primality Testing                  
 10.5. Backtracking Algorithms                  
 10.5.1. The Turnpike Reconstruction Problem                  
 10.5.2. Games                  
 Summary                  
 Exercises                  
 References                  
 Chapter 11 Amortized Analysis                  
 11.1. An Unrelated Puzzle                  
 11.2. Binomial Queues                  
 11.3. Skew Heaps                  
 11.4. Fibonacci Heaps                  
 11.4.1. Cutting Nodes in Leftist Heaps                  
 11.4.2. Lazy Merging for Binomial Queues                  
 11.4.3. The Fibonacci Heap Operations                  
 11.4.4. Proof of the Time Bound                  
 11.5  Splay Trees                  
 Summary                  
 Exercises                  
 References                  
 Chapter 12 Advanced Data Structures                  
 and Implementation                  
 12.1. Top-Down Splay Trees                  
 12.2. Red-Black Trees                  
 12.2.1. Bottom-Up Insertion                  
 12.2.2. Top-Down Red-Black Trees                  
 12.2.3. Top-Down Deletion                  
 12.3. Deterministic Skip Lists                  
 12.4. AA-Trees                  
 12.5. Treaps                  
 12.6. k-d Trees                  
 12.7. Pairing Heaps                  
 Summary                  
 Exercises                  
 References                  
 Appendix A Some Library Routines                  
 A. 1. Classes in Package java.lang                  
 A.1.1. Character                  
 A.1.2. Integer                  
 A.1.3. Object                  
 A.1.4. String                  
 A.1.5. StringBuffer                  
 A.1.6. System                  
 A.1.7. Throwable                  
 A.2. Classes in Package java.io                  
 A.2.1. BufferedReader                  
 A.2.2. BufferedWriter                  
 A.2.3. File                  
 A.2.4. FileReader                  
 A.2.5. FileWriter                  
 A.2.6. InputStreamReader                  
 A.2.7. PrintWriter                  
 A.2.8. PushbackReader                  
 A.3. Classes in Package java.util                  
 A.3.1. Random                  
 A.3.2. StringTokenizer                  
 Appendix B The Collections Library                  
 B.1. Introduction                  
 B.2. Basic Classes                  
 B.2.1. Collection                  
 B.2.2. Iterator                  
 B.2.3. Comparable                  
 B.2.4. Comparator                  
 B.3. Lists                  
 B.3.1. ArrayList vs. LinkedList                  
 B.3.2. Stacks and Queues                  
 B.3.3. ListIterator                  
 B.4. Sets                  
 B.5. Maps                  
 B.5.1. put, get, remove, and contains                  
 B.5.2. Getting a Collection from the Map                  
 B.5.3. Map. Entry Pairs                  
 B.6. Example: Generating a Concordance                  
 B.6.1. Collections API Version                  
 B.6.2. Version Using Package DataStructures                  
 B.7. Example: Shortest-Path Calculation                  
 B.7.1. Collections API Implementation                  
 B.7.7. Version Using Package DataStructures                  
 B.8. Priority Queues                  
 Summary                  
 Index