数据结构与算法分析：C++语言描述（英文版 第4版）

Chapter 1　Programming： A General Overview / 第 1章　程序设计：概述　　　　1

1．1　What’s This Book About / 本书讨论的内容　　　　1

1．2　Mathematics Review / 数学知识复习　　　　2

1．2．1　Exponents / 指数　　　　3

1．2．2　Logarithms / 对数　　　　3

1．2．3　Series / 级数　　　　4

1．2．4　Modular Arithmetic / 模运算　　　　5

1．2．5　The P Word / 证明方法　　　　6

1．3　A Brief Introduction to Recursion / 递归简论　　　　8

1．4　C++ Classes / C类　　　　12

1．4．1　Basic class Syntax / 基本的class语法　　　　12

1．4．2　Extra Constructor Syntax and Accessors / 构造函数的附加语法和访问函数　　　　13

1．4．3　Separation of Interface and Implementation / 接口与实现的分离　　　　16

1．4．4　vector and string / vector类和string类　　　　19

1．5　C++Details / C细节　　　　21

1．5．1　Pointers / 指针　　　　21

1．5．2　Lvalues， Rvalues， and References / 左值、右值和引用　　　　23

1．5．3　Parameter Passing / 参数传递　　　　25

1．5．4　Return Passing / 返回值传递　　　　27

1．5．5　std：：swap and std：：move / std：：swap和std：：move　　　　29

1．5．6　The Big-Five： Destructor， Copy Constructor， Move Constructor， Copy Assignment operator=， Move Assignment operator= / 五大函数：析构函数、拷贝构造函数、移动构造函数、拷贝赋值operator=和移动赋值operator=　　　　30

1．5．7　C-style Arrays and Strings / C风格数组和字符串　　　　35

1．6　Templates / 模板　　　　36

1．6．1　Function Templates / 函数模板　　　　37

1．6．2　Class Templates / 类模板　　　　38

1．6．3　Object， Comparable， and an Example / Object、Comparable和一个例子　　　　39

1．6．4　Function Objects / 函数对象　　　　41

1．6．5　Separate Compilation of Class Templates / 类模板的分离式编译　　 44

1．7　Using Matrices / 使用矩阵　　　　44

1．7．1　The Data Members， Constructor， and Basic Accessors / 数据成员、构造函数和基本访问函数　　　　44

1．7．2　operator[] / operator[]　　　　45

1．7．3　Big-Five / 五大函数　　　　46

Summary / 小结　　　　46

Exercises / 练习　　　　46

References / 参考文献　　　　48

Chapter 2 Algorithm Analysis / 第 2章　算法分析　　　　51

2．1　Mathematical Background / 数学基础　　　　51

2．2　Model / 模型　　　　54

2．3　What to Analyze / 要分析的问题　　　　54

2．4　Running-Time Calculations / 运行时间计算　　　　57

2．4．1　A Simple Example / 一个简单的例子　　　　58

2．4．2　General Rules / 一般法则　　　　58

2．4．3　Solutions for the Maximum Subsequence Sum Problem / 最大子序列和问题的求解　　　　60

2．4．4　Logarithms in the Running Time / 运行时间中的对数　　　　66

2．4．5　Limitations of Worst-Case Analysis / 最坏情形分析的局限性　　　 70

Summary / 小结　　　　70

Exercises / 练习　　　　71

References / 参考文献　　

76

Chapter 3 Lists， Stacks， and Queues / 第3章　表、栈和队列\t77

3．1　Abstract Data Types (ADTs) / 抽象数据类型　　　　77

3．2　The List ADT / 表的抽象数据类型　　　　78

3．2．1　Simple Array Implementation of Lists / 表的简单数组实现　　　　78

3．2．2　Simple Linked Lists / 简单链表　　　　79

3．3　vector and list in the STL / STL中的vector和list　　　　80

3．3．1　Iterators / 迭代器　　　　82

3．3．2　Example： Using erase on a List / 例子：对表使用erase　　　　83

3．3．3　const_iterators / const_iterators　　　　84

3．4　Implementation of vector / vector的实现　　　　86

3．5　Implementation of list / list的实现　　　　91

3．6　The Stack ADT / 栈的抽象数据类型　　　　103

3．6．1　Stack Model / 栈模型　　　　103

3．6．2　Implementation of Stacks / 栈的实现　　　　104

3．6．3　Applications / 应用　　　　104

3．7　The Queue ADT / 队列的抽象数据类型　　　　112

3．7．1　Queue Model / 队列模型　　　　113

3．7．2　Array Implementation of Queues / 队列的数组实现　　　　113

3．7．3　Applications of Queues / 队列的应用　　　　115

Summary / 小结　　　　116

Exercises / 练习　　　　116

