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

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

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

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

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

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

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

Оскільки структура компонентів масиву може бути довільною, то він може мати компоненти структурованого типу, зокрема, масиви. Такий масив можна трактувати подвійно: як масив, що складається з декількох масивів, або як один двовимірний масив (матрицю). Кожна чергова вкладеність масивів збільшує розмірність масиву. Більшість мов програмування, зокрема, 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), Т₀ - тип компонент.

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

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

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

Якщо, наприклад, існує опис змінної w регулярного типу, то складене значення w з компонентами w₁..., w_n задається за допомогою конструктора. При цьому конструктор розподіляє пам'ять під змінну-вектор w і дозволяє надалі сприймати її як єдине ціле.

Для розподілу пам'яті під масив конструктор пов'язує з ім'ям відповідної змінної деяку адресу w_o і резервує необхідну для розміщення всіх компонент кількість комірок пам'яті з урахуванням розмірності компонент. Розміщення структури регулярного типу в пам'яті ЕОМ ілюструється рис.1.

Рис.3.1. Розміщення вектора w в пам’яті ЕОМ.

Операція, яка дозволяє звертатися до окремих компонентів вектора, це - селектор. Дана операція задає правило обчислення номера потрібної компоненти. Наприклад, при звертанні w [ i ] селектор обчислює адресу цієї компоненти за допомогою складання з w _o значення індексу i, забезпечуючи тим самим прямий доступ до самої компоненти.

Як індекси при звертанні до елементів масивів можуть використовуватися довільні вирази, що включають константи і змінні допустимих порядкових типів. Наприклад,

A [3,1], С[2,k], Mas [i + 2, j].

¨¨¨ У більшості мов програмування використовується числовий принцип нумерації елементів масиву, причому, в одних мовах програмування нумерація може починатись з 0, а в інших — з 1.

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

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

- розмірність масиву,

- базовий тип елементів,

- "спосіб" нумерування елементів (не у всіх мовах програмування).

Так БНФ-нотація задання масиву у мові Pascal має вигляд:

оголошення масиву::= array “ [“тип індекса {, тип індекса} “]” of базовий тип

тип індекса::= допустимий порядковий тип,

допустимий порядковий тип::= char | boolean | перелічувальний тип | допустимий цілочисельний тип | допустимий обмежений тип

допустимий цілочисельний тип::= byte | word | integer | shortint

допустимий обмежений тип::= обмежений тип на базі byte | обмежений тип на базі word | обмежений тип на базі integer | обмежений тип на базі shortint

Тип індексу опосередковано задає кількість елементів певної розмірності масиву (як кількість можливих значень цього типу) і "спосіб" їх нумерування (як відповідне значення типу індексу, а не порядковий номер елемента в масиві). Тому він може бути тільки порядкового типу (окрім типу longint і обмежених типів, побудованих на базі типу longint), оскільки інші різновиди скалярного типу не дозволять однозначно встановити кількість компонент масиву.

Такий спосіб задання типу індекса дає змогу наочно і зрозуміло інтерпретувати окремі елементи масиву. Наприклад,

Type

day = (mon, tues, wen, th, fri, sat, sun);

mas = array [1.. 20, 1..10] of real;

Var

workday: array [1.. 5] of day; { робочі дні тижня окремого працівника }

k_ill: array [day] of byte; { кількість захворілих протягом тижня }

kol: array [1950.. 1996] of longint; { кількість населення у визначені роки }

m: mas;

Із змінною workday пов'язаний опис масиву, тип індексів для якого задано відрізком типу 1..5, тобто вектор складається з 5-ти компонент. Тип компонент у свою чергу визначений як перелічувальний тип. У масива k_ill сім компонент, які індексуються значеннями, визначеними перелічувальним типом, а тип компонент - цілочисельний. Масив kol має 47 цілочисельних компонент. З ім'ям mas пов'язаний опис двовимірного масиву (матриці) дійсних чисел розмірності 20х10.

При оголошенні масиву можна використовувати попередньо визначеніконстанти. Наприклад,

Const

min = 1984; max = 1995;

Var

mas: array [min.. max] of integer.

У загальному випадку індекси багатовимірних масивів не обов'язково повинні мати однаковий тип. Наприклад, структура, що містить інформацію про чисельність населення окремої соціальної групи в декількох містах за певний період часу:

Type

town = (Moscow, Kiev, Minsk);

group = (worker, office_worker, peasant);

Var

kol: array (town, group, 1960..2011) of longint.

Тут має місце тривимірний масив, причому кожна з його розмірностей визначається своїм типом.

Формат оголошення масиву у С:

тип ім'я [кількість];

Наприклад,

int a[3];

double b[10];

int a[2][3]; - a[0][0] a[0][1] a[0][2] a[1][0] a[1][1] a[1][2]

Формат визначення у С:

тип ім’я[кількість]={список значень};

Наприклад,

char c[3] = {'a', 'k', 'c'};

float b[5] = {5.7, 0.4, 3.9, 2.7, 1.8};

int d[2][3] = {{3, 5, 7}, {4, 3, 1}};

Особливості визначення:

1) кількість елементів масиву при оголошенні може бути опущена (визначається кількістю елементів в списку початкових значень), наприклад,

char a[] = {'a', 'b', 'c'};

int m[][2] = {3, 5, 7, 1};

2) якщо початкових значень менше, ніж елементів в масиві, всі інші елементи автоматично ініціалізуються 0, наприклад,

int d[10] = {5, 8, 19, 34}; ® 5, 8, 19, 34, 0, 0, 0, 0, 0, 0

int m[3][2] = {3, 5, 7} ® 3 5

7 0

0 0

int m[2][3] = {{3}, {5, 7}}; ® 3 0 0

5 7 0

3) Для недопущення подальшої зміни значень елементів масиву треба визначити його з ключовим словом const, наприклад,

const int m[] = {3, 5, 7, 1};

БНФ-нотація звертання до елемента масиву має вид:

елемент масиву::= ім’я масиву”[“ індекс {, індекс}”]”

індекс::= константа | змінна | вираз.

Відповідний формат:

ім’я масиву [індекс_1, індекс_2, …, індекс_n]

Наприклад, A [3,1], С[2,10, 4].

Доступ до елементів масиву у С здійснюється:

- за індексом (індексація елементів масиву є стандартною і починається з 0);

- за покажчиком (ім’я масиву – покажчик на його перший елемент), наприклад,

int m[3][2];

int *p;

p = &m[0][0];

p++; - перехід до наступного елемента.

Поиск по сайту: