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
鄂公網(wǎng)安備 42010302001612號 