在C语言作为教学语言时期，数据结构几乎都是用C语言来描述其算法。Java语言诞生后，以其功能完备及跨平台等特性，逐渐为计算机领域广大科技工作者所偏爱。因此，用Java语言来描述数据结构及其算法，有着很重要的现实意义。本书顺应了计算机科学发展的需要，以面向对象的方式描述了数据结构的设计和实现范例，在数据结构的实现中用Java作为编程语言。
本书的重点是数据结构，算法是从数据结构的角度来考虑的。本书强调了数据结构和算法之间的联系，详尽地描述了不同类型的递归，在每一章(除了第2章)都提供了示例学习和编程作业。本书适合作为初学数据结构的学生的教材，同时也为高年级学生提供了一些极富吸引力的内容。
数据结构的学习，既是计算机科学教育的一个重要组成部分，又是其他计算机研究方向的基础。数据结构的很多知识是希望从事任何软件系统的设计实施、测试和维护的学生所必需的。本书为这类学生提供了所需的知识。
本书主要讲述了数据结构的三个重要方面。第一，重点强调了数据结构和算法间的联系，包括分析算法的复杂性。第二，根据当前设计和实现范例，以面向对象的方式描述数据结构。特别是强调了提升封装和分解的信息隐藏原理。最后，这本书的一个重要的部分是数据结构的实现，它选择了Java作为编程语言。
Java作为C和C++的面向对象的后代语言，在工业和学术领域内都很流行，由于它适于Internet的广泛应用，所以被认为是一种优秀的编程语言。因为Java能一致使用面向对象的特性以及语言安全性，所以用Java来介绍数据结构成为很自然的事情。当前，C++是教授数据结构的首选语言，但由于Java在应用程序编程中的广泛应用以及它的面向对象特性，使用Java来讲授数据结构和算法课程，即使对于初学者来说也是很恰当的。
大部分章节都包括了一个示例学习，说明了使用某些算法和数据结构的完整的上下文。
这些示例是从计算机科学的不同领域(像解释器、符号计算和文件处理等)中挑选出来的，用来说明讨论的主题可以应用的广阔的范围。
Java代码的简单示例贯穿全书，阐述了数据结构的应用重要性。但理论分析同样重要，因此，算法描述和效率分析就结合在一起。
描述递归时要特别小心，因为即使是高年级的学生在处理它时也常出问题。经验说明，只有考虑运行时的堆栈，递归才能被最好地诠释。不只是在递归的章节，在其他章节中也有通过跟踪一个递归函数来显示堆栈的变化的例子。例如，如果不解释系统在运行时的堆栈所做的工作，遍历树的一个出人意料的短方法就会是个迷。讨论数据结构和算法时如果脱离系统，保持一个纯理论的态度未必有用。这本书还全面地讨论了数据压缩和存储管理。
本书的重点是数据结构，其他的主题在这里只是为了帮助正确地理解这个主题。算法是从数据结构的角度来考虑的，因此读者看不到多种不同类型的算法的全面讨论以及某个算法的完整描述。但是，正如我们曾说过的，本书深刻地诠释了递归，还详细描述了算法的复杂性分析。
第1-8章介绍了一些不同的数据结构和操作它们的算法，并分析了每个算法的效率，提出了改进算法的建议。
第1章讲述了面向对象编程的基本原理，介绍了动态内存分配和指针的使用以及Java的入门简介。
第2章描述了评定算法效率的方法。
第3章介绍了链表。
第4章讲述了堆栈和队列以及它们的应用。
第5章包含了递归的详细讨论，讨论了多种类型的递归并剖析了一个递归调用。
第6章讨论了二叉树，包括实现、遍历和查找，并且介绍了平衡树。
第7章描述了更一般的树，像线索(trie)、2-4树和B树。
第8章主要描述了图。
第9—12章描述了前几章介绍的数据结构的不同应用。强调了所涉及的主题的各方面的数据结构。
第9，章详细地分析了排序，描述了几个基本和非基本的方法。
第10章讨论了散列——查找中最重要的领域之一。在描述不同技术的同时强调了数据结构的使用。
第11章讨论了数据压缩算法和数据结构。
第12章描述了存储管理的不同技术和数据结构。
附录A进一步详尽地讨论了第2章介绍的大O表示法。
每一章包含了对某个素材的讨论，并配有相应的图表说明。除了第2章，所有的章都包含了一个示例学习，就是使用那一章讨论的特性的扩展示例。每章正文的后面都包含各种难度的习题。除了第2章，每一章都有编程作业和最新的相关文献的参考书目。
第1—6章(除了2．9节、3．4节、6．4．3节、6．7节和6．8节)包含了构成数据结构课程的基础的核心素材，应当顺序学习这些章。余下的六章可以按任意顺序学习。一个学期的课程应当包括第1-6、9章和10．1节和10．2节。整本书也可以是两学期的课程的一部分。
本书中的示例的源代码可以通过以下Web站点下载：www．mathcs．duq．edu／drozdek／DSinJava。
致谢
忠心感谢下列人士的审稿，他们为本书的改进提供了宝贵意见和建议：
James Ball，Indiana State University
Li-hsiangCheo，William Paterson University of New Jersey
Julius Dichter，University of Bridgeport
Le Gruenwald，University of Oklahoma
George Harrison，Norfolk State University
Craig Morgenstern，TexasChristianUniversity
Jong-MinPark，SanDiegoStateUniversity
然而，作为本书作者，欢迎读者对本书中的疏漏和不足指正，我的电子信箱地址是drozdek@duq．edu。
Adam Drozdek
周翔 王建芬 黄小青：暂无简介
数据结构是计算机科学技术专业的基础。计算机科学技术的各个领域都要用到多种数据结构，它既是程序设计(特别是非数值性程序设计)的基础，又是设计和实现编译程序、操作系统、数据库管理系统以及其他系统程序和大型应用程序的重要基础。
在C语言作为教学语言时期，数据结构几乎都是用C语言来描述其算法。Java语言诞生后，以其功能完备及其跨平台等特性，逐渐为计算机领域广大科技工作者所偏爱。因此，用Java语言来描述数据结构及其算法，有着很重要的现实意义。据了解，在美国等发达国家大学中，已经很少采用C语言讲解数据结构，而Java则越来越多地被用在数据结构课程中。
本书顺应了计算机科学发展的需要，以面向对象的方式描述了数据结构的当前设计和实现范例，在数据结构的实现中用Java作为编程语言。本书的重点是数据结构，其他的主题在这里只是为了能正确地理解这个科目。算法是从数据结构的角度来考虑的，因此本书并不展开一个完整的不同类型的算法的讨论以及关于算法的全面的描述。
本书由周翔、王建芬、黄小青组织翻译，参加翻译工作的人员还有王勇、隋立恒、蔡刿、贺海军、向尕、闫慧等。由于时间仓促，水平有限，书中难免有错误和不足之处，敬请广大读者批评指正。
译 者
2002年12月
第1章 Java语言的面向对象编程
1．1 Java入门
1．1．1 变量声明
1．1．2 运算符
1．1．3 选择语句
1．1．4 循环语句
1．1．5 异常处理
1．2 Java面向对象编程
1．2．1 封装
1．2．2 抽象数据类型
1．2．3 继承
1．2．4 多态性
1．3 输入和输出
1．4 Java和指针
1．5 java．util中的向量
1．6 数据结构和面向对象编程
1．7 示例学习：随机存取文件
1．8 习题
1．9 编程作业
参考文献
第2章 复杂性分析
2．1 计算复杂性和渐近复杂性
2．2 大O表示法
2．3 大O表示法的性质
2．4 和表示法
2．5 可能出现的问题
2．6 复杂性示例
2．7 寻找渐近复杂性：示例
2．8 最好的、平均的和最坏的情况
2．9 补偿复杂性
2．10 习题
参考文献
第3章 链表
3．1 单向链表
3．1．1 插入
3．1．2 删除
3．1．3 查找
3．2 双向链表
3．3 循环链表
3．4 跳转表
3．5 自组织表
3．6 稀疏表
3．7 用java．util的链表
3．8 小结
3．9 示例学习：图书馆管理
3．10 习题
3．11 编程作业
参考文献
第4章 堆栈和队列
4．1 堆栈
4．2 队列
4．3 优先级队列
4．4 示例学习：逃离迷宫
4．5 习题
4．6 编程作业
参考文献
第5章 递归
5．1 递归定义
5．2 方法调用和递归实现
5．3 剖析一个递归调用
5．4 尾递归
5．5 非尾递归
5．6 间接递归
5．7 嵌套递归
5．8 过分递归
5．9 回溯
5．10 小结
5．11 示例学习：一个递归下降解释器
5．12 习题
5．13 编程作业
参考文献
第6章 二叉树
6．1 树、二叉树和折半查找树
6．2 实现二叉树
6．3 搜索折半查找树
6．4 树的遍历
6．4．1 广度优先遍历
6．4．2 深度优先遍历
6．4．3 无堆栈深度优先遍历
6．5 插入
6．6 删除
6．6．1 归并删除法
6. 6. 2 拷贝删除法
6．7 树的平衡，
6．7．1 DSW算法
6．7．2 AVL树
6．8 自适应树
6．8．1 自调整树
6．8．2 扩展
6．9 堆
6．9．1 堆作为优先级队列
6．9．2 以堆形式组织数组
6．10 波兰表示法和表示树
6．11 示例学习：计算单词频率
6．12 习题
6．13 编程作业
参考文献
第7章 多分树
7．1 B树家族
7，1．1 B树
7．1．2 B*树
7．1．3 B树
7．1．4 前缀B树
7．1．5 比特树
7．1．6 R树
7．1．7 2-4树
7．1．8 java．util中的集合
7．1，9 java．util中的映像
7．2 线索
7．3 小结
7．4 示例学习：拼写检查程序
7．5 习题
7．6 编程作业
参考文献
第8章 图
8．1 图的表示法
8．2 图的遍历
8．3 最短路径
8．4 环路检测
8．5 生成树
8．5．1 Boruvka算法
8．5．2 Kruskal算法
8．5．3 Jarnik-Prim算法
8．5．4 Dijkstra算法
8．6 连通性
8．6．1 无向图的连通性
8．6．2 有向图的连通性
8．7 拓扑排序
8．8 网络
8．8．1 最大流
8．8．2 最小代价的最大流量
8．9 匹配
8．9．1 分配问题
8．9．2 非二部图中的匹配
8．10 欧拉图和哈密顿图
8．10．1 欧拉图
8．10．2 哈密顿图
8．11 示例学习：典型代表问题
8．12 习题
8．13 编程作业
参考文献
第9章 排序
9．1 元素排序算法
9．1．1 插入排序
9．1．2 选择排序
9．1．3 起泡排序
9．2 决策树
9．3 高效排序算法
9．3．1 希尔排序
9．3．2 堆排序
9．3．3 快速排序
9．3．4 归并排序
9．3．5 基数排序
9．4 java．util中的排序
9．5 小结
9．6 示例学习：多项式加法
9．7 习题
9．8 编程作业
参考文献
第10章 散列
10．1 散列函数
10．1．1 除法
10．1．2 折叠法
10．1．3 平方取中散列函数
10．1．4 提取方法
10．1．5 基数变换
10．2 冲突解决
10．2．1开放地址法
10．2．2 链
10．2．3 桶地址法
10．3 删除
10．4 理想散列函数
10．4．1 Cichelli方法
10．4．2 FHCD算法，
10．5 可扩展文件的散列函数
10．5．1 可扩展散列
10．5．2 线性散列
10．6 java．util中的散列
10．7 示例学习
10．8 习题
10．9 编程作业
参考文献
第11章 数据压缩
11．1 数据压缩的条件
11．2 霍夫曼编码
11．3 Shannon-Fano码
11．4 运行长度编码
11．5 Ziv-Lempel编码
11．6 示例学习：结合运行长度编码的霍夫曼方法
11．7 习题
11．8 编程作业
参考文献
第12章 存储管理
12．1 连续适应方法
12．2 非连续适应方法
12．3 无用单元收集
12．3．1 标记与清除算法
12．3．2 拷贝方法
12．3．3 增量式无用单元收集
12．4 小结
12．5 示例学习：内置无用单元收集器
12．6 习题
12．7 编程作业
参考文献
附录A 大O的计算
人名索引
名词索引
