Логічна та фізична структури

ЛОГІЧНА СТРУКТУРА. Масив – така структура даних, що характеризується:

– фіксованим набором елементів однакового типу;

– кожен елемент має унікальний набір значень індексів;

– кількість індексів визначає мірність масиву, наприклад, два індекси – двовимірний масив, три індекси – тривимірний масив, один індекс – одновимірний масив або вектор;

– звернення до елементу масиву виконується за іменем масиву і значенням індексів для даного елементу.

Інше визначення: масив – це вектор, кожен елемент якого є вектор.

Синтаксис опису масиву:

<Ім'я>: 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.2.

Багатомірні масиви зберігаються в неперервній області пам'яті. Розмір слота визначається базовим типом елементу масиву. Кількість елементів масиву і розмір слота визначають розмір пам'яті для збереження масиву. Принцип розподілу елементів масиву в пам'яті визначений мовою програмування. У FORTRAN елементи розподіляються по так, що швидше міняються ліві індекси; у PASCAL – по рядках, при цьому зміна індексів виконується в напрямку справа -наліво.

@Mas

+0	+Sizeof(Тип)		+ (k2 – n2)*Sizeof(Тип)
Mas[n1, n2]	Mas[n1, n2 + 1]	…	Mas[n1, k2]
…	…	…	…
Mas[k1, k2]	Mas[k1,n2+1]	…	Mas[n1, k2]
+(k1 – n1)*(k2 – n2 + 1)* Sizeof(Тип)	+((k1 – n1)*(k2 – n2 + 1) +1) * Sizeof(Тип)		+((k1 – n1)*(k2 – n2+1)+ +(k2 – n2))*Sizeof(Тип)

Рис. 3.2. Розподіл пам'яті для двовимірного масиву

Кількість байтів пам'яті, зайнятих двовимірним масивом, визначається за формулою:

ByteSіze = (k1 – n1 + 1) * (k2 – n2 + 1) * SіzeOf(Тип).

Адресою масиву є адреса першого байта початкового компонента масиву. Зсув до елементу масиву Mas[і1,і2] визначається за формулою:

ByteNumber = [(і1 – n1)*(k2 – n2+1)+(і2 – n2)]*SіzeOf(Тип),

адреса: @Mas[і1,і2] = @mas + ByteNumber

Наприклад:

var Mas: Array [3..5] [7..8] of Word;

Цей масив буде займати в пам'яті: (5 – 3 + 1)*(8 – 7 + 1)*2 = 12 байтів;

адреса елементу Mas[4,8] буде:

@Mas[4,8] = @Mas+((4 – 3)*(8 – 7 + 1) +(8 – 7)*2 = @Mas + 6

ОПЕРАЦІЇ. Найважливіша операція фізичного рівня над масивом – доступ до заданого елементу. Як тільки реалізовано доступ до елементу, над ним може бути виконана будь-яка операція, що має сенс для того типу даних, якому відповідає елемент. Перетворення логічної структури у фізичну називається процесом лінеаризації, в ході якого багатомірна логічна структура масиву перетвориться на одновимірну фізичну структуру.

Відповідно до формул та за аналогією з вектором для двовимірного масиву з границями зміни індексів: [n1..k1][n2..k2] розміщеного в пам'яті по рядках, адреса елементу з індексами [і1,і2] може бути обчислена як:

@Ім'я[і1, і2] = @Ім'я + ((і1 – n1)*(k2 – n2 + 1) + (і2 – n2))*SіzeOf(Тип) =

=@Ім'я + (і1*N2 + і2)*SіzeOf(Тип) – (n1*N2 + n2)*SіzeOf(Тип) =

= A0 + (і1*N2 + і2)*SіzeOf(Тип),

де: A0 = @Ім'я – (n1*N2 + n2)*SіzeOf(Тип) – постійна складова,

N2 = k2 – n2 + 1; – кількість елементів у рядку.

Для тривимірного масиву адреса елементу визначається так:

@Ім'я[і1, і2, і3] =

= @Ім'я + ((і1 – n1)*(k2 – n2 + 1)*(k3 – n3 + 1) + (і2 – n2)(k3 – n3 + 1) +

+ (і3 – n3))*SіzeOf(Тип) =

= @Ім'я + (і1*N2 + і2*N3 + і3)*SіzeOf(Тип) – (n1*N2 + n2*N3 +

+ n3)*SіzeOf(Тип) =

= A0 + (і1*N2 + і2*N3 + і3)*SіzeOf(Тип),

де: A0 = @Ім'я – (n1*N2 + n2*N3 + n3)*SіzeOf(Тип)– постійна складова,

N2 = (k2 – n2 + 1)*(k3 – n3 + 1),

N3 =k3 – n3 + 1; – кількість елементів у рядку.

Для прискорення обчислення адреси елементу масиву множники Nі обчислюються заздалегідь і зберігаються в дескрипторі масиву. Дескриптор масиву, таким чином, містить:

а) початкову адресу масиву,

б) число вимірів у масиві;

в) постійну складову формули лінеаризації (А0);

г) для кожного з n вимірів масиву:

– значення граничних індексів,

– множник формули лінеаризації – Nі.

У результаті, час звертання до елементу масиву залежить від мірності масиву і складає:

1- мірний масив – 2 операції, 2-мірний масив – 4 операції,

3-мірний масив – 6 операцій, n-мірний масив – 2*n операцій.

Одне з визначень масиву говорить, що це вектор, кожен елемент якого – вектор. Деякі мови програмування дозволяють виділити з багатомірного масиву один чи кілька вимірів і розглядати їх як масив меншої мірності.

Наприклад, якщо в PL/1-програмі оголошений двовимірний масив:

DECLARE A(10, 10),

то вираз: A[*,І] – буде звертатися до одновимірного масиву, що складається з елементів: A(1,І), A(2,І),...,A(10,І). Символ-джокер "*" означає, що вибираються всі елементи масиву за тим виміром, якому відповідає заданий джокером індекс. Використання джокера дозволяє також задавати групові операції над всіма елементами масиву чи над його обраним виміром, наприклад:

A(*, І) = A(*, І) + 1.

До операцій логічного рівня над масивами необхідно віднести такі, як сортування масиву, пошук елементу за ключем.

З наведених формул видно, що обчислення адреси елементу багатомірного масиву може зажадати багато часу, оскільки при цьому повинні виконуватись операції додавання і множення, число яких залежить від розмірності масиву. Операцію множення можна виключити, якщо застосовувати метод представлення масиву за допомогою векторів Айліффа, що дозволяє скоротити час доступу до його елементів.