要学好“数据结构”,必须要明确各种概念及其相互之间的关系。本节介绍一些常用的术语和基本概念。

(1)数据

数据(data)是信息的载体,也就是说数据里面隐含着信息;它能够被计算机识别、存储和加工处理。它是计算机程序加工的“原料”。随着计算机软件、硬件的发展,以及计算机应用领域的扩大,数据的含义也随之拓广了,它不仅仅是数字和字符串,而图形、图像、声音等,它们也属于数据的范畴。

(2)数据元素

数据元素(data element)是数据的基本单位。有些情况下,数据元素也称为元素、结点、顶点、记录。有时一个数据元素可以由若干个数据项(也可称为字段、域、属性)组成,数据项是具有独立含义的最小标识单位。

(3)数据结构

数据结构(data structure)由数据和结构两部分构成。其中,数据部分是指数据元素的集合:结构就是关系,结构部分是指数据元素之间关系的集合。概括地讲,数据结构就是指相互之间有一种或多种特定关系的数据元素的集合。在计算机上要处理数据,就要保存数据及它们之间的关系。在这里,关系就是数据的逻辑结构,它指反映数据元素之间的逻辑关系的数据结构,其中的逻辑关系是指元素之间的前后关系,而与它们在计算机中的存储位置无关。

1)数据的逻辑结构

数据的逻辑结构是从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。因此,数据的逻辑结构可以看成从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实现(亦称为映像),它是依赖于计算机语言的,对机器语言而言,存储结构是具体的,但我们只在高级语言的层次上来讨论存储结构。数据的运算是定义在数据的逻辑结构上的,每种逻辑结构都有一个运算的集合。例如,最常用的运算有检索、插入、删除、更新、排序等。

从逻辑上可以把数据结构分为线性结构和非线性结构,主要包括集合、线性、树形和图状结构:

①集合结构

集合结构(set structure)中的数据元素除了“同属于一个集合”的关系外,再无其他关系。如整数集、字符集等。

②线性结构

线性结构(linear structure)中的数据元素之间在“一对一”的关系。比如数组、队列等。

③树形结构

树形结构(tree structure)中的数据元素之间存在“一对多”的关系。比如人机对弈等。

④图状结构

图状结构(graphic structure,也称网状结构)中的数据元素之间存在“多对多”的关系。比如城市交通图等。(www.daowen.com)

2)数据的存储结构

数据的存储结构可用以下4种基本存储方法得到:

①顺序存储方法

该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表称为顺序存储结构(sequential storage structure),通常借助程序语言的数组描述。

该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。

②链接存储方法

该方法不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系由附加的指针字段表示。由此得到的存储表称为链式存储结构(linked storage structure),通常借助于程序语言的指针类型描述。

③索引存储方法

该方法通常在储存结点信息的同时,还建立附加的索引表,索引表由若干索引项组成。若每个结点在索引表中都有一个索引项,则该索引表称之为稠密索引(dense index)。若一组结点在索引表中只对应一个索引项,则该索引表称为稀疏索引(spare index)。索引项的一般形式是:

(关键字、地址)

关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置;稀疏索引中索引项的地址指示一组结点的起始存储位置。

④散列存储方法(不知道存储地址,要计算得到该地址)

该方法的基本思想是:根据结点的关键字直接计算出该结点的存储地址。四种基本存储方法,既可单独使用,也可组合起来对数据结构进行存储映像。同一逻辑结构采用不同的存储方法,可以得到不同的存储结构(图6.34)。选择何种存储结构来表示相应的逻辑结构,视具体要求而定,主要考虑运算方便及算法的时空要求。数据逻辑结构层次关系如图6.35所示。

图6.34　逻辑结构与对应的存储结构

图6.35　数据逻辑结构层次关系图