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

图书标准信息

• 作者 ・ 著；[美]Clifford、A.、Shaffer、克利福德、Clifford、A.、Shaffer 译
• 出版社 电子工业出版社
• 出版时间 2020-08
• 版次 1
• ISBN 9787121393549
• 定价 109.00元
• 装帧 平装
• 开本 16开
• 页数 604页
• 字数 1256千字

【内容简介】

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

【作者简介】

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