Chapter 4 Trees / 第4章　树　　　　121

4．1　Preliminaries / 预备知识　　　　121

4．1．1　Implementation of Trees / 树的实现　　　　122

4．1．2　Tree Traversals with an Application / 树的遍历及应用　　　　123

4．2　Binary Trees / 二叉树　　　　126

4．2．1　Implementation / 实现　　　　128

4．2．2　An Example： Expression Trees / 一个例子——表达式树　　　　128

4．3　The Search Tree ADT—Binary Search Trees / 查找树的抽象数据类型——二叉查找树　　　　132

4．3．1　contains / contains　　　　134

4．3．2　findMin and findMax / findMin和findMax　　　　135

4．3．3　insert / insert　　　　136

4．3．4　remove / remove　　　　139

4．3．5　Destructor and Copy Constructor / 析构函数和拷贝构造函数　　　　141

4．3．6　Average-Case Analysis / 平均情况分析　　　　141

4．4　AVL Trees / AVL树　　　　144

4．4．1　Single Rotation / 单旋转　　　　147

4．4．2　Double Rotation / 双旋转　　　　149

4．5　Splay Trees / 伸展树　　　　158

4．5．1　A Simple Idea (That Does Not Work) / 一个简单的想法（不能直接使用）　　　　158

4．5．2　Splaying / 展开　　　　160

4．6　Tree Traversals (Revisited) / 树的遍历（再次讨论）　　　　166

4．7　B-Trees / B树　　　　168

4．8　Sets and Maps in the Standard Library / 标准库中的集合与映射　　　　173

4．8．1　Sets / 集合　　　　173

4．8．2　Maps / 映射　　　　174

4．8．3　Implementation of set and map / set和map的实现　　　　175

4．8．4　An Example That Uses Several Maps / 使用多个映射的示例　　　　176

Summary / 小结　　　　181

Exercises / 练习　　　　182

References / 参考文献　　　　189

Chapter 5 Hashing / 第5章　哈希　　　　193

5．1　General Idea / 一般想法　　　　193

5．2　Hash Function / 哈希函数　　　　194

5．3　Separate Chaining / 分离链接法　　　　196

5．4　Hash Tables without Linked Lists / 不用链表的哈希表　　　　201

5．4．1　Linear Probing / 线性探测法　　　　201

5．4．2　Quadratic Probing / 平方探测法　　　　202

5．4．3　Double Hashing / 双哈希　　　　207

5．5　Rehashing / 再哈希　　　　208

5．6　Hash Tables in the Standard Library / 标准库中的哈希表　　　　210

5．7　Hash Tables with Worst-Case O(1) Access / 以最坏情形O(1)访问的哈希表　　　　212

5．7．1　Perfect Hashing / 完美哈希　　　　213

5．7．2　Cuckoo Hashing / 杜鹃哈希　　　　215

5．7．3　Hopscotch Hashing / 跳房子哈希　　　　227

5．8　Universal Hashing / 通用哈希　　　　230

5．9　Extendible Hashing / 可扩哈希　　　　233

Summary / 小结　　　　236

Exercises / 练习　　　　237

References / 参考文献　　　　241

Chapter 6 Priority Queues (Heaps) / 第6章　优先队列（堆）\t245

6．1　Model / 模型　　　　245

6．2　Simple Implementations / 一些简单的实现　　　　246

6．3　Binary Heap / 二叉堆　　　　247

6．3．1　Structure Property / 结构性质　　　　247

6．3．2　Heap-Order Property / 堆序性质　　　　248

6．3．3　Basic Heap Operations / 基本的堆操作　　　　249

6．3．4　Other Heap Operations / 其他的堆操作　　　　252

6．4　Applications of Priority Queues / 优先队列的应用　　　　257

6．4．1　The Selection Problem / 选择问题　　　　258

6．4．2　Event Simulation / 事件模拟　　　　259

6．5　d-Heaps / d堆　　　　260

6．6　Leftist Heaps / 左式堆　　　　261

6．6．1　Leftist Heap Property / 左式堆的性质　　　　261

6．6．2　Leftist Heap Operations / 左式堆操作　　　　262

6．7　Skew Heaps / 斜堆　　　　269

6．8　Binomial Queues / 二项队列　　　　271

6．8．1　Binomial Queue Structure / 二项队列构建　　　　271

6．8．2　Binomial Queue Operations / 二项队列操作　　　　271

6．8．3　Implementation of Binomial Queues / 二项队列的实现　　　　276

6．9　Priority Queues in the Standard Library / 标准库中的优先队列　　　　282

Summary / 小结　　　　283

Exercises / 练习　　　　283

References / 参考文献　　　　288

Chapter 7 Sorting / 第7章　排序　　　　291

7．1　Preliminaries / 预备知识　　　　291

