数据结构与算法分析（C++版）（第三版）（英文版） 下载 pdf 百度网盘 epub 免费 2025 电子书 mobi 在线

本书采用程序员偏爱的面向对象C 语言来描述数据结构和算法，并把数据结构原理和算法分析技术有机地结合在一起，系统介绍了各种类型的数据结构和排序、检索的各种方法。作者非常注意对每一种数据结构的不同存储方法及有关算法进行分析比较。书中还引入了一些比较高级的数据结构与先进的算法分析技术，并介绍了可计算性理论的一般知识。书中分别给出了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

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

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

暂无出版社相关信息，正在全力查找中！

暂无相关书籍摘录，正在全力查找中！

在线阅读地址：数据结构与算法分析（C++版）（第三版）（英文版）在线阅读

在线听书地址：数据结构与算法分析（C++版）（第三版）（英文版）在线收听

在线购买地址：数据结构与算法分析（C++版）（第三版）（英文版）在线购买

The following is a true story. A few years ago, one of

my graduate students had a big problem. His thesis work involved several intricate operations on a large database. He was now working on the final step. “Dr. Shaffer,” he said, “I am running this program and it seems to be taking a long time.” After examining the algorithm we realized that its running time was Ө(n^2), and that it would likely take one to two weeks to complete. Even if we could keep the computer running uninterrupted for that long, he was hoping to complete his thesis and graduate before then. Fortunately, we realized that there was a fairly easy way to convert

the algorithm so that its running time was Ө(n log n). By the next day he had modified the program. It ran in only a few hours, and he finished his thesis on tim...

As an interesting aside, writing a correct binary search algorithm is not easy. Knuth [Knu98] notes that while the first binary search was published in 1946, the first bug-free algorithm was not published until 1962! Bentley (“Writing Correct Programs” in [Ben00]) has found that 90% of the computer professionals he tested could not write a bug-free binary search in two hours.

编辑推荐

本书采用程序员偏爱的面向对象C 语言来描述数据结构和算法，并把数据结构原理和算法分析技术有机地结合在一起，系统介绍了各种类型的数据结构和排序、检索的各种方法。作者非常注意对每一种数据结构的不同存储方法及有关算法进行分析比较。书中还引入了一些比较高级的数据结构与先进的算法分析技术，并介绍了可计算性理论的一般知识。

前言

导读

本书是关于数据结构与算法的经典教材，主要论述了数据的逻辑结构、存储结构、算法设计以及算法评价，使读者能够深入了解线性表、栈、队列、树、图等数据结构以及排序和检索等基础算法，并掌握在不同的数据结构上进行有关算法设计的思想和技巧。书中包含大量代码实例和详尽的解释，非常适合作为计算机专业本科生的低年级入门教材。

全书由浅入深，分成了五部分。针对计算机专业的低年级本科生而言，可重点学习前面三部分的内容，学有余力的读者可以在此基础上继续研读后面的内容。下面为读者介绍本书的重点内容。

基础知识

本书第1章介绍数据结构的入门基础知识。其中1.1节主要介绍数据结构的定义、基本术语以及数据结构的基本类型。读者可通过该节的学习，重点理解数据结构对抽象表达、程序建模的重要作用，了解在实际应用过程中数据结构的优缺点分析方法。1.2节重点介绍基于抽象数据类型的数据结构描述方法，这是整本书中各个数据结构的基本描述方法。读者可穿插翻阅后面第4章至第6章中各种数据结构的抽象数据类型，加深对此概念的理解。此外，通过学习1.4节，读者可进一步理解数据结构、问题与算法的关系。

第2章介绍本课程涉及的一些基础数学知识。这里介绍的绝大部分数学知识，读者都在中学阶段学过。读者可简单快速地浏览一下，用时再来回顾翻查。

第3章主要介绍算法复杂度的定义以及分析方法。通过学习这一章，读者就能了解渐近算法复杂度分析方法，理解上界分析、下界分析以及确切界的具体定义和快速分析方法，并掌握针对任意给定程序片段的基本分析方法。

数据结构

本书第II部分是整本教材的重点，主要讨论了线性表(List)、二叉树(Binary Tree)、普通树(General Tree)和图(Graph)的定义与实现方法。为了能对各类数据结构融会贯通，建议读者将第4章至第6章以及第11章放在一起来进行对比学习。

第4章主要介绍线性表的定义、存储实现方法，以及插入、删除和定位等基本运算；介绍了栈和队列的基本定义、基本操作，以及灵活运用线性表解决现实工程问题的方法。本章的重点是分析线性表的数组和链表这两种实现方法的优缺点，实现线性表的插入、删除和定位等基本运算的算法，掌握栈的入栈和出栈的操作以及队列的入队和出队的操作。本章的难点是掌握单链表及循环链表的算法设计综合应用，掌握在循环队列上进行入队、出队以及求队列长度的操作。

第5章主要阐述二叉树的基本定义和存储实现方式，介绍二叉树的遍历和搜索等基本操作，并讨论堆和哈夫曼树的基本原理和实现方法。本章的重点是基于链接和数组两种存储结构的二叉树实现方法，基于递归的二叉树遍历算法，以及二叉检索树的搜索、删除结点和添加结点等操作的实现。本章的难点是堆的构建，插入删除结点的算法实现，以及哈夫曼树和哈夫曼编码的原理。

第6章主要介绍普通树的基本定义、遍历算法，以及树的基本存储结构的原理。本章的重点是左子结点/右兄弟结点的实现方法，以及普通树和森林与二叉树的相互转换方法。本章的难点是普通树的顺序存储方法。

第11章主要介绍图的定义和实现方法，图的遍历算法、拓扑排序算法、短路径算法以及小生成树算法。本章的重点是图的邻接表和邻接矩阵两种实现方法的原理以及优缺点对比，基于递归函数的图的遍历算法的实现，拓扑排序算法的实现方法以及应用。本章的难点是Dijkstra短路径算法、Floyd短路径算法，以及小支撑树算法。

排序与检索算法

第III部分主要介绍排序与检索这两类比较常见的算法，读者在掌握了前面所学数据结构的基础上，可以较为容易地掌握这些算法。

第7章和第8章主要介绍排序算法的定义、排序算法的稳定性分析方法、排序算法的设计与实现、排序算法的复杂度对比分析，以及排序算法的应用。这两章的重点是快速排序算法、归并排序算法以及堆排序算法的实现。这两章的难点是希尔排序算法的原理和实现，以及快速排序算法的改进方法。

第9章主要介绍检索的基本原理和二分法检索，讨论了哈希表的原理、构建以及相关操作。本章的重点是哈希表的原理、哈希函数的设计方法，以及哈希表的插入和删除算法的实现。本章的难点是哈希表的冲突解决策略。

第10章主要介绍线性索引、2-3树索引、B/B 树索引的构建方法，以及算法复杂度分析方法。本章的重点是线性索引和2-3树索引的插入、删除和检索算法，以及B树和B 树的定义。本章的难点是B树和B 树的插入、删除和检索算法。

至此，通过前三部分的学习，读者已掌握了数据结构的基本知识、理论和分析方法，为从事相关计算机程序分析和设计工作以及相关专业的后续课程学习打下了扎实的基础。读者在本书各章节的学习过程中，可动手实践对应的程序代码，掌握各类数据结构与算法的实现方法。华南理工大学计算机科学与工程学院的“数据结构”课程采用了本书作为教材。我们授课团队结合本书设计了相应的在线教学视频(https://next.xuetangx.com/course/SCUT08091000960/)，感兴趣的读者可参考学习，定能起到事半功倍的作用。采用本书作为教材的授课教师，也可登录华信教育资源网(www.hxedu.com.cn)注册后免费下载我们的教学用PPT等相关资料。

吕建明教授  博导

华南理工大学计算机科学与工程学院

Preface

We study data structures so that we can learn to write more efficient programs. But why must programs be efficient when new computers are faster every year? The reason is that our ambitions grow with our capabilities. Instead of rendering efficiency needs obsolete, the modern revolution in computing power and storage capability merely raises the efficiency stakes as we attempt more complex tasks.

The quest for program efficiency need not and should not conflict with sound design and clear coding. Creating efficient programs has little to do with “programming tricks” but rather is based on good organization of information and good algorithms. A programmer who has not mastered the basic principles of clear design is not likely to write efficient programs. Conversely, concerns related to development costs and maintainability should not be used as an excuse to justify inefficient performance. Generality in design can and should be achieved without sacrificing performance, but this can only be done if the designer understands how to measure performance and does so as an integral part of the design and implementation process. Most computer science curricula recognize that good programming skills begin with a strong emphasis on fundamental software engineering principles. Then, once a programmer has learned the principles of clear program design and implementation, the next step is to study the effects of data organization and algorithms on program efficiency.

Approach: This book describes many techniques for representing data. These techniques are presented within the context of the following principles:

1. Each data structure and each algorithm has costs and benefits. Practitioners need a thorough understanding of how to assess costs and benefits to be able to adapt to new design challenges. This requires an understanding of the principles of algorithm analysis, and also an appreciation f