数学分析葵花宝典

Data structures and algorithms is a fundamental course in Computer Science, which enables learners across any discipline to develop the much-needed foundation of efficient programming, leading to better problem solving in their respective disciplines. A Textbook of Data Structures and Algorithms is a textbook that can be used as course material in classrooms, or as self-learning material. The book targets novice learners aspiring to acquire advanced knowledge of the topic. Therefore, the content of the book has been pragmatically structured across three volumes and kept comprehensive enough to help them in their progression from novice to expert. With this in mind, the book details concepts, techniques and applications pertaining to data structures and algorithms, independent of any programming language. It includes 181 illustrative problems and 276 review questions to reinforce a theoretical understanding and presents a suggestive list of 108 programming assignments to aid in the implementation of the methods covered. Cover 1 Title Page 5 Copyright Page 6 Contents 7 Preface 13 Acknowledgments 19 Chapter 13. Hash Tables 21 13.1. Introduction 21 13.1.1. Dictionaries 21 13.2. Hash table structure 22 13.3. Hash functions 24 13.3.1. Building hash functions 24 13.4. Linear open addressing 25 13.4.1. Operations on linear open addressed hash tables 28 13.4.2. Performance analysis 30 13.4.3. Other collision resolution techniques with open addressing 31 13.5. Chaining 33 13.5.1. Operations on chained hash tables 35 13.5.2. Performance analysis 37 13.6. Applications 38 13.6.1. Representation of a keyword table in a compiler 38 13.6.2. Hash tables in the evaluation of a join operation on relational databases 39 13.6.3. Hash tables in a direct file organization 42 13.7. Illustrative problems 43 Chapter 14. File Organizations 53 14.1. Introduction 53 14.2. Files 54 14.3. Keys 56 14.4. Basic file operations 58 14.5. Heap or pile organization 58 14.5.1. Insert, delete and update operations 59 14.6. Sequential file organization 59 14.6.1. Insert, delete and update operations 59 14.6.2. Making use of overflow blocks 60 14.7. Indexed sequential file organization 61 14.7.1. Structure of the ISAM files 61 14.7.2. Insert, delete and update operations for a naïve ISAM file 62 14.7.3. Types of indexing 63 14.8. Direct file organization 68 14.9. Illustrative problems 70 Chapter 15. k-d Trees and Treaps 81 15.1. Introduction 81 15.2. k-d trees: structure and operations 81 15.2.1. Construction of a k-d tree 85 15.2.2. Insert operation on k-d trees 89 15.2.3. Find minimum operation on k-d trees 90 15.2.4. Delete operation on k-d trees 92 15.2.5. Complexity analysis and applications of k-d trees 94 15.3. Treaps: structure and operations 96 15.3.1. Treap structure 96 15.3.2. Operations on treaps 97 15.3.3. Complexity analysis and applications of treaps 102 15.4. Illustrative problems 103 Chapter 16. Searching 113 16.1. Introduction 113 16.2. Linear search 114 16.2.1. Ordered linear search 114 16.2.2. Unordered linear search 114 16.3. Transpose sequential search 116 16.4. Interpolation search 118 16.5. Binary search 120 16.5.1. Decision tree for binary search 121 16.6. Fibonacci search 124 16.6.1. Decision tree for Fibonacci search 125 16.7. Skip list search 128 16.7.1. Implementing skip lists 132 16.7.2. Insert operation in a skip list 133 16.7.3. Delete operation in a skip list 134 16.8. Other search techniques 136 16.8.1. Tree search 136 16.8.2. Graph search 136 16.8.3. Indexed sequential search 136 16.9. Illustrative problems 138 Chapter 17. Internal Sorting 151 17.1. Introduction 151 17.2. Bubble sort 152 17.2.1. Stability and performance analysis 154 17.3. Insertion sort 155 17.3.1. Stability and performance analysis 156 17.4. Selection sort 158 17.4.1. Stability and performance analysis 160 17.5. Merge sort 160 17.5.1. Two-way merging 161 17.5.2. k-way merging 163 17.5.3. Non-recursive merge sort procedure 164 17.5.4. Recursive merge sort procedure 165 17.6. Shell sort 167 17.6.1. Analysis of shell sort 173 17.7. Quick sort 173 17.7.1. Partitioning 173 17.7.2. Quick sort procedure 176 17.7.3. Stability and performance analysis 178 17.8. Heap sort 179 17.8.1. Heap 179 17.8.2. Construction of heap 180 17.8.3. Heap sort procedure 183 17.8.4. Stability and performance analysis 187 17.9. Radix sort 187 17.9.1. Radix sort method 187 17.9.2. Most significant digit first sort 191 17.9.3. Performance analysis 191 17.10. Counting sort 191 17.10.1. Performance analysis 195 17.11. Bucket sort 195 17.11.1. Performance analysis 198 17.12. Illustrative problems 199 Chapter 18. External Sorting 217 18.1. Introduction 217 18.1.1. The principle behind external sorting 217 18.2. External storage devices 218 18.2.1. Magnetic tapes 219 18.2.2. Magnetic disks 220 18.3. Sorting with tapes: balanced merge 222 18.3.1. Buffer handling 224 18.3.2. Balanced P-way merging on tapes 225 18.4. Sorting with disks: balanced merge 226 18.4.1. Balanced k-way merging on disks 227 18.4.2. Selection tree 228 18.5. Polyphase merge sort 232 18.6. Cascade merge sort 234 18.7. Illustrative problems 236 Chapter 19. Divide and Conquer 249 19.1. Introduction 249 19.2. Principle and abstraction 249 19.3. Finding maximum and minimum 251 19.3.1. Time complexity analysis 252 19.4. Merge sort 253 19.4.1. Time complexity analysis 253 19.5. Matrix multiplication 254 19.5.1. Divide and Conquer-based approach to “high school” method of matrix multiplication 254 19.5.2. Strassen’s matrix multiplication algorithm 256 19.6. Illustrative problems 259 Chapter 20. Greedy Method 265 20.1. Introduction 265 20.2. Abstraction 265 20.3. Knapsack problem 266 20.3.1. Greedy solution to the knapsack problem 267 20.4. Minimum cost spanning tree algorithms 269 20.4.1. Prim's algorithm as a greedy method 270 20.4.2. Kruskal's algorithm as a greedy method 270 20.5. Dijkstra's algorithm 271 20.6. Illustrative problems 271 Chapter 21. Dynamic Programming 281 21.1. Introduction 281 21.2. 0/1 knapsack problem 283 21.2.1. Dynamic programming-based solution 284 21.3. Traveling salesperson problem 286 21.3.1. Dynamic programming-based solution 287 21.3.2. Time complexity analysis and applications of traveling salesperson problem 289 21.4. All-pairs shortest path problem 289 21.4.1. Dynamic programming-based solution 290 21.4.2. Time complexity analysis 292 21.5. Optimal binary search trees 292 21.5.1. Dynamic programming-based solution 294 21.5.2. Construction of the optimal binary search tree 296 21.5.3. Time complexity analysis 299 21.6. Illustrative problems 300 Chapter 22. P and NP Class of Problems 307 22.1. Introduction 307 22.2. Deterministic and nondeterministic algorithms 309 22.3. Satisfiability problem 312 22.3.1. Conjunctive normal form and Disjunctive normal form 314 22.3.2. Definition of the satisfiability problem 314 22.3.3. Construction of CNF and DNF from a logical formula 315 22.3.4. Transformation of a CNF into a 3-CNF 316 22.3.5. Deterministic algorithm for the satisfiability problem 317 22.3.6. Nondeterministic algorithm for the satisfiability problem 317 22.4. NP-complete and NP-hard problems 317 22.4.1. Definitions 318 22.5. Examples of NP-hard and NP-complete problems 320 22.6. Cook's theorem 322 22.7. The unsolved problem P ? = NP 323 22.8. Illustrative problems 324 References 331 Index 333 Summaries of other volumes 337 EULA 356