Найбільш важливими з найпростіших структур даних є стек та черга. Ці структури зустрічаються в програмуванні на кожному кроці, у найрізноманітніших ситуаціях.
Мета роботи
Вивчення можливостей мови С++ при роботі з масивами та записами. Отримання практичних навичок використання можливостей роботи з масивами та записами при вирішенні практичних завдань.
5.2 Організація самостійної роботи студентів
Під час підготовки до виконання лабораторної роботи необхідно вивчити індивідуальне завдання (п. 5.3), виконати розробку алгоритму вирішення задачі та підготовити текст програми щодо реалізації розробленого алгоритму, підготовити відповідні розділи звіту та вивчити відповідний теоретичний матеріал, який викладено у лекціях: „Технологія роботи із масивами та записами у С++”, „Символьні та логічні змінні і вирази. Масиви та текстові строки”, та у наступних підручниках і навчальних посібниках [1, 4, 5, 7, 8].
Структура даних — це виконавець, що організує роботу з даними, включаючи їхнє зберігання, додавання та вилучення, модифікацію, пошук та інше. Структура даних підтримує певний порядок доступу до них. Структуру даних можна розглядати як свого роду склад або бібліотеку. При описі структури даних потрібно перелічити набір дій, які можливі для неї, та чітко описати результат кожної дії. Такі дії називаються приписами. Із програмної точки зору, системі приписів структури даних відповідає набір функцій, які працюють над загальними змінними.
Структура даних реалізується на основі більше простої, яка раніше вже була реалізована, або на основі масиву та набору простих змінних. Необхідно чітко розрізняти опис структури даних з логічної точки зору та опис її реалізації. Різних реалізацій може бути багато, з логічної ж точки зору (тобто з погляду зовнішнього користувача) всі вони еквівалентні та розрізняються, можливо, лише швидкістю виконання приписів.
Оперативна пам'ять із погляду програміста — це масив елементів. Будь-який елемент масиву можна прочитати або записати відразу, за одну елементарну дію. Масив можна розглядати як найпростішу структуру даних. Структури даних, у яких можливий безпосередній доступ до їхніх елементів, називають структурами даних із прямим, або з довільним доступом (по-англійському random access). Поряд з масивом, структурою даних із прямим доступом є множина. В інших структурах даних безпосередній доступ можливий лише до одному або декількох елементам, для доступу до інших елементів треба виконати додаткові дії. Такі структури даних називаються структурами послідовного доступу. Прикладом структури послідовного доступу є магнітофон, на яких записані пісні. У будь-який момент можна прослухати лише чергову пісню. Щоб добратися до інших музичних фрагментів, треба перемотати стрічку вперед або назад.
З логічної точки зору, масивом є найважливіша складова комп'ютера – магнітний диск. Елементарною одиницею зчитування та запису для магнітного диска є блок. Розмір блоку залежить від конструкції конкретного диска, звичайно він кратний 512. За одну елементарну операцію можна прочитати або записати один блок із заданою адресою.
Отже, найбільш важливі запам'ятовувальні пристрої комп'ютера – оперативна пам'ять та магнітний диск – представляють собою масиви. Робота з елементами масиву здійснюється винятково швидко, всі елементи масиву доступні без усяких попередніх дій. Але масивів недостатньо для написання ефективних програм. Наприклад, пошук елемента в масиві, якщо його елементи не впорядковані, неможливо реалізувати ефективно: не можна винайти нічого кращого, крім послідовного перебору елементів. У випадку впорядкованого зберігання елементів можна використовувати ефективний бінарний пошук, але ускладнення виникають при додаванні або вилученні елементів у середині масиву, що призводять до масових операцій, тобто операціям, час виконання яких залежить від числа елементів структури. Від цих недоліків вдається позбутися, реалізуючи множину елементів на базі збалансованих дерев або хеш-функції.
Є й інші причини, відповідно до яких необхідно використовувати більше складні, ніж масиви, структури даних. Логіка багатьох задач вимагає організації певного порядку доступу до даних. Наприклад, у випадку черги елементи можна додавати тільки в кінець, а забирати тільки з початку черги; у стеку доступні лише елементи у вершині стека, у списку — елементи до та за покажчиком.
Нарешті, масив має обмежений розмір. Збільшення при необхідності розміру масиву призводить до переписування його вмісту в захоплену область пам'яті більшого розміру, тобто знову ж до масової операції. Від цього недоліку вільні посилальні реалізації структур даних: реалізації на основі лінійних списків або на основі дерев.
Реалізація структури даних на основі базової структури — це опис її роботи в термінах базової структури. При цьому вважається, що базова структура або дана споконвічно, або вже кимсь реалізована. Реалізація повинна містити в собі опис ідеї реалізації (яким чином елементи реалізованої структури зберігаються в базовій структурі, які додаткові змінні використовуються) та набір підпрограм, кожна з яких моделює деякий припис реалізованої структури за допомогою приписів базової структури.
Найбільш важливими з найпростіших структур даних є стек та черга. Ці структури зустрічаються в програмуванні на кожному кроці, у найрізноманітніших ситуаціях.
Черга містить елементи, які розміщуються один за одним у ланцюжок (рис.5.1). Черга має початок і кінець. Додавати нові елементи можна тільки в кінець черги, забирати елементи можна тільки з початку. Із середини черги видаляти елементи не можна.
Черга можна представити у вигляді трубки. В один кінець трубки можна додавати кульки – елементи черги, з іншого кінця вони вибираються. Елементи в середині черги, тобто кульки усередині трубки, недоступні. Кінець трубки, у який додаються кульки, відповідає кінцю черги, кінець, з якого вони витягають – початку черги. Таким чином, кінці трубки не симетричні, кульки усередині трубки рухаються тільки в одному напрямку.
Рисунок 5.1 – Логічне представлення черги
У принципі, можна було б дозволити додавати елементи в обидва кінці черги та забирати їх також з обох кінців. Така структура даних у програмуванні теж існує, її назву – "дек", від англ. Double Ended Queue, тобто черга із двома кінцями. Дек застосовується значно рідше, ніж черга.
Черга практично завжди пов'язана з обслуговуванням запитів, у тих випадках, коли вони не можуть бути виконані миттєво. Черга підтримує також порядок обслуговування запитів.
Стек – найбільш популярна та, навіть, найважливіша структура даних у програмуванні. Стек – це запам'ятовуючий пристрій, з якого елементи вибираються у порядку, зворотному їхньому додаванню. Це так би мовити – неправильна черга, у якій першим обслуговують того, хто встав до неї останнім. У програмістській літературі загальноприйнятими є абревіатури, що позначають дисципліну роботи черги та стека. Дисципліна роботи черги позначається FIFO, що означає першим прийшов – першим будеш обслужений (First In First Out). Дисципліна роботи стека позначається LIFO, останнім прийшов – першим будеш обслужений (Last In First Out).
Стек можна представити у вигляді трубки з підпруженим дном, яка розміщена вертикально. Верхній кінець трубки відкритий, до нього можна додавати, або, як говорять, заштовхувати елементи (push). При вибиранні елементів зі стека вони як би виштовхуються нагору (pop).
| Рисунок 5.2 – Логічне представлення стека |
Прикладом стека може служити стіг сіна, стопка паперів на столі, стопка тарілок та інше.
У програмуванні досить часто розглядають структуру більше складну, ніж проста множина: навантажена множина. Нехай кожний елемент множини втримується в ньому разом з додатковою інформацією, що називають навантаженням елемента. При додаванні елемента до множини необхідно також вказувати навантаження, що він несе. Такі структури називають Відображенням (Map) або Словником (Dictionary). Дійсно, елементи множини як би відображаються на навантаження, що вони несуть (відмітимо, що в математиці поняття функції або відображення визначається строго як множина пар; першим елементом кожної пари є конкретне значення аргументу функції, другим – значення, на яке функція відображає аргумент). В інтерпретації Словника елемент множини – це іноземне слово, навантаження елемента – це переклад слова на відповідну мову (зрозуміло, переклад може включати кілька варіантів, але тут переклад розглядається як єдиний текст).
Підкреслимо, що всі елементи знаходяться в навантаженій множині в одному екземплярі, тобто різні елементи множини не можуть бути рівні один одному. На відміну від самих елементів, їхнє навантаження може збігатися (так, різні іноземні слова можуть мати однаковий переклад). Тому іноді елементи навантаженої множини називають ключами, їхнє навантаження — значеннями ключів. Кожний ключ унікальний. Прийнято говорити, що ключі відображаються на їхні значення.
Іще одним прикладом навантаженої множини є множина банківських рахунків. Банківський рахунок – це унікальний ідентифікатор, що складається з 20 десяткових цифр. Навантаження рахунку – це вся інформація, що йому відповідає, тобто ім'я, адреса власника рахунку, код валюти, сума остачі, інформація про останні транзакції та інше.
Найбільше часто застосовувана операція в навантаженій множині – це визначення навантаження для заданого елемента x (значення ключа x). Реалізація цієї операції включає пошук елемента x у множині, тому ефективність будь-якої реалізації множини визначається насамперед швидкістю пошуку.