《数据结构与算法》全面系统地介绍了计算机科学教育中的一个重要组成部分——数据结构,并以C++语言实现相关的算法。书中主要强调了数据结构和算法之间的联系,使用面向对象的方法介绍数据结构,其内容包括算法的复杂度分析、链表、栈队列、递归技术、二叉树、图、排序以及散列。《数据结构与算法》还清楚地阐述了同类教材中较少提到的内存管理、数据压缩和字符串匹配主题。书中包含大量的示例分析和图形,便于读者进一步理解和巩固所学的知识。

数据结构知识是计算机科学教育的一个基本组成部分,其他许多计算机科学领域都构建在这个基础之上。对于想从事实际的软件设计、实现、测试、维护工作的学生而言,掌握基本数据结构的知识是非常必要的。本书介绍的内容将会给从事以上工作的读者提供必要的知识。
本书突出了数据结构中的三个重要方面。首先,强调了数据结构与其算法之间的联系,包括算法的复杂度分析。接着,依照当前的设计和实现范例,使用面向对象的方法来介绍数据结构,特别强调了有助于封装与分解的信息隐藏原理。*后,本书的一个重要组成部分是数据结构的实现,它选择C++作为编程语言。
C++语言是C语言面向对象的后裔,在业界和学术界得到了广泛的应用,是一种非常**的编程语言。自然地,我们就选用C++来介绍数据结构。而且,由于C++语言在应用程序设计中的广泛使用以及这门语言的面向对象特性,使用它来讲授数据结构和算法课程(即使是入门级的课程)是非常合理的。
本书大多数章节都包括一个案例分析,它阐明了一个完整的、使用特定算法和数据结构的环境。为了说明所论述的主题的广泛应用范围,这些案例分析都是从计算机科学的不同领域中挑选出来的,包括解释程序、符号计算和文件处理。
本书自始至终包含了简要的C++程序例子,举例说明数据结构在实践中的重要性。然而,理论分析同样也很重要,所以算法的探讨都包含了对算法效率的分析。
要特别留意关于递归的介绍,因为即使是*高明的学生,在这个方面也会出现一些问题。经验表明,如果考虑运行时栈的话,就可以极好地说明递归的含义。我们不但在递归一章里在跟踪递归函数时显示出了栈的变化,在其他章节里也说明了栈的变化。比如说,如果不解释系统在运行时栈上所做的工作,甚至一个短小的树遍历函数也可能难于理解。在讨论数据结构和算法时,脱离系统,只从纯理论的角度出发是没有什么用处的。
这本书讨论的**是数据结构,而附带介绍其他一些主题仅仅是为了更好地理解数据结构。算法都是从数据结构的角度来讨论的,所以没有对各种算法进行全面的讨论,也没有列出介绍一个算法所需要的全部内容。然而,如前所述,本书将深入论述递归。另外,对算法的复杂度分析也介绍得比较详细。
第1和3~8章介绍了许多不同的数据结构以及使用这些数据结构的算法,分析了每一种算法的效率,同时给出了改进算法的建议。
● 第1章介绍了面向对象程序设计的基本原理,介绍了动态内存分配、指针的使用以及标准模板库(Standard Template Library,STL)。
● 第2章讲述了一些评价算法效率的方法。
● 第3章介绍了不同类型的链表,着重阐述了其指针实现。
● 第4章介绍了栈、队列及其应用。
● 第5章对递归进行了详细讨论。论述了不同类型的递归,并剖析了其中的一个递归
调用。

● 第6章讨论了二叉树,包括二叉树的实现、遍历和搜索。在这一章中还介绍了平衡树。
● 第7章详细介绍了更一般化的树,比如森林、2-4树、B树。
● 第8章介绍图。
第9~12章给出了前面章节所介绍的数据结构的不同应用,并强调了这些应用在数据结构方面的问题。
● 第9章详细介绍了排序,以及一些基础的和非基础的方法。
● 第10章讨论了散列,它是搜索算法中*重要的主题之一。在强调数据结构使用的同时介绍了各种各样的技术。
● 第11章讨论了数据压缩算法和相应的数据结构。
● 第12章介绍了内存管理的多种方法和相应的数据结构。
● 第13章介绍了字符串的**匹配和模糊匹配的许多算法。
● 附录A详细介绍了在第2章中提到的大O符号。
● 附录B介绍了标准模板库(STL)中的标准算法。
● 附录C证明了Cook理论,并用一个例子进行了说明。
每一章都包含了对一些材料的讨论,并配以合适的图表和表格。除第2章外,所有的章节都包括一个案例分析,这个案例分析是该章所讨论的特性的一个范例。所有的案例分析都在PC上用Visual C++编译器测试过,还在Unix上用g++编译器测试过,只有von Koch snowflake除外,它只在PC上用Visual C++测试过。每一章的*后是一些不同难度的练习题。除了第2章之外,所有的章节都包括了程序设计作业以及一些*新的相关参考书籍。
第1~6章(2.9、3.4、6.4.3、6.7、6.8节除外)包含了构成任何数据结构课程基础的核心内容。应该按照顺序来学习这些章。其后的6章内容可以按照任意次序学习。一个学期的课程可以包括1~6章、第9章,以及10.1和10.2节。整本书可以在一个学年中学完。
本书中示例程序的源代码可以通过Web站点http://www.course.com或http://www. tupwk.com.cn /downpage进行访问。
第3版的改动
新版本扩展了旧版本,主要包括一些当前未涉及到的新主题,如下:
● 第13章中的模式匹配算法
● 2.10节粗略介绍了NP完整性,8.12节列举了NP完整性的问题范例,附录C讨论了Cook理论
● 一些新图(8.9.1节、8.10.1节、8.10.2节和8.11节中的某些图)
● 7.1.7节讨论了vh树的删除算法
在整本书中还有许多小的改动。

第1章 C++面向对象程序设计 1
1.1 抽象数据类型 1
1.2 封装 1
1.3 继承 5
1.4 指针 7
1.4.1 指针和数组 9
1.4.2 指针和复制构造函数 11
1.4.3 指针和析构函数 13
1.4.4 指针和引用变量 14
1.4.5 函数指针 16
1.5 多态性 17
1.6 C++和面向对象程序设计 19
1.7 标准模板库 20
1.7.1 容器 20
1.7.2 迭代器 20
1.7.3 算法 21
1.7.4 函数对象 21
1.8 标准模板库中的向量 23
1.9 数据结构与面向对象编程 30
1.10 案例分析:随机访问文件 30
1.11 习题 39
1.12 程序设计作业 41

第2章 复杂度分析 44
2.1 计算复杂度和渐近复杂度 44
2.2 大O符号 45
2.3 大O符号的性质 47
2.4 Ω符号与Θ符号 48
2.5 可能的问题 49
2.6 复杂度举例 49
2.7 确定渐近复杂度举例 51
2.8 *好、平均和*坏情况 52
2.9 阻尼复杂度 55
2.10 NP完整性 58
2.11 习题 60

第3章 链表 64
3.1 单链表 64
3.1.1 插入 69
3.1.2 删除 71
3.1.3 查找 75
3.2 双链表 75
3.3 循环链表 79
3.4 跳跃链表 80
3.5 自组织链表 85
3.6 稀疏表 89
3.7 标准模板库中的链表 91
3.8 标准模板库中的双端队列 95
3.9 小结 99
3.10 案例分析:图书馆 100
3.11 习题 107
3.12 程序设计作业 109

第4章 栈与队列 113
4.1 栈 113
4.2 队列 119
4.3 优先队列 125
4.4 标准模板库中的栈 126
4.5 标准模板库中的队列 127
4.6 标准模板库中的优先队列 128
4.7 案例分析:迷宫问题 130
4.8 习题 135
4.9 程序设计作业 136

第5章 递归 139
5.1 递归定义 139
5.2 函数调用与递归实现 141
5.3 递归调用的剖析 143
5.4 尾部递归 145
5.5 非尾部递归 146
5.6 间接递归 151
5.7 嵌套递归 153
5.8 不合理递归 153
5.9 回溯 156
5.10 小结 162
5.11 案例分析:递归下降解释器 163
5.12 习题 169
5.13 程序设计作业 172

第6章 二叉树 175
6.1 树、二叉树和二叉搜索树 175
6.2 二叉树的实现 178
6.3 二叉搜索树的查找 181
6.4 树的遍历 183
6.4.1 广度优先遍历 183
6.4.2 深度优先遍历 184
6.4.3 不用栈实现的深度优先遍历 190
6.5 插入 195
6.6 删除 198
6.6.1 合并删除 198
6.6.2 通过复制进行删除 201
6.7 树的平衡 203
6.7.1 DSW算法 205
6.7.2 AVL树 207
6.8 自调整树 212
6.8.1 自重新构造树 212
6.8.2 “张开”策略 213
6.9 堆 217
6.9.1 将堆作为优先队列 219
6.9.2 将数组组织为堆 221
6.10 波兰记号和表达式树 224
6.11 案例分析:计算单词出现的频率 228
6.12 习题 234
6.13 程序设计作业 237

