Списки стеки очереди в C (стр. 1 из 5)

ЗМІСТ

Вступ

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

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. Розробити закінчений програмний продукт по темі дослідження.

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

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