ПЛАН
РЕГУЛЯРНІ ТИПИ ДАНИХ 1
Масиви як структури даних 1
Поняття масиву 1
Оголошення масиву 3
Обробка масивів 5
Операції з масивами 7
Базові операції обробки одновимірних масивів 7
Регулярні типи даних Масиви як структури даних Поняття масиву
Тільки невелика кількість об'єктів навколишнього світу може бути описана за допомогою однієї характеристики, тобто відображатися даними простого типу. Нагадаємо, що характерною ознакою простих типів даних є їх атомарність, а саме, наявність тільки одного елементу даних як значення змінної або константи відповідного типу. Структуровані або складені типи даних характеризуються множиною елементів (компонентів), з яких складаються дані таких типів. При цьому кожна компонента структури може бути як окремим елементом даним, так і у свою чергу значенням будь-якого із структурованих типів. Структуровані типи задають певний спосіб організаціїданих.
Однією із найпростішихі найбільш широкоуживаних в програмах структур даних є регулярна структура (масив), призначена для представлення одноріднихінформаційних об’єктів. Необхідність в масивах виникає усякий раз, коли при вирішенні задачі доводиться мати справу з великою, але кінцевою кількістю однотипних упорядкованих даних, наприклад, результатами багаторазових вимірів температури повітря протягом року, вибіркою результатів експериментів і т.ін.
Масив - це структура даних, що являє собою впорядкований набір фіксованої кількості однотипних компонент довільної структури. Тип компонентів масиву, який ще називають базовим типом масиву, в кінцевому рахунку повинен бути простим.
Порядок розташування елементів масиву визначається набором значень індексного типу, а самі ці значення називаються індексами. Кожному елементу масиву відповідає певний індекс.
Оскільки структура компонентів масиву може бути довільною, то вінможематикомпоненти структурованого типу, зокрема, масиви. Такий масив можна трактувати подвійно: як масив, що складається з декількох масивів, або як один двовимірний масив (матрицю). Кожна чергова вкладеність масивів збільшує розмірність масиву.
Слід зазначити, що у С/C++ «класичних» багатовимірних масивів немає. Тут введені одновимірні масиви і масиви масивів. Останні є більш загальною структурою даних і дозволяють задати не тільки багатовимірний куб, а порізану, ступінчасту структуру. Проте використання масиву масивів менш зручне.
Більшість мов програмування не накладає обмежень на рівень вкладеності: теоретично масиви можуть бути 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 - тип індексів (і = 1, 2, ..., n), Т0 - тип компонент.
Визначення кардинального числа складеного типа використовується при розподілі пам'яті під відповідні змінні, а з позицій користувача воно необхідне для оцінки ємкісної складності алгоритмів.