前 言 本书假定读者熟知Java的基础知识，如数据类型、控制结构、函数与参数、数组等。如果读者需要复习这些概念，或者将C++作为第一编程语言，可以在附录F中找到相关的内容。如果需要更详细地了解附录F中的主题，请参考《Java基础教程—— 从问题分析到程序设计》一节以及附录G中列出的参考文献。另外，本书还要求读者具备一定的数学基础，如高等数学。 本书主要内容 作为计算机科学专业的基础课程，本书把重点放在数据结构和面向对象设计(object-oriented design，OOD)上。书中提供的编程示例有效地使用了面向对象设计技术，通过程序解决特定的问题。 第1章介绍了软件工程原理。首先描述了软件的生命周期，然后讨论了算法分析的重要性，并介绍了算法分析中使用的大O表示法。面向对象设计技术有3个基本原则：封装性、继承性和多态性。Java通过类来实现封装性。第1章的后半部分讨论了用户定义的类。如果读者熟悉如何创建并使用自己的类，可以略过这部分内容。这一章还讨论了解决特定问题的基本面向对象设计技术。 第2章继续讨论面向对象设计原则，介绍了继承性和异常处理，并解释如何通过继承性原则来扩展类的定义。在执行Java程序时，可能会发生一些错误。例如，不小心进行了除0操作，标记不存在的字符串，数组的索引超出了边界；这些类型的错误在Java中称为异常。Java对程序异常的处理提供了强大的支持。本章除了说明如何使用已有的Java异常类之外，还阐述了如何构建自己的异常类。 第3章讨论如何在数组中组织和处理数据。本章除了解释如何开发自己的代码之外，还演示了Java类Vector的工作原理。 第4章讨论了链表。首先解释了链表的基本属性，如数据的插入和删除，链表的创建等。接着，开发了一段通用代码，来处理单向链表中的数据。这一章还讨论了双重链表，带有头尾节点的链表以及循环链表。 第5章介绍了递归，并用大量的示例演示了如何以递归的方式解决问题。 第6章和第7章讨论了堆栈和队列。除了演示如何开发自己的通用代码来实现堆栈和队列外，还解释了Java类Stack的工作原理，以及堆栈和队列的应用。 第8章描述了搜索算法。在分析顺序搜索算法之后，又讨论了二叉树搜索算法，并对这种算法进行了简要的分析。在初步探讨基于比较的搜索算法之后，本章还讨论了散列算法。 第9章介绍了排序算法，如选择排序、插入排序、快速排序、合并排序和堆排序。第10章讨论了二叉树。第11章介绍了图和图的算法，如最短路径，最小生成树和拓扑排序。 附录A列出了Java中的保留字。附录B列出了Java运算符的优先级和关联性。附录C列出了ASCII(American Standard Code for Information Interchange，美国信息交换标准码)和EBCDIC(扩充二进制代码的十进制交换码)的字符集。附录D介绍了用户定义的类在Java程序中的使用方法。附录E描述了本书中使用的Java类。附录F回顾了Java的基本要点，并比较了Java和C++语言的基本概念，如数据类型，控制结构，函数和参数以及数组。如果第一编程语言是C++，就可以通过附录F掌握这些Java基本要点。附录G为进一步学习Java知识和附录F中没有提到的主题提供了一些参考文献。附录H提供书中部分练习题的答案。 本书的使用方法 本书的主要目的在于介绍数据结构，用Java和面向对象设计技术来解决问题。为此，本书讨论了一些数据结构，如链表、堆栈、队列和二叉树。Java也提供了必要的代码来实现这些数据结构。总之，本书的重点是讲述如何开发自己的代码。同时，学会使用已编好的专业代码。 第5章讨论了递归。但在学习第6、7章的内容之前，并不一定要先学习第5章。如果打算在学习第6、7章之后再阅读第5章，可以跳过第6章的“消除递归”一节，在学习了第5章之后，再阅读这一节。学习第8章时不要求理解第5章，但第8、9章应按顺序学习。因此，最好在学习第8章之前先阅读第5章。图0-1说明了这些章节的关系。