【数据结构专题】「延时队列算法」史上手把手带你认识一下数据结构的基本概念与术语

在本节中，我们将对一些概念和术语赋以确定的含义，以便与读者取得“共同的语言”。这些概念和术语将在以后的章节中多次出现。

数据

概念

数据(data) 是对客观事物的符号表示， 在计算机科学中是指所有能输人到计算机中并被计算机程序处理的符号的总称。 它是计算机程序加工的“原料”。主要分为两大类：

• 数值型数据
• 非数值型数据

案例

例如，一个利用数值分析方法解代数方程的程序，其处理对象是整数和实数；一个编译程序或文字处理程序的处理对象是字符串。因此，对计算机科学而言，数据的含义极为广泛，如图像、声音等都可以通过编码而归之于数据的范畴。

数据元素

数据元素(data element) 是数据的基本单位， 在计算机程序中通常作为一个整体进行考虑和处理。

例如，例2中的“树”中的一个棋盘格局，例3中的“图”中的一个圆圈都被称为一个数据元素。

一个数据元素可由若干个数据项(data item) 组成。

数据项

例1中一本书的书目信息为一个数据元素，而书目信息中的每一项(如书名、作者名等)为一个数据项。

数据项是数据的不可分割的最小单位。

数据对象

数据对象(dataobject) 是性质相同的数据元素的集合， 是数据的一个子集。

例如，整数数据对象是集合N={0，士l，士2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’}。

数据结构

数据结构(datastructure) 是相互之间存在一种或多种特定关系的数据元素的集合。

按某种逻辑关系组织起来的一批数据(或称带结构的数据元素的集合)应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。

从上面的3个例子可以看到，在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构(structure)。

根据数据元素之间关系的不同特性，通常有下列4类基本结构：

1. 集合结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系；
2. 线性结构结构中的数据元素之间存在一个对一个的关系；
3. 树形结构结构中的数据元素之间存在一个对多个的关系；
4. 图状结构或网状结构结构中的数据元素之间存在多个对多个的关系。

下图为上述4类基本结构的关系图，由于“集合”是数据元素之间关系极为松散的一种结构，因此也可用其他结构来表示它。

数据结构的形式定义为一个二元组：Data_Structure=(D， S)。其中：D是数据元素的有限集，S是D上关系的有限集。下面举两个简单例子说明之。

在计算机科学中，复数可取如下定义：

复数是一种数据结构：

Complex=(C,R)

C是含两个实数的集合{c1,c2}；R={P}，而Ｐ是定义在集合C上的一种关系{<c1,c2>}，其中有序偶<c1,c2>表示c1是复数的实部，c2是复数的虚部。

假设我们需要编制一个事务管理的程序

管理学校科学研究课题小组的各项事务，则首先要为程序的操作对象——课题小组设计一个数据结构。

假设每个小组由1位教师、1-3名研究生及1~6名本科生组成，小组成员之间的关系是：教师指导研究生，而由每位研究生指导一至两名本科生。则可以如下定义数据结构：

Group=(P,R)

其中：P={T,G(1),…,G(n),S(1)…S(m),1≤n≤3,1≤m≤2}

T表示导师，G表示研究生，S表示大学生。

R={R1,R2}
R1={<T,Gi> | 1≤i≤n，1≤n≤3}
R2={<G(i),S(ij)> | 1≤i≤n，1≤j≤m，1≤n≤3，1≤m≤2}

上述数据结构的定义仅是对操作对象的一种数学描述，换句话说，是从操作对象抽象出来的数学模型。

结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。然而，讨论数据结构的目的是为了在计算机中实现对它的操作，因此还需研究如何在计算机中表示它。

数据结构在计算机中的表示(又称映像)称为数据的物理结构，又称存储结构。

它包括数据元素的表示和关系的表示。在计算机中表示信息的最小单位是二进制数的一位，叫做位(bit) 。

• 在计算机中， 我们可以用一个由若干位组合起来形成的一个位串表示一个数据元素(如用一个字长的位串表示一个整数，用8位二进制数表示一个字符等)，通常称这个位串为元素(element) 或结点(node) 。

