Вектори

 

ЛОГІЧНА СТРУКТУРА. Вектор (одновимірний масив) – структура даних з фіксованим числом елементів однакового типу. Кожен елемент вектора має унікальний в рамках заданого вектора номер. Звертання до елементу вектора виконується за іменем вектора і номером необхідного елементу.

МАШИННЕ ПРЕДСТАВЛЕННЯ. АДРЕСАЦІЯ ЕЛЕМЕНТІВ СТРУКТУР. Елементи вектора розміщуються в пам'яті в підряд розташованих комірках пам'яті. Під елемент вектора виділяється така кількість байтів пам'яті, яка зумовлена базовим типом елементу цього вектора. Необхідне число байтів пам'яті для збереження одного елементу вектора називається слотом. Розмір пам'яті для збереження вектора визначається добутком довжини слота на число елементів.

У мовах програмування вектор представляється одновимірним масивом із синтаксисом опису вигляду (PASCAL):

<Ім'я> : array [n..k] of <тип>;

де n – номер першого елементу, k – номер останнього елементу.

Представлення в пам'яті вектора буде таке, як показано на рис. 3.1.

 

@ Iм’я	+ 0	+Sizeof(тип)	...		+(k– n)*Sizeof(тип)
	Iм’я [n]	Iм’я [n + 1]		Iм’я[k – 1]	Iм’я[k]

 

Рис. 3.1. Представлення вектора в пам'яті

 

Тут: @ Ім'я – адреса вектора або адреса першого елементу вектора,

Sіzeof(тип) – розмір слота,

(k – n)*Sіzeof(тип) – відносна адреса елементу з номером k чи зсув елементу з номеромk відносно початку вектора.

У мовах, де пам'ять розподіляється до виконання програми, на етапі компіляції (C, PASCAL, FORTRAN), при описі типу вектора граничні значення індексів повинні бути визначені. У мовах, де пам'ять може розподілятися динамічно (ALGOL, PL/1), значення індексів можуть бути задані під час виконання програми.

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

ByteSіze = ( k – n + 1 ) * Sіzeof (тип).

Звертання до і-го елементу вектора виконується за адресою вектора плюс зсув до даного елементу. Зсув і-го елементу вектора визначається за формулою: ByteNumer = ( і– n ) * Sіzeof (тип),

а його адреса: @ Ім'я[і] = @ ім'я + ByteNumber,

де @ ім'я – адреса першого елементу вектора.

Наприклад:

var МAS: array [ 5..10 ] of word;

Цей вектор буде займати в пам'яті: (10 – 5+1)*2 = 12 байтів.

Зсув до елементу вектора з номером 8 становить (8 – 5)*2 = 6 байтів.

Адреса елементу з номером 8 буде: @ MAS + 6.

При доступі до вектора задається ім'я вектора і номер елементу вектора. Таким чином, адреса і-го елементу може бути обчислена як:

@Ім'я[і] = @Ім'я + і*Sіzeof(тип) – n*Sіzeof(тип).

Це обчислення не може бути виконане на етапі компіляції, тому що значення змінної у цей час ще невідомо. Отже, обчислення адреси елементу повинно виконуватися на етапі виконання програми при кожному звертанні до елементу вектора. Але для цього на етапі виконання, по-перше, повинні бути відомі: @Ім'я, Sіzeof(тип), n, а по-друге, при кожному звертанні повинні виконуватися дві операції множення і дві – додавання. Перетворивши формулу, одержимо:

@Ім'я[і] = A0 + і*Sіzeof(тип),

де A0 = @Ім'я – n*Sіzeof(тип).

Таким чином, скорочується число збережених параметрів до двох, а число операцій – до одного множення й одного додавання, тому що значення A0 може бути обчислене на етапі компіляції і збережено разом з Sіzeof(тип) у дескрипторі вектора. Звичайно в дескрипторі вектора зберігаються і граничні значення індексів. При кожному звертанні до елементу вектора задане значення порівнюється з граничними і програма аварійно завершується, якщо заданий індекс виходить за припустимі межі.

Таким чином, інформація, що міститься в дескрипторі вектора, дозволяє, по-перше, скоротити час доступу, а по-друге, забезпечує перевірку правильності звертання. Але за ці переваги доводиться платити, по-перше, швидкодією, тому що звертання до дескриптора – це команди, по-друге, пам'яттю як для розміщення самого дескриптора, так і для команд, з ним працюючих.

Чи можна обійтися без дескриптора вектора? У мові C, наприклад, дескриптор вектора відсутній, точніше, він не зберігається на етапі виконання. Індексація масивів у C обов'язково починається з нуля. Компілятор кожне звертання до елементу масиву заміняє на послідовність команд, що реалізує окремий випадок формули при n = 0:

@Ім'я[і] = @Ім'я + і*Sіzeof(тип).

Але по-перше, обмеження у виборі початкового індексу саме по собі може бути незручністю для програміста, по-друге, відсутність граничних значень індексів робить неможливим контроль виходу за межі масиву. Програмісти, які працюють з C, добре знають, що саме такі помилки часто є причиною "зависання" C-програми при її налагодженні.