1.2　基本概念和术语

1.2.1　基本概念

1．数据

数据是可被计算机识别并加工处理的对象。数据不仅包括整型、实型等数值数据，还包括声音、图像、视频等非数值数据。例如，MP3格式的文件是常见的音频声音数据，BMP格式的文件是典型的图像数据，RMVB格式的文件是视频数据。

2．数据元素

数据元素是由数据组成的具有一定意义的基本单位，在计算机中通常作为一个整体来处理。有些情况下，数据元素也称为元素、记录。

3．数据项

数据项是组成数据元素的、不可分割的最小单位。

表1.1为学生信息表，其中每个学生的信息可看作一个数据元素，它由学号、姓名、性别、籍贯等数据项组成。

表1.1　学生信息表

1.2.2　数据结构

数据结构（Data Structure）是由某一数据对象及该对象中所有数据元素之间的关系组成的。数据结构包括数据的逻辑结构、存储结构及数据的运算三方面的内容。接下来从这三方面分别阐述。

1．数据的逻辑结构

数据的逻辑结构是从逻辑关系上描述数据。数据的逻辑结构仅考虑数据之间的内在关系，是面向应用问题的，它是独立于计算机的。根据数据结构中数据元素之间关系的不同特征，可划分为四种基本逻辑结构，如图1.2所示。

（1）线性结构

线性结构中数据元素之间存在一对一的关系。例如，表1.1所示的学生信息表可看成一个线性结构，学生信息按照学号依次排列。

（2）树形结构

树形结构中数据元素之间存在一对多的关系。例如，一所学校有多个学院，一个学院有多个专业，构成树形结构。

（3）图结构

图结构中数据元素之间存在多对多的关系。例如，微信朋友圈中，“我”的朋友们彼此之间可能是相识关系，也可能是不相识关系，他们之间存在多对多的朋友关系，从而构成图结构。

图1.2　四种基本的逻辑结构示例

（4）集合结构

数据元素之间除了“属于同一个集合”的联系之外没有其他关系。例如，学生存在于某个班级中，若不考虑学生之间的其他关系，则可视班级为一个集合结构。

以上四种基本的逻辑结构还可进一步分成两类：线性结构和非线性结构。除了线性结构以外，树形、图和集合结构可统一归入非线性结构一类。

2．数据的存储结构

数据的存储结构是数据及数据之间的关系在计算机内的表示形式。它是面向计算机的，是数据的逻辑结构在计算机存储中的影像。数据的存储结构中，最常见的两种基本存储结构分别是顺序存储结构和链式存储结构。

（1）顺序存储结构

顺序存储结构是将逻辑上相关的数据元素依次存储在地址连续的存储空间中。这种存储结构是借助数据元素在存储空间中的相对位置来表示它们之间的逻辑关系。假定有一线性结构的数据（a0,a1,a2），每个元素占2个存储单元，连续存储空间的起始地址是100，则其顺序存储表示如图1.3（a）所示。

顺序表示方法并不仅限于存储线性结构的数据。例如，树形结构的数据对象有时也可采用顺序存储的方法表示。这将在以后章节中详细阐述。

（2）链式存储结构

链式存储结构中，数据元素可以存储在任意的存储空间中，可以是连续的存储空间，也可以是不连续的存储空间。在这种情况下，数据元素的存储位置并不能体现它们之间的逻辑关系，需要用指针域存储逻辑上相关的数据元素的地址。因此，为了存储一个元素，需要存放数据元素本身和与该元素逻辑上相关的其他元素的地址，这两部分信息组成一个结点。

假定有一线性结构的数据（a0,a1,a2），其链式存储表示如图1.3（b）所示。其中，每个结点存储了数据元素和该元素逻辑上的后继结点的地址。注意：一个结点的存储地址通常是指存放该结点的存储块的起始存储单元地址。

图1.3　两种基本的存储表示方法

在此约定，在不会引起混淆的场合，本书将不明确区分结点和元素这两个术语。但必要时，将包括数据元素和地址在内的整个存储块称为结点，而将其中的数据元素称为该结点的元素。

3．数据的运算

如果说数据的逻辑结构描述了数据的静态特性，那么在数据的逻辑结构上定义的一组运算给出了数据被使用的方式，即数据的动态特性。使用数据结构上定义的运算，用户可对数据结构的实例或组成实例的数据元素实施相应的操作。运算的结果可使数据改变状态。

数据结构最常见的运算有：

（1）搜索运算——在数据结构中搜索满足一定条件的元素；

（2）插入运算——在数据结构中插入新元素；

（3）删除运算——将数据结构中指定元素删除；

（4）更新运算——将数据结构中指定元素更新为新的元素。