Êý¾Ý½á¹¹ÓëËã·¨·ÖÎö(C++°æ) µÚÈý°æ Ó¢ÎÄ°æ

¢ñ Preliminaries
1 Data Structures and Algorithms
1£®1 A Philosophy of Data Structures
1£®1£®1 The Need for Data Structures
1£®1£®2 Costs and Benefits
1£®2 Abstract Data Types and Data Structures
1£®3 Design Patterns
1£®3£®1 Flyweight
1£®3£®2 Visitor
1£®3£®3 Composite
1£®3£®4 Strategy
1£®4 Problems£¬ Algorithms£¬ and Programs
1£®5 Further Reading
1£®6 Exercises
2 Mathematical Preliminaries
2£®1 Sets and Relations
2£®2 Miscellaneous Notation
2£®3 Logarithms
2£®4 Summations and Recurrences
2£®5 Recursion
2£®6 Mathematical Proof Techniques
2£®6£®1 Direct Proof
2£®6£®2 Proof by Contradiction
2£®6£®3 Proof by Mathematical Induction
2£®7 Estimation
2£®8 Further Reading
2£®9 Exercises
3 Algorithm Analysis
3£®1 Introduction
3£®2 Best£¬ Worst£¬ and Average Cases
3£®3 A Faster Computer£¬ or a Faster Algorithm?
3£®4 Asymptotic Analysis
3£®4£®1 Upper Bounds
3£®4£®2 Lower Bounds
3£®4£®3 Notation
3£®4£®4 Simplifying Rules
3£®4£®5 Classifying Functions
3£®5 Calculating the Running Time for a Program
3£®6 Analyzing Problems
3£®7 Common Misunderstandings
3£®8 Multiple Parameters
3£®9 Space Bounds
3£®10 Speeding Up Your Programs
3£®11 Empirical Analysis
3£®12 Further Reading
3£®13 Exercises
3£®14 Projects

¢ò Fundamental Data Structures
4 Lists£¬ Stacks£¬ and Queues
4£®1 Lists
4£®1£®1 Array-Based List Implementation
4£®1£®2 Linked Lists
4£®1£®3 Comparison of List Implementations
4£®1£®4 Element Implementations
4£®1£®5 Doubly Linked Lists
4£®2 Stacks
4£®2£®1 Array-Based Stacks
4£®2£®2 Linked Stacks
4£®2£®3 Comparison of Array-Based and Linked Stacks
4£®2£®4 Implementing Recursion
4£®3 Queues
4£®3£®1 Array-Based Queues
4£®3£®2 Linked Queues
4£®3£®3 Comparison of Array-Based and Linked Queues
4£®4 Dictionaries
4£®5 Further Reading
4£®6 Exercises
4£®7 Projects
5 Binary Trees
5£®1 Definitions and Properties
5£®1£®1 The Full Binary Tree Theorem
5£®1£®2 A Binary Tree Node ADT
5£®2 Binary Tree Traversals
5£®3 Binary Tree Node Implementations
5£®3£®1 Pointer-Based Node Implementations
5£®3£®2 Space Requirements
5£®3£®3 Array Implementation for Complete Binary Trees
5£®4 Binary Search Trees
5£®5 Heaps and Priority Queues
5£®6 Huffman Coding Trees
5£®6£®1 Building Huffman Coding Trees
5£®6£®2 Assigning and Using Huffman Codes
5£®6£®3 Search in Huffman Trees
5£®7 Further Reading
5£®8 Exercises
5£®9 Projects
6 Non-Binary Trees
6£®1 General Tree Definitions and Terminology
6£®1£®1 An ADT for General Tree Nodes
6£®1£®2 General Tree Traversals
6£®2 The Parent Pointer Implementation
6£®3 General Tree Implementations
6£®3£®1 List of Children
6£®3£®2 The Left-Child/Right-Sibling Implementation
6£®3£®3 Dynamic Node Implementations
6£®3£®4 Dynamic ¡°Left-Child/Right-Sibling¡± Implementation
6£®4 K-ary Trees
6£®5 Sequential Tree Implementations
6£®6 Further Reading
6£®7 Exercises
6£®8 Projects

