数据结构与算法分析(C++版第3版英文版)/国外计算机科学教材系列

本书采用程序员偏爱的面向对象C++语言来描述数据结构和算法，并把数据结构原理和算法分析技术有机地结合在一起，系统介绍了各种类型的数据结构和排序、检索的各种方法。作者非常注意对每一种数据结构的不同存储方法及有关算法进行分析比较。书中还引入了一些比较高级的数据结构与先进的算法分析技术，并介绍了可计算性理论的一般知识。书中分别给出了C++实现方法和伪码实现方法，便于读者根据情况选择。在作者维护的网站可下载相关代码、编程项目和辅助练习资料。本书已根据作者在网站提供的勘误表进行过内容更正。

Clifford A. Shaffer教授于美国马里兰大学获得计算机科学博士学位，在弗吉尼亚理工大学计算机科学系任教超过30年，具有丰富的教学经验，并参与遗传学、生物信息学和计算生物学等交叉项目。著有多本数据结构和算法分析的教材。

Contents Part I Preliminaries 预备知识 Chapter 1 Data Structures and Algorithms 数据结构和算法 3 1.1 A Philosophy of Data Structures 数据结构的原则 4 1.1.1 The Need for Data Structures 学习数据结构的必要性 4 1.1.2 Costs and Benefits 代价与效益 6 1.2 Abstract Data Types and Data Structures 抽象数据类型和数据结构 8 1.3 Design Patterns 设计模式 12 1.3.1 Flyweight 享元模式 13 1.3.2 Visitor 访问者模式 13 1.3.3 Composite 组合模式 14 1.3.4 Strategy 策略模式 15 1.4 Problems, Algorithms, and Programs 问题、算法和程序 16 1.5 Further Reading 深入学习导读 18 1.6 Exercises 习题 20 Chapter 2 Mathematical Preliminaries 数学预备知识 25 2.1 Sets and Relations 集合和关系 25 2.2 Miscellaneous Notation 常用数学术语 29 2.3 Logarithms 对数 31 2.4 Summations and Recurrences 级数求和与递归 32 2.5 Recursion 递归 36 2.6 Mathematical Proof Techniques 数学证明方法 38 2.6.1 Direct Proof 直接证明法 39 2.6.2 Proof by Contradiction 反证法 39 2.6.3 Proof by Mathematical Induction 数学归纳法 40 2.7 Estimation 估计 46 2.8 Further Reading 深入学习导读 47 2.9 Exercises 习题 48 Chapter 3 Algorithm Analysis 算法分析 55 3.1 Introduction 概述 55 3.2 Best, Worst, and Average Cases 最佳、最差和平均情况 61 3.3 A Faster Computer, or a Faster Algorithm 换一台更快的计算机，还是换一种更快的算法 62 3.4 Asymptotic Analysis 渐近分析 65 3.4.1 Upper Bounds 上限 65 3.4.2 Lower Bounds 下限 67 3.4.3 Θ Notation Θ表示法 68 3.4.4 Simplifying Rules 化简法则 69 3.4.5 Classifying Functions 函数分类 70 3.5 Calculating the Running Time for a Program 程序运行时间的计算 71 3.6 Analyzing Problems 问题的分析 76 3.7 Common Misunderstandings 容易混淆的概念 77 3.8 Multiple Parameters 多参数问题 79 3.9 Space Bounds 空间代价 80 3.10 Speeding Up Your Programs 加速你的程序 82 3.11 Empirical Analysis 实证分析 85 3.12 Further Reading 深入学习导读 86 3.13 Exercises 习题 86 3.14 Projects 项目设计 90 Part II Fundamental Data Structures 基本数据结构 Chapter 4 Lists, Stacks, and Queues 线性表、栈和队列 95 4.1 Lists 线性表 96 4.1.1 Array-Based List Implementation 顺序表的实现 100 4.1.2 Linked Lists 链表 103 4.1.3 Comparison of List Implementations 线性表实现方法的比较 112 4.1.4 Element Implementations 元素的表示 114 4.1.5 Doubly Linked Lists 双链表 115 4.2 Stacks 栈 120 4.2.1 Array-Based Stacks 顺序栈 121 4.2.2 Linked Stacks 链式栈 123 4.2.3 Comparison of Array-Based and Linked Stacks 顺序栈与链式栈的比较 123 4.2.4 Implementing Recursion 递归的实现 125 4.3 Queues 队列 127 4.3.1 Array-Based Queues 顺序队列 128 4.3.2 Linked Queues 链式队列 133 4.3.3 Comparison of Array-Based and Linked Queues 顺序队列与链式队列的比较 133 4.4 Dictionaries 字典 133 4.5 Further Reading 深入学习导读 145 4.6 Exercises 习题 145 4.7 Projects 项目设计 148 Chapter 5 Binary Trees 二叉树 151 5.1 Definitions and Properties 定义及主要特性 151 5.1.1 The Full Binary Tree Theorem 满二叉树定理 153 5.1.2 A Binary Tree Node ADT 二叉树的抽象数据类型 155 5.2 Binary Tree Traversals 遍历二叉树 155 5.3 Binary Tree Node Implementations 二叉树的实现 160 5.3.1 Pointer-Based Node Implementations 使用指针实现二叉树 160 5.3.2 Space Requirements 空间代价 166 5.3.3 Array Implementation for Complete Binary Trees 使用数组实现完全二叉树 168 5.4 Binary Search Trees 二叉检索树 168 5.5 Heaps and Priority Queues 堆与优先队列 178 5.6 Huffman Coding Trees Huffman编码树 185 5.6.1 Building Huffman Coding Trees 建立Huffman编码树 186 5.6.2 Assigning and Using Huffman Codes Huffman编码及其用法 192 5.6.3 Search in Huffman Trees 在Huffman树中搜索 195 5.7 Further Reading 深入学习导读 196 5.8 Exercises 习题 196 5.9 Projects 项目设计 200 Chapter 6 Non-Binary Trees 树 203 6.1 General Tree Definitions and Terminology 树的定义与术语 203 6.1.1 An ADT for General Tree Nodes 树结点的ADT 204 6.1.2 General Tree Traversals 树的遍历 205 6.2 The Parent Pointer Implementation 父指针表示法 207 6.3 General Tree Implementations 树的实现 213 6.3.1 List of Children 子结点表表示法 214 6.3.2 The Left-Child/Right-Sibling Implementation 左子结点/右兄弟结点表示法 215 6.3.3 Dynamic Node Implementations 动态结点表示法 215 6.3.4 Dynamic “Left-Child/Right-Sibling” Implementation 动态左子结点/右兄弟结点表示法 218 6.4 K-ary Trees K叉树 218 6.5 Sequential Tree Implementations 树的顺序表示法 219 6.6 Further Reading 深入学习导读 223 6.7 Exercises 习题 223 6.8 Projects 项目设计 226 Part III Sorting and Searching 排序与检索 Chapter 7 Internal Sorting 内排序 231 7.1 Sorting Terminology and Notation 排序术语 232 7.2 Three Θ(n2) Sor