Предмет дослідження: Вивчення динамічних інформаційних структур.

Об'єкт дослідження: Побудова динамічних структур на С++ та використання їх на практиці.

Досягненням мети й відповідно до поставленої гіпотези визначаються наступні завдання:

1. Вивчити літературу по темі динамічні інформаційні структури, реалізація структур на С++;

2. Проаналізувати стеки, черги їх практичне застосування;

3. Створити на мові С++ динамічні структури: стеки, черги і показати всі можливі дії, які над ними можна проводити;

4. Розробити закінчений програмний продукт по темі дослідження.

Розділ І. Динамічні структури даних. Списки та їх різновиди

1.1 Списки

Список (list) – набір елементів, розташованих у певному порядку. Таким набором бути може ряд знаків у слові, слів у пропозицій у книзі. Цей термін може також ставитися до набору елементів на диску. Використання при обробці інформації списків як типи даних привело до появи в мовах програмування засобів обробки списків.

Список черговості (pushup list) – список, у якому останній вступник елемент додається до нижньої частини списку.

Список з використанням покажчиків (linked list) – список, у якому кожний елемент містить покажчик на наступний елемент списку.

Лінійний список (linear list) — це безліч, що складається з вузлів , структурні властивості якого по суті обмежуються лише лінійним (одномірним) відносним положенням вузлів, тобто тими умовами, що якщо , те є першим вузлом; якщо , те k-му вузлу передує й за ним треба ; є останнім вузлом.

Операції, які ми можемо право виконувати над лінійними списками, є наступними:

1. Одержати доступ до k-го вузла списку, щоб проаналізувати й/або змінити вміст його полів.

2. Включити новий вузол безпосередньо перед k-им вузлом.

3. Виключити k-й вузол.

4. Об'єднати два (або більше) лінійних списки в один список.

5. Розбити лінійний список на два (або більше) списки.

6. Зробити копію лінійного списку.

7. Визначити кількість вузлів у списку.

8. Виконати сортування вузлів списку в зростаючому порядку по деяких інформаційних полях у вузлах.

9. Знайти в списку вузол із заданим значенням у деякім полі.

Спеціальні випадки k=1 і k=n в операціях (1), (2) і (3) особливо виділяються, оскільки в лінійному списку простіше одержати доступ до першого й останнього елементів, ніж до довільного елемента.

У машинних додатках рідко потрібні всі дев'ять із перерахованих вище операцій у самому загальному виді. Ми побачимо, що є багато способів подання лінійних списків залежно від класу операцій, які необхідно виконувати найбільше часто. Очевидно, важко спроектувати єдиний метод подання лінійних списків, при якому всі ці операції виконуються ефективно; наприклад, порівняно важко ефективно реалізувати доступ до k-го вузла в довгому списку для довільного k, якщо в той же час ми включаємо й виключаємо елементи в середині списку. Отже, ми будемо розрізняти типи лінійних списків по головних операціях, які з ними виконуються.

Дуже часто зустрічаються лінійні списки, у яких вставка, видалення або доступ до значень майже завжди розпочинаються із першого або останнього вузла. Такі види списків мають спеціальні назви – стеки, черги, деки.

Важливість таких структур стала на стільки важливою, що вони отримали нові назви, подекуди навіть жартівливі: стек називали пуш-даун (push-down) списком, реверсивною пам'яттю, гніздовою пам'яттю, магазином, списком типу LIFO ("last-in-first-out" - "останнім входиш - першим виходиш") і навіть вживається такий термін, як список йо-йо! Чергу іноді називають - циклічною пам'яттю або списком типу FIFO ("first-in-first-out" - "першим входиш - першим виходиш"). Протягом багатьох років бухгалтери використали терміни LIFO і FIFO як назви методів при складанні прейскурантів. Ще один термін "архів" застосовувався до дек з обмеженим виходом, а деки з обмеженим входом називали "переліками", або "реєстрами". Така розмаїтість назв цікаво саме по собі, оскільки вони свідчить про важливість цих понять. Слова "стек" і "черга" поступово стають стандартними термінами; із всіх інших словосполучень, перерахованих вище, лише "пуш-даун список" залишається ще досить розповсюдженим, особливо в теорії ігрових автоматів.

При описі алгоритмів, що використають такі структури, прийнята спеціальна термінологія; так, ми поміщаємо елемент на верх стеку або видаляємо верхній елемент. У низу стека перебуває найменш доступний елемент, і він не видаляється доти, доки не будуть видалені всі інші елементи. Часто говорять, що елемент опускається (push down) у стек або що стек піднімається (pop up), якщо видаляється верхній елемент. Ця термінологія бере свій початок від "стеків" закусок (американська страва), які можна зустріти в кафетеріях, або за аналогією з колодами карт. Стислість слів "опустити" і "підняти" має свою перевагу, але ці терміни помилково припускають рух усього списку в пам'яті машини. Фізично, однак, нічого не опускаються; елементи просто додаються зверху. У відношенні до черг ми говоримо про початок і кінець черги; об'єкти встають у кінець черги й виходять в момент, коли нарешті досягають її початку. Говорячи про деки, ми вказуємо лівий і правий кінці. Не існує, однак, яких-небудь стандартних правил щодо того, де повинен бути верх, початок і кінець: ліворуч або праворуч. Таким чином, ми маємо, що в наших алгоритмах застосована багата розмаїтість описових слів: "зверху — униз" — для стеків, "ліворуч — праворуч" — для деків і "очікування в черзі" — для черг.

Однонаправлений і двонаправлений список – це лінійний список, у якому всі видалення й вставки відбуваються в будь-якому місці списку.

Однонаправлений список відрізняється від двонаправленного списку тільки зв'язком. Тобто в односпрямованому списку можна переміщатися тільки в одному напрямку (з початку в кінець), а двонаправленому - у кожному. З малюнка це видно: зверху однонаправлений список, а знизу двонаправлений.