基本概念

数据（data）是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。
数据的含义非常广泛，除了通常的数值数据、字符、字符串是数据以外，声音、图像等一切 可以输入计算机并能被处理的都是数据。例如除了表示人的姓名、身高、体重等的字符、数字是数据，人的照片、指纹、三维模型、语音指令等也都是数据。
数据元素（data element）是数据的基本单位，是数据集合的个体，在计算机程序中通常作为一个整体来进行处理。例如一条描述一位学生的完整信息的数据记录就是一个数据元 素；空间中一点的三维坐标也可以是一个数据元素。数据元素通常由若干个数据项组成，例 如描述学生相关信息的姓名、性别、学号等都是数据项；三维坐标中的每一维坐标值也是数 据项。数据项具有原子性，是不可分割的最小单位。
数据对象（data object）是性质相同的数据元素的集合，是数据的子集。例如一个学校 的所有学生的集合就是数据对象，空间中所有点的集合也是数据对象。
数据结构（data structure）是指相互之间存在一种或多种特定关系的数据元素的集合。 是组织并存储数据以便能够有效使用的一种专门格式，它用来反映一个数据的内部构成，即 一个数据由那些成分数据构成，以什么方式构成，呈什么结构。 由于信息可以存在于逻辑思维领域，也可以存在于计算机世界，因此作为信息载体的数 据同样存在于两个世界中。表示一组数据元素及其相互关系的数据结构同样也有两种不同的 表现形式，一种是数据结构的逻辑层面，即数据的逻辑结构；一种是存在于计算机世界的物 理层面，即数据的存储结构。
数据的逻辑结构按照数据元素之间相互关系的特性来分，可以分为以下四种结构：集合、 线性结构、树形结构和图状结构。本书中讨论的数据结构主要有线性表、栈、队列、树和图， 其中线性表、栈、队列属于线性结构，树和图属于非线性结构。
数据的逻辑结构可以采用两种方法来描述：二元组、图形。
数据结构的二元组表示形式为： 数据结构 = {D , S} 其中 D 是数据元素的集合；S 是 D 中数据元素之间的关系集合，并且数据元素之间的 关系是使用序偶来表示的。序偶是由两个元素 x 和 y 按一定顺序排列而成的二元组，记作 ，x 是它的第一元素，y 是它的第二元素。
当使用图形来表示数据结构时，是用图形中的点来表示数据元素，用图形中的弧来表示 数据元素之间的关系。如果数据元素 x 与 y 之间有关系，则在图形中有从表示 x 的点 出发到达表示 y 的点的一条弧。

抽象数据类型

抽象数据类型是描述数据结构的一种理论工具。在介绍抽象数据类型之前我们先介绍一 下数据类型的基本概念。
数据类型（data type）是一组性质相同的数据元素的集合以及加在这个集合上的一组操作。
例如 Java 语言中就有许多不同的数据类型，包括数值型的数据类型、字符串、布尔型 等数据类型。以 Java 中的 int 型为例，int 型的数据元素的集合是[-2147483648,2147483647] 间的整数，定义在其上的操作有加、减、乘、除四则运算，还有模运算等。
抽象数据类型（abstract data type, 简称 ADT）由一种数据模型和在该数据模型上的一 组操作组成。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。
抽象数据类型可以使用一个三元组来表示：
ADT = (D, S, P) 其中 D 是数据对象，S 是 D 上的关系集，P 是加在 D 上的一组操作。 在定义抽象数据类型时，我们使用以下格式：
ADT 抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
}
各个计算机，不管是大型机、小型机、PC、平板电脑、PDA, 甚至智能手机都拥有“整数”类型，也需要整数间的运算，那么整型其实就是一个抽象数据类型，尽管它在上面提到的这些在不同计算机中实现方法上可能不一样，但由于其定义的数学特性相同，在计算机编程者看来，它们都是相同的。因此，“抽象”的意义在于数据类型的数学抽象特性。
而且，抽象数据类型不仅仅指那些已经定义并实现的数据类型，还可以是计算机编程者在设计软件程序时自己定义的数据类型，比如我们编写关于计算机绘图或者地图类的软件系统，经常都会用到坐标。也就是说，总是有成对出现的x和y,在3D 系统中还有z出现，既然这三个整型数字是始终在一起出现，我们就定义一个叫point 的抽象数据类型，它有x、y、z三个整型变量，这样我们很方便地操作一个point数据变量就能知道这一点的坐标了。
根据抽象数据类型的定义，它还包括定义在该模型上的一组操作。就像“超级玛丽”这个经典的任天堂游戏，里面的游戏主角是马里奥（Mario)。我们给他定义了几种基本操作，走（前进、后退、上、下)、跳、打子弹等。
一个抽象数据类型定义了：一个数据对象、数据对象中各数据元素之间的关系及对数据元素的操作。至于，一个抽象数据类型到底需要哪些操作，这就只能由设计者根据实际需要来定。像马里奥， 可能开始只有两种操作，走和跳，后来发现应该要增加一种打子弹的操作，再后来发现有些玩家希望它可以走得快一点，就有了按住打子弹键后前进就会“跑”的操作。这都是根据实际情况来设计的。
事实上，抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。抽象数据类型把实际生活中的问题分解为多个规模小且容易处理的问题，然后建立一个计算机能处理的数据模型，并把每个功能模块的实现细节作为一个独立的单元，从而使具体实现过程隐藏起来。
抽象数据类型(ADT)的定义和实现通常是分开的。定义只包含数据逻辑结构的定义和所允许的一组操作；使用者通过这些定义了的操作对ADT进行操作；另一方面，实现者根据这些定义来完成ADT的各种具体实现方式。