线性表元素存储地址怎么算

2.3.2　线性表的顺序存储结构

线性表的顺序表指的是用一组地址连续的存储单元依次存储线性表的数据元素。

线性表的顺序存储结构具备如下两个基本特点：

①线性表中所有元素所占的存储空间是连续的；

②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

由此可以看出，在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。

在线性表的顺序存储结构中，如果线性表中各数据元素所占的存储空间（字节数）相等，则要在该线性表中查找某一个元素是很方便的。

假设线性表中的第一个数据元素的存储地址（指第一个字节的地址，即首地址）为ADR(a₁)，每一个数据元素占k个字节，则线性表中第i个元素a_i在计算机存储空间中的存储地址为ADR(a_i)=ADR(a₁)+(i-1)k。

即在顺序存储结构中，线性表中每一个数据元素在计算机存储空间中的存储地址由该元素在线性表中的位置序号唯一确定。一般来说，长度为n的线性表表示为(a_l，a₂，…，a_i，…，a_n)。

在计算机中的顺序存储结构如图2-5所示。

图2-5　线性表的顺序存储结构

在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。因为程序设计语言中的一维数组与计算机中实际的存储空间结构是类似的，这就便于用程序设计语言对线性表进行各种运算处理。

在用一维数组存放线性表时，该一维数组的长度通常要定义得比线性表的实际长度大一些，以便对线性表进行各种运算，特别是插入运算。在一般情况下，如果线性表的长度在处理过程中是动态变化的，则在开辟线性表的存储空间时要考虑到线性表在动态变化过程中可能达到的最大长度。如果开始时所开辟的存储空间太小，则在线性表动态增长时可能会出现存储空间不够而无法再插入新的元素；但如果开始时所开辟的存储空间太大，而实际上又用不着那么大的存储空间，则会造成存储空间的浪费。在实际应用中，可以根据线性表动态变化过程中的一般规模来决定开辟的存储空间量。

在线性表的顺序存储结构下，可以对线性表做以下运算：

①在线性表的指定位置处加入一个新的元素（即线性表的插入）；

②在线性表中删除指定的元素（即线性表的删除）；

③在线性表中查找某个（或某些）特定的元素（即线性表的查找）；

④对线性表中的元素进行整序（即线性表的排序）；

⑤按要求将一个线性表分解成多个线性表（即线性表的分解）；

⑥按要求将多个线性表合并成一个线性表（即线性表的合并）；

⑦复制一个线性表（即线性表的复制）；

⑧逆转一个线性表（即线性表的逆转）等。

下面两小节主要讨论线性表在顺序存储结构下的插入与删除的问题。