数据结构与算法分析（C++版 第二版 英文原版） (2008 年度畅销榜NO.6988 )

本书采用了当前十分流行且适合于Internet 环境的面向对象的程序设计语言Java作为算法描述语言。本书利用Java的接口来定义抽象数据类型，并把数据结构原理和算法分析技术有机地结合在一起，系统地介绍了各种类型的数据结构和排序、检索的各种方法。
\r\n

I PRELIMINARIES\r\n\r\n1 Data Structures and Algorithms\r\n\r\n1.1 A Philosophy of Data Structures\r\n1.1.1 The Need for Data Structures\r\n1.1.2 Costs and Benefits\r\n1.2 Abstract Data Types and Data Structures\r\n1.3 Problems, Algorithms, and Programs\r\n1.4 Further Reading\r\n1.5 Exercises\r\n\r\n2 Mathematical Preliminaries\r\n\r\n2.1 Sets and Relations\r\n2.2 Miscellaneous Notation\r\n2.3 Logarithms\r\n2.4 Recursion\r\n2.5 Summations and Recurrences\r\n2.6 Mathematical Proof Techniques\r\n2.6.1 Proof by Contradiction\r\n2.6.2 Proof by Mathematical Induction\r\n2.7 Estimating\r\n2.8 Further Reading\r\n2.9 Exercises\r\n\r\n3 Algorithm Analysis\r\n\r\n3.1 Introduction\r\n3.2 Best, Worst, and Average Cases\r\n3.3 A Faster Computer, or a Faster Algorithm?\r\n3.4 Asymptotic Analysis\r\n3.4.1 Upper Bounds\r\n3.4.2 Lower Bounds\r\n3.4.3 O Notation\r\n3.4.4 Simplifying Rules\r\n3.5 Calculating the Running Time of a Program\r\n3.6 Analyzing Problems\r\n3.7 Common Misunderstandings\r\n3.8 Multiple Parameters\r\n3.9 Space Bounds\r\n3.10 Some Practical Considerations\r\n3.11 Further Reading\r\n3.12 Exercises\r\n3.13 Projects\r\n\r\nII FUNDAMENTAL DATA STRUCTURES\r\n\r\n4 Lists, Stacks, and Queues\r\n\r\n4.1 Lists\r\n4.1.1 Array--Based List Implementation\r\n4.1.2 Linked Lists\r\n4.1.3 Comparison of List Implementations\r\n4.1.4 Element Implementations\r\n4.1.5 Doubly Linked Lists\r\n4.2 The Dictionary ADT\r\n4.3 Stacks\r\n4.3.1 Array-Based Stacks\r\n4.3.2 Linked Stacks\r\n4.3.3 Comparison of Array--Based and Linked Stacks\r\n4.3.4 Implementing Recursion\r\n4.4 Queues\r\n4.4.1 Array-Based Queues\r\n4.4.2 Linked Queues\r\n4.4.3 Comparison of Array-Based and Linked Queues\r\n4.5 Further Reading\r\n4.6 Exercises\r\n4.7 Projects\r\n\r\n5 Binary Trees\r\n\r\n5.1 Definitions and Properties\r\n5.1.1 The Full Binary Tree Theorem\r\n5.1.2 A Binary Tree Node ADT\r\n5.2 Binary Tree Traversals\r\n5.3 Binary Tree Node Implementations\r\n5.3.1 Pointer-Based Node Implementations\r\n5.3.2 Space Requirements\r\n5.3.3 Array Implementation for Complete Binary Trees\r\n5.4 Binary Search Trees\r\n5.5 Heaps and Priority Queues\r\n5.6 Huffman Coding Trees\r\n5.6.1 Building Huffman Coding Trees\r\n5.6.2 Assigning and Using Huffman Codes\r\n5.7 Further Reading\r\n5.8 Exercises\r\n5.9 Projects\r\n\r\n6 Non-Binary Trees\r\n\r\n6.1 General Tree Definitions and Terminology\r\n6.1.1 An ADT for General Tree Nodes\r\n6.1.2 General Tree Traversals\r\n6.2 The Parent Pointer Implementation\r\n6.3 General Tree Implementations\r\n6.3.1 List of Children\r\n6.3.2 The Left-Child/Right-Sibling Implementation\r\n6.3.3 Dynamic Node Implementations\r\n6.3.4 Dynamic ''Left--Child/Right-Sibling'' Implementation\r\n6.4 K-ary Trees\r\n6.5 Sequential Tree Implementations\r\n6.6 Further Reading\r\n6.7 Exercises\r\n6.8 Projects\r\n\r\nIII Sorting and Searching\r\n\r\n7 Internal Sorting\r\n\r\n7.1 Sorting Terminology and Notation\r\n7.2 Three O(n) Sorting Algorithms\r\n7.2.1 Insertion Sort\r\n7.2.2 Bubble Sort\r\n7.2.3 Selection Sort\r\n7.2.4 The Cost of Exchange Sorting\r\n7.3 Shellsort\r\n7.4 Quicksort\r\n7.5 Mergesort\r\n7.6 Heapsort\r\n7.7 Binsort and Radix Sort\r\n7.8 An Empirical Comparison of Sorting Algorithms\r\n7.9 Lower Bounds for Sorting\r\n7.10 Further Reading\r\n7.11 Exercises\r\n7.12 Projects\r\n\r\n8 File Processing and External Sorting\r\n\r\n8.1 Primary versus Secondary Storage\r\n8.2 Disk Drives\r\n8.2.1 Disk Drive Architecture\r\n8.2.2 Disk Access Costs\r\n8.3 Buffers and Buffer Pools\r\n8.4 The Programmer's View of Files\r\n8.5 External Sorting\r\n8.6 Simple Approaches to External Sorting\r\n8.7 Replacement Selection\r\n8.8 Multiway Merging\r\n8.9 Further Reading\r\n8.10 Exercises\r\n8.11 Projects\r\n\r\n9 Searching\r\n\r\n9.1 Searching Sorted Arrays\r\n9.2 Self Organizing Lists\r\n9.3 Searching in Sets\r\n9.4 Hashing\r\n9.4.1 Hash Functions\r\n9.4.2 Open Hashing\r\n9.4.3 Closed Hashing\r\n9.5 Further Reading\r\n9.6 Exercises\r\n9.7 Projects\r\n\r\n10 Indexing\r\n\r\n10.1 Linear Indexing\r\n10.2 ISAM\r\n10.3 Tree Indexing\r\n10.4 2-3 Trees\r\n10.5 B-Trees\r\n10.5.1 B+-Trees\r\n10.5.2 B-Tree Analysis\r\n10.6 Further Reading\r\n10.7 Exercises\r\n10.8 Projects\r\n\r\nIV Applications and Advanced Topics\r\n\r\n11 Graphs\r\n\r\n11.1 Terminology and Representations\r\n11.2 Graph Implementations\r\n11.3 Graph Traversals\r\n11.3.1 Depth-First Search\r\n11.3.2 Breadth-First Search\r\n11.3.3 Topological Sort\r\n11.4 Shortest-Paths Problems\r\n11.4.1 Single-Source Shortest Paths\r\n11.4.2 All-Pairs Shortest Paths\r\n11.5 Minimum-Cost Spanning Trees\r\n11.5.1 Prim's Algorithm.\r\n11.5.2 Kruskal's Algorithm\r\n11.6 Further Reading\r\n11.7 Exercises\r\n11.8 Projects\r\n\r\n12 Lists and Arrays Revisited\r\n\r\n12.1 Skip Lists\r\n12.2 Multilists\r\n12.3 Matrix Representations\r\n12.4 Memory Management\r\n12.4.1 Dynamic Storage Allocation\r\n12.4.2 Failure Policies and Garbage Collection\r\n12.5 Further Reading\r\n12.6 Exercises\r\n12.7 Projects\r\n\r\n13 Advanced Tree Structures\r\n\r\n13.1 Tries\r\n13.2 Balanced Trees\r\n13.2.1 The AVL Tree\r\n13.2.2 The Splay Tree\r\n13.3 Spatial Data Structures\r\n13.3.1 The K-D Tree\r\n13.3.2 The PR quadtree\r\n13.3.3 Other Spatial Data Structures\r\n13.4 Further Reading\r\n13.5 Exercises\r\n13.6 Projects\r\n\r\n14 Analysis Techniques\r\n\r\n14.1 Summation Techniques\r\n14.2 Recurrence Relations\r\n14.2.1 Estimating Upper and Lower Bounds\r\n14.2.2 Expanding Recurrences\r\n14.2.3 Divide and Conquer Recurrences\r\n14.2.4 Average-Case Analysis of Quicksort\r\n14.3 Amortized Analysis\r\n14.4 Further Reading\r\n14.5 Exercises\r\n14.6 Projects\r\n\r\n15 Limits to Computation\r\n\r\n15.1 Reductions\r\n15.2 Hard Problems\r\n15.2.1 NP--Completeness\r\n15.2.2 Getting Around NP-Complete Problems\r\n15.3 Impossible Problems\r\n15.3.1 Uncountability\r\n15.3.2 The Halting Problem Is Unsolvable\r\n15.3.3 Determining Program Behavior Is Unsolvable\r\n15.4 Further Reading\r\n15.5 Exercises\r\n15.6 Projects\r\n\r\nV APPENDIX\r\nA Utility Functions\r\nBibliography\r\nIndex