1.2.3 基本概念和术语

本小节将给出一些概念和术语的定义，这些概念和术语将多次出现在之后的章节中。

数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。在计算机中，它泛指所有能输入计算机中并被计算机程序处理的符号。它是计算机程序加工的原料，文字、表格、声音、图像等都称为数据。

数据元素是数据的基本单位，在程序中通常把数据元素作为一个整体进行考虑和处理。例如，表1-1所示的学生表中，如果把每行当作一个数据元素来处理，此表共包含7个数据元素。一个数据元素可由若干数据项组成，例如表1-1中每一个学生的信息作为数据元素，而学生信息的每一项（如学号、姓名等）都是数据项。数据的最小单位即数据项。

表1-1　学生表

数据结构是指数据及其之间的相互关系，可以看成相互之间存在一种或多种特定关系的数据元素的集合。因此，可以把数据结构看成带结构的数据元素的集合。数据结构包括以下3个方面。

①数据元素之间的逻辑关系，即数据的逻辑结构。

②数据元素及其关系在计算机存储系统中的存储方式，即数据的存储结构，也称为数据的物理结构。

③施加在该数据上的操作，即数据的运算。

为了更准确地描述数据结构，通常采用二元组表示，表示方法为

B = (D, R)

其中，B是一种数据结构，它由数据元素的集合D和D中二元关系的集合R组成，即

D = {d_i| 1 ≤ i ≤ n, n ≥ 0}

R = {r_j | 1 ≤ j ≤ m, m ≥ 0}

其中，d_i表示集合D中的第i个结点或数据元素，n为D中结点的个数，特别地，若n=0，则D是一个空集，因而B也就无结构可言，有时把这种情况认为是具有任意结构。rj表示集合R中的第j个关系，m为R中关系的个数，特别地，若m=0，则R是一个空集，表明集合D中的结点间不存在任何关系，彼此是独立的。

R中的一个关系r是序偶的集合，对于r中的任一序偶<x, y>(x, y∈D)，把x叫作序偶的第一结点，把y叫作序偶的第二结点，称序偶的第一结点为第二结点的直接前驱，称第二结点为第一结点的直接后继。若某个结点没有直接前驱，则称该结点为开始结点；若某个结点没有直接后继，则称该结点为终端结点。

数据类型是一个值的集合和定义在这个集合上的一组操作的总称。例如，Java语言中的整型变量，其值集为某个区间上的整数，定义在其上的操作为加、减、乘、除和模运算等。按“值”的不同特性，高级程序设计语言中的数据类型可分为两种：原子类型和结构类型。原子类型的值是不可分解的，例如Java语言中的基本类型（整型、布尔型等）；结构类型的值是若干成分按照某种结构组成的，因此是可以分解的，其组成成分既可以是结构的，也可以是非结构的。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内的存储形式无关，即不论其内部结构如何变化，只要它的逻辑特性不变，都不影响外部使用。

抽象数据类型的范畴十分广，它不仅包括当前各处理器中已定义并实现的数据类型（固有类型），而且包括用户在设计软件时自定义的数据类型。本书定义抽象数据类型格式如下：

ADT 抽象数据类型名{
    数据对象：（数据对象定义）
    数据关系：（数据关系定义）
    数据操作：（数据操作定义）
}ADT 抽象数据类型名