МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
|||||||
Поняття структури даних
Структура даних (СД) - загальна властивість інформаційного об'єкта, з яким взаємодіє та або інша програма. Ця загальна властивість характеризується: ü множиною допустимих значень цієї структури; ü набором допустимих операцій; ü характером організованості. Найпростіші структури дацих називаються також типами даних. У програмуванні та комп'ютерних науках структури даних—це способи організації даних у комп'ютерах. Часто разом зі структурою даних пов'язується і специфічний перелік операцій, які можуть бути виконаними над даними, організованими в таку структуру. Правильний підбір структур даних є надзвичайно важливим для ефективного функціонування відповідних алгоритмів їх опрацювання. Добре побудовані структури даних дозволяють оптимізувати використання машинного часу та пам'яті комп'ютера для виконання найбільш критичних операцій. Відома формула ≪Програма = Алгоритми + Структури даних≫ дуже точно виражає необхідність відповідального ставлення до такого підбору. Тому іноді навіть не обраний алгоритм для опрацювання масиву даних визначає вибір тієї чи іншої структури даних для їх збереження, а навпаки.
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
Тема: Поняття та подання графу
Ціль: розглянути визначення графу та охарактеризувати його основні властивості, способи подання графу та варіанти реалізації операцій над ним
Читайте також:
|
||||||||
|