7．2　Insertion Sort / 插入排序　　　　292

7．2．1　The Algorithm / 算法　　　　292

7．2．2　STL Implementation of Insertion Sort / 插入排序的STL实现　　　　293

7．2．3　Analysis of Insertion Sort / 插入排序的分析　　　　294

7．3　A Lower Bound for Simple Sorting Algorithms / 一些简单排序算法的下界　　　　295

7．4　Shellsort / 希尔排序　　　　296

7．4．1　Worst-Case Analysis of Shellsort / 希尔排序的最坏情形分析　　　　297

7．5　Heapsort / 堆排序　　　　300

7．5．1　Analysis of Heapsort / 堆排序的分析　　　　301

7．6　Mergesort / 归并排序　　　　304

7．6．1　Analysis of Mergesort / 归并排序的分析　　　　306

7．7　Quicksort / 快速排序　　　　309

7．7．1　Picking the Pivot / 选取枢纽元　　　　311

7．7．2　Partitioning Strategy / 分割策略　　　　313

7．7．3　Small Arrays / 小数组　　　　315

7．7．4　Actual Quicksort Routines / 实际的快速排序例程　　　　315

7．7．5　Analysis of Quicksort / 快速排序的分析　　　　318

7．7．6　A Linear-Expected-Time Algorithm for Selection / 选择问题的线性期望时间算法　　　　321

7．8　A General Lower Bound for Sorting / 排序算法的一般下界　　　　323

7．8．1　Decision Trees / 决策树　　　　323

7．9　Decision-Tree Lower Bounds for Selection Problems / 选择问题的决策树下界　　　　325

7．10　Adversary Lower Bounds / 对手下界　　　　328

7．11　Linear-Time Sorts： Bucket Sort and Radix Sort / 线性时间排序：桶式排序和基数排序　　　　331

7．12　External Sorting / 外部排序　　　　336

7．12．1　Why We Need New Algorithms / 为什么需要一些新的算法　　　　336

7．12．2　Model for External Sorting / 外部排序模型　　　　336

7．12．3　The Simple Algorithm / 简单算法　　　　337

7．12．4　Multiway Merge / 多路合并　　　　338

7．12．5　Polyphase Merge / 多相合并　　　　339

7．12．6　Replacement Selection / 替换选择　　　　340

Summary / 小结　　　　341

Exercises / 练习　　　　341

References / 参考文献　　　　347

Chapter 8 The Disjoint Sets Class / 第8章　不相交集算法\t351

8．1　Equivalence Relations / 等价关系　　　　351

8．2　The Dynamic Equivalence Problem / 动态等价性问题　　　　352

8．3　Basic Data Structure / 基本数据结构　　　　353

8．4　Smart Union Algorithms / 灵巧求并算法　　　　357

8．5　Path Compression / 路径压缩　　　　360

8．6　Worst Case for Union-by-Rank and Path Compression / 按秩求并和路径压缩的最坏情形　　　　361

8．6．1　Slowly Growing Functions / 缓慢增长的函数　　　　362

8．6．2　An Analysis by Recursive Decomposition / 通过递归分解进行的分析　　　　362

8．6．3　An O (M log*N) Bound / 一个O (M log*N)界　　　　369

8．6．4　An O (Mα(M， N)) Bound / 一个O (Mα(M， N))界　　　　370

8．7　An Application / 一个应用　　　　372

Summary / 小结　　　　374

Exercises / 练习　　　　375

References / 参考文献　　　　376

Chapter 9 Graph Algorithms / 第9章　图论算法　　　　379

9．1　Definitions / 若干定义　　　　379

9．1．1　Representation of Graphs / 图的表示　　　　380

9．2　Topological Sort / 拓扑排序　　　　382

9．3　Shortest-Path Algorithms / 最短路径算法　　　　386

9．3．1　Unweighted Shortest Paths / 无权最短路径　　　　387

9．3．2　Dijkstra’s Algorithm / Dijkstra算法　　　　391

9．3．3　Graphs with Negative Edge Costs / 具有负边值的图　　　　400

9．3．4　Acyclic Graphs / 无圈图　　　　400

9．3．5　All-Pairs Shortest Path / 所有顶点对间的最短路径　　　　404

9．3．6　Shortest Path Example / 最短路径的例　　　　404

9．4　Network Flow Problems / 网络流问题　　　　406

9．4．1　A Simple Maximum-Flow Algorithm / 一个简单的最大流算法　　　　408

9．5　Minimum Spanning Tree / 最小生成树　　　　413

9．5．1　Prim’s Algorithm / Prim算法　　　　414

9．5．2　Kruskal’s Algorithm / Kruskal算法　　　　417

9．6　Applications of Depth-First Search / 深度优先搜索的应用　　　　419

