前言
开设数据结构的目的是对前期学习的计算机技术进行总结与提高，为后续其他专业课程的学习提供基础。
数据结构上承《计算机导论》、《程序设计语言》和《离散数学》；下启《算法分析与设计》、《操作系统》、《数据库原理》等专业课程。
教材的内容共分8章，内容如下：
数据结构课程
讨论的内容
沃思(Niklaus Wirth)教授认为：程序是计算机指令的组合，用来控制计算机的工作流程，完成一定的逻辑功能以实现某种任务；算法是程序的逻辑抽象，是解决某类客观问题的策略；数据结构是现实世界中的数据及其之间关系的反映。
数据结构可以从逻辑结构和存储结构两个层面进行刻画，其中客观事物自身所具有的结构特点，称为逻辑结构；而具有这种逻辑结构的数据在计算机存储器中的组织形式则称为存储结构。
求解问题举例
人们利用计算机的目的是为了能快速解决实际的应用问题，因而利用计算机实现问题的求解，就需要完成一个从问题到程序的实现过程，此过程的主要步骤如下：
①确定问题求解的数学模型(或逻辑结构)；
②确定存储结构；
③设计算法；
④编程并测试结果。
可见，程序设计的本质在于解决两个主要问题：一是根据实际问题选择一种好的数据结构，二是设计一个好的算法，后者的好坏在很大程度上取决于前者。
例子在后续课程中再讲述。
本课程讨论的内容
数据结构与数学、计算机硬件和软件有着十分密切的关系。它是介于数学、计算机硬件和软件之间的一门计算机类和电子信息类相关专业的核心课程之一，是高级程序设计语言、编译原理、操作系统、数据库、人工智能等课程的基础。同时，数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。
从上节可知，用计算机来解决一个具体问题，总是围绕以下3个主要步骤进行：
①抽象出所求解问题中需要处理的数据对象的逻辑结构(数学模型)。
②根据所求解问题需要完成的功能特性实现对抽象数据的存储结构表述。
③确定为求解问题而需要进行的操作或运算。
事实上，只有这三者的结合，才能清新地刻画出数据结构的本质特性。因此,通常在本课程中讨论数据结构，既要讨论在解决问题时各种可能遇到典型的逻辑结构，又要讨论这些逻辑结构在计算机中的存储映射(存储结构)，此外、还要讨论数据结构的相关操作及其实现。与此同时，为了构造出好的数据结构并加以实现，还必须考虑其实现方法的性能评价。因此，数据结构课程的内容体系可如下所示进行归纳。
基本概念与术语
接下来将对一些常用的基本概念与术语给出详细的讲解，这些基本概念与术语将贯穿数据结构学习的整个过程。
数据
①数据(Data)
数据是信息的载体，是对客观事物的符号表示，它能够被计算机程序识别、存储、加工和处理。因此，数据就是所有能够有效地输入到计算机中并且能够被计算机处理的符号总称，也是计算机程序处理对象的集合，是计算机程序加工的“原料”。
例如，一个利用数值分析方法求解代数方程的程序，其处理对象是整数和实数等数值数据；一个编译程序或文字处理程序的处理对象是字符串。数据还包括图像、声音等非数值数据。
②数据元素(Data Element)
数据元素是数据中的一个“个体”，是数据的基本组织单位。在计算机程序中通常将它作为一个整体进行考虑和处理。在不同条件下，数据元素又可称为结点、顶点和记录。
例如下表中的一行数据称为一个数据元素或一条记录。在树或图中，一个数据元素用一个圆圈表示，每一个圆圈所表示的是一个数据元素，并称之为一个顶点。
③数据项(Data Item)
数据项是数据元素的组成部分，是具有独立含义的标识单位。一个数据元素可以由若干个数据项组成。如上表中的每一列，“生产订单号”、“物料名称”等都是一个数据项。数据项又可分为两种，一种是简单数据项；另一种是组合数据项。
例如上表所示，其中“生产订单号”、“行”等是简单数据项，它们在数据处理时不能再分割；而“开工时间”、“完工时间”则是一个组合数据项，它可以进一步划分为“年”“月”和“日”等更小的数据项。
④数据对象(Data Object)
数据对象是性质相同的数据元素的集合。例如，在对生产订单进行查询时，计算机所处理的数据对象是上表中的所有数据，这张表就可以看成是一个数据对象。
除了最简单的数据对象之外，一般说来，数据对象中的数据元素不会是孤立的，而是彼此相关的，这种彼此之间的关系称为“结构”。例如，上表所示的生产订单表，所有订单按生产订单号递增顺序排列，所有的订单记录都处在一种有序的线性序列中。由此可以引出下面有关数据结构的定义。
数据结构
数据结构(Data Structure)是相互之间存在一种或多种特定关系的数据元素的集合。其实关于数据结构这个概念，不同的教材有不同的提法，至今还没有一个被一致公认的定义。但无论是何种定义，对于数据结构的不同理解，实际上都离不开对数据的逻辑结构、数据的存储结构和数据的操作3个方面的考虑。
①逻辑结构
数据的逻辑结构是指各个数据元素之间的逻辑关系，是呈现在用户面前的、能感知到的数据元素的组织形式。上表中第一个数据元素是生产订单号为00000010的订单记录，这条记录称之为开始结点；最后一个数据元素是生产订单号为00000013的订单记录，这条记录称之为终端结点，其他数据元素的前、后都有且仅有一个数据元素与它相邻，分别称之为此数据元素的前驱和后继，这就反映了逻辑结构的特性。
按照数据元素之间逻辑关系的特性来分，可将数据结构归纳为以下4类：
简而言之就是：
数据的逻辑结构表述涉及两个方面的内容，一方面是数据元素，另一方面是数据元素之间的关系。所以从形式上可采用一个二元组来定义，定义形式为：
Data_Structures=(D,R)
其中，D是数据元素的有限集，R是D上关系的有限集。R中的关系描述了D中数据元素之间的逻辑关系，即数据元素之间的关联方式(或邻接方式)。
设R1∈R，则R1是一个DXD的关系子集，若a,b∈D，<a,b>∈R1，则称a是b的前驱，b是a的后继，对R1而言，a和b是相邻的结点。没有前驱的结点就是开始结点(或根结点)，没有后继的结点就是终端结点(或叶子结点)。
②存储结构
数据的逻辑结构是从数据元素之间的逻辑关系来观察数据的，它与数据的存储无关，是独立于计算机之外的。
数据的存储结构(物理结构)是数据的逻辑结构在计算机中的实现。它包括数据元素值在计算机中的存储表示和逻辑关系在计算机中的存储表示这两部分，是依赖于计算机的。在计算机中最小的数据表示单位是二进制数的一位(bit)，故通常用一个由若干位组合起来的位串来表示一个数据元素。当数据元素由若干个数据项组成时，位串中对应于各个数据项的子位串称为数据域。所以，数据元素值在数据域中是以二进制的存储形式表示的，而数据元素之间逻辑关系的存储表示则通常有以下4种方式。
在以上4种存储方式中，顺序存储和链式存储是两种最基本、最常用的存储方式。索引存储和散列存储是两种为了提高查找效率而经常采用的存储方式。
任何一种存储方式都有各自的优缺点。在实际应用中，选择何种存储方式表示数据的逻辑结构，要分别根据各种存储结构的特点和处理问题时需进行的一些操作视具体情况而定，总体原则就是要达到操作方便、高效。
③数据的操作
数据的操作就是对数据进行某种方法的处理，也称数据的运算。只有当数据对象按一定的逻辑结构组织起来，并选择了适当的存储方式存储到计算机中时，与其相关的运算才有了实现的基础，所以，数据的操作也可被认为是定义在数据逻辑结构上的操作，但操作的实现却要考虑数据的存储结构。
对于不同的数据逻辑结构其对应的运算集也可能不同，常用的操作可归纳为以下几种。
①创建操作：建立数据的存储结构。
②销毁操作：对已经存在的存储结构将其所有空间释放。
③插入操作；在数据存储结构的适当位置上加入一个指定的新的数据元素。
④删除操作：将数据存储结构中某个满足指定条件的数据元素进行删除。
⑤查找操作：在数据存储结构中查找满足指定条件的数据元素。
⑥修改操作：修改数据存储结构中某个数据元素的值。
⑦遍历操作：对数据存储结构中每一个数据元素按某种路径访问一次且仅访问一次。
数据的逻辑结构、存储结构和运算是数据结构讨论中不可分割的3个方面，它们中任何一个不同都将导致不同的数据结构。
例如，在后续章节中将要介绍的顺序表与单链表、线性表与栈和队列。其中，顺序表与单链表具有相同的逻辑结构，但由于它们的存储结构不同，所以赋以了不同的数据结构名。线性表与栈、队列不但具有相同的逻辑结构，而且给定相同的存储结构，但由于线性表的插入和删除操作允许位置不同，则将限制在表的一端进行的线性表称为栈；而将插入操作限制在表的一端进行、删除操作限制在表的另一端进行的线性表称为队列。由此可见，只有当3个方面的内容都相同，才能称之为完全相同的数据结构。
数据类型
如何描述数据的存储结构呢？其实在不同的编程环境中，存储结构可有不同的描述方法。当用高级程序设计语言进行编程时，通常可以用高级编程语言中提供的数据类型加以描述。
我们知道在用高级程序语言编写的程序中，每个数据都有一个所属的、确定的数据类型，一个数据的数据类型描述了3个方面的内容：存储区域的大小(存储结构)、取值范围(数据集合)和允许进行的操作。
每一种程序设计语言都提供了一些内置的数据类型，也称为基本数据类型。Java语言中提供了8种基本数据类型。基本数据类型的值是不可分解的，是一种只能作为一个整体来进行处理的数据类型。当数据对象是由若干个不同类型的数据成分组合而成的复杂数据时，程序设计语言的基本数据类型就不能满足需求，它还必须提供引入新的数据类型的手段。
在Java语言中，引入新的数据类型的手段是类的声明(class declaration)。类的对象(object)是新的类型的实例，类的成员变量确定了新的数据类型的数据表示方法和存储结构，类的构造函数和成员函数确定了新的数据类型的操作。具有新的数据类型的数据将各个不同的成分按某种结构组合成一个整体；反过来，又可以将这个整体的各个不同的成分进行分解，并且它的成分可以是基本数据类型，也可以是新引入的数据类型。
抽象数据类型
抽象(Abstract)就是抽取反映问题本质的东西，忽略其非本质的细节。也就是在问题求解过程中只要求人们关注“做什么”，而不是“怎么做”的过程。因为人们在使用数据时通常会将注意力放在想要用这些数据去“做什么”，而不是注意如何实现这些任务以及如何在计算机中表示这些数据。
例如，在对两个整数进行加法运算时，并不关心它们在计算机中是如何存储表示的；同样，连接两个字符串时并不需要知道它们的内部表示。这种把数据的使用与实现分离开来的作法称为数据抽象(DataAbstraction)。
数据的抽象是通过抽象数据类型来实现的。抽象数据类型(Abstract Data Type，ADT)是指一数据值的集合和定义在这个集合上的一组操作。它不包括数据的计算机存储表示，而且这里的操作是脱离了具体实现的抽象操作，即不涉及它的实现细节。换句话说，抽象数据类型是指隐藏了数据的存储结构并且不涉及操作的实现细节的数据类型。
在Java语言中，抽象数据类型的描述可采用两种方法：第一种是用抽象类(abstract class)表示，抽象类型的实现用继承该抽象类的子类表示；第二种是用Java接口(interface)表示，抽象类型的实现用实现该接口的类表示。接下来将全部采用Java接口表示抽象数据类型。下面通过两个具体实例来说明抽象数据类型的描述和实现。
用Java接口来描述复数的抽象类型。
左右滑动或点击查看全图
Complex类实现了IComplex接口中的5个方法，该类中还包括两个私有成员变量real、imag和1个构造方法。
