Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



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

 

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

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

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

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

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

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

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

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

 

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

 

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

 

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

 


Читайте також:

  1. II. Поняття соціального процесу.
  2. III. Процедура встановлення категорій об’єктам туристичної інфраструктури
  3. V. Поняття та ознаки (характеристики) злочинності
  4. А/. Поняття про судовий процес.
  5. Адаптивні організаційні структури управління.
  6. Адміністративний проступок: поняття, ознаки, види.
  7. Адміністративні провадження: поняття, класифікація, стадії
  8. Акти застосування юридичних норм: поняття, ознаки, види.
  9. Аналіз асортименту й структури випуску продукції.
  10. Аналіз динаміки і структури валового нагромадження.
  11. Аналіз динаміки і структури витрат підприємства
  12. Аналіз динаміки та структури банківських доходів




Переглядів: 7082

<== попередня сторінка | наступна сторінка ==>
Поняття структури даних | Поняття графу

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.02 сек.