1.1.3　数据结构、数据类型和抽象数据类型

数据结构用来反映一个数据的内部构成，即一个数据由哪些数据元素构成，以什么方式构成，呈什么结构。数据结构包括逻辑上的数据结构和物理上的数据结构。逻辑上的数据结构反映数据元素之间的逻辑关系，物理上的数据结构反映数据元素在计算机内的存储方式。数据结构是数据存在的形式。

数据按照数据结构分类，具有相同数据结构的数据属同一类。同一类数据的全体称为一个数据类型。在高级程序设计语言中，数据类型用来说明一个数据在数据分类中的归属。它是数据的一种属性。这个属性限定了该数据的变化范围。为了解题的需要，根据数据结构的种类，高级语言定义了一系列的数据类型。不同的高级语言所定义的数据类型不完全相同，例如，C++语言所定义的数据类型如图1-2所示。

图1-2　C++的数据类型

其中，基本数据类型对应于简单的数据结构，非基本数据类型对应于复杂的数据结构。在复杂的数据结构中，允许数据元素本身具有复杂的数据结构，因而，非基本数据类型允许复合嵌套。指针类型对应于数据结构中数据元素之间的关系，表面上属基本数据类型，实际上都指向复杂的数据元素即构造数据类型中的数据，因此这里没有把它划入基本数据类型中，而是把它划入非基本数据类型中。

数据结构反映数据内部的构成方式，常常用一个结构图来描述：数据中的每一项，数据元素被看作一个结点，并用方框或圆圈表示，数据元素之间的关系用带箭头的连线表示。如果数据元素本身又有它自身的结构，则结构出现嵌套。这里的嵌套还允许是递归的嵌套。

指针数据的引入使构造各种复杂的数据结构成为可能。

按照数据结构中的数据元素之间的关系，数据结构有线性与非线性之分。在非线性数据结构中又有层次与网状之分。由于数据类型是按照数据结构划分的，因此一类数据结构对应一种数据类型。数据类型按照该类型中的数据所呈现的结构也有线性与非线性之分和层次与网状之分。一个数据变量在高级语言中的类型说明必须是该变量所具有的数据结构所对应的数据类型。

抽象数据类型（Abstract Data Type，ADT）是带有一些操作的数据元素的集合，是一种描述用户和数据间接口的抽象模型，ADT的主要功能是简单而明确地描述数据结构的操作。此处的“抽象”意味着应该从与实现方法无关的角度去研究数据结构。抽象数据类型为用户提供了一种定义数据类型的手段，其关键的两个要素为数据的结构以及在该结构上相应的操作的集合。

引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的应用隔开，使它们相互独立。对于抽象数据类型的描述，除了必须描述它的数据结构外，还必须描述定义在它上面的运算（过程或函数）。抽象数据类型上定义的过程和函数以该抽象数据类型的数据所应具有的数据结构为基础。

下面的各节将讨论一些基本抽象数据类型。所谓基本，只是相对而言，这些数据类型是最基本、最简单的，并且是实现其他抽象数据类型的基础。

在后面的内容中我们将了解到表、栈、队列、串、树、图等常见的基本抽象数据类型的ADT操作以及这些操作用不同数据描述方法的具体实现。