本书全面系统地介绍了计算机科学教育中的一个重要组成部分——数据结构，并以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 trie278
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 计算大O566
A.1 调和数序列n566
A.2 函数的近似值566
A.3 快速排序中平均情况的大O568
A.4 随机二叉树中的平均路径
长度569
A.5 AVL树中的节点数570
附录B 标准模板库中的算法572
附录C NP完整性581