Поняття структури даних

Структура даних (СД) - загальна властивість інформаційного об'єкта, з яким взаємодіє та або інша програма. Ця загальна властивість характеризується:

ü множиною допустимих значень цієї структури;

ü набором допустимих операцій;

ü характером організованості.

Найпростіші структури дацих називаються також типами даних.

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

Правильний підбір структур даних є надзвичайно важливим для ефективного функціонування відповідних алгоритмів їх опрацювання. Добре побудовані структури даних дозволяють оптимізувати використання машинного часу та пам'яті комп'ютера для виконання найбільш критичних операцій.

Відома формула ≪Програма = Алгоритми + Структури даних≫ дуже точно виражає необхідність відповідального ставлення до такого підбору. Тому іноді навіть не обраний алгоритм для опрацювання масиву даних визначає вибір тієї чи іншої структури даних для їх збереження, а навпаки.

2 Рівні описування даних

Розрізняють наступні рівні описуваннявання даних:

• абстрактний (математичний) рівень;

• логічний рівень;

• фізичний рівень.

Логічний рівень (ЛСД) – подання структури даного на тій чи іншій мові програмування.

Фізичний рівень (ФСД) — відображення у пам'ять комп'ютера інформаційного об'єкту відповідно до логічного описування.

Оскільки пам'ять комп'ютера обмежена, то виникають питання розподілу пам'яті й керування нею.

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

Рисунок 4 – Зв'язок між логічним та фізичним рівнями подання СД.

Будь-яка структура на абстрактному рівні може бути подана у вигляді двійки <D,R>, де D - скінчена множина елементів, які можуть бути типами даних або структурами даних, a R - множина відношень, властивості якої визначають різні типи структур даних на абстрактному рівні.

3 Класифікація структур даних у програмах користувача й у пам'яті комп'ютера

Структури даних поділяються на вбудовані (реалізовані в мовах програмування) та похідні (утворюються користувачами). Класифікація СД у програмах користувача та пам'яті комп'ютера подана на рисунку 5.

Рисунок 5 – Класифікація СД.

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

4 Основні види складених типів даних

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

Перерахуємо складені типи даних та дамо їм коротку характеристику.

Множина – скінчена сукупність елементів, в якої R = Ø.

Послідовність — абстрактна структура, у якої множина R складається з одного відношення лінійного порядку (тобто для кожного елемента, крім першого і останнього, є попередній і наступний елементи).

Матриця – структура, в якої множина R складається із двох відношень лінійного порядку.

Дерево – множина R складається з одного відношення ієрархічного порядку.

Граф – множина R складається з одного відношення бінарного порядку.

Гіперграф – множина R складається із двох і більше відношень різного порядку.

Приклади СД подано на рисунку 6

Рисунок 6 – Приклади подання структур даних.

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

5 Структури даних у пам'яті комп'ютера

5.1 Структури даних в оперативній пам'яті

В оперативній пам'яті структури даних можна подати як на рисунку 7.

Рисунок 7 – Подання СД в оперативній пам’яті

Слід зазначити, що оперативна пам'ять є масивом. Слово - мінімальна кількість біт, яка може опрацьовуватися одночасно.

5.2 СД у зовнішній пам'яті

На рисунку 8 подано структури даних у зовнішній пам'яті.

Рисунок 8 – Подання СД у зовнішній пам’яті.

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

На мові Сі для послідовного зчитування з файла можна скористатися таким

фрагментом програми:

f=fopen("my.txt", "rt"); //відкрили послідовно для читання

for(i=0;i<k;i++)

{читаємо k елементів без перевірки правильності зчитування}

fscanf(f, "%d",&x);

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

Переваги: швидкість, простота.

Недоліки: відірваність процедур доступу від самих даних.

Прикладом прямого доступу є запис у файл fd змінної типу long, починаючи з 20-ої позиції:

#define SEEK_SET 0 // позиція на початку файла

Long а=0х1256;

fseek(fd, 20L, SEEK_SET);

fwrite (&a, sizeof(long),1,fd);

Індексно-послідовна модель передбачає, що для кожного опрацьованого елемента даних вводиться ідентифікатор даних - ключ. Звертання до елементів даних здійснюється через значення ключа. Прикладом такого ключа є номер елемента масиву.

Контрольні питання

1. Поняття структури даних. Рівні подання структур даних.

2. Рівні описування даних.

3. Основні види (типи) структур даних.

4. Класифікація структур даних у програмах користувача й у пам'яті комп'ютера.

5. Приклади структур даних.

6. Структури даних в оперативній пам'яті.

7. Структури даних у зовнішній пам'яті.

8. Порівняти різні схеми зберігання даних.

9. Навести приклади прямого доступу до даних.

Тести для закріплення матеріалу

1. Структури даних характеризуються:

а) множиною допустимих значень певної структури;

б) описом правил переходу від одного значення до іншого;

в) набором допустимих операцій;

г) набором помилок опрацювання даних;

д) характером організованості.

2. Перерахувати структурні типи даних:

а) дерево;

б) масив;

в) таблиця,

г) запис;

д) множина;

є) рекурсивний тип.

3. Перерахувати лінійні структури даних:

а) масив;

б) таблиця;

в) стек;

г) множина;

д) черга;

є) напрямлений граф.

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

а) множина;

б) матриця;

в) послідовність;

г) дерево;

д) граф.

5. Перерахувати схеми зберігання структур даних є зовнішній пам'яті:

а) подвійне слово;

б) напівслово;

в) фізичний блок;

г) прямого доступу;

д) послідовного доступу;

є) індексно-послідовного доступу.

6. Обрати тип даних, що відповідає визначенню: абстрактна структура, у якої множина R складається з одного відношення лінійного

порядку:

а) множина;

б) матриця;

в) послідовність;

г) дерево;

д) граф.

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

а) множина;

б) матриця;

в) послідовність;

г) дерево;

д) граф.

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

а) множина;

б) матриця;

в) послідовність;

г) дерево;

д) мультиграф.

9. Обрати можливі варіанти схеми зберігання даних:

а) прямий доступ;

б) обернений доступ;

в) індексний доступ;

г) паралельний доступ;

д) перпендикулярний доступ.

ЛЕКЦІЯ № 4

Тема: Поняття та подання графу

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

План