数据结构的内容

1.2　数据结构的内容

数据结构是指相互之间存在一种或多种特定关系的数据元素所组成的集合。具体来说,数据结构包括三方面的内容,即数据的逻辑结构、数据的存储结构和对数据所施加的运算。这三个方面的关系如下。

●数据的逻辑结构独立于计算机,是数据本身所具有的。

●数据的存储结构是逻辑结构在计算机存储器中的映像,必须依赖于计算机。

●运算是指所施加的一组操作的总称。运算的定义直接依赖于逻辑结构,但运算的实现必须依赖于存储结构。

1.逻辑结构

数据的逻辑结构是指数据的直接逻辑关系。大多数情况下,数据的结构可以用二元组表示:

S＝（D,R）

其中,D表示数据元素的集合；R是D上关系的有限集,表示D上的一种关系。

【例1－3】　二元组L＝（D,R1）,T＝（D,R2）,G＝（D,R3）分别描述了5个结点的三种不同的逻辑结构,分别如下。

则R₁,R₂,R₃的逻辑结构分别如图1－1所示。

图1－1　逻辑结构示意图

根据数据元素之间关系的不同特性,通常有下列四种基本结构,如图1－2所示。

图1－2　四种基本数据结构示意图

（1）集合关系:该结构中的数据元素之间除了同属于一个集合的关系外,无任何其他关系。

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

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

（4）图状结构或网状结构:该结构中的数据元素之间存在着多对多的任意关系。

由于集合关系中只有属于或不属于这种简单的属于关系,故可以用其他的结构代替。因此,数据的四种基本逻辑结构可概括如下。

2.存储结构

存储结构（又称物理结构）是逻辑结构在计算机中的存储映象,是逻辑结构在计算机中的实现,它包括数据元素的表示和关系的表示。数据结构从存储结构上划分为以下两种形式。

1）顺序存储

顺序存储（向量存储）是所有数据元素存放在一片连续的存储单元中,逻辑上相邻的元素存放到计算机内存中仍然相邻。

假设每个数据元素占用一个存储单元,数据从100号单元开始由低地址向高地址存放,则例1－3中线性结构的顺序存储结构如图1－3所示。

2）链式存储

链式存储是指所有数据元素可以存放在一片不连续的存储单元中,但数据元素之间的关系可以通过地址确定,逻辑上相邻的元素存放到计算机内存后不一定是相邻。

链式存储结构中,每个结点占用两个连续的存储单元,其中一个存储单元用于存放数值,另一个存储单元用于存放后继结点的地址。例1－3中线性结构的链式存储结构如图1－4所示。

图1－3　顺序存储结构

图1－4　链式存储结构

3）索引存储

使用索引存储的方法存储元素的同时,还需建立相应的索引表,索引表中的每一项称为索引项。索引项的一般形式为:

（关键字、地址）

其中,关键字是能唯一标识一个结点的那些数据项。索引存储的具体方法为:①建立索引表和结点表；②将每个结点的数值按顺序放在结点表中,而将每个结点的存储地址则用顺序存储方法存放在索引表中。对于线性结构来说,各结点的存储地址在索引表中是按结点的序号依次排列的。

例1－3中线性结构的索引存储结构如图1－5所示。

图1－5　索引存储结构

4）散列存储

散列存储方式通过构造散列函数,用函数的值来确定数据元素存放的地址。散列存储的具体方法为:以结点中某个字段的值作为自变量,通过某个函数（称为散列函数）计算出对应的函数值i,再将i作为结点的存储地址。

将例1－3中线性结构改为散列存储结构,可选用如下函数来计算各结点的地址。

LOC（k）＝k%7

其中,k为各结点数值的ASCII值,计算结果如下。

于是,可以得到如图1－6所示的散列存储结构。

图1－6　散列存储结构

同一逻辑结构采用不同的存储方法,可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构,应视具体要求而定,主要需考虑运算方便及算法的时空要求。

3.运算集合

讨论数据结构的目的是为了在计算机中实现操作,因此,在结构上的运算集合是很重要的部分,数据结构就是用于研究某一类数据的表示及其相关的运算操作。例如,表1－1的学生成绩表,数据元素之间采用顺序存放,该表采用的是线性表的逻辑结构。因为学生成绩表可以有成千上万名学生,既可以采用顺序存放,也可以采用非顺序存放,具体采用何种方式,这要看具体问题来分析。对于学生成绩表来说,若学生情况有异动,则可以对表格进行添加、删除、修改等操作。这里的增、删、查、改就是数据的集合操作。

4.数据结构三方面的关系

数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。如果孤立地去理解其中某一个方面,而不注意它们之间的联系是不可取的。

存储结构是数据结构不可缺少的一个方面,同一逻辑结构的不同存储结构可以冠以不同的数据结构名称来标识。

【例1－4】　线性表是一种逻辑结构,若采用顺序存储方法,可称其为顺序表；若采用链式存储方法,则可称其为链表；若采用散列存储方法,则可称其为散列表。

数据的运算也是数据结构中不可分割的一个方面。在给定了数据的逻辑结构和存储结构之后,若定义的运算集合及其运算的性质不同,也可能导致完全不同的数据结构。

【例1－5】　若对线性表上的插入、删除运算限制在表的一端进行,则该线性表称之为栈；若将插入运算限制在表的一端进行,而删除运算限制在表的另一端进行,则该线性表称之为队列。更进一步,若线性表采用顺序表或链表作为存储结构,则对插入和删除运算做了上述限制之后,可分别得到顺序栈或链栈,以及顺序队列或链队列。