书籍详情
数据结构与算法分析：C++语言描述（英文版 第4版）
作者：[美] 马克·艾伦·维斯 著，肖鉴明 译
出版社：人民邮电出版社
出版时间：2022-02-01
ISBN：9787115580924
定价：¥129.90
购买这本书可以去
内容简介
本书是数据结构和算法分析领域的教材。全书以 C++作为具体的实现语言，介绍了表、栈、队列、树、哈希表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、后缀数组、后缀树、k-d 树、配对堆等内容。本书把算法分析和 C++程序的开发有机结合起来，深入剖析每种算法，内容缜密严谨，还详细讲解了精心构建程序的方法。本书可作为高等院校计算机相关专业的教学用书或参考用书，也可供计算机领域的工程技术人员参考
作者简介
Mark Allen Weiss，佛罗里达国际大学计算与信息科学学院教授、副院长，本科教育主任和研究生教育主任。他于1987年获得普林斯顿大学计算机科学博士学位，师从Bob Sedgewick。他曾经担任全美AP（Advanced Placement）考试计算机学科委员会的主席（2000-2004）。Weiss教授在数据结构和算法分析方面卓有建树，他的数据结构和算法分析的书籍，受到广泛好评．已被世界500余所大学用作教材。
目录
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
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
猜您喜欢
