ПЛАН

РЕГУЛЯРНІ ТИПИ ДАНИХ 1

Поняття масиву 1

Конструктори і селектори 2

Оголошення масиву 3

Операції з масивами 5

Регулярні типи даних Поняття масиву

В навколишньому світі тільки невелика кількість об'єктів може бути описана за допомогою однієї характеристики, тобто відображатися даними простого типу. Нагадаємо, що характерною ознакою простих типів даних є їх атомарність, а саме, наявність тільки одного елементу даних як значення змінної або константи відповідного типу.

Структуровані ж типи даних характеризуються множиною елементів (компонентів), з яких складаються дані таких типів. При цьому кожна компонента структури може бути як окремим елементом даним, так і у свою чергу значенням будь-якого із структурованих типів.

Однією із найпростіших і найбільш широко уживаних в комп'ютерних програмах структур даних є регулярна структура (масив), призначена для представлення однорідних інформаційних об’єктів. Необхідність в масивах виникає всякий раз, коли при вирішенні задачі доводиться мати справу з великою, але кінцевою кількістю однотипних впорядкованих даних, наприклад, результатами багаторазових вимірів температури повітря протягом року, вибіркою результатів експериментів і т.ін.

Масив - це структура даних, що являє собою впорядкований набір фіксованої кількості однотипних компонент довільної структури. Тип компонентів масиву, який ще називають базовим типом масиву, в кінцевому рахунку повинен бути простим.

Масив визначається ім'ям, що є єдиним для всіх його елементів, і розмірністю - кількістю координат (індексів), необхідних для визначення місцезнаходження потрібного елемента в масиві.

Оскільки структура компонентів масиву може бути довільною, то він може мати компоненти структурованого типу, зокрема, масиви. Такий масив можна трактувати подвійно: як масив, що складається з декількох масивів, або як один двовимірний масив (матрицю). Кожна чергова вкладеність масивів збільшує розмірність масиву. Більшість мов програмування, зокрема, Pascal, при цьому не накладає обмежень на рівень вкладеності: теоретично масиви можуть бути n–вимірними. Практично ж розмірність масиву обмежується обсягом сегменту даних. Тому об’єм оперативної пам’яті для розміщення масивів потрібно розраховувати заздалегідь і встановлювати його на розумному рівні.

При вирішенні реальних задач, як правило, використовують:

- одновимірні масиви (вектора)

- двовимірні масиви (матриці)

- тривимірні масиви

Масиви більшої розмірності на практиці зустрічаються рідко.

Характерною особливістю масивів є прямий (випадковий) доступ до їх елементів: всі компоненти масиву можуть вибиратися довільно і однаково доступні. Для позначення окремої компоненти в цьому випадку потрібно, окрім імені, вказати її порядковий номер в структурі – індекс (або декілька індексів).

В пам’яті ЕОМ масив займає зв’язну область пам'яті і зберігається як безперервна послідовність елементів. При цьому першим змінюється (зростає) самий правий його індекс. Наприклад, елементи масиву розмірності 5х5 будуть розміщені в оперативній пам’яті у такий спосіб:

A(1,1), ..., A(1,5), A(2,1), ..., A(2,5), ..., A(5,1), ..., A(5,5).

Це потрібно враховувати при обробці масивів.

Таким чином, у будь-якій мові програмування масив характеризується:

• спільним ім’ям для всіх елементів масиву;

• розмірністю;

• прямим доступом до елементів масиву;

• збереженням вмісту масиву в безперервній області пам'яті.

Кардинальне число (потужність) структурованого типу даних визначається як добуток кардинальних чисел усіх його компонентів. Для масиву кардинальне число обчислюється так:

(card(T₀))ⁿ, де n=card(I)

Тут I - тип індексів (I =1, 2, ..., n), Т₀ - тип компонент.

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