《數據結構與算法分析（C++版）（第三版）（英文版）》是2013年1月電子工業出版社出版的圖書，作者是Clifford A. Shaffer （克利福德 A. 謝弗）。
基本介紹
- 中文名：數據結構與算法分析（C++版）（第三版）（英文版）
- 作者：Clifford A. Shaffer （克利福德 A. 謝弗）
- ISBN：9787121192609
- 頁數：612頁
- 定價：99元
- 出版社：電子工業出版社
- 出版時間：2013年1月
- 開本：16開
內容簡介,目錄,
內容簡介
本書採用程式設計師最愛用的面向對象C++語言來描述數據結構淚去提和多拘笑算法，並把數據結構原理和算法分析技術有機地結合在一起，系統介紹淋厚了各種類型的數據結構和排序、檢索的各種方法。局蜜料應作者非常注意對每一種數據結構的不同存儲方法及有關算法進行分析比較。書中還引入了一些比較高級的數據結構與汗捉棕邀先進的算法分析技術，並介紹了可計算性理論的一般知識。本版的重要改進在於引入了參數化的模板，從而提熱店腿高了算法中數據類型的通用性，支持高狼囑兆效的代碼重用。
目錄
Preface
Part I Preliminaries
Chapter 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
Chapter 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
Chapter 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
Part II Fundamental Data Structures
Chapter 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
Chapter 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
Chapter 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
Part III Sorting and Searching
Chapter 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
Chapter 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
Chapter 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
Chapter 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
Part IV Advanced Data Structures
Chapter 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
Chapter 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
Chapter 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
Part V 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
Chapter 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
Chapter 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
Chapter 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
Part VI APPENDIX
A Utility Functions
Bibliography
Index,Preface
Part I Preliminaries
Chapter 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
Chapter 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
Chapter 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
Part II Fundamental Data Structures
Chapter 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
Chapter 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
Chapter 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
Part III Sorting and Searching
Chapter 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
Chapter 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
Chapter 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
Chapter 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
Part IV Advanced Data Structures
Chapter 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
Chapter 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
Chapter 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
Part V 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
Chapter 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
Chapter 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
Chapter 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
Part VI APPENDIX
A Utility Functions
Bibliography
Index
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
Part II Fundamental Data Structures
Chapter 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
Chapter 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
Chapter 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
Part III Sorting and Searching
Chapter 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
Chapter 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
Chapter 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
Chapter 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
Part IV Advanced Data Structures
Chapter 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
Chapter 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
Chapter 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
Part V 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
Chapter 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
Chapter 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
Chapter 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
Part VI APPENDIX
A Utility Functions
Bibliography
Index,Preface
Part I Preliminaries
Chapter 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
Chapter 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
Chapter 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
Part II Fundamental Data Structures
Chapter 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
Chapter 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
Chapter 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
Part III Sorting and Searching
Chapter 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
Chapter 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
Chapter 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
Chapter 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
Part IV Advanced Data Structures
Chapter 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
Chapter 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
Chapter 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
Part V 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
Chapter 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
Chapter 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
Chapter 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
Part VI APPENDIX
A Utility Functions
Bibliography
Index
