前 言 前言基本概念 ● 学习本书的方法 ● 原理 小时候，你的母亲可能给你买过比较有教育意义的玩具，如积木、万能工匠(Tinker Toy) ，或者拼装玩具等。这些玩具都是有教育意义的：它们可以培养我们的空间思维能力，并且教会我们逐渐构造复杂的结构。你可以开发出能粘在一起的模块，并形成指导建造过程的规则。 阅读本书的过程就像是玩有教育意义的玩具。你可以把编写程序当作是艺术创作的过程，只是你已经从玩积木发展成为编写程序。除了你能编写的程序的复杂性没有限制之外，用于积木搭建结构的规则同样适用于编写程序。 当编写比较大的程序时，用来维护程序中数据的数据结构决定着程序运行过程中的时间和空间复杂度。此外，较大的程序也需要时间去编写。使用不同的数据结构实际上将会影响编写程序所花费的时间。选择错误的数据结构会使程序运行效率很差，或者很难甚至是不可能有效地实现。 因此，编写程序时有一部分时间是花费在选择数据结构上的。理想情况下，你会通过分析和比较它们不同的优缺点得出结论。本书的重点集中在现代编程环境中传统数据结构的创建和分析上，这里的编程环境是指Java编程语言或者简称Java。 自述 每一章都有特定的主题，许多主题都与特定的数据结构相关。我们将要研究的数据结构是从Java应用程序中抽象出来的，可以从Internet 上获得。另外还有一些主题涉及商业应用方面。在所有主题中，有一些是数学方面的，有一些是哲学上的，但它们都很好地考虑到了编程过程。 我们所介绍的主题并不是涵盖一切的，一些有用的数据结构没有包含在本书中。因为我们学习的是编写数据结构的原理，按照本书的内容编排进行阅读，就可以自己编写出新的更好的数据结构。 本书中最重要的部分可能是每章后面的一组练习题。所有这些练习题都值得认真思考。有一些问题我会在本书的后面提供一些合理的提示或者答案。为什么应该思考这些问题呢？熟能生巧。我可以教你如何骑独轮脚踏车，但是如果你从来都不练习，那就永远也学不会。当学习并理解了这些问题之后，你将会发现自己的设计和分析能力都得到了提高。 有时候我们会在本书中提出一些问题，这些问题没有答案(有时候它们会作为正式的问题在每章后面出现，那里会有答案)，在阅读过程中要仔细思考这些问题。手边准备纸和笔有助于“思考”这些问题。 本书简练并切中要点。大多数人都对实验感兴趣，我们将会留出尽可能多的时间来解问题，仔细阅读代码，并练习编写程序。在通读每一章的时候，你还会发现联机阅读源代码是很有帮助的。 另外一点，与其他许多图书一样，本书所涉及到的是一项正在进行的工作，最新的思想可能不会包含在本书中。如果还有什么疑问，可以登录网站获取更新的信息。在网站上也会发现使用javadoc从代码生成的每个数据结构的联机文档。为了获得最新的详细信息，最好是阅读联机文档，以及其他没有正式出现在本书中的许多数据结构的文档。 原理的作用 确实，在本书中有一些策略性的评论。这些内容在刚开始可能是微不足道的，可以越过。然而，如果作为一个程序员和一个计算机科学工作者想要提高工作技巧，我建议你还是阅读一下。有时候这些评论是相当重要的，可能会成为原理： 原理1 一个理性的程序员会很好地理解一条原理，对它形成一个看法。 自测题 这些问题的答案参见附录A.1。 (1) 在哪里可以找到自测题的答案？ (2) 大型程序的特点有哪些？ (3) 你会阅读整本书吗？ (4) 原理就是真理吗？ 本章问题 奇数问题的答案参见附录A.2。 (1) 所有的奇数问题都有答案，你是在哪里找到这些问题的答案的(提示：参见附录A.2)？ (2) 假设你是一个经验丰富的程序员，你会给新入门的程序员哪5条重要建议？ (3) 登录与本书相关的网站，查看提供给你的资源。 (4) 本书中描述了下面哪些数据结构？(参见附录D)：BinarySearchTree、BinaryTree、BitSet、Map、Hashtable、List？ (5) 登录网站查看Java的开发者Sun公司所提供的资源。 (6) 查看关于Sun公司的java.util包的文档(参见中的内核API文档)。这个包中包含了下面哪些数据结构：BinarySearchTree、BinaryTree、BitSet、Map、Hashtable、List？ (7) 查看一下附近的图书馆或者书店中关于Java的参考书。 (8) 编写一个Java应用程序，写一行代码来学习如何使用本地的Java编程环境(提示：阅读附录B)。 (9) 寻找本地关于Structure包的文档。如果没有发现，记住在Internet的上有同样的资料。 (10) 寻找与Structure包一起以电子形式发布的示例。这些示例中的许多将会在后述章节中讨论。