¢ó Sorting and Searching
7 Internal Sorting
7£®1 Sorting Terminology and Notation
7£®2 Three¡õ£¨n2£© Sorting Algorithms
7£®2£®1 Insertion Sort
7£®2£®2 Bubble Sort
7£®2£®3 Selection Sort
7£®2£®4 The Cost of Exchange Sorting
7£®3 Shellsort
7£®4 Mergesort
7£®5 Quicksort
7£®6 Heapsort
7£®7 Binsort and Radix Sort
7£®8 An Empirical Comparison of Sorting Algorithms
7£®9 Lower Bounds for Sorting
7£®10 Further Reading
7£®11 Exercises
7£®12 Projects
8 File Processing and External Sorting
8£®1 Primary versus Secondary Storage
8£®2 Disk Drives
8£®2£®1 Disk Drive Architecture
8£®2£®2 Disk Access Costs
8£®3 Buffers and Buffer Pools
8£®4 The Programmer¡¯s View of Files
8£®5 External Sorting
8£®5£®1 Simple Approaches to External Sorting
8£®5£®2 Replacement Selection
8£®5£®3 Multiway Merging
8£®6 Further Reading
8£®7 Exercises
8£®8 Projects
9 Searching
9£®1 Searching Unsorted and Sorted Arrays
9£®2 Self-Organizing Lists
9£®3 Bit Vectors for Representing Sets
9£®4 Hashing
9£®4£®1 Hash Functions
9£®4£®2 Open Hashing
9£®4£®3 Closed Hashing
9£®4£®4 Analysis of Closed Hashing
9£®4£®5 Deletion
9£®5 Further Reading
9£®6 Exercises
9£®7 Projects
10 Indexing
10£®1 Linear Indexing
10£®2 ISAM
10£®3 Tree-based Indexing
10£®4 2-3 Trees
10£®5 B-Trees
10£®5£®1 B+-Trees
10£®5£®2 B-Tree Analysis
10£®6 Further Reading
10£®7 Exercises
10£®8 Projects

¢ô Advanced Data Structures
11 Graphs
11£®1 Terminology and Representations
11£®2 Graph Implementations
11£®3 Graph Traversals
11£®3£®1 Depth-First Search
11£®3£®2 Breadth-First Search
11£®3£®3 Topological Sort
11£®4 Shortest-Paths Problems
11£®4£®1 Single-Source Shortest Paths
11£®5 Minimum-Cost Spanning Trees
11£®5£®1 Prim¡¯s Algorithm
11£®5£®2 Kruskal¡¯s Algorithm
11£®6 Further Reading
11£®7 Exercises
11£®8 Projects
12 Lists and Arrays Revisited
12£®1 Multilists
12£®2 Matrix Representations
12£®3 Memory Management
12£®3£®1 Dynamic Storage Allocation
12£®3£®2 Failure Policies and Garbage Collection
12£®4 Further Reading
12£®5 Exercises
12£®6 Projects
13 Advanced Tree Structures
13£®1 Tries
13£®2 Balanced Trees
13£®2£®1 The AVL Tree
13£®2£®2 The Splay Tree
13£®3 Spatial Data Structures
13£®3£®1 The K-D Tree
13£®3£®2 The PR quadtree
13£®3£®3 Other Point Data Structures
13£®3£®4 Other Spatial Data Structures
13£®4 Further Reading
13£®5 Exercises
13£®6 Projects

¢õ Theory of Algorithms
14 Analysis Techniques
14£®1 Summation Techniques
14£®2 Recurrence Relations
14£®2£®1 Estimating Upper and Lower Bounds
14£®2£®2 Expanding Recurrences
14£®2£®3 Divide and Conquer Recurrences
14£®2£®4 Average-Case Analysis of Quicksort
14£®3 Amortized Analysis
14£®4 Further Reading
14£®5 Exercises
14£®6 Projects
15 Lower Bounds
15£®1 Introduction to Lower Bounds Proofs
15£®2 Lower Bounds on Searching Lists
15£®2£®1 Searching in Unsorted Lists
15£®2£®2 Searching in Sorted Lists
15£®3 Finding the Maximum Value
15£®4 Adversarial Lower Bounds Proofs
15£®5 State Space Lower Bounds Proofs
15£®6 Finding the ith Best Element
15£®7 Optimal Sorting
15£®8 Further Reading
15£®9 Exercises
15£®10 Projects
16 Patterns of Algorithms
16£®1 Dynamic Programming
16£®1£®1 The Knapsack Problem
16£®1£®2 All-Pairs Shortest Paths
16£®2 Randomized Algorithms
16£®2£®1 Randomized algorithms for finding large values
16£®2£®2 Skip Lists
16£®3 Numerical Algorithms
16£®3£®1 Exponentiation
16£®3£®2 Largest Common Factor
16£®3£®3 Matrix Multiplication
16£®3£®4 Random Numbers
16£®3£®5 The Fast Fourier Transform
16£®4 Further Reading
16£®5 Exercises
16£®6 Projects
17 Limits to Computation
17£®1 Reductions
17£®2 Hard Problems
17£®2£®1 The Theory of NP-Completeness
17£®2£®2 NP-Completeness Proofs
17£®2£®3 Coping with NP-Complete Problems
17£®3 Impossible Problems
17£®3£®1 Uncountability
17£®3£®2 The Halting Problem Is Unsolvable
17£®4 Further Reading
17£®5 Exercises
17£®6 Projects

¢ö APPENDIX
A Utility Functions
Bibliography
Index