数据结构相关概念

来自计算思维百科
跳转至: 导航搜索

数据(Data)

是描述客观事物的符号,是计算机中科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据不仅包括整型、实型等数值类型,还包括字符及声音、图像、视频等非数值类型。

数据元素(Data Element)

是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成,数据项是数据的不可分割的最小单位。

数据对象(Data Object)

是性质相同的数据元素的集合,是数据的一个子集。

结构(Structure)

简单的理解就是关系,比如分子结构就是组成分子的原子之间的排列方式。严格点说,结构是指各个组成部分相互搭配和排列的方式。现实世界中,不同数据元素之间不是独立的,而是存在特定的关系,我们将这些关系称为结构。而数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。

在计算机中,数据元素并不是孤立、杂乱无序的,而是具有内在联系的数据集合。数据元素之间存在的一种或多种特定关系,也就是数据的组织形式。

逻辑结构(Logical Structure)

按照视点的不同,可以把数据结构分为逻辑结构和物理结构。所谓逻辑结构(Logical Structure),是指数据对象中数据元素之间的相互关系。逻辑结构分为以下4种:

(1)集合,结构中的数据元素之间除了“同属于一个集合”的关系外,别无其他关系,如图1(a)所示;

(2)线性结构,结构中的数据元素之间存在一个对一个的关系,如图1(b)所示;

(3)树形结构,结构中的数据元素之间存在一个多对多的关系,如图1 (c)所示;

(4)图状结构或网状结构,结构中的数据元素之间存在多个对多个的关系,如图1 (d)所示。

3.2.3.png3.2.4.png3.2.5.png3.2.6.png

图1不同类型的逻辑结构

存储结构(Storage Structure)

不同逻辑结构的数据,均需存储到计算机中,因此将数据结构在物理中的表示称为物理结构(Physical Structure),又称为存储结构(Storage Structure)。数据的存储结构应正确反映数据元素之间的逻辑关系。数据元素的存储结构形式有两种:顺序存储和链式存储。

顺序存储结构

顺序存储结构(Sequential Storage Structure):把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的。例如图2中,元素1-9被存放在连续的存储单元中,即为一种顺序存储方式。顺序存储结构的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。顺序存储非常适合进行数据元素的查找,例如,若知道第一个元素的存储地址,即可以根据每个元素的存储单元大小及其在逻辑结构中的位置,计算其实际的存储位置;但如果对采用顺序存储的大量数据进行数据元素的插入、删除等更新操作,则会导致比较大的开销。

3.2.7.png

图2 顺序存储结构

链式存储结构

链式存储结构(Chained Storage Structure):把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的。由于数据元素的存储关系并不能反映其逻辑关系,因此需要用一个指针存放数据元素的地址,这样通过地址可以找到相关联的数据元素的位置。例如,图3中,元素9被存放在不同位置的存储单元中,每个数据元素提供一个指针指向其后续的数据元素。在采用链式存储的数据对象中进行数据元素的插入和删除开销会比较小,但若需要查找某个数据元素,则必须从链式存储的第一个元素开始,沿着指针,进行查找。

3.2.8.png

图3 链式存储结构