Новини освіти і науки:

G+

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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