数据结构和算法课程是计算机科学教育的核心内容，本书提供了该领域必备的知识。根据当前的设计和实现范例，本书以面向对象的方式描述数据结构，深入浅出地讲解了相关的难点。Drozdek强调了数据结构和算法之间的关系，分析了算法的复杂性，还讲解了增强封装和分解的信息隐藏原理，对递归方法和递归进行了清晰、详尽的阐述。
本书第1版取材新颖，被很多学校采用为教学参考书。第2版在延续了第1版理论结合实际的风格的同时，在理论上更精深了一层，添加了很多数据结构的经典问题与新的思想，比如NP完整性、图论中的团问题以及结合自动机理论探讨的字符串匹配技术等。
本书特点：
示例学习 贯穿全书，从实际应用的角度诠释概念。
编程作业 为读者提供大量的实践机会。
丰富的图表 增强对数据结构用途的理解。
清晰地阐述递归 即使对高年级学生而言，这也是具有挑战性的主题。
无
数据结构既是计算机科学教育的一个重要组成部分，又是其他计算机研究领域的基础。数据结构的很多知识是希望从事软件系统的设计、实现、测试和维护的学生所必须具备的。本书为这类学生提供了必要的知识。
本书主要讲述了数据结构的三个重要方面。第一，重点强调数据结构和算法间的联系，包括分析算法的复杂性。第二，根据当前设计和实现范例，以面向对象的方式描述数据结构。特别是强调了增强封装和分解的信息隐藏原理。最后一个重要部分是数据结构的实现，选择Java作为编程语言。
Java语言作为C和C++的面向对象的后代语言，流行于工业和学术领域内。由于它在Internet上的广泛应用，被认为是一种优秀的编程语言。因为Java一致地使用面向对象的性质以及语言的安全性，所以，用Java来介绍数据结构是很自然的事情。当前，C++是数据结构教学的主选语言。不过，由于Java在应用程序编程中的广泛应用以及它的面向对象特性，使用Java来讲授数据结构和算法课程，即使对于初学者也是很恰当的。
本书可以作为旧版ACM课程中CS2和CS7的课程教材，同时，也符合新版ACM课程中CA202，CD202和CF 204大多数课程的要求。 很多章都包括示例学习，用来说明某个算法和数据结构的应用的完整上下文。这些示例学习是从计算机科学的不同领域（比如解释器、符号计算和文件处理等）中摘选出来的，反映了讨论的主题可以应用的广阔范围。
Java代码的简单实例贯穿全书，阐述了数据结构在实践中的重要性。但是，理论分析也是同样重要的。因此，算法描述往往和效率分析结合在一起。
在描述递归时要特别小心，因为即使是高年级学生在处理它时也会出问题。经验说明，只有考虑运行时堆栈，才能最好地诠释递归。不只是在递归的章节，在其他章也有对递归函数的跟踪，用来显示堆栈的变化。例如，如果不解释系统在运行堆栈上所做的工作，那么遍历树的出奇短的方法可能就是个谜。讨论数据结构和算法时如果远离系统，用纯理论的态度未必有效。本书还全面地讨论了数据压缩和存储管理。
本书介绍的重点是数据结构，其他方面的主题讨论是为了帮助读者正确地理解数据结构。算法是从数据结构的角度考虑的，因此，读者看不到多种不同类型的算法的全面讨论以及对某个算法的完整描述。但如前所述，本书深刻地诠释了递归，还详细描述了算法的复杂性分析。
第1章和第3～8章介绍了不同的数据结构和操作它们的算法。分析了每个算法的效率，并提出了改进算法的建议。
* 第1章讲述面向对象编程的基本原理，介绍动态内存分配和指针的使用以及Java基础知识。
* 第2章描述评定算法效率的方法。
* 第3章介绍链表。
* 第4章介绍堆栈、队列及其应用。
* 第5章包含对递归的详细讨论，讨论多种类型的递归并剖析一个具体的递归调用。
* 第6章讨论二叉树，包括实现、遍历和查找。并且介绍了平衡树。
* 第7章描述更一般的树，如检索树、2-4树和B树。
* 第8章描述图的理论和方法。
第9~12章描述了前几章介绍的数据结构的不同应用，突出了每个主题所涉及的数据结构。
* 第9章详细分析排序，描述了几个基本的和非基本的方法。
* 第10章讨论散列—查找中最重要的领域之一。在描述不同技术的同时，强调数据结构的使用。
* 第11章讨论数据压缩算法和数据结构。
* 第12章描述存储管理的不同技术和数据结构。
* 第13章讨论精确和近似字符串匹配的多种算法。
* 附录A详尽讨论第2章介绍的大O符号。
* 附录B给出库克（Cook）定理的证明，并结合示例进行阐述。
每一章包含对某个素材的讨论，并配有相应的图表说明。除第2章之外，其他所有章都包含示例学习，即使用该章讨论的特性的扩展实例。所有的示例学习都在PC机上用Visual C++编译器，或是在UNIX上用g++编译器测试过（除von Koch雪花问题之外）。每章的后面是各种难度的习题。除了第2章之外，每一章还有编程作业和最近的相关文献的参考书目。
第1~6章（除了第2.9，3.4，6.4.3，6.7和6.8节之外）包含数据结构课程的核心素材，应当顺序学习。余下的六章可以按任意顺序学习。一个学期的课程可以包括第1~6章，第9章，第10.1节和10.2节。全书也可以作为两学期课程的教材。 教学工具 电子版教师手册。教师手册包含了本书所有习题的完整解答。 电子版图文件：提供授课所需的本书中所有图像文件。
源代码。书中的示例源代码可以通过Web站点下载，地址是：http://www.mathes.duq.edu/ drozdek/DSinJava。
源代码部分，学生也可以从www.course.com下载。除此之外，上述教辅资源仅适用于教师教学使用。需要者请与汤姆森学习出版集团北京代表处联系。（具体联系方式请见本书最后所附的“教学支持服务”说明表。—编辑注） 第2版的变化 相对于第1版，本书增加了一些关于新主题的素材。主要有 新添的第13章的模式匹配算法。
* 简要介绍NP完整性（第2.10节），举例讨论NP完整性问题（第8.12节），库克定理的概要（附录B）。
* 关于图的新素材（第8.9.1节，8.10.1.1节，8.10.2.1节，8.11节）。
* 讨论垂直水平树的删除算法 ǖ .1.7节）。
* 介绍Java文件（第1.3.1~1.3.6节）。
同时还更新了java.util软件包中的方法列表。此外，还有一些小的改动，不再一一赘述。 致谢 衷心感谢下列人士的审阅，他们为本书的改进提供了宝贵意见和建议：James Ball（Indiana State University）、Robin Dawes（Queen誷 University）和Julius Dichter（University of Bridgeport）。 作为本书作者，欢迎读者对本书中的疏漏和不足进行指正，我的电子邮箱是：drozdek@duq.edu。
Adam Drozdek
Adam Drozdek：Adam Drozdek: 毕业于美国莱特州立大学，现任迪尤肯大学计算机科学系副教授。曾出版多部著作，包括《Data Structures and Algorithms in C++》和《The Elements of Data Compression》等。
周翔：暂无简介
随着计算机的普及和硬件的不断升级，软件业的市场不断扩大。当前的用户对软件的期望不仅局限于满足功能方面的需求，同时还要求节约空间、提高效率。因而，对程序设计者提出了更高的要求。编写比传统意义更“好”的软件在一定程度上表现为寻求最佳的算法以及简洁的数据，数据结构的内容正是试图涵盖这两方面的理念。
编程语言自出现以来，经历了结构化编程-面向对象-面向方面的发展过程。目前，编程者广泛采用的仍是面向对象的OOP技术。Java语言作为一种面向对象的编程语言，在诞生之后，因其具有完备的功能和跨平台的特性，逐渐为计算机领域的广大科技工作者所接受。Java不仅可以用来实现计算机用户的各项基本要求，同时还能为当前流行的嵌入式、网络分布式系统服务。由于Java语言在商业领域取得的巨大成就，被很多国外大学选用为计算机专业学生的程序设计语言课程。本书采用Java语言实现算法，取代过去传统的C语言教学模式，突出OOP的封装和分解的信息隐藏原理，以更好地适应当前计算机技术更新进步的需要。
本书2003年出版了第1版，因取材新颖，被很多国内外院校采用为教学参考书。第2版相对于第1版而言，延续了理论结合实际的风格，在介绍理论的同时，配合大量的实际应用案例。用丰富生动的图表诠释枯燥的概念。同时，在章节后面附以示例学习和编程作业，循序渐进、深入浅出地帮助读者理解并灵活应用数据结构理论。
本书由周翔统稿翻译，由隋立恒完成了全书的审校。全书共分13章，其中第1章、第2章介绍了Java的入门知识以及复杂性计算的数学基础，特别对第1版而言，添加了关于NP完整性的讨论；第3~8章介绍了一些基本的数据结构以及操作算法，其中增加了很多经典问题，如图论的邮递员、旅行商、团问题等；第9~12章描述各种数据结构在软件开发中的应用；第13章字符串匹配是第1版中未涉及的领域。字符串作为计算机常用的一种数据，其编码、匹配技术广泛应用在软件开发和网络检测等各项领域。本书结合自动机理论和各种数据结构给出了多种匹配算法；最后的附录则是数学知识方面的补充。对使用者尤其是教学人员而言，第2版内容的更新、补充和整体编排、重构意义重大，作者试图从更深层面、更广泛的角度与读者做有意义的探讨。
作为一名不够资深的译者，我深知计算机行业发展的迅速和自己水平的有限，虽多经揣摩但译文中仍难免存在一些疏误，真诚欢迎热心的读者给予批评指正，以便帮助我们学习提高和今后再版时校正。 在此还要感谢我的家人和朋友在翻译过程中给予的理解和支持，特别要感谢机械工业出版社华章分社的编辑负责、细致的工作，使本书顺利地翻译出版，与读者见面。
周 翔
2006年2月
第1章 Java语言的面向对象编程 1
1.1 Java入门 1
1.1.1 变量的声明 1
1.1.2 运算符 3
1.1.3 选择语句 3
1.1.4 循环语句 4
1.1.5 异常处理 5
1.2 Java面向对象编程 6
1.2.1 封装 6
1.2.2 抽象数据类型 12
1.2.3 继承 13
1.2.4 多态性 16
1.3 输入和输出 19
1.3.1 输入、输出字节 21
1.3.2 行输入 21
1.3.3 标志输入：单词和数字 22
1.3.4 基本数据类型的输入和输出 22
1.3.5 对象的输入和输出 23
1.3.6 随机存取文件 24
1.4 Java和指针 24
1.5 java.util中的向量 28
1.6 数据结构和面向对象的编程 32
1.7 示例学习：随机存取文件 32
1.8 习题 39
1.9 编程作业 41
参考文献 42
第2章 复杂性分析 44
2.1 计算复杂性和渐近复杂性 44
2.2 大O表示法 44
2.3 大O表示法的性质 46
2.4 W和Q表示法 47
2.5 可能出现的问题 48
2.6 复杂性示例 48
2.7 寻找渐近复杂性：示例 49
2.8 最好的、平均的和最坏的情况 51
2.9 平摊复杂性 53
2.10 NP完整性 56
2.11 习题 58
参考文献 60
第3章 链表 62
3.1 单向链表 62
3.1.1 插入 66
3.1.2 删除 67
3.1.3 查找 70
3.2 双向链表 72
3.3 循环链表 74
3.4 跳转表 75
3.5 自组织表 80
3.6 稀疏表 83
3.7 java.util的链表 85
3.7.1 LinkedList 85
3.7.2 ArrayList 89
3.8 结论 91
3.9 示例学习：图书馆 92
3.10 习题 99
3.11 编程作业 101
参考文献 103
第4章 堆栈和队列 105
4.1 堆栈 105
4.2 队列 111
4.3 优先级队列 117
4.4 示例学习：脱离迷宫 118
4.5 习题 122
4.6 编程作业 124
参考文献 125
第5章 递归 126
5.1 递归定义 126
5.2 方法调用和递归实现 128
5.3 剖析递归调用 129
5.4 尾递归 132
5.5 非尾递归 133
5.6 间接递归 137
5.7 嵌套递归 139
5.8 过分递归 139
5.9 回溯 142
5.10 小结 147
5.11 示例学习：递归下降解 推 147
5.12 习题 153
5.13 编程作业 155
参考文献 157
第6章 二叉树 158
6.1 树、二叉树和二叉查找树 158
6.2 二叉树实现 161
6.3 搜索二叉查找树 163
6.4 树的遍历 164
6.4.1 广度优先遍历 165
6.4.2 深度优先遍历 165
6.4.3 无堆栈深度优先遍历 171
6.5 插入 175
6.6 删除 178
6.6.1 归并删除法 179
6.6.2 复制删除法 181
6.7 树的平衡 183
6.7.1 DSW算法 185
6.7.2 AVL树 187
6.8 自调整树 191
6.8.1 自重构树 192
6.8.2 伸展树 192
6.9 堆 196
6.9.1 堆作为优先级队列 197
6.9.2 以堆的形式组织数组 199
6.10 波兰表示法和表达式树 202
6.11 示例学习：计算单词频率 206
6.12 习题 212
6.13 编程作业 214
参考文献 217
第7章 多分树 220
7.1 B树家族 220
7.1.1 B树 221
7.1.2 B*树 229
7.1.3 B+树 230
7.1.4 前缀B+树 232
7.1.5 比特树 233
7.1.6 R树 235
7.1.7 2-4树 236
7.1.8 java.util中的树 248
7.2 检索树 257
7.3 结论 264
7.4 示例学习：拼写检查程序 264
7.5 习题 273
7.6 编程作业 274
参考文献 277
第8章 图 279
8.1 图的表示法 280
8.2 图的遍历 281
8.3 最短路径 284
8.4 圈检测 291
8.5 生成树 293
8.6 连通性 297
8.6.1 无向图的连通性 297
8.6.2 有向图的连通性 300
8.7 拓扑排序 302
8.8 网络 303
8.8.1 最大流 303
8.8.2 最小代价的最大流量 311
8.9 匹配 313
8.9.1 稳定匹配问题 318
8.9.2 分配问题 319
8.9.3 非二部图中的匹配 321
8.10 欧拉图和哈密顿图 322
8.10.1 欧拉图 322
8.10.2 哈密顿图 324
8.11 图的着色 329
8.12 图论中的NP完整性问题 331
8.12.1 团问题 331
8.12.2 3色问题 332
8.12.3 顶点覆盖问题 333
8.12.4 哈密顿回路问题 333
8.13 示例学习：典型代表问题 335
8.14 习题 336
8.15 编程作业 345
参考文献 346
第9章 排序 349
9.1 基本排序算法 350
9.1.1 插入排序 350
9.1.2 选择排序 352
9.1.3 冒泡排序 353
9.2 决策树 355
9.3 高效排序算法 357
9.3.1 Shell排序 357
9.3.2 堆排序 360
9.3.3 快速排序 363
9.3.4 归并排序 367
9.3.5 基数排序 370
9.4 java.util中的排序 373
9.5 总结 375
9.6 示例学习：多项式加法 376
9.7 习题 383
9.8 编程作业 384
参考文献 384
第10章 散列 387
10.1 散列函数 387
10.1.1 除法 387
10.1.2 折叠法 388
10.1.3 平方取 泻 388
10.1.4 提取方法 388
10.1.5 基数变换 388
10.2 冲突解决 389
10.2.1 开放定址法 389
10.2.2 链 393
10.2.3 桶定址法 394
10.3 删除 394
10.4 完全散列函数 395
10.4.1 Cichelli方法 396
10.4.2 FHCD算法 398
10.5 可扩展文件的散列函数 400
10.5.1 可扩展散列 400
10.5.2 线性散列 402
10.6 java.util中的散列 404
10.6.1 HashMap 404
10.6.2 HashSet 407
10.6.3 Hashtable 410
10.7 示例学习：桶散列 414
10.8 习题 421
10.9 编程作业 422
参考文献 423
第11章 数据压缩 425
11.1 数据压缩的条件 425
11.2 赫夫曼编码 426
11.3 顺串长度编码 436
11.4 Ziv-Lempel编码 437
11.5 示例学习：结合顺串长度编码的 赫夫曼方法 439
11.6 习题 448
11.7 编程作业 448
参考文献 449
第12章 存储管理 451
12.1 顺序适配方法 451
12.2 非顺序适配算法 452
12.3 无用单元收集 459
12.3.1 标记和清除算法 459
12.3.2 复制方法 465
12.3.3 增量式无用单元收集 466
12.4 总结 471
12.5 示例学习：内置无用单元收集器 472
12.6 习题 473
12.7 编程作业 479
参考文献 481
第13章 字符串匹配 484
13.1 精确字符串匹配 484
13.1.1 直接匹配算法 484
13.1.2 Knuth-Morris-Pratt算法 486
13.1.3 Boyer-Moore算法 492
13.1.4 多路查找 500
13.1.5 面向位方法 501
13.1.6 词匹配集 504
13.1.7 正则表达式匹配 510
13.1.8 后缀检索树和树 513
13.1.9 后缀数组 517
13.2 近似字符串匹配 518
13.2.1 字符串相似度 519
13.2.2 k误配的字符串匹配 524
13.3 示例学习：最长公共子字符串 526
13.4 习题 533
13.5 编程作业 535
参考文献 535
附录A 大O的计算 537
A.1 谐波级数 537
A.2 函数lg (n!) 的近似 537
A.3 快速排序平均情况的大O 538
A.4 随机二叉树中的平均路径长度 540
A.5 AVL树中的节点数量 541
附录B NP完整性 542
索引 554
