数据结构一直是计算机科学专业课程的核心内容，它是信息的组织方式。对于相同的算法，用不同的数据结构表示其中的抽象数据类型会造成不同的执行效率。
本书从面向对象程序设计的角度，具体使用C++语言，讲述了数据结构及其算法。通过对方法接口、示例和应用的学习，引导学生逐渐理解和掌握如何高效地使用数据结构。
本书与传统数据结构教材相比，除了保留系统、全面的风格之外，还具有重视与实际编程结合、侧重标准模板库的实现描述等特点；并配有丰富的习题及实验，是一本优秀的课堂和自学参考用书。
无
本书讲述了数据结构及算法。实现语言选用了C++，这适用于已经学习过相关基础课程的学生。这些课程并不一定是面向对象的，但应当覆盖基本语句和数据类型，比如数组和文件处理的基础。
标准模板库
本书的显著特点是其依据为标准模板库（STL）—这个库由惠普公司提供。使用这种方法有几个优点。首先，这些代码是被详尽检测过的；其次，读者通过本书有机会学习到以前没有接触过的专业代码，它是相当高效率和简洁的；第三，这个库在今后的课程中也是非常有用的。
大多数情况下库不会描述数据结构的实现。这是有好处的，我们可以将注意力放在功能而不是实现细节上。关于这些类的定义，可以参阅惠普研究实验室的Stepanov等人的原始实现（参见Stepanov and Lee，1994）。这个惠普实现是作者所知的全部实现的基础。
考虑过的其他实现
与标准模板库的惠普实现同样重要的是，本书不是只关注于数据结构和算法的基础课程。和惠普实现不同的方法也是值得考虑的。例如，list类的实现使用了有头节点的双向链表，它和单链表以及有头尾域的双向链表是不同的。另外本书还比较了不同实现的差异。当然，还有一些数据结构（像图）和算法（像回溯）是不在标准模板库里的。
本书也可以满足数据结构和算法课程的基本需要：让学生练习开发他们自己的数据结构。书中有许多编程项目，它们的数据结构要么是从头创建的，要么是从章中的范例扩展而来的。另外还有一些项目，是开发或扩展那些使用标准模板库的应用程序。
标准C++
所有的代码都是基于ANSI/ISO标准C++的，并且在Windows平台（C++ Builder和Visual C++）和Unix平台(G++)上测试过。标准模板库遵循的规范（不是指具体实现）是ANSI/ISO C++的一部分。
教学方法的特点
本书有几个特点，这些可以改善教学者的教学环境以及学生的学习环境。每章开头都给出了目标，末尾至少给出一个主要编程任务。每个数据结构都描述得很详细，每个方法都有一个前置条件和后置条件。另外，大部分方法都给出了调用示例以及调用结果。
对细节问题，特别是标准模板库的惠普实现，进行了认真的研究，并在29个实验中得到补充。参阅前言的“实验的组织”部分可以了解更多关于这些实验的信息。每章后都有多种习题，教师可以使用这些习题的答案。
辅助材料
所有的辅助材料都放在网站上：www.mhhe.com/collins。
网站为学生提供了下列信息的链接：
实验的观察以及入门方法。
本文开发的所有项目的源代码。
项目的Applet，它有一个很强的可视化组件。
另外，教师可以从网站获取下列信息：
教师关于实验的选择。
每章的PowerPoint幻灯片（大约1500张幻灯片）。
每章习题的答案，PowerPoint里展示的习题以及实验的答案。
章节纲要
第1章介绍了作为后续章节基础的C++的特点。大部分材料表现的都是面向对象技术：类，继承，构造器，析构器以及运算符的重载。通过实验来回顾类、继承和运算符的重载。
第2章介绍了容器类以及和容器类存储相关的问题。顺序存储和链式存储都需要使用指针。为了说明链式存储，创建了一个单链表类。这个过分简单的Linked类为描述标准模板库的几个关键特色（如模板、迭代器和通用型算法）提供了背景。相关的实验是基于指针、迭代器、运算符重载和通用型算法的。
第3章是软件工程简介，概述了开发软件的四个步骤：分析，设计，实现和维护。使用统一建模语言（UML）作为设计工具来描述继承、复合和聚合。贯穿后续章节的大O表示法可用于脱离环境来评估方法的时间代价。本章还探讨了带驱动器的运行时评估和计时，而且每个主题都对应一个实验。
第4章讲述了递归，它将重点暂时从数据结构转移到算法上。介绍了回溯，把回溯作为解决问题的一般技术。并采用了相同的BackTrack类，用于搜索迷宫、在棋盘上放置八个皇后（使她们不能互相攻击）等应用，并阐述了一个马可以遍历棋盘上的每个空格，而且每个空格只经过一次。其他的递归调用，如汉诺塔游戏和生成置换，更进一步地突出了递归的优雅，尤其是将它和对应的迭代实现相比较时。在后面的章节里也会遇到递归，特别是快速排序法的实现和二叉树的定义中。此外，对每个专业程序员而言，递归是一个必不可缺的工具。
在第5章里，开始使用vector和deque类学习标准模板库。向量是一个灵巧的数组：自动调整大小，并配有方法处理任意位置的插入和删除操作。而且，向量是模板化的，因此将int类型元素插入int类型向量的方法和将string类型元素插入string类型向量的方法是完全相同的。设计过程从vector类中最常用方法的方法接口（前置条件，后置条件和方法头）开始，然后是惠普的大致实现和实验中的进一步的细节。vector类的应用、高精度的算法是公钥加密算法的基础。这个应用在实验和编程项目里进行了更深层次的研究。队列和向量很相似，至少从数据结构的角度来说是这样的。但是实现细节上仍有较大区别，这些细微差异将在实验里探讨。
第6章描述了list数据结构和类，它们的特征是，方法花费线性时间进行随机插入、删除和检索。这个属性迫使它们使用链表迭代器：遍历list对象，并使用常数时间的方法在当前位置上插入、删除和检索对象。本章也介绍了双链式的环型实现，并在一个实验中介绍了其他细节。其应用是一个小的行编辑器，这很适合链表迭代器。在编程项目中对该应用做了进一步的扩展。还有关于迭代器种类，以及向量、双端队列和链表的运行时间比较的实验。
queue和stack类是第7章的主题。这两个类都是容器配接器：它们采用了其他一些类的方法接口。对queue和stack类而言，缺省的“其他”类都是deque类。因而得到的stack和queue类的方法定义都是单行的。队列的具体应用—计算洗车处的平均等待时间，属于计算机仿真的范畴。stack类有两个应用：递归的实现，以及中缀到后缀的转换。后一个应用在实验中进行了扩展，并构成了“求一个条件的值”编程项目的基础。
第8章的重点是一般的二叉树，特别是折半查找树。介绍了二叉树的基本特点；这些对理解AVL树、红黑树、堆、霍夫曼树和决策树是很重要的。折半查找树类是红黑树的惠普实现的单色版本。
第9章中考察了AVL树。作为实现重新平衡的机制，介绍了旋转。借助于斐波纳契树，确定了AVL树的高度总是和树中项的数量成对数关系。AVLTree类不是标准模板库的组成部分，但是包含了几个重要的特色，如函数对象；还对该难题提供了后续的实验研究。除了erase方法（编程项目9.1）之外，整个类都得到了实现。AVL树的应用是一个简单的拼写检查器。
红黑树在第10章中进行了研究。仔细研究了红黑树中的插入和删除算法，并且提供了相关的实验。红黑树不在标准模板库中，但是它们是标准模板库中四个关联容器类（set、map、multiset和multimap）大部分实现的基础。在一个集合里，每个项只由一个键组成，是不允许重复键的。多集合允许重复键。在一个映射里，每个项只由一个惟一的键部分和另一部分组成。多映射允许重复键。本章还介绍了一个应用（用来计算文件中每个单词出现的频率），以及有关四个关联容器类的实验。
第11章介绍了priority_queue类，即另一个容器配接器。缺省使用的是vector类，但幕后还有一个堆，使得以常数平均时间进行插入，而且即使在最坏情况下，也能以对数时间删除最高优先级的元素。可以考虑基于list或基于set的实现。它的应用是在数据压缩领域，特别是霍夫曼编码：给定一个文本文件，生成一个最小的无前缀编码。编程项目的任务是将编码转换回原来的文本文件。实验将公平性融进了优先队列，这样即便是同为最高优先级的项，也总是先处理在优先队列中滞留时间最长的。
排序是第12章的主题。开发了基于比较的排序的最小上界的估算。研究了四种“快速”排序：树排序（多集合），堆排序（随机访问容器），归并排序（列表）和快速排序（随机访问容器）。本章的实验在随机产生的数值上比较了这些排序方法。编程项目是排序姓名和社会保障号码文件。
第13章先开始复习了顺序和折半查找，然后研究了散列。通常，在标准C++或标准模板库的惠普实现中都不支持散列类。本章开发了一个hash_map类。这个类的方法接口和map类的是相同的，除了插入，删除或查找的平均时间花费是常数而不是对数时间！应用包含了字符表的创建和维护，以及对第9章中拼写检查器应用的修正。还比较了链式散列和开放地址散列；在编程项目中进一步探索了它们的不同。hash_map类的速度是实验的主题。
第14章介绍了最常用的数据结构—图、树和网络。给出了基本算法的框架：广度优先迭代，深度优先迭代，连通性，寻找最小生成树以及查找两个顶点间的最短路径。开发的惟一的类是使用邻接表实现的network类。其他类（如undirected_graph和undirected_network）可以直接定义为network类的子类。在实验中研究了货郎担问题，并且提出了一个编程项目，要求完成network类的邻接矩阵版本。本章还提出了另一个回溯应用，使用的仍然是第4章所介绍的BackTrack类。
每一章都对应一个相关的网页，其中包括了该章中开发的所有程序以及适于阐释概念的Applet。
附录
附录1包含了有助于学生理解书中数学概念的背景信息。累加符号和对数的初步性质是最基本的，而数学归纳原理使得我们能更深地分析二叉树和开放地址散列。
string类是附录2的主题。这个功能强大的类是标准模板库的一个重要组成部分，并使得学生可以绕开乏味的字符数组。
多态性是一个指针引用对象层次中不同对象的能力，在附录3中进行了说明。多态性是面向对象编程的一个基本特性，但被归入了附录，因为它并不是介绍数据结构和算法所必需的论题。
实验的组织
本书中共涉及到29个网络实验。学生和教师可以访问的URL是：
www.mhhe.com/collins
实验不只包含了基本素材，还提供了对文字材料的补充。例如，在研究了vector、deque和list类之后，用一个实验对这三个类进行了一些时间测试。
实验是独立的，因此教师可以很灵活地指定实验。可以将它们指定为：
1) 闭卷实验
2) 开卷实验
3) 不计分作业
除了能明显地提高学习积极性，这些实验还能鼓励学生运用科学的方法。学生们观察到一些现象，如标准模板库的list类的组织。然后阐明并提交一个关于该现象的假设—以及他们自己的代码。测试之后可能需要修正他们的假设，提交根据实验得到的最终结论。
Bill Collins
周翔：暂无简介
数据结构一直是计算机科学专业课程的核心内容。它是信息的组织方式。对于相同的算法，用不同的数据结构表示其中的抽象数据类型会造成不同的执行效率。因此，对数据结构的研究一直是计算机科技工作者努力的方向。本书从面向对象程序设计语言的角度讲述数据结构及其算法，使用了惠普公司提供的标准模板库（STL）作为基础，代码具有简洁性和高效率的特点，有很重要的实践意义。
在教材内容的安排上，本书仍按照各种不同的数据结构分类进行系统的介绍。在给出了面向对象程序设计及容器类的一般概念之后，通过堆栈、队列、树等常用数据结构剖析了方法接口及其简单的应用。随着C++的广泛应用，容器和模板也越来越受到编程者的重视。以往的教材虽然也详尽地介绍了各种数据结构，但总局限于理论上的探讨；与此不同的是，本书更强调标准模板库的使用，而不仅仅是一般的结构和算法。在介绍每种结构时，都尽可能地融入了它在STL中的表现形式和接口，这样就较好地解决了数据结构和实际编程应用脱节的问题。
本书与传统数据结构教材相比，除了保留系统、全面的风格之外，还增加了以下的新特点：
重视数据结构与实际编程的结合。书中的源代码都使用C++语言编写，并进行了验证，更方便有编程需要的读者理解和使用。
侧重STL。书中提供了大量的方法接口及实例分析。
使用了大量的文本和图表进行辅助说明。
每章都包含了章节目标及丰富的习题，对了解学习要求和进一步深入学习提供了很好的帮助。
对于学习和了解数据结构的本、专科学生及研究生而言，本书可作为他们的教材和教学参考书；而对于编程人员、技术服务人员以及程序使用者而言，本书也是一本很好的参考读物。
译 者
2003年9月
第1章 C++中的类 1
1.1 类 1
1.1.1 方法接口 1
1.1.2 对象 2
1.1.3 数据抽象 4
1.1.4 构造器 6
1.1.5 一个Employee类 7
1.1.6 Employee类的定义 11
实验1：Company项目 13
1.1.7 继承 13
1.1.8 受保护的访问 14
1.1.9 HourlyEmployee类 15
实验2：关于继承的更多的细节 18
1.1.10 运算符的重载 19
1.1.11 友元 20
实验3：重载运算符“=”和运算符“>>” 21
1.1.12 信息隐藏 21
总结 22
习题 22
编程项目1.1：一个Sequence类 25
第2章 容器类的存储结构 27
2.1 指针 27
2.1.1 堆和堆栈的对比 29
2.1.2 引用参数 29
2.1.3 指针字段 30
2.1.4 数组和指针 30
实验4：指针变量赋值与动态变量赋值的对比 31
2.1.5 动态变量的存储空间释放 31
2.2 数组 32
2.3 容器类 33
2.3.1 容器类的存储结构 33
2.3.2 链式结构 34
2.3.3 迭代器 37
2.3.4 Iterator类的设计和实现 39
实验5：定义其他的迭代器运算符 40
2.3.5 pop_front方法 40
2.3.6 析构器 41
实验6：重载运算符operator = 42
2.3.7 通用型算法 42
实验7：更多关于通用型算法的知识 46
2.3.8 数据结构和标准模板库 46
总结 46
习题 47
编程项目2.1：扩展Linked类 47
第3章 软件工程简介 49
3.1 软件开发生命周期 49
3.2 问题分析 49
3.3 程序设计 51
3.3.1 方法接口和字段 51
3.3.2 依赖关系图 53
3.4 程序实现 54
3.4.1 方法验证 55
实验8：驱动器 56
3.4.2 正确性实现的可行性 56
3.4.3 方法效率评估 56
3.4.4 大O表示法 57
3.4.5 快速获取大O估算 59
3.4.6 平衡折中 62
3.4.7 运行时间分析 63
3.4.8 随机性 65
实验9：计时和随机性 66
3.4.9 类型转换 66
3.5 程序维护 67
总结 67
习题 67
编程项目3.1：Linked类的进一步扩充 69
第4章 递归 71
4.1 简介 71
4.2 阶乘 71
4.3 十进制到二进制的转换 75
实验10：斐波纳契数 78
4.4 汉诺塔 78
4.5 回溯 86
4.6 折半查找 97
实验11：迭代折半查找 106
4.7 生成置换 106
4.8 间接递归 114
4.9 递归的代价 115
总结 116
习题 116
编程项目4.1：汉诺塔的迭代版本 121
编程项目4.2：八皇后问题 122
编程项目4.3：马的遍历问题 123
第5章 向量和双端队列 127
5.1 标准模板库 127
5.2 向量 128
5.2.1 vector类的方法接口 129
5.2.2 向量迭代器 134
5.2.3 向量和其他容器的对比 136
5.2.4 vector类可能的字段 137
5.2.5 vector类的一个实现 137
实验12：vector类的更多的实现细节 142
5.3 向量的一个应用：高精度算法 142
5.3.1 very_long_int类的设计 143
5.3.2 very_long_int类的一个实现 144
实验13：扩展very_long_int类 147
5.4 双端队列 147
实验14：惠普的deque类实现的更多细节 154
5.5 双端队列的一个应用：非常长的整数 154
总结 154
习题 155
编程项目5.1：扩展very_long_int类 157
编程项目5.2：deque类的另一种实现 157
第6章 表 159
6.1 表 159
6.1.1 list类的方法接口 160
6.1.2 迭代器接口 163
6.1.3 链表方法和向量或双端队列方法的差别 165
6.1.4 list类的字段和实现 166
6.1.5 list节点的存储 171
实验15：更多list类的实现细节 174
实验16：计时顺序容器 174
实验17：迭代器，第二部分 174
6.1.6 list类的其他实现 175
6.2 链表应用：一个行编辑器 177
6.2.1 Editor类的设计 180
6.2.2 Editor类的实现 182
总结 187
习题 187
编程项目6.1：扩展Editor类 189
编程项目6.2：list类的另一种设计和实现 195
第7章 队列和堆栈 197
7.1 队列 197
7.1.1 queue类的方法接口 197
7.1.2 使用queue类 200
7.1.3 容器配接器 201
7.1.4 一个接近的设计 202
7.2 计算机仿真 204
7.3 队列应用：洗车仿真 205
7.3.1 程序设计 207
7.3.2 CarWash类的实现 208
7.3.3 CarWash方法的分析 212
7.3.4 随机化到达时间 212
实验18：随机化到达时间 214
7.4 堆栈 214
7.4.1 Stack类的方法接口 214
7.4.2 使用stack类 215
7.4.3 stack类是一个容器配接器 216
7.5 堆栈应用1：递归是如何实现的 216
7.6 堆栈应用2：将中缀转换成后缀 222
7.6.1 后缀表示法 224
7.6.2 转换矩阵 226
7.6.3 记号 227
实验19：将中缀转化成后缀 228
7.6.4 前缀表示法 228
总结 230
习题 231
编程项目7.1：扩展洗车仿真 232
编程项目7.2：求一个条件的值 233
编程项目7.3：一个迭代的迷宫搜索 237
编程项目7.4：queue类的另一个设计 237
第8章 二叉树和折半查找树 239
8.1 定义和属性 239
8.1.1 二叉树定理 245
8.1.2 外部路径长度 247
8.1.3 二叉树的遍历 248
8.2 折半查找树 253
8.2.1 BinSearchTree类 254
8.2.2 BinSearchTree类的Iterator类 255
8.2.3 BinSearchTree类的字段和实现 257
8.2.4 递归方法 261
8.2.5 BinSearchTree迭代器 269
实验20：BinSearchTree的平均高度 270
总结 270
习题 271
编程项目8.1：BinSearchTree类的另一种实现 274
第9章 AVL树 277
9.1 平衡的折半查找树 277
9.2 旋转 277
9.3 AVL树 281
9.3.1 AVL树的高度 282
9.3.2 函数对象 284
实验21：更多的函数对象的细节 286
9.3.3 AVLTree类 286
9.3.4 fixAfterInsertion方法 289
9.3.5 insert方法的正确性 297
9.4 AVL树的应用：一个简单的拼写检查器 299
总结 302
习题 302
编程项目9.1：AVLTree类的erase方法 305
编程项目9.2：改进的SpellChecker项目 305
第10章 红黑树 307
10.1 红黑树 307
10.1.1 红黑树的高度 310
10.1.2 惠普的rb_tree类 313
10.1.3 rb_tree类中的insert方法 315
实验22：使用全部三种情况的红黑树插入 320
10.1.4 erase方法 320
实验23：erase的调用，其中应用了全部四种情况 331
10.2 标准模板库的关联容器 331
10.3 集合应用：再次讨论拼写检查器 334
10.3.1 multiset类 335
实验24：更多与set和multiset类相关的知识 336
10.3.2 map类 336
10.3.3 multimap类 339
实验25：更多与map和multimap类相关的知识 340
总结 340
习题 340
编程项目10.1：一个简单的辞典 343
编程项目10.2：创建一个词汇索引 343
第11章 优先队列和堆 347
11.1 介绍 347
11.1.1 priority_queue类 348
11.1.2 priority_queue类的字段和实现 350
11.1.3 堆 351
实验26：优先队列中的公平性 359
11.1.4 priority_queue类的另一种设计及实现 359
11.2 优先队列的应用：霍夫曼编码 360
11.2.1 huffman类的设计 364
11.2.2 huffman类的实现 366
总结 371
习题 372
编程项目11.1：解码一个消息 374
第12章 排序 377
12.1 介绍 377
12.2 排序能有多快 380
12.3 快速排序 382
12.3.1 树排序 382
12.3.2 堆排序 383
12.3.3 归并排序 385
12.3.4 快速排序 390
12.3.5 分治法算法 395
实验27：排序算法的运行时间 396
总结 396
习题 397
编程项目12.1：排序一个文件 402
第13章 查找和散列类 405
13.1 分析查找的框架 405
13.2 查找方式复习 405
13.2.1 顺序查找 405
13.2.2 折半查找 406
13.2.3 红黑树查找 408
13.3 hash_map类 408
13.3.1 hash_map类中的字段 409
13.3.2 散列 409
13.3.3 链式 412
13.3.4 iterator类的字段和实现 419
13.3.5 hash_map类的实现 420
13.3.6 链式散列分析 423
13.3.7 value_type类 425
13.3.8 应用 425
实验28：hash_map计时 427
13.4 hash_set类 427
13.5 开放地址散列 427
13.5.1 erase方法 430
13.5.2 主聚类 434
13.5.3 双散列 435
13.5.4 开放地址散列分析 439
总结 441
习题 442
编程项目13.1：使用链式和双散列构造一个符号表的运行时间比较 444
第14章 图、树和网络 445
14.1 无向图 445
14.2 有向图 447
14.3 树 448
14.4 网络 450
14.5 图算法 451
14.5.1 迭代器 451
14.5.2 连通性 457
14.5.3 产生最小生成树 458
14.5.4 寻找网络中的最短路径 462
14.6 开发一个网络类 465
14.7 network类 465
14.7.1 network类中的字段 467
14.7.2 network类的实现 469
14.7.3 与边相关的方法的实现 470
14.7.4 全局方法的实现 472
14.7.5 get_minimum_spanning_tree方法 475
14.7.6 get_shortest_path方法 476
14.7.7 网络方法的时间花费估算 478
实验29：货郎担问题 479
14.7.8 network类的另一种设计和实现 479
14.8 回溯通过网络 481
总结 483
习题 484
编程项目14.1：完成邻接矩阵的实现 486
编程项目14.2：回溯通过一个网络 486
附录1 数学背景 489
附录2 string类 501
附录3 多态性 511
参考文献 515
索引 517
