Логическая структура
Массив - такая структура данных, которая характеризуется:
· фиксированным набором элементов одного и того же типа;
· каждый элемент имеет уникальный набор значений индексов;
· количество индексов определяют мерность массива, например, два индекса - двумерный массив, три индекса - трехмерный массив, один индекс - одномерный массив или вектор;
· обращение к элементу массива выполняется по имени массива и значениям индексов для данного элемента.
Другое определение: массив - это вектор, каждый элемент которого - вектор.
Синтаксис описания массива представляется в виде:
< Имя > : Array [n1..k1] [n2..k2] .. [nn..kn] of < Тип >.
Для случая двумерного массива:
Mas2D : Array [n1..k1] [n2..k2] of < Тип >, или
Mas2D : Array [n1..k1 , n2..k2] of < Тип >
Наглядно двумерный массив можно представить в виде таблицы из (k1-n1+1) строк и (k2-n2+1) столбцов.
Физическая структура
Физическая структура - это размещение элементов массива в памяти ЭВМ. Для случая двумерного массива, состоящего из (k1-n1+1) строк и (k2-n2+1) столбцов физическая структура представлена на рис. 3.3.
Рис. 3.3. Физическая структура двумерного массива из (k1-n1+1) строк и (k2-n2+1) столбцов
Многомерные массивы хранятся в непрерывной области памяти. Размер слота определяется базовым типом элемента массива. Количество элементов массива и размер слота определяют размер памяти для хранения массива. Принцип распределения элементов массива в памяти определен языком программирования. Так в FORTRAN элементы распределяются по столбцам - так, что быстрее меняется левые индексы, в PASCAL - по строкам - изменение индексов выполняется в направлении справа налево.
Количество байтов памяти, занятых двумерным массивом, определяется по формуле :
ByteSize = (k1-n1+1)*(k2-n2+1)*SizeOf(Тип)
Адресом массива является адрес первого байта начального компонента массива. Смещение к элементу массива Mas[i1,i2] определяется по формуле:
ByteNumber = [(i1-n1)*(k2-n2+1)+(i2-n2)]*SizeOf(Тип)
его адрес : @ByteNumber = @mas + ByteNumber.
Например:
var Mas : Array [3..5] [7..8] of Word;
Базовый тип элемента Word требует два байта памяти, тогда таблица 3.2 смещений элементов массива относительно @Mas будет следующей:
Смещение (байт) | Идентификатор поля | Смещение (байт) | Идентификатор поля |
+ 0 | Mas[3,7] | + 2 | Mas[3,8] |
+ 4 | Mas[4,7] | +6 | Mas[4,8] |
+ 8 | Mas[5,7] | + 10 | Mas[5,8] |
Таблица 3.2
Этот массив будет занимать в памяти: (5-3+1)*(8-7+1)*2=12 байт; а адрес элемента Mas[4,8]:
@Mas+((4-3)*(8-7+1)+(8-7)*2 = @Mas+6
Операции
Важнейшая операция физического уровня над массивом - доступ к заданному элементу. Как только реализован доступ к элементу, над ним может быть выполнена любая операция, имеющая смысл для того типа данных, которому соответствует элемент. Преобразование логической структуры в физическую называется процессом линеаризации, в ходе которого многомерная логическая структура массива преобразуется в одномерную физическую структуру.
В соответствии с формулами (3.3), (3.4) и по аналогии с вектором (3.1), (3.2) для двумерного массива c границами изменения индексов:
[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)]
получим:
Addr[I(1),I(2),...,I(n)] = Addr[B(1),B(2),...B(n)] -
n n (3.6)
- Sizeof(Тип)*СУММА[B(m)*D(m)] + Sizeof(Тип)*СУММА[I(m)*D(m)]
m=1 m=1
где 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
К операциям логического уровня над массивами необходимо отнести такие как сортировка массива, поиск элемента по ключу. Наиболее распространенные алгоритмы поиска и сортировок будут рассмотрены в данной главе ниже.
Дата добавления: 2016-07-22; просмотров: 1441;