1.2.1 基本概念和术语

1.数据（Data）

数据是信息的载体，是所有能够被计算机识别、存储和加工处理的符号的总称。它是计算机程序加工的原料，应用程序可以处理各种各样的数据。在计算机科学中，数据是计算机加工处理的对象，它可以是数值数据，也可以是非数值数据。数值数据是一些整数、实数和复数，主要用于工程计算、科学计算和商务处理等；非数值数据包括字符、文字、图形、图像和语音等。

2.数据项（Data Item）

数据项是具有独立含义的标识单位，是数据不可分割的最小单位。例如，学生成绩表中的“学号”和“姓名”等。数据项有名和值之分，数据项名是一个数据项的标识，用变量定义，而数据项值是它的一个可能取值，表中“20221801”是数据项“学号”的一个取值。数据项具有一定的类型，依数据项的取值类型而定。

3.数据元素（Data Element）

数据元素是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。例如，考试查分系统的学生成绩表中的一个记录、棋盘布局问题中状态树的一个状态、教学计划编排问题中的一个顶点等，都被称为一个数据元素。

有时，一个数据元素可由若干个数据项组成。例如，学籍管理系统中学生信息表的每一个数据元素就是一个学生记录。它包括学生的学号、姓名、性别、籍贯、出生年月、成绩等数据项。这些数据项可以分为两种：一种叫作初等项，如学生的性别、籍贯等，这些数据项是在数据处理时不能再分割的最小单位；另一种叫作组合项，如学生的成绩，它可以再划分为数学、物理、化学等更小的项。通常，在解决实际应用问题时每个学生记录是被当作一个基本单位进行访问和处理的。

4.数据对象（Data Object）

数据对象或数据元素类（Data Element Class）是具有相同性质的数据元素的集合。在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），属于同一数据对象（数据元素类），数据元素是数据元素类的一个实例。例如，在交通咨询系统的交通网中，所有的顶点是一个数据元素类，顶点A和顶点B各代表一个城市，是该数据元素类中的两个实例，其数据元素的值分别为A和B。

5.数据结构（Data Structure）

数据结构是指互相之间存在着一种或多种关系的数据元素的集合。数据结构涉及数据元素之间的逻辑关系，数据在计算机中的存储方式和在这些数据上定义的一组运算，一般称这三个方面为数据的逻辑结构、数据的存储结构和数据的运算。

（1）数据的逻辑结构

在任何问题中，数据元素之间都不会是孤立的，在它们之间都存在着这样或那样的逻辑关系，这种数据元素之间的关系称为逻辑结构。数据的逻辑结构包含两个要素：一个是数据元素的集合，另一个是关系的集合。

在形式上，数据的逻辑结构通常可以采用一个二元组来表示：

Data_Structure=（D，R）

其中，D是数据元素的有限集，R是D上关系的有限集。

根据数据元素间关系的不同特性，数据的逻辑结构通常分为以下四类。

1）集合。在集合中，数据元素间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构。

2）线性结构。该结构的数据元素之间存在着一对一的关系。

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

4）图形结构。该结构的数据元素之间存在着多对多的关系。图形结构也称作网状结构。

图1-3所示为上述四类基本逻辑结构的示意图。

由于集合是数据元素之间关系极为松散的一种结构，因此也可用其他结构来表示它。

数据的逻辑结构可以看作是从具体问题抽象出来的数学模型，它与数据的存储结构无关。人们研究数据结构的目的是为了在计算机中实现对它的操作，为此还需要研究如何在计算机中表示一个数据结构。数据结构在计算机中的标识（又称映像）称为数据的物理结构，又称存储结构。它所研究的是数据的逻辑结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。

（2）数据的存储结构

数据的存储结构最常用的是顺序存储和链式存储两种方法。

1）顺序存储方法是把逻辑上相邻的元素存储在物理位置相邻的存储单元中，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助程序设计语言中的数组来实现。

2）链式存储方法对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过相关联的指示来表示，由此得到的存储表示称为链式存储结构。链式存储结构通常借助程序设计语言中的指针或引用来实现。

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

3）索引存储方法是在存储结点信息的同时，还建立附加的索引表。索引表中的每一项包含关键字和地址，关键字是能够唯一标识一个数据元素的数据项，地址指示出数据元素所在的存储位置。索引存储主要是针对数据内容的存储，而不强调关系的存储。索引存储方法主要面向查找操作。

4）散列存储方法是以数据元素的关键字的值为自变量，通过某个函数（散列函数）计算出该元素的存储位置。索引存储也是针对数据内容的存储方式。

以上四种存储方法中，顺序存储方法和链式存储方法是最基本和最常用的，索引存储方法和散列存储方法在具体实现时需要用到前两种方法。在实际应用中，一种逻辑结构可以有不同的存储方法，选用何种存储结构来表示相应的逻辑结构要视具体情况而定，主要考虑运算的实现及算法的时空要求。

（3）数据的运算

运算是对数据的处理。运算与逻辑结构紧密相连，每种逻辑结构都有一个运算的集合。运算的种类很多，根据操作的结果，可将运算分为两种类型。

1）引用型运算。这类运算不改变数据结构中原有数据元素的状态，只根据需要读取某些信息。

2）加工型运算。这类运算的结果会改变数据结构中原有数据的状态，如数据元素的内容和个数等。

数据的运算是定义在数据的逻辑结构上的，但运算的具体实现是在数据的存储结构上进行的。数据的运算是数据结构不可分割的一个方面，在数据的逻辑结构和存储结构给定之后，如果定义的运算集及运算的性质不同，也会导致完全不同的数据结构，如后面章节中将要介绍的线性表、栈和队列等。