1.2 数据结构的基本概念

1.2.1 数据结构

1.数据

数据（data）是信息的载体，在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号集合。可以将数据分为两大类：一类是整数、实数等数值数据；另一类是文字、声音、图形和图像等非数值数据。

数据是计算机程序处理的“原料”，例如，编译程序处理的数据是源程序；学籍管理程序处理的数据是学籍登记表。

2.数据元素

数据元素（dataelement）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。构成数据元素的不可分割的最小单位称为数据项（dataitem）。例如，对于学生学籍登记表，每个学生的档案就是一个数据元素，而档案中的学号、姓名、出生日期等是数据项，如图1-9所示。

数据元素具有广泛的含义，一般来说，能独立、完整地描述问题世界的一切实体都是数据元素。例如，对弈中的棋盘格局、教学计划中的某门课程、一年中的四个季节，甚至一次学术报告、一场足球比赛都可以作为数据元素。

3.数据结构

数据结构（datastructure）是指相互之间存在一定关系的数据元素的集合。需要强调的是，数据元素是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。按照视点的不同，数据结构分为逻辑结构和存储结构。

（1）逻辑结构

数据的逻辑结构（logicalstructure）是指数据元素之间逻辑关系的整体，是从实际问题抽象出的数据模型，在形式上可定义为一个二元组：

Data＿Structure=（D，R）

其中，D是数据元素的有限集合，R是D上关系的集合。实质上，这个形式定义是对操作对象的一种数学描述，请看下面的例子。

【例1-8】 图1-8所示七巧板涂色问题的数据模型可表示为：DS＿puzzle=（D，R），其中，D={A，B，C，D，E，F，G}，R={R1}，R1={＜A，B＞，＜A，E＞，＜A，F＞，＜B，C＞，＜B，D＞，＜C，D＞，＜D，E＞，＜D，G＞，＜E，F＞，＜E，G＞}。

根据数据元素之间逻辑关系的不同，数据结构分为四类：

① 集合：数据元素之间就是“属于同一个集合”，除此之外，没有任何关系；

② 线性结构：数据元素之间存在着一对一的线性关系；

③ 树结构：数据元素之间存在着一对多的层次关系；

④ 图结构：数据元素之间存在着多对多的任意关系。

树结构和图结构也称为非线性结构。

通常用逻辑关系图来描述数据的逻辑结构，其描述方法是：将每一个数据元素看做一个结点，用圆圈表示，元素之间的逻辑关系用结点之间的连线表示；如果强调关系的方向性，则用带箭头的连线表示关系。

（2）存储结构

数据的存储结构（storagestructure）又称为物理结构，是数据及其逻辑结构在计算机中的表示（也称映像），换言之，存储结构除了存储数据元素之外，必须隐式或显式地存储数据元素之间的逻辑关系。

通常有两种存储结构：顺序存储结构和链接存储结构。顺序存储结构的基本思想是用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。链接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。

【例1-9】 对于数据结构DS＿color=（D，R），其中D={red，green，blue}，R={R1}，R1={＜red，green＞，＜green，blue＞}，DS＿color的顺序存储如图1-11所示，DS＿color的链接存储如图1-12所示。

如何描述存储结构呢？数据的存储结构涉及数据元素及其逻辑关系在计算机内存中的物理位置，本书是在高级程序设计语言的层次上讨论数据结构及其操作的，因此，可以采用自定义数据类型来描述数据的存储结构，具体请参见各章存储结构的定义。

如图1-13所示，数据的逻辑结构是从具体问题抽象出来的数据模型，是面向问题的，反映了数据元素之间的关联方式或邻接关系。数据的存储结构是面向计算机的，其基本目标是将数据及其逻辑关系存储到计算机的内存中。在不致混淆的情况下，常常将数据的逻辑结构称为数据结构。

数据的逻辑结构和存储结构是密切相关的两个方面。一般来说，一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。

1.2.2 抽象数据类型

1.数据类型

数据类型（datatype）是一组值的集合以及定义于这个值集上的一组操作的总称。数据类型规定了该类型数据的取值范围以及能够执行的操作。例如，C语言中整型变量的取值范围是机器所能表示的最小负整数和最大正整数之间的任何一个整数，允许执行的操作有算术运算（+、-、*、/、%）、关系运算（＜、＜=、＞、＞=、==、！=）和逻辑运算（&&、‖、！）等。

2.抽象

所谓抽象（abstract），就是抽出问题的本质特征而忽略非本质的细节，是对具体事物的一个概括。比如，地图是对它所描述地域的一种抽象，中国人是对所有具有中国国籍的中国公民的一种抽象。

无论在数学领域还是程序设计领域，抽象的能力都源于这样一个事实：一旦一个抽象的问题得到解决，则很多同类的具体问题便可迎刃而解。抽象还可以实现封装和信息隐藏，例如，C语言将能够完成某种功能并可重复执行的一段程序抽象为函数，在需要执行这种功能时调用这个函数，从而将“做什么”和“怎么做”分离开来，实现了算法细节和数据内部结构的隐藏。

3.抽象数据类型

抽象数据类型（AbstractDataType，ADT）是一个数据结构以及定义在该结构上的一组操作的总称。ADT可理解为对数据类型的进一步抽象，数据类型和ADT的区别仅在于：数据类型指的是高级程序设计语言支持的基本数据类型，而ADT指的是自定义的数据类型。

在设计ADT时，把ADT的定义和实现分开。定义部分只包含数据的逻辑结构和所允许的基本操作集合，一方面，ADT的使用者依据这些定义来使用ADT，即通过操作集合对该ADT进行操作；另一方面，ADT的实现者依据这些定义来完成该ADT各种基本操作的具体实现，如图1-14所示。ADT提供了定义和实现的不同视图，实现了封装和信息隐藏。例如，整数的数学概念和施加到整数的运算构成一个ADT，C语言的int型是对这个ADT的物理实现，各种程序设计语言都提供了整数类型，尽管它们在不同编译器上实现的方法不同，但由于其ADT相同，在用户看来都是相同的。

一个ADT的定义不涉及它的实现细节，在形式上可繁可简，本书对ADT的定义包括抽象数据类型名、数据元素之间逻辑关系的定义、每种基本操作的接口（操作的名称和该操作的前置条件、输入、功能、输出、后置条件的定义），形式如下：

            ADT抽象数据类型名
            Data
                  数据元素之间逻辑关系的定义
            Operation
            操作1
                  前置条件：执行此操作前数据所必须的状态
                  输入：执行此操作所需要的输入
                  功能：该操作将完成的功能
                  输出：执行该操作后产生的输出

                  后置条件：执行该操作后数据的状态
            操作2
                  …
            操作n
                  …
            endADT