1.2.5 数据的存储结构

数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示（亦称为映象），也就是逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。数据元素之间的关系在计算机中有两种表示方式：顺序映象和非顺序映象。归纳起来，数据的存储结构在计算机中有以下4种。

微课1-2　数据的存储结构

1. 顺序存储结构

顺序存储结构是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构称为顺序存储结构，通常顺序存储结构是借助于计算机程序设计语言的数组来描述的。

顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全部用于存放结点的数据，结点之间的逻辑关系没有占用额外的存储空间。采用这种结构时，可实现对结点的随机存取。然而顺序存储结构的主要缺点是不便于修改，在对结点进行插入、删除运算时，可能要移动一系列的结点。

2. 链式存储结构

链式存储结构不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系是由附加的“指针”字段表示的。由此得到的存储结构称为链式存储结构。

链式存储结构的优点是便于修改，在对结点进行插入、删除操作时，仅需要修改相应结点的“指针域”，不必移动结点。但与顺序存储结构相比，链式存储结构的存储空间利用率较低，因为分配给数据的存储单元有一部分被用来存储结点间的逻辑关系了。另外，由于逻辑上相邻的结点在物理位置上并不一定相邻，所以不能对结点进行随机访问操作。

3. 索引存储结构

索引存储结构通常在存储结点信息的同时建立附加的索引表。索引表的每一项称为索引项，索引项的一般形式是（关键字，地址），关键字唯一标识一个结点，地址作为指向结点的指针。这种带有索引表的存储结构可以大大提高数据查找的速度。

线性结构采用索引存储结构后，可以对结点进行随机访问。在对结点进行插入、删除运算时，只需移动存储在索引表中对应结点的存储地址，而不必移动存放在结点表中结点的数据，所以仍保持较高的数据修改效率。索引存储结构的缺点是增加了索引表及存储空间开销。

4. 哈希存储结构

哈希存储结构的基本思想是根据结点的关键字通过哈希函数直接计算出一个值，并将这个值作为该结点的存储地址。

哈希存储结构的优点是查找速度快，只要给出待查找结点的关键字，就可以计算出该结点的存储地址。与前3种存储结构不同的是，哈希存储结构只存储结点的数据，不存储结点之间的逻辑关系。哈希存储结构一般适用于要求对数据能够进行查找和插入的场景。