计算机导论（第2版）：数据结构与顺序存储

2023-11-25 理论教育版权反馈

【摘要】：数据元素也称元素、结点、顶点、记录。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。该方法的基本思想是，根据数据元素的关键字直接计算出该结点的存储地址。

数据（data）是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的“原料”。随着计算机应用领域的扩大，数据的范畴包括整数、实数、字符串、图像、声音和视频等。

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

数据结构（data structure）指的是数据元素之间的相互关系，即数据的组织形式。数据结构主要研究数据的逻辑结构和数据的存储结构。

1.数据的逻辑结构

数据的逻辑结构指反映数据元素之间逻辑关系的数据结构，逻辑关系是指数据元素之间的前后关系，而与它们在计算机中的存储位置无关。逻辑结构的类型如下。

1）集合

数据结构中的元素之间除了“同属一个集合”的相互关系外，别无其他关系。

2）线性结构

数据结构中的元素之间是一对一的相互关系。

3）树形结构

数据结构中的元素之间属于一对多的相互关系。

4）图形结构(www.chuimin.cn)

数据结构中的元素之间呈现多对多的相互关系。

2.数据的存储结构

数据的存储结构指数据的逻辑结构在计算机存储空间的存放形式。

数据的存储结构是数据的逻辑结构在计算机中的表示，具体实现的方法有顺序、链接、索引、散列等多种形式，因此，一种数据的逻辑结构可表示成一种或多种存储结构。顺序存储结构和链式存储结构是常用的两种存储结构。

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

（1）顺序存储方法。该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。

（2）链接存储方法。该方法不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构，通常借助程序语言的指针类型描述。

（3）索引存储方法。该方法通常在储存结点信息的同时建立附加的索引表。索引表由若干索引项组成，一般每个数据元素在索引表中都有一个索引项，通过索引项可以找到相应的数据元素。

（4）散列存储方法。该方法的基本思想是，根据数据元素的关键字直接计算出该结点的存储地址。

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

数据的逻辑结构和存储结构确定之后，就要设计出基于当前数据结构的算法，也就是解决问题的步骤。选择好的算法有两条标准，一是尽量少地占用计算机的存储空间，二是算法消耗的时间尽量少，也即计算速度尽量快。对于算法，经常不是空间和时间都各自达到最优，往往根据实际需要在二者之间取得一个平衡，以解决实际问题的效果来评判和选择。

计算机导论（第2版）：数据结构与顺序存储

相关推荐