Размещение прямоугольных массивов в последовательной памяти

Массивы

В качестве примера рассмотрим трёх­мерный прямоугольный массив (3 слоя по 4 строки по 5 элементов в строке). Такой массив можно представить в виде паралле­лепи­педа (рис 3.). Предположим, что элементы массива следуют в памяти в лексико­графическом порядке, то есть так, что первым изменяется последний индекс. Такой порядок используется в большинстве алгоритмических языков, но есть и исключения, например, Фортран. Порядковый номер элемента массива A[i][j][k] можно вычислить по формуле:

В общем случае описание массива может иметь вид:

A[i₁:j₁][i₂:j₂]…[i_n:j_n]

где i_m, j_{m –} нижняя и верхняя граница индекса в m-м измерении. Каждый раз, когда программа обращается к элементу массива, она должна вычислить его адрес по заданным индексам k₁,k₂…k_n. Функция упорядочения, которая это делает, имеет вид:

где L – искомый адрес; b – начальный адрес массива (адрес его 1-го элемента); D_m – объем m-го сечения массива (слоя, строки…) в байтах. В общем случае функцию упорядочения можно записать в виде:

, где

Константу с называют базовым адресом массива, который определяется как адрес возможно несуществующего элемента массива, у которого все индексы равны нулю.

Пример: для массива с границами индексов 3:5,1:4,0:1 имеем:

D₃=1

D₂₌(j₃-i₃+1)*D₃=2

D₁₌(j₂-i₂+1)*D₂=8

с=b-(i₁*D₁+i₂*D₂+i₃*D₃)=26*(b-1)

И функция упорядочения имеет вид:

L=25*(b-1)+8*k₁+2*k₂+k₃

Функция упорядочения строится компиляторами автоматически. Исходные данные о массиве представляются обычно в виде информационного вектора массива:

I_A=(n, число элементов, C, D₁, D₂,…D_n, i_1, j₁, i₂, j₂,…i_n, j_n)