• 当数据元素由若干数据项组成时， 位串中对应于各个数据项的子位串称为数据域(datafield) 。因此， 元素或结点可看成是数据元素在计算机中的映像。

存储结构的类型

数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。

顺序映像

顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。

假设用两个字长的位串表示一个实数，则可以用地址相邻的4个字长的位串表示一个复数，如下图为表示复数z1=3.0-2.3i和z2=-0.7+4.8i的顺序存储结构；

顺序存储结构

链式存储结构

非顺序映像的特点是借助指示元素存储地址的指针(pointer) 表示数据元素之间的逻辑关系， 如下图为表示复数xl的链式存储结构，其中实部和虚部之间的关系用值为“0415”的指针来表示(0415是虚部的存储地址)。

数据的逻辑结构和物理结构是密切相关的两个方面，任何一个算法的设计取决于选定的数据(逻辑)结构，而算法的实现依赖于采用的存储结构。

如何描述存储结构呢

虽然存储结构涉及数据元素及其关系在存储器中的物理位置，但由于本书是在高级程序语言的层次上讨论数据结构的操作，因此不能如上那样直接以内存地址来描述存储结构，但我们可以借用高级程序语言中提供的“数据类型”来描述它。

数据类型

数据类型(datatype) 是和数据结构密切相关的一个概念， 它最早出现在高级程序语言中，用以刻画(程序)操作对象的特性。

在用高级程序语言编写的程序中，每个变量、常量或表达式都有一个它所属的确定的数据类型。可以用所有高级程序语言中都有的“一维数组”类型来描述顺序存储结构，以C语言提供的“指针”来描述链式存储结构。

我们把C语言看成是一个执行C指令和C数据类型的虚拟处理器，那么本书中讨论的存储结构是数据结构在Ｃ虚拟处理器中的表示，不妨称它为虚拟存储结构。

• 数据类型的规范：类型明显或隐含地规定了在程序执行期间变量或表达式所有可能取值的范围，以及在这些值上允许进行的操作。因此数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

例如，C语言中的整型变量，其值集为某个区间上的整数(区间大小依赖于不同的机器)，定义在其上的操作为加、减、乘、除和取模等算术运算。

数据类型的分类

按“值”的不同特性，高级程序语言中的数据类型可分为两类：

• 一类是非结构的原子类型。原子类型的值是不可分解的，例如C语言中的基本类型(整型、实型、字符型和枚举类型)、指针类型和空类型。
• 另一类是结构类型。结构类型的值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可以是结构的。
  • 例如，数组的值由若干分量组成，每个分量可以是整数，也可以是数组等。在某种意义上，数据结构可以看成是“一组具有相同结构的值”，则结构类型可以看成由一种数据结构和定义在其上的一组操作组成。

实际上，在计算机中，数据类型的概念并非局限于高级语言中，每个处理器(包括计算机硬件系统、操作系统、高级语言、数据库等计算机的硬件系统和软件系统)都提供了一组原子类型或结构类型。例如，一个计算机硬件系统通常含有 “位”、“字节”、“字” 等原子类型，它们的操作通过计算机设计的一套指令系统直接由电路系统完成，而高级程序语言提供的数据类型，其操作需通过编译器或解释器转化成低层，即汇编语言或机器语言的数据类型来实现。

• 引人“数据类型”的目的，从硬件的角度看，是作为解释计算机内存中信息含义的一种手段，而对使用数据类型的用户来说，实现了信息的隐蔽，即将一切用户不必了解的细节都封装在类型中。
  • 例如，用户在使用“整数”类型时，既不需要了解“整数”在计算机内部是如何表示的，也不需要知道其操作是如何实现的。如“两整数求和”，程序设计者注重的仅仅是其“数学上求和”的抽象特性，而不是其硬件的“位”操作如何进行。

抽象数据类型

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

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

抽象数据类型的发展

抽象数据类型的范畴更广，它不再局限于前述各处理器中已定义并实现的数据类型(也可称这类数据类型为固有数据类型)，还包括用户在设计软件系统时自己定义的数据类型。

为了提高软件的复用率，在近代程序设计方法学中指出，一个软件系统的框架应建立在数据之上，而不是建立在操作之上(后者是传统的软件设计方法所为)。