9．6．1　Undirected Graphs / 无向图　　　　420

9．6．2　Biconnectivity / 双连通性　　　　421

9．6．3　Euler Circuits / 欧拉回路　　　　425

9．6．4　Directed Graphs / 有向图　　　　429

9．6．5　Finding Strong Components / 查找强分支　　　　431

9．7　Introduction to NP-Completeness / NP完全性介绍　　　　432

9．7．1　Easy vs． Hard / 难与易　　　　433

9．7．2　The Class NP / NP类　　　　434

9．7．3　NP-Complete Problems / NP完全问题　　　　434

Summary / 小结　　　　437

Exercises / 练习　　　　437

References / 参考文献　　　　445

Chapter 10 Algorithm Design Techniques / 第 10章　算法设计技巧　　449

10．1　Greedy Algorithms / 贪婪算法　　　　449

10．1．1　A Simple Scheduling Problem / 一个简单的调度问题　　　　450

10．1．2　Huffman Codes / 哈夫曼编码　　　　453

10．1．3　Approximate Bin Packing / 近似装箱问题　　　　459

10．2　Divide and Conquer / 分治算法　　　　467

10．2．1　Running Time of Divide-and-Conquer Algorithms / 分治算法的运行时间　　　　468

10．2．2　Closest-Points Problem / 最近点问题　　　　470

10．2．3　The Selection Problem / 选择问题　　　　475

10．2．4　Theoretical Improvements for Arithmetic Problems / 一些算术问题的理论改进　　　　478

10．3　Dynamic Programming / 动态规划　　　　482

10．3．1　Using a Table Instead of Recursion / 用表代替递归　　　　483

10．3．2　Ordering Matrix Multiplications / 矩阵乘法的顺序安排　　　　485

10．3．3　Optimal Binary Search Tree / 二叉查找树　　　　487

10．3．4　All-Pairs Shortest Path / 所有点对最短路径　　　　491

10．4　Randomized Algorithms / 随机化算法　　　　494

10．4．1　Random-Number Generators / 随机数发生器　　　　495

10．4．2　Skip Lists / 跳跃表　　　　500

10．4．3　Primality Testing / 素性测试　　　　503

10．5　Backtracking Algorithms / 回溯算法　　　　506

10．5．1　The Turnpike Reconstruction Problem / 收费公路重建问题　　　　506

10．5．2　Games / 游戏　　　　511

Summary / 小结　　　　518

Exercises / 练习　　　　518

References / 参考文献　　　　527

Chapter 11 Amortized Analysis / 第 11章　摊还分析　　　　533

11．1　An Unrelated Puzzle / 一个无关的智力问题　　　　534

11．2　Binomial Queues / 二项队列　　　　534

11．3　Skew Heaps / 斜堆　　　　539

11．4　Fibonacci Heaps / 斐波那契堆　　　　541

11．4．1　Cutting Nodes in Leftist Heaps / 切除左式堆中的节点　　　　542

11．4．2　Lazy Merging for Binomial Queues / 二项队列的懒惰合并　　　　544

11．4．3　The Fibonacci Heap Operations / 斐波那契堆操作　　　　548

11．4．4　Proof of the Time Bound / 时间界的证明　　　　549

11．5　Splay Trees / 伸展树　　　　551

Summary / 小结　　　　555

Exercises / 练习　　　　556

References / 参考文献　　　　557

Chapter 12 Advanced Data Structures and Implementation / 第 12章　高级数据结构及其实现　　　　559

12．1　Top-Down Splay Trees / 自顶向下伸展树　　　　559

12．2　Red-Black Trees / 红黑树　　　　566

12．2．1　Bottom-Up Insertion / 自底向上的插入　　　　567

12．2．2　Top-Down Red-Black Trees / 自顶向下红黑树　　　　568

12．2．3　Top-Down Deletion / 自顶向下删除　　　　570

12．3　Treaps / treap 树　　　　576

12．4　Suffix Arrays and Suffix Trees / 后缀数组和后缀树　　　　579

12．4．1　Suffix Arrays / 后缀数组　　　　580

12．4．2　Suffix Trees / 后缀树　　　　583

12．4．3　Linear-Time Construction of Suffix Arrays and Suffix Trees / 后缀数组和后缀树的线性　　　　586

12．5　k -d Trees / k-d 树　　　　596

12．6　Pairing Heaps / 配对堆　　　　602

Summary / 小结　　　　606

Exercises / 练习　　　　608

References / 参考文献　　　　612

Appendix A Separate Compilation of Class Templates / 附录A　类模板的分离式编译　　　　615

A．1 Everything in the Header / 头文件中的内容　　　　616

A．2 Explicit Instantiation / 显示实例化　　　　616