5.1.2 数组的顺序存储表示

  由于数组类型不作插入和删除的操作,因此只需要通过"顺序映象"得到它的存储结构,即借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。

  通常有两种映象方法:即"以行(序)为主(序)"的映象方法和"以列(序)为主(序)"的映象方法。

  以图示的二维数组为例,"以行为主"的存储结构是对二维数组进行"按行切分",即将数组中的数据元素"按行依次排放"在存储器中;"以列为主"的存储结构是对二维数组进行"按列切分",即将数组中的数据元素"按列依次排放"在存储器中。

  假设二维数组 R[m][n] 中每个数据元素占L个存储地址,并以 LOC(i,j) 表示下标为 (i,j) 的数据元素的存储地址,则该数组中任何一对下标 (i,j) 对应的数据元素在"以行为主"的顺序映象中的存储地址为:
   LOC(i,j) = LOC(0,0) + (in+j) L

  在"以列为主"的顺序映象中的存储地址为:
   LOC(i,j) = LOC(0,0) + (jm+i) L

  其中 LOC(0,0) 是二维数组中第一个数据元素(下标为(0,0))的存储地址,称为数组的 "基地址" 或"基址"。
 
  由于数组中的数据元素之间是一个"多维"的关系,而存储地址是一维的,因此数组的顺序存储表示要解决的是一个"如何用一维的存储地址来表示多维的关系"的问题。

  二维数组:
A
B
C
D
E
M
N
O
P
Q
U
V
X
Y
Z

   

  现有的高级语言中的大多数都是按"以行为主"实现数组类型的。