数据的存储结构可以通过以下四种基本存储方法获得：

(1)顺序存储法

在这种方法中，逻辑上相邻的节点存储在物理上相邻的存储单元中，节点之间的逻辑关系由存储单元的相邻关系来反映。

由此产生的存储表示称为SequentialStorageStructure，在编程语言中通常用数组来描述。

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

(2)链接存储方法

这种方法不要求逻辑上相邻的节点物理上相邻，节点之间的逻辑关系用附加的指针字段来表示。由此产生的存储表示称为LinkedStorageStructure，在编程语言中通常通过指针类型来描述。

(3)索引存储方法

这种方法通常存储节点信息并建立一个附加的索引表。索引表由几个索引项组成。如果每个节点在索引表中都有一个索引条目，则该索引表称为DenseIndex。如果一组节点只对应于索引表中的一个索引项，则该索引表称为SpareIndex。索引条目的一般形式是：

(关键词，地址)

关键字是那些可以唯一标识节点的数据项。密集索引中的索引条目的地址指示节点的存储位置；稀疏索引中索引条目的地址指示一组节点的初始存储位置。

(4)哈希存储方法

该方法的基本思想是根据节点的关键字直接计算出节点的存储地址。

四种基本存储方法可以单独使用，也可以组合使用来存储和映像数据结构。

同一逻辑结构可以采用不同的存储方式，可以得到不同的存储结构。选择存储结构来表示相应的逻辑结构取决于具体要求，主要考虑操作的方便性和算法的时空要求。

数据结构三个方面的关系

数据的逻辑结构、数据的存储结构和数据的操作是一个整体。孤立地理解一个方面而不注意它们之间的关系是不可取的。存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可以用不同的数据结构名称来标识。

【例题】线性表是一种逻辑结构，如果用顺序方法表示，可以称为顺序表。如果采用链式存储方式，可以称之为链表；如果采用哈希存储方式，可以称之为哈希表。

数据的操作也是数据结构不可分割的一个方面。给定数据的逻辑结构和存储结构，定义的操作集合及其操作的性质是不同的，这也可能导致完全不同的数据结构。

【示例】如果对线性表的插入和删除操作仅限于表的一端，则线性表称为栈；如果插入被限制在表的一端，删除被限制在表的另一端，则线性表称为队列。再者，如果线性表采用顺序表或链表作为存储结构，对插入和删除操作进行上述限制后，可以分别得到顺序栈或链栈、顺序队列或链队列。责任编辑：抄送

标签：存储节点结构