第7章 多叉树 243
7.1 B树家族 243
7.1.1 B树 244
7.1.2 B*树 252
7.1.3 B+树 253
7.1.4 前缀B+树 255
7.1.5 位树 257
7.1.6 R树 258
7.1.7 2-4树 260
7.1.8 标准模板库中的集和多集 270
7.1.9 标准模板库中的映射和多映射 274
7.2 trie 278
7.3 小结 285
7.4 案例分析:拼写检查器 285
7.5 习题 293
7.6 程序设计作业 294

第8章 图 299
8.1 图的表示法 300
8.2 图的遍历 301
8.3 *短路径 304
8.4 环的检测 311
8.5 生成树 314
8.6 连通性 316
8.6.1 无向图中的连通性 316
8.6.2 有向图中的连通性 318
8.7 拓扑排序 320
8.8 网络 321
8.8.1 *大流 321
8.8.2 成本*低的*大流 329
8.9 匹配 332
8.9.1 稳定匹配问题 337
8.9.2 分配问题 339
8.9.3 非二分图中的匹配集合 341
8.10 欧拉(Eulerian)图与汉密尔顿(Hamiltonian)图 343
8.10.1 欧拉图 343
8.10.2 汉密尔顿图 345
8.11 给图加上颜色 350
8.12 图理论中的NP完整性问题 352
8.12.1 派系问题 352
8.12.2 三色问题 353
8.12.3 顶点覆盖问题 354
8.12.4 汉密尔顿环问题 355
8.13 案例分析:惟一代表 356
8.14 习题 365
8.15 程序设计作业 369

第9章 排序 374
9.1 基本的排序算法 375
9.1.1 插入排序 375
9.1.2 选择排序 377
9.1.3 冒泡排序 379
9.2 决策树 380
9.3 **排序算法 383
9.3.1 希尔排序 383
9.3.2 堆排序 386
9.3.3 快速排序 389
9.3.4 归并排序 393
9.3.5 基数排序 396
9.4 标准模板库中的排序 400
9.5 小结 403
9.6 案例分析:多项式相加 403
9.7 习题 409
9.8 程序设计作业 411

第10章 散列 415
10.1 散列函数 415
10.1.1 除余法 416
10.1.2 折叠法 416
10.1.3 平方取中法 416
10.1.4 提取法 417
10.1.5 基数转换法 417
10.2 冲突解决方法 417
10.2.1 开放定址法 418
10.2.2 链接法 422
10.2.3 桶定址 424
10.3 删除 425
10.4 理想散列函数 426
10.4.1 Cichelli方法 426
10.4.2 FHCD算法 429
10.5 可扩展文件的散列函数 430
10.5.1 可扩展散列 431
10.5.2 线性散列 433
10.6 案例分析:使用桶的散列 435
10.7 习题 442
10.8 程序设计作业 443

第11章 数据压缩 446
11.1 数据压缩的条件 446
11.2 Huffman编码 447
11.3 Run-Length编码方式 458
11.4 Ziv-Lempel编码方式 459
11.5 案例分析:Huffman方法和Run-Length编码方式 462
11.6 习题 471
11.7 程序设计作业 471

第12章 内存管理 474
12.1 sequential-fit方法 475
12.2 Nonsequential-fit方法 475
12.3 无用单元回收 483
12.3.1 标记和清除 483
12.3.2 复制方法 489
12.3.3 递增的无用单元回收 490
12.4 小结 496
12.5 案例分析 496
12.6 习题 503
12.7 程序设计作业 504

第13章 字符串匹配 509
13.1 字符串的**匹配 509
13.1.1 简单的算法 509
13.1.2 Knuth-Morris-Pratt算法 512
13.1.3 Boyer-Moore算法 518
13.1.4 多次搜索 527
13.1.5 面向位的方法 528
13.1.6 单词集合的匹配 532
13.1.7 正则表达式的匹配 537
13.1.8 后缀trie和树 540
13.1.9 后缀数组 545
13.2 字符串的模糊匹配 546
13.2.1 字符串的近似性 547
13.2.2 有k个错误的字符串匹配 552
13.3 案例分析:*长的共有子字
符串 555
13.4 习题 561
13.5 程序设计作业 563

附录A 计算大O 566
A.1 调和数序列n 566
A.2 函数的近似值 566
A.3 快速排序中平均情况的大O 568
A.4 随机二叉树中的平均路径
长度 569
A.5 AVL树中的节点数 570
附录B 标准模板库中的算法 572
附录C NP完整性 581
……