Списки, стеки, очереди в C++

ЗМІСТ

Вступ

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

1.1 Списки

1.2 Стеки

1.3 Черги

Розділ ІІ. Практична реалізація динамічних структур на мові програмування С++

2.1 Робота з динамічною пам'яттю

2.1.1 Вказівники

2.1.2 Операції NEW та DELETE

2.2 Стеки

2.3 Черги

Розділ ІІІ. Побудова динамічних структур використовуючи стандартні шаблони

3.1 Використання бібліотеки Stack

3.2 Використання бібліотеки Queue

Висновок

Література

Вступ

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

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

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

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

У найпростішій формі таблиця може бути лінійним списком елементів. Тоді властиві їй структурні властивості містять у собі відповіді на такі питання, як: "Який елемент є першим у списку? який - останнім? який елемент передує даному або слідує за даним?" Можна багато говорити про структуру навіть у цьому зовсім очевидному випадку.

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

Системи обробки списків корисні в дуже багатьох випадках, однак при їхньому використанні програміст нерідко зіштовхується із зайвими обмеженнями.

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

Одними із видів списків є стеки і черги, що відмінні між собою лише в деякому логічному представленні і дещо різні за створенням.

Динамічні структури даних можна побудувати на багатьох мовах програмування як високого так і низького рівня. Проте, будувати динамічні структури найкраще на мові програмування фірми Borland - С++.

С++ побудована на основі мови С. Вона зберігає основні типи даних, операції, синтаксис операторів та структуру програми мови С ( про це свідчить сама назва мови: “C” та “++”). Водночас, це зовсім інша мова, яка ввела в практику програмування новий технологічний підхід - об'єктно-орієнтоване програмування. Введення в практику програмування об'єктно-орієнтованої парадигми дозволяє значно підвищити рівень технології створення програмних засобів, скоротити затрати на розробку програм, їх повторне використання, розширити інтелектуальні можливості ЕОМ. Розробка мови С++ - віха в становленні об'єктно-орієнтованого підходу як практично універсальної бази в інформаційній індустрії.

Метою роботи є: Знайомство з теоретичним положенням, що стосуються інформаційних структур і розробка та реалізація динамічних структур типу черга, стек на мові програмування С++.

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

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

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

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

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

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

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

Список (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), якщо видаляється верхній елемент. Ця термінологія бере свій початок від "стеків" закусок (американська страва), які можна зустріти в кафетеріях, або за аналогією з колодами карт. Стислість слів "опустити" і "підняти" має свою перевагу, але ці терміни помилково припускають рух усього списку в пам'яті машини. Фізично, однак, нічого не опускаються; елементи просто додаються зверху. У відношенні до черг ми говоримо про початок і кінець черги; об'єкти встають у кінець черги й виходять в момент, коли нарешті досягають її початку. Говорячи про деки, ми вказуємо лівий і правий кінці. Не існує, однак, яких-небудь стандартних правил щодо того, де повинен бути верх, початок і кінець: ліворуч або праворуч. Таким чином, ми маємо, що в наших алгоритмах застосована багата розмаїтість описових слів: "зверху -- униз" -- для стеків, "ліворуч -- праворуч" -- для деків і "очікування в черзі" -- для черг.

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

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

На малюнку нижче видно як додається й видаляється елемент із двонаправленого списку. При додаванні нового елемента (позначений N) між елементами 2 і 3. Зв'язок від 3 іде до N, а від N до 4, а зв'язок між 3 і 4 видаляється.

В односпрямованому списку структура додавання й видалення така ж тільки зв'язок між елементами однобічна.

1.2 Стеки

Стек (stack) -- лінійний список, у якому всі видалення й доповнення (і звичайно всякий доступ) робляться з одного кінця списку.

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

Стек у вигляді списку (pushdown list) - стек, організований таким чином, що останній елемент, що вводить в область пам'яті, розміщується на вершині списку.

З стека ми завжди виключаємо "молодший" елемент із наявних у списку, тобто той, котрий був включений пізніше інших. Для черги справедливо в точності протилежне правило: видаляється завжди "старший" елемент; вузли залишають список у тім порядку, у якому вони в нього ввійшли.

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

У стеці елемент додаються й віддаляються тільки з одного кінця. На малюнку це елемент N. Тобто якщо він додався, то видалятися може спочатку тільки він, а вже потім всі інші.

Для стеку характерні такі властивості:

· елементи додаються у вершину (голову) стеку;

· елементи видаляються з вершини (голови) стеку;

· покажчик в останньому елементі стеку дорівнює NULL;

· неможливо вилучити елементи стеку, не вилучивши всі елементи, що йдуть попереду.

Страницы: 1, 2, 3, 4