Операции над массивами

Важнейшая операция физического уровня над массивом - доступ к заданному элементу. Как только реализован доступ к элементу, над ним может быть выполнена любая операция, имеющая смысл для того типа данных, которому соответствует элемент. Преобразование логической структуры в физическую, в ходе которого многомерная логическая структура массива преобразуется в одномерную физическую структуру, называется процессом линеаризации.

В соответствии с формулами (3.3), (3.4) и по аналогии с вектором (3.1), (3.2)для двумерного массива с границами изменения индексов:

[B(1)..E(1)][B(2)..E(2)], размещенного в памяти по строкам, адрес элемента с индексами [I(1),I(2)] может быть вычислен как:

Addr[I(1),I(2)] = Addr[B(1),B(2)] +

+ { [I(1)-B(1)] * [E(2)-B(2)+1] + [I(2)-B(2)] }*SizeOf(Тип) (3.5)

Обобщая (3.5) для массива произвольной размерности:

Mas[B(1)..E(2)][B(2)..E(2)]...[B(n)..E(n)]

получим:

(3.6)

где Dm зависит от способа размещения массива. При размещении по строкам:

D(m)=[E(m+1)-B(m+1)+1]*D(m+1), где m = n-1,...,1 и D(n)=1

при размещении по столбцам:

D(m)=[E(m-1)-B(m-1)+1]*D(m-1), где m = 2,...,n и D(1)=1

При вычислении адреса элемента наиболее сложным является вычисление третьей составляющей формулы (3.6), т.к. первые две не зависят от индексов и могут быть вычислены заранее. Для ускорения вычислений множители D(m) также могут быть вычислены заранее и сохраняться в дескрипторе массива. Дескриптор массива, таким образом, содержит:

начальный адрес массива - Addr[I(1),I(2),...,I(n)];

число измерений в массиве - n;

постоянную составляющую формулы линеаризации (первые две составляющие формулы (3.6);

для каждого из n измерений массива:

значения граничных индексов - B(i), E(i);

множитель формулы линеаризации - D(i).

Одно из определений массива гласит, что это вектор, каждый элемент которого - вектор. Некоторые языки программирования позволяют выделить из многомерного массива одно или несколько измерений и рассматривать их как массив меньшей мерности.

Например, если в PL/1-программе объявлен двумерный массив:

DECLARE A(10,10) BINARY FIXED;

то выражение: A[*,I] - будет обращаться к одномерному массиву, состоящему из элементов: A(1,I), A(2,I),...,A(10,I).

Символ-джокер "*" означает, что выбираются все элементы массива по тому измерению, которому соответствует заданный джокером индекс. Использование джокера позволяет также задавать групповые операции над всеми элементами массива или над выбранным его измерением, например: A(*,I) = A(*,I) + 1

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