1.2 有关概念和术语

在系统地学习数据结构知识之前，先对一些基本概念和术语赋予确切的定义。

1.数据

数据（Data）是信息的载体，它能够被计算机识别、存储和处理。数据是计算机程序加工的原料，应用程序能处理各种各样的数据，包括数值数据和非数值数据。数值数据是一些整数、实数或复数；非数值数据包括字符、文字、图形、图像、语音等。

2.数据元素

数据元素（Data Element）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项（Data Item）组成。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。例如，学生信息检索系统中学生信息表中的一个记录、教学计划编排问题中的一个顶点等，都被称为一个数据元素。

3.数据项

数据项（Data Item）指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段（field）或域。例如，学籍管理系统中学生信息表的每一个数据元素就是一个学生记录。它包括学生的学号、姓名、性别、籍贯、出生年月、成绩等数据项。这些数据项可以分为两种：一种叫做初等项，如学生的性别、籍贯等，这些数据项是在数据处理时不能再分割的最小单位；另一种叫做组合项，如学生的成绩，它可以再划分为数学、物理、化学等更小的项。通常，在解决实际应用问题时把每个学生记录当做一个基本单位进行访问和处理。

4.数据结构

数据结构（Data Structure）是指互相之间存在着一种或多种关系的数据元素的集合。在任何问题中，数据元素都不会是孤立的，在它们之间存在着这样或那样的关系，这种数据元素之间存在的关系称为数据的逻辑结构。根据数据元素之间关系的不同特性，通常有以下4类基本的逻辑结构。

（1）集合结构：在集合结构中，数据元素之间的关系是“属于同一个集合”。数据元素之间除了同属一个集合外，不存在其他关系。

（2）线性结构：在该结构中，数据元素除了同属于一个集合外，数据元素之间还存在着一对一的顺序关系。

（3）树形结构：该结构的数据元素之间存在着一对多的层次关系。

（4）图状结构：该结构的数据元素之间存在着多对多的任意关系，图状结构也称为网状结构。

上述4类基本结构的示意图如图1.5所示。

由于集合是数据元素之间极为松散的一种结构，本书不专门讨论。因此，本书主要讨论线性结构（表、栈、队、串等）和非线性结构（树、图或网）。

从上面所介绍的数据结构的概念中可以知道，一个数据结构有两个要素：一是数据元素，二是数据元素之间的关系。因此，数据结构通常可以采用一个二元组来表示：

Data_Structure=（D,R）

其中，D是数据元素集合，R是D中元素之间关系的集合。

【例1.4】 假设一个数据结构定义如下：

DS=（D,R）
D={ a, b, c, d, e, f, g }
R={ <a, b>,<a, c>,<a, d>,<c, e>,<c, f>,<d, g> }

则该数据结构的逻辑示意如图1.6所示，显然是一个树形结构。

数据结构包括数据的逻辑结构和物理结构。数据的逻辑结构可以看做从具体问题抽象出来的数学模型，它与数据的存储无关。数据的逻辑结构在计算机中的存储表示（又称映像）称为数据的物理结构（或称存储结构），它所研究的是数据结构在计算机中的实现方法，包括数据结构中数据元素的存储表示及数据元素之间关系的表示。

在计算机中，数据的存储方法包括顺序存储和链式存储。

（1）顺序存储方法通过数据元素在计算机中存储位置关系来表示元素间的逻辑关系，通常把逻辑上相邻的元素存储在物理位置相邻的存储单元中。顺序存储是一种最基本的存储表示方法，通常借助程序设计语言中的数组来实现。

（2）链式存储方法对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过指针字段来表示，链式存储结构通常借助程序设计语言中的指针来实现。

除了顺序存储方法和链式存储方法外，有时为了查找方便还采用索引存储方法和散列表（Hash）存储方法。

讨论数据结构的目的就是在计算机中实现对数据的操作，因此在讨论数据的组织结构时必然要考虑在该结构上进行的操作（或称运算）。事实上，数据结构是专门研究某一类数据的表示方法及其相关操作实现算法的一门学科。

5.数据类型

数据类型（Data Type）是和数据结构密切相关的一个概念，在高级程序设计语言中用以限制变量取值范围和可能进行的操作的总和称为数据类型。因此，所谓数据类型，一是限定了数据的取值范围（实际上与存储形式有关）；二是规定了数据能够进行的一组操作（运算）。

数据类型可分为两类：一类是非结构的原子类型，原子类型的值是不可再分解的，如C语言中的基本类型（整型、实型、字符型及指针类型和空类型）；另一类是结构类型，它的成分可以由多个结构类型组成，并可以分解。结构类型的成分可以是非结构的，也可以是结构的。例如，数组的值由若干分量组成，每个分量可以是整数等基本类型，也可以是数组等结构类型。

6.抽象数据类型

抽象数据类型（Abstract Data Type，ADT）是指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。即无论其内部结构如何变化，只要它的数学特性不变，就不影响其外部的使用。

抽象数据类型和数据类型实质上是一个概念。例如，各种计算机都拥有的整数类型就是一个抽象数据类型，尽管它们在不同处理器上的实现方法可以不同，但由于其定义的数学特性相同，在用户看来都是相同的。因此，“抽象”的意义在于数据类型的数学抽象特性。

抽象数据类型的定义可以由一种数据结构和定义在其上的一组操作组成，而数据结构又包括数据元素及元素间的关系，因此抽象数据类型一般可以由元素、关系及操作三个要素来定义。

本书在讨论各种数据结构时，针对其逻辑结构和具体的存储结构给出相应的数据类型，并在确定的数据类型上通过各种算法实现各种操作。