ПЛАН
РЕГУЛЯРНІ ТИПИ ДАНИХ 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(T0))n, де n=card(I)
Тут I - тип індексів (I =1, 2, ..., n), Т0 - тип компонент.
Звідси витікає, що зміна значення однієї з компонент приводить до нового значення всієї змінної. Визначення кардинального числа складеного типа використовується при розподілі пам'яті під відповідні змінні, а з позицій користувача воно необхідне для оцінки ємкісної складності алгоритмів.