![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
ЛОГІЧНА СТРУКТУРА. Масив – така структура даних, що характеризується:
– фіксованим набором елементів однакового типу;
– кожен елемент має унікальний набір значень індексів;
– кількість індексів визначає мірність масиву, наприклад, два індекси – двовимірний масив, три індекси – тривимірний масив, один індекс – одновимірний масив або вектор;
– звернення до елементу масиву виконується за іменем масиву і значенням індексів для даного елементу.
Інше визначення: масив – це вектор, кожен елемент якого є вектор.
Синтаксис опису масиву:
<Ім'я>: 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.
До операцій логічного рівня над масивами необхідно віднести такі, як сортування масиву, пошук елементу за ключем.
З наведених формул видно, що обчислення адреси елементу багатомірного масиву може зажадати багато часу, оскільки при цьому повинні виконуватись операції додавання і множення, число яких залежить від розмірності масиву. Операцію множення можна виключити, якщо застосовувати метод представлення масиву за допомогою векторів Айліффа, що дозволяє скоротити час доступу до його елементів.
Дата публикования: 2014-12-08; Прочитано: 624 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!