1.3 数据的存储结构

数据在计算机中的存储表示称为数据的存储结构，也称为物理结构。数据的存储结构是逻辑结构在计算机存储器中的实现。本书将介绍常用的两种基本的存储结构：顺序存储结构和链式存储结构。

数据的逻辑结构和存储结构的关系是：存储结构是逻辑关系的映像与元素本身映像，是数据结构的实现；逻辑结构是数据结构的抽象。

1.顺序存储结构

顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。

【例1-4】 对于表1-1提出的学生信息登记表进行存储，假定每个元素占用50个存储单元，数据从1000号单元开始由低地址向高地址存放，对应的顺序存储结构如表1-3所示。

表1-3 表1-1的学生信息登记表的顺序存储表

在C语言中，最简单的方法是用一维数组来实现顺序存储。

顺序存储结构的主要特点如下。

◆ 可实现对各数据元素的随机访问。这是因为只要知道存储的首地址以及每个数据元素所占的存储单元，就可以计算出各数据元素的存储地址。

◆ 不利于修改，在对数据元素进行插入、删除运算时可能要移动一系列的数据元素。

2.链式存储结构

链式存储结构特点是借助指示元素存储地址的指针表示数据元素间的逻辑关系。

【例1-5】 对于表1-1学生信息登记表进行链式存储时，在每个数据元素后方附加一个指向“下一个结点地址”的指针字段，用于存放后继数据元素的存储地址，每个数据元素的地址是随机的，可以不连续。对应的链式存储结构见表1-4所示。

表1-4 表1-1学生信息登记表的链式存储表

链式存储结构的主要特点：

◆ 利于修改，在对数据元素进行插入、删除运算时，仅需修改数据元素的指针字段值，而不必移动数据元素；

◆ 由于逻辑上相邻的数据元素在存储位置中不一定相邻，因此，链式存储结构不能对数据元素进行随机访问。

3.索引存储结构

索引存储是在原有的存储结构的基础上，附加建立一个索引表，索引表中的每一项都由关键字和地址组成。索引表反映了按某一个关键字递增或递减排列的逻辑次序。采取索引存储的主要作用是为了提高数据的检索速度。

4.散列存储结构

散列存储是通过构造散列函数来确定数据存储地址或查找地址。例如，某一地区进行2000年以后出生的人口统计。我们用“出生年份-2000=存储地址”来构造一个函数，即用出生年份减去2000得到的差值就是存储地址，这样就能方便的得到这样的调查表，如表1-5所示。

表1-5 2000年后出生人口调查表