数据结构与算法分析（C++版 第三版 英文版）

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) Sorting Algorithms 三种代价为Θ(n2)的排序算法 233
7．2．1 Insertion Sort 插入排序 233
7．2．2 Bubble Sort 冒泡排序 235
7．2．3 Selection Sort 选择排序 237
7．2．4 The Cost of Exchange Sorting 交换排序算法的时间代价 238
7．3 Shellsort Shell排序 239
7．4 Mergesort 归并排序 241
7．5 Quicksort 快速排序 244
7．6 Heapsort 堆排序 251
7．7 Binsort and Radix Sort 分配排序和基数排序 252
7．8 An Empirical Comparison of Sorting Algorithms 对各种排序算法的实验比较 259
7．9 Lower Bounds for Sorting 排序问题的下限 261
7．10 Further Reading 深入学习导读 265
7．11 Exercises 习题 265
7．12 Projects 项目设计 269
Chapter 8 File Processing and External Sorting 文件管理和外排序 273
8．1 Primary versus Secondary Storage 主存储器和辅助存储器 273
8．2 Disk Drives 磁盘 276
8．2．1 Disk Drive Architecture 磁盘结构 276
8．2．2 Disk Access Costs 磁盘访问代价 280
8．3 Buffers and Buffer Pools 缓冲区和缓冲池 282
8．4 The Programmer’s View of Files 程序员的文件视图 290
8．5 External Sorting 外排序 291
8．5．1 Simple Approaches to External Sorting 外排序的简单方法 294
8．5．2 Replacement Selection 置换选择排序 296
8．5．3 Multiway Merging 多路归并 300
8．6 Further Reading 深入学习导读 303
8．7 Exercises 习题 304
8．8 Projects 项目设计 307
Chapter 9 Searching 检索 311
9．1 Searching Unsorted and Sorted Arrays 检索未排序和已排序的数组 312
9．2 Self-Organizing Lists 自组织线性表 317
9．3 Bit Vectors for Representing Sets 集合检索 323
9．4 Hashing 散列方法 324
9．4．1 Hash Functions 散列函数 325
9．4．2 Open Hashing 开散列方法 330
9．4．3 Closed Hashing 闭散列方法 331
9．4．4 Analysis of Closed Hashing 闭散列方法分析 339
9．4．5 Deletion 删除 344
9．5 Further Reading 深入学习导读 345
9．6 Exercises 习题 345
9．7 Projects 项目设计 348
Chapter 10 Indexing 索引技术 351
10．1 Linear Indexing 线性索引 353
10．2 ISAM 索引顺序访问方法 356
10．3 Tree-based Indexing 基于树的索引 358
10．4 2-3 Trees 2-3树 360
10．5 B-Trees B树 364
10．5．1 B+-Trees B+树 368
10．5．2 B-Tree Analysis B树分析 374
10．6 Further Reading 深入学习导读 375
10．7 Exercises 习题 375
10．8 Projects 项目设计 377
Part IV Advanced Data Structures 高级数据结构
Chapter 11 Graphs 图 381
11．1 Terminology and Representations 术语和表示法 382
11．2 Graph Implementations 图的实现 386
11．3 Graph Traversals 图的遍历 390
11．3．1 Depth-First Search 深度优先搜索 393
11．3．2 Breadth-First Search 广度优先搜索 394
11．3．3 Topological Sort 拓扑排序 394
11．4 Shortest-Paths Problems 最短路径问题 399
11．4．1 Single-Source Shortest Paths 单源最短路径 400
11．5 Minimum-Cost Spanning Trees 最小支撑树 402
11．5．1 Prim’s Algorithm Prim算法 404
11．5．2 Kruskal’s Algorithm Kruskal算法 407
11．6 Further Reading 深入学习导读 408
11．7 Exercises 习题 408
11．8 Projects 项目设计 412
Chapter 12 Lists and Arrays Revisited 线性表和数组高级技术 415
12．1 Multilists 广义表 415
12．2 Matrix Representations 矩阵的表示方法 418
12．3 Memory Management 存储管理 422
12．3．1 Dynamic Storage Allocation 动态存储分配 424
12．3．2 Failure Policies and Garbage Collection 失败处理策略和无用单元收集 431
12．4 Further Reading 深入学习导读 435
12．5 Exercises 习题 436
12．6 Projects 项目设计 437
Chapter 13 Advanced Tree Structures 高级树结构 439
13．1 Tries Tries结构 439
13．2 Balanced Trees 平衡树 444
13．2．1 The AVL Tree AVL树 445
13．2．2 The Splay Tree 伸展树 447
13．3 Spatial Data Structures 空间数据结构 450
13．3．1 The k-d Tree k-d树 452
13．3．2 The PR quadtree PR四分树 457
13．3．3 Other Point Data Structures 其他点状数据结构 461
13．3．4 Other Spatial Data Structures 其他空间数据结构 463
13．4 Further Reading 深入学习导读 463
13．5 Exercises 习题 464
13．6 Projects 项目设计 465
Part V Theory of Algorithms 算法理论
Chapter 14 Analysis Techniques 分析技术 471
14．1 Summation Techniques 求和技术 472
14．2 Recurrence Relations 递归关系 477
14．2．1 Estimating Upper and Lower Bounds 估算上下限 477
14．2．2 Expanding Recurrences 扩展递归 480
14．2．3 Divide and Conquer Recurrences 分治法递归 482
14．2．4 Average-Case Analysis of Quicksort 快速排序平均情况分析 484
14．3 Amortized Analysis 均摊分析 486
14．4 Further Reading 深入学习导读 489
14．5 Exercises 习题 489
14．6 Projects 项目设计 493
Chapter 15 Lower Bounds 下限 495
15．1 Introduction to Lower Bounds Proofs 下限证明简介 496
15．2 Lower Bounds on Searching Lists 线性表检索的下限 498
15．2．1 Searching in Unsorted Lists 无序线性表检索 498
15．2．2 Searching in Sorted Lists 有序线性表检索 500
15．3 Finding the Maximum Value 查找最大值 501
15．4 Adversarial Lower Bounds Proofs 对抗性下限证明 503
15．5 State Space Lower Bounds Proofs 状态空间下限证明 506
15．6 Finding the ith Best Element 查找第i大元素 509
15．7 Optimal Sorting 优化排序 511
15．8 Further Reading 深入学习导读 514
15．9 Exercises 习题 514
15．10 Projects 项目设计 517
Chapter 16 Patterns of Algorithms 算法模式 519
16．1 Dynamic Programming 动态规划 519
16．1．1 The Knapsack Problem 背包问题 521
16．1．2 All-Pairs Shortest Paths 全局最短路径 523
16．2 Randomized Algorithms 随机算法 525
16．2．1 Randomized algorithms for finding large values 查找最大值的随机算法 525
16．2．2 Skip Lists 跳跃表 526
16．3 Numerical Algorithms 数值算法 532
16．3．1 Exponentiation 幂运算 533
16．3．2 Largest Common Factor 最大公约数 533
16．3．3 Matrix Multiplication 矩阵相乘 534
16．3．4 Random Numbers 随机数 536
16．3．5 The Fast Fourier Transform 快速傅里叶变换 537
16．4 Further Reading 深入学习导读 542
16．5 Exercises 习题 542
16．6 Projects 项目设计 543
Chapter 17 Limits to Computation 计算的限制 545
17．1 Reductions 归约 546
17．2 Hard Problems 难解问题 551
17．2．1 The Theory of NP-Completeness NP完全性理论 553
17．2．2 NP-Completeness Proofs NP完全性证明 557
17．2．3 Coping with NP-Complete Problems 处理NP完全性问题 562
17．3 Impossible Problems 不可解问题 565
17．3．1 Uncountability 不可数性 566
17．3．2 The Halting Problem Is Unsolvable 停机问题的不可解性 569
17．4 Further Reading 深入学习导读 571
17．5 Exercises 习题 572
17．6 Projects 项目设计 574
Part VI Appendix 附录
Appendix A Utility Functions 实用函数 579
Bibliography 参考文献 581