I 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 Problems, Algorithms, and Programs
1.4 Further Reading
1.5 Exercises
2 Mathematical Preliminaries
2.1 Sets and Relations
2.2 Miscellaneous Notation
2.3 Logarithms
2.4 Recursion
2.5 Summations and Recurrences
2.6 Mathematical Proof Techniques
2.6.1 Proof by Contradiction
2.6.2 Proof by Mathematical Induction
2.7 Estimating
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 O Notation
3.4.4 Simplifying Rules
3.5 Calculating the Running Time of a Program
3.6 Analyzing Problems
3.7 Common Misunderstandings
3.8 Multiple Parameters
3.9 Space Bounds
3.10 Some Practical Considerations
3.11 Further Reading
3.12 Exercises
3.13 Projects
II 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 The Dictionary ADT
4.3 Stacks
4.3.1 Array-Based Stacks
4.3.2 Linked Stacks
4.3.3 Comparison of Array--Based and Linked Stacks
4.3.4 Implementing Recursion
4.4 Queues
4.4.1 Array-Based Queues
4.4.2 Linked Queues
4.4.3 Comparison of Array-Based and Linked Queues
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.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
III Sorting and Searching
7 Internal Sorting
7.1 Sorting Terminology and Notation
7.2 Three O(n) 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 Quicksort
7.5 Mergesort
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.6 Simple Approaches to External Sorting
8.7 Replacement Selection
8.8 Multiway Merging
8.9 Further Reading
8.10 Exercises
8.11 Projects
9 Searching
9.1 Searching Sorted Arrays
9.2 Self Organizing Lists
9.3 Searching in Sets
9.4 Hashing
9.4.1 Hash Functions
9.4.2 Open Hashing
9.4.3 Closed Hashing
9.5 Further Reading
9.6 Exercises
9.7 Projects
10 Indexing
10.1 Linear Indexing
10.2 ISAM
10.3 Tree 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
IV Applications and Advanced Topics
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.4.2 All-Pairs 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 Skip Lists
12.2 Multilists
12.3 Matrix Representations
12.4 Memory Management
12.4.1 Dynamic Storage Allocation
12.4.2 Failure Policies and Garbage Collection
12.5 Further Reading
12.6 Exercises
12.7 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 Spatial Data Structures
13.4 Further Reading
13.5 Exercises
13.6 Projects
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 Limits to Computation
15.1 Reductions
15.2 Hard Problems
15.2.1 NP--Completeness
15.2.2 Getting Around NP-Complete Problems
15.3 Impossible Problems
15.3.1 Uncountability
15.3.2 The Halting Problem Is Unsolvable
15.3.3 Determining Program Behavior Is Unsolvable
15.4 Further Reading
15.5 Exercises
15.6 Projects
V APPENDIX
A Utility Functions
Bibliography
Index
鄂公网安备 42010302001612号 