Лекція 7:
Тема: Поняття про динамічні типи дних. Стек та черга. Метод FIFO і LIFQ
Мета лекції.
План:
Структури даних
Загальне поняття структури даних
Масив як базова структура
Реалізація одних структур на базі інших
Прості структури даних. Стік. Черга
Структури даних
"Алгоритми + структури даних = програми". Обидві складові в рівній мірі важливі. Не тільки недосконалий алгоритм, але і невдала організація роботи з даними може привести до уповільнення роботи програми в десятки, а іноді і в мільйони разів. З іншого боку, володіння теорією прорамування і уміння систематично застосовувати її на практиці дозволяє швидко розробляти ефективні і в той же час естетично красиві програми.
Загальне поняття структури даних
Структура даних — це виконавець, який організовує роботу з даними, включаючи їх зберігання, додавання і видалення, модифікацію, пошук і так далі Структура даних підтримує певний порядок доступу до них. Структуру даних можна розглядати як свого роду склад або бібліотеку. При описі структури даних потрібно перерахувати набір дій, які можливі для неї, і чітко описати результат кожної дії. Такі дії - розпорядженнями. З програмної точки зору, системі розпоряджень структури даних відповідає набір функцій, які працюють над загальними змінними.
Структура даних реалізується на основі більш простій базової структури, раніше вже реалізованою, або на основі масиву і набору простих змінних. Опис структури даних з логічної точки зору розрізняється з описом її реалізації. Різних реалізацій може бути багато, з логічної ж точки зору (тобто з погляду зовнішнього користувача) всі вони еквівалентні і розрізняються, можливо, лише швидкістю виконання розпоряджень.
Масив як базова структура
Оперативна пам'ять з погляду програміста — це масив елементів. Будь-який елемент масиву можна прочитати або записати відразу, за одну елементарну дію. Масив можна розглядати як просту структуру даних. Структури даних, в яких можливий безпосередній доступ до довільних їх елементів, називають структурами даних з прямим, або з довільним доступом (по-англійськи random access). Разом з масивом, структурою даних з прямим доступом є множина, яка буде розглянуто нижче. У інших структурах даних безпосередній доступ можливий лише до одному або декількох елементів, для доступу до решти елементів треба виконати додаткові дії. Такі структури даних називаються структурами послідовного доступу. Прикладом структури послідовного доступу є магнітофон, на яким записані пісні. У будь-який момент можна прослуховувати лише чергову пісню. Щоб дістатися до інших музичних фрагментів, треба перемотати стрічку вперед або назад. До речі, такі магнітофони, або накопичувачі на магнітній стрічці, дуже довго використовувалися на ЕОМ, хоча зараз поступилися своїм місцем надійнішим і компактнішим системам (знімним магнітним і оптичним дискам, флэш-памяти і тому подібне). Пристрій комп'ютерного магнітофона був аналогічно пристрою звичайного побутового магнітофона.
З логічної точки зору, масивом є також найважливіша складова комп'ютера — магнітний диск. Елементарною одиницею читання і запису для магнітного диска служить блок. Розмір блоку залежить від конструкції конкретного диска, зазвичай він кратний 512. За одну елементарну операцію можна прочитати або записати один блок із заданою адресою.
Отже, найбільш важливі пристрої комп'ютера, що запам'ятовують, — оперативна пам'ять і магнітний диск — є масиви. Робота з елементами масиву здійснюється виключно швидко, всі елементи масиву доступні без всяких попередніх дій.
Є і інші причини, по яких необхідно використовувати складніші, ніж масиви, структури даних. Логіка багатьох завдань вимагає організації певного порядку доступу до даним. Наприклад, у разі черги елементи можна додавати тільки в кінець, а забирати тільки з початку черги; у стеку доступні лише елементи у вершині стека, в списку — елементи до і за покажчиком.
Нарешті, масив має обмежений розмір. Збільшення розміру масиву у разі потреби приводить до переписування його вмісту в захоплену область пам'яті більшого розміру, тобто знову ж таки до масової операції. Від цього недоліку вільні посилальні реалізації структур даних: реалізації на основі лінійних списків або на основі дерев.