抽象数据类型的复用

即在构成软件系统的每个相对独立的模块上，定义一组数据和施于这些数据上的一组操作，并在模块内部给出这些数据的表示及其操作的细节，而在模块外部使用的只是抽象的数据和抽象的操作。所定义的数据类型的抽象层次越高，含有该抽象数据类型的软件模块的复用程度也就越高。

抽象数据类型的组成

一个含抽象数据类型的软件模块通常应包含定义、表示和实现3个部分。
抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。若按其值的不同特性，可细分为下列3种类型：

• 原子类型(atomic datatype) 属原子类型的变量的值是不可分解的。这类抽象数据类型较少，因为一般情况下，已有的固有数据类型足以满足需求。但有时也有必要定义新的原子数据类型。例如，数位为100的整数。

• 固定聚合类型(fixed-aggregate datatype) 属该类型的变量， 其值由确定数目的成分按某种结构组成。例如，复数是由两个实数依确定的次序关系构成。

• 可变聚合类型(variable-aggregate datatype) 和固定聚合类型相比较， 构成可变聚合类型“值”的成分的数目不确定。例如，可定义一个“有序整数序列”的抽象数据类型，其中序列的长度是可变的，数组、队列等模型就是。

后两种类型可统称为结构类型。

和数据结构的形式定义相对应，抽象数据类型可用以下三元组表示：

(D，S，P)

其中，D是数据对象，S是D上的关系集，P是对Ｄ的基本操作集。我们采用以下格式定义抽象数据类型：

ADT抽象数据类型名{
	数据对象：<数据对象的定义>
	数据关系：<数据关系的定义>
	基本操作：<基本操作的定义>
}ADT抽象数据类型名

其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为

基本操作名(参数表)
初始条件：<初始条件描述>
操作结果：<操作结果描述>

基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。

• “初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。
• “操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。

抽象数据类型三元组的定义

ADT Triplet{
	数据对象：D={e1,e2,e3 l e1,e2,e3 -> ElemSet(定义了关系运算的某个集合) }
	数据关系：R1={<el,e2>,<e2,e3>}
	基本操作：
		InitTriplet(&T,v1, v2,v3)
			操作结果：构造了三元组T，元素e1,e2和e3分别被赋以参数vl,v2和v3的值。
		DestroyTriplet(&T)
			操作结果：三元组T被销毁。
		Get(T,i,&e)
			初始条件：三元组T已存在，1≤i≤3。
			操作结果：用e返回T的第i元的值。(输出结果)
		Put(&T， i， e)
			初始条件：三元组T已存在，1≤i≤3。
			操作结果：改变T的第i元的值为e。
		IsAscending(T)
			初始条件：三元组T已存在。
			操作结果：如果T的3个元素按升序排列，则返回1，否则返回0。
		IsDescending(T)
			初始条件：三元组T已存在。
			操作结果：如果T的3个元素按降序排列，则返回1，否则返回0。
		Max(T,&e)
			初始条件：三元组T已存在。
			操作结果：用e返回T的3个元素中的最大值。
		Min(T,&e)
			初始条件：三元组T已存在。
			操作结果：用e返回T的3个元素中的最小值。
} ADT Triplet

多形数据类型(polymorphic datatype)

多形数据类型(polymorphic datatype) 是指其值的成分不确定的数据类型。

• 上面定义的抽象数据类型Triplet， 其元素e1、e2和e3可以是整数或字符或字符串， 甚至更复杂地由多种成分构成(只要能进行关系运算即可)。

• 不论其元素具有何种特性，元素之间的关系相同，基本操作也相同。

从抽象数据类型的角度看，具有相同的数学抽象特性，故称之为多形数据类型。

显然，需借助面向对象的程序设计语言如C++/Java等实现之。我们讨论的各种数据类型大多是多形数据类型，我们暂时只讨论含有确定成分的数据元素的情况。上面的ElemSet是某个确定的、将由用户自行定义的、含某个关系运算的数据对象。

课后习题

问题

描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别？

答案

• 抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。

• 一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。

抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。

设有数据结构(D,R)，其中

试按图论中图的画法惯例画出其逻辑结构图

答案