Списки стеки очереди в 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.1 Списки
Список (list) – набір елементів, розташованих у певному порядку. Таким набором бути може ряд знаків у слові, слів у пропозицій у книзі. Цей термін може також ставитися до набору елементів на диску. Використання при обробці інформації списків як типи даних привело до появи в мовах програмування засобів обробки списків.
Список черговості (pushup list) – список, у якому останній вступник елемент додається до нижньої частини списку.
Список з використанням покажчиків (linked list) – список, у якому кожний елемент містить покажчик на наступний елемент списку.
Лінійний список (linear list) — це безліч, що складається з />вузлів />, структурні властивості якого по суті обмежуються лише лінійним (одномірним) відносним положенням вузлів, тобто тими умовами, що якщо />, те />є першим вузлом; якщо />, те k-му вузлу />передує />й за ним треба />; />є останнім вузлом.
Операції, які ми можемо право виконувати над лінійними списками, є наступними:
1. Одержати доступ до k-го вузла списку, щоб проаналізувати й/або змінити вміст його полів.
2. Включити новий вузол безпосередньо перед k-им вузлом.
3. Виключити k-й вузол.
4. Об'єднати два (або більше) лінійних списки в один список.
5. Розбити лінійний список на два (або більше) списки.
6. Зробити копію лінійного списку.
7. Визначити кількість вузлів у списку.
8. Виконати сортування вузлів списку в зростаючому порядку по деяких інформаційних полях у вузлах.--PAGE_BREAK--
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.3 Черги
Черга (queue)—лінійний список, у якому всі видалення відбуваються на одному кінці списку, а всі включення (і звичайно всякий доступ) робляться на іншому його кінці.
Черга— тип даних, при якому нові дані розташовуються слідом за існуючими в порядку надходження; першими дані, що надійшли, при цьому обробляються першими.
Удеяких розділах математики слово «чергу» використовують у більше широкому змісті, позначаючи будь-який сорт списку, у якому наявні видалення й додавання; зазначені вище спеціальні випадки називаються тоді «чергами з різними дисциплінами». Однак тут термін «черга» використовується у більш вузькому змісті, аналогічному впорядкованим чергам людей, що очікують обслуговування.     продолжение
--PAGE_BREAK--
Правило тут таке ж, як у живій черзі: першим прийшов — першим тебе і обслужений. Прийшов новий покупець, встав (добавився) у кінець черги, а який уже зробив покупки пішов (вийшов) з початку черги. Тобто першим прийшов, першим пішов.
Інакше кажучи, у черги єголова(head) іхвіст(tail). Елемент, що додається в чергу, виявляється в її хвості.
Учерзі новий елемент додається тільки з одного кінця. Видалення елемента відбувається на іншому кінці. Черга, це по суті однонаправлений список, тільки додавання й видалення елементів відбувається на кінцях списку.
Черга характеризується такими властивостями:
елементи додаються в кінець черги;
елементи зчитуються та видаляються з початку (вершини) черги;
покажчик в останньому елементі черги дорівнює NULL;
неможливо отримати елемент із середини черги, не вилучивши все елементи що ідуть попереду.
Наведемо приклади застосування черг в обчислювальній техніці. У мережній операційній системі процесор сервера обслуговує в певний момент часу тільки одного користувача. Запити інших користувачів записуються до черги. Під час обслуговування користувачів кожен запит просувається до початку черги. Перший в черзі запит підлягає «першочерговому» обслуговуванню. У комп’ютерній мережі за чергою обслуговуються інформаційні пакети. Черги застосовуються також для буферизації потоків даних, що виводяться на друк, якщо в комп’ютерній мережі використовується один принтер.
Крім цих структур існують і інші, наприклад деки, двонаправленні списки, кільцеві списки і т.і.
На малюнку вище графічно зображено дек(deck) (стек із двома кінцями)— лінійний список, у якому всі додавання й видалення (і звичайно всякий доступ) робляться на обох кінцях списку.
Дек по суті двонаправлений список.
У зв'язаному списку(linked list)елементи лінійно впорядковані, але порядок визначається не номерами, як у масиві, а покажчиками, що входять до складу елементів списку. Списки є зручним способом зберігання динамічних даних, що дозволяють реалізувати всі операції, (хоча й не завжди ефективно).
Інакше кажучи, елементдвостороннє зв'язаного списку(doubly linked list) — це запис, що містить три поля: key(ключ) і два покажчики — next(наступний) і prev(від previous-попередній). Крім цього, елементи списку можуть містити додаткові дані. Якщо х—елемент списку, то next вказує на наступний елемент списку, а prev— на попередній. Якщо prev{х}=nil,то в елемента хнемає попереднього: цеголова (head) списку. Якщо next{х}= nil,то х— останній елемент списку або, як говорять, йогохвіст (tail). Ці дані є неявно загальноприйнятими в програмуванні.
Звичайно, динамічні структури даних не обмежуються наведеними вище. Існують і інші, зокрема графи, дерева що займають свою окрему нішу у програмуванні і почасти вирішення певних питань не можливе без їх застосування.
Розділ ІІ. Практична реалізація динамічних структур на мові програмування С++
2.1 Робота з динамічною пам’яттю
2.1.1 Вказівники
Робота із динамічними структурами у С++ передбачає безпосередню роботу із посиланнями і вказівниками. Розглянемо детально як же їх створювати і які операції можна над ними проводити.
Змінні-вказівники містять в якості своїх значень адреси пам’яті. Зазвичай змінна містить деяке значення. З іншої сторони, вказівники містять адрес змінної, яка містить деяке значення. В цьому смислі ім’я змінної відсилається до значення прямо, а вказівник – побічно. Перехід на значення через вказівник називається побічною адресацією.
Вказівники, подібно до будь-яких інших змінних, перед своїм використанням повинні бути оголошені. Оголошення
int*countP;
оголошує перемінну countPтипу int* (тобто вказівник за ціле число). Символ * в оголошенні вказує що йде оголошення вказівника. Вказівники можна оголошувати, що вказувати на об’єкти довільного типу.
Вказівники повинні бути ініціалізовані або при своєму оголошенні, або в операторі присвоєння. Вказівник можу бути ініціалізований значенням 0, NULLабо адресом. Вказівник із значенням 0 або NULLні на що не вказує.
Для вказівників характерні ряд операцій, так поряд із ними використовується операція адресації або ж &, — унарна операція, що повертає адрес свого операнда. Наприклад, якщо маємо оголошення
inty=5;
int*yP;
то операнд
yP-&y;
присвоює адрес змінної у вказівнику уР. Кажуть, що змінна уР «вказує» на у.
Операція *, зазвичай називається операцією побічною адресацією або операцією розіменування, повертає значення об’єкта, на який вказує її операдн (тобто вказівник). Наприклад, оператор
cout
виводить значення змінної у. Використання * вказаним способом називається розіменуванням вказівника. Варто відзначити, що розіменування вказівника можливе також в лівій частині оператора присвоєння, наприклад,
*уР=9;
де 9 присвоюється у. Розіменований вказівник може також використовуватися для отримання вхідної величини, наприклад,
cin
Нижче наведемо приклад програми, що буде виконувати всі перераховані вище операції:
Prog_1.cpp
#include
#include «conio.h»
using std::cout;
using std::endl;
int main(void)
{
int a=7; // a – ціле
int *aP; // *аР – вказівник на ціле число
aP=&a; // аР – отримує адрес а
cout
cout    продолжение
--PAGE_BREAK--
*aP=10; // розіменовується вказівник і отримує значення 10
cout
getch();
return 0;
}
Результат роботи програми:
Adresa= 0хfff4
ZnachenaaP= 0хfff4
Znachenaa= 7
Znachena*aP= 7
ZnachenaaP= 10
Znachena*aP= 0хfff4
2.1.2. Операції NEW та DELETE
Для роботи із пам’яттю в С++ можна використовувати досить багато операцій та функцій, це і malloc, calloc, free та інші. Проте найбільш зручними є операції new і delete.
Операція new і deleteзабезпечують біль зручні засоби для реалізації динамічного розпроділення динамічної пам’яті.
Операція newслужить для виділення пам’яті. Синтаксично допускається 3 способи її використання:
1. new type_name
Приклад: float *r=new float;
При такому оголошенні r буде вказівником на значення типу float, причому вказувати він буде на початок вже виділеної області пам’яті розміром float, на відміну від оголошення float *r;, де пам’ять не виділяється.
2. new (type_name)
Приклад: float *r=new (float);
Цей випадок аналогічний попередньому.
3. new type_name [expression]
Приклад: float*r=new float [20];
Цей випадок показує що вказівник rвказує на масив із десяти елементів типу float.
Використовуючи операцію newвказівнику вже при ініціалізації можна присвоїти початкове значення:
int*d= newint(12);
Операція delete служить для звільнення пам’яті в “кучі”. Відповідно до операції new, синтаксично допускаються такі способи її використання
1. delete var_name;
Приклад: float*r=new float [20];
delete r;
2. delete [expr] var_name
Приклад: float*r=new float [20];
delete [20] r;
Відмітимо, що дія в першому та другому випадках аналогічна. Виділивши пам’ять, наприклад, так:
float *r = new float [20];
можемо звільнити її будь-яким з наступних способів:
delete [200] r; delete [20] r; delete [10] r; delete [ ] r; delete r;
Якщо вказівник залишається не видаленим із пам’яті, це може призвести до непоправних наслідків, аж до збою у роботі ОС.
2.2 Стеки
Для роботи зі стеком достатньо мати покажчик headна його вершину та допоміжний покажчик (наприклад current) на елемент стеку. Наведемо алгоритми основних операцій зі стеком – вставка та видалення його елемента.
Алгоритм вставки елемента до стеку
1. Виділити пам’ять для нового елемента стеку.
2. Ввести дані до нового елемента.
3. Зв’язати допоміжний елемент із вершиною.
4. Встановити вершину стеку на новостворений елемент.
Графічне представлення алгоритму вставки елемента до стеку
Зауважимо, що значення покажчика headна вершину порожнього стеку є NULL. Тому для створення стеку слід виконати оператор Head=NULLта повторити щойно наведений алгоритм потрібну кількість раз.
Алгоритм видалення елемента із непорожнього стеку
1. Створити копію покажчика на вершину стеку
2. Перемістити покажчик на вершину стеку на наступний елемент
3. Звільнити пам’ять із-під колишньої вершини стеку.
Зрозуміло, що для очищення всього стеку слід повторювати кроки 1-3 доти, доки покажчик headне дорівнюватиме NULL.
Графічне представлення алгоритму видалення елемента із непорожнього стеку
Для наглядної ілюстрації роботи із стеком напишемо програму, основні функції, використовувані при роботі зі стеками — push і pop. Функція push створює новий вузол і поміщає його на вершину стека. Функція pop видаляє верхній вузол стека, звільняє пам'ять, що була виділена вилученому вузлу, і повертає вилучене значення.
Програма на працює із простим стеком цілих чисел. Програма виконує три дії на вибір:
1) поміщає значення в стек (функція push);    продолжение
--PAGE_BREAK--
2) вилучає значення зі стека (функція pop);
3) завершує роботу.
Prog_2.cpp
/*Програма створення простого стеку*/
#include
#include «stdio.h»
#include «stdlib.h»
#include «conio.h»
struct stackNode {/*структура, що посилається на себе*/
int data;
struct stackNode *nextPtr;
};
typedef struct stackNode STACKNODE;
typedef STACKNODE *STACKNODEPTR;
void push(STACKNODEPTR *, int);
int pop(STACKNODEPTR *);
int isEmpty(STACKNODEPTR);
void printStack(STACKNODEPTR);
void instructions(void);
using std::cout;
using std::endl;
main() {
STACKNODEPTR stackPtr = NULL;/*Вказівник на вершину*/
int choice, value;
instructions();
printf ("? ");
scanf("%d", &choice) ;
while (choice !=3) {
switch (choice) {
case 1: /*Занесення значення в стек*/
printf(«Enter an integer: „);
scanf(“%d», &value);
push (&stackPtr, value);
printStack (stackPtr);
break;
case 2: /*Видалення значення із стеку*/
if (!isEmpty(stackPtr))
printf(«The popped value is %d.\n», pop(&stackPtr)) ;
printStack(stackPtr);
break;
default:
printf(«Invalid choice.\n\n»);
instructions();
break;
}
printf ("? ");
scanf("%d", &choice); }
printf(«End of run.%n»); return 0;
}
/*Вивід інструкції на екран*/
void instructions(void) {
printf(«Enter choice:\n»
«1 to push a value on the stack\n»
«2 to pop a value off the stack\n»
«3 to end program\n»); }
/*Занесення нового значення у вершинку стеку*/
void push (STACKNODEPTR *topPtr, int info)
{ STACKNODEPTR newPtr;
newPtr =new STACKNODE;
if (newPtr != NULL) {
newPtr->data = info;
newPtr->nextPtr = *topPtr;
*topPtr = newPtr; } else
printf("%d not inserted. No memory available.\n", info);
}
/*Видалення вузла на вершині стеку*/
int pop(STACKNODEPTR *topPtr)
{ STACKNODEPTR tempPtr;
int popValue;
tempPtr = *topPtr;
popValue = (*topPtr)->data;
*topPtr = (*topPtr)->nextPtr;
free(tempPtr); return popValue;
}    продолжение
--PAGE_BREAK--
/*Друк стеку*/
void printStack(STACKNODEPTR currentPtr)
{ if (currentPtr == NULL)
printf («The stack is empty.\n\n»);
else { printf(«The stack is:\n»);
while (currentPtr != NULL) {
coutdata";
currentPtr = currentPtr->nextPtr;}
printf(«NULL\n\n»); }
}
/*Перевірка чи пустий стек*/
int isEmpty(STACKNODEPTR topPtr)
{ return topPtr == NULL;}
При виконанні програми можливі результати:
Enter choice:
1 to push a value on the stack
2 to pop a value off the stack
3 to end program? 1
Enter an integer: 5 The stack is:
5 --> NULL
? 1
Enter an integer: 6
The stack is:
6-->5-->NULL
? 1
Enter an integer: 4 The stack is:
4--> 6 -->5 -->NULL
? 2
The popped value is 4.
The Stack is:
6 --> 5 --> NULL
? 2
The popped value is 6. The Stack is:
5 --> NULL
? 2
The popped value is 5.
The stack is empty.
? 2
The stack is empty.
? 4
Invalid choice.
Enter choice.:
1 to push a value on the stack
2 to pop a value off the stack
3 to end program? 3
End of run.
Функція push поміщає новий вузол на вершину стека. За попередньо наведеним алгоритмом маємо: створення нового вузла відбувається за допомогою виклику операції new, при цьому вказівник newPtr має адресу блоку виділеної пам'яті, змінній newPtr->data привласнюється значення, яке необхідно помістити в стек, і покажчику newPtr->nextPtr вказуєNULL, далі вказівнику newPtr->nextPtr привласнюється *topPtr (вказвник на вершину стека); єднальний елемент newPtr тепер вказує на вузол, що був верхнім до цього.*topPtr привласнюється значення newPtr, *topPtr тепер вказує на нову вершину стека.
Функція pop видаляє верхній вузол стека. Відзначимо, що перед тим як викликати pop, main визначає, чи не порожній стек. Функція pop працює наступним чином:
1) Покажчику tempPtr привласнюється *topPtr (tempPtr буде використаний для звільнення вільної пам'яті).
2) Змінній popValue привласнюється значення (*topPtr)->data (зберігається значення, що перебувало у верхньому вузлі).
3) *topPtr привласнюється (*topPtr)->nextPtr (*topPtr привласнюється адреса нового верхнього вузла).
Звільнення пам'яті, на яку вказує tempPtr.
Відбувається повертається значення popValue функції main.
Реалізувати стек використовуючи класи теж не видається складним. Наприклад, маємо Завдання1: Реалізуйте динамічну структуру типу стек, що працювала б із об’єктами довільних класів, ми можемо отримати наступну програму:
Prog_2_1.cpp
#include
#include «stdio.h»
#include «stdlib.h»
#include «conio.h»
using std::cout;
using std::cin;
using std::endl;
//Батьківський клас, що посилається сам на себе
class fazer{
protected:    продолжение
--PAGE_BREAK--
fazer *n;
public:
//конструктор
fazer(){n=NULL;}
//деструктор
~fazer(){delete n;}
//віртуальнафункція, щобудевиводитиімякласувідповідногообєка
virtual void prin(){};
//занесенняобєктакласудостеку
void push(fazer *l){
l->n=this->n;
this->n=l;
}
//перехід по стеку із вивиденням елементів
void druc(){
if (this->n!=NULL) {this->n->prin(); this->n->druc();}
}
void pop(){
this->n=this->n->n;
}
//перевіркачинепорожнійстек
int Size(){if (this->n!=NULL) return 1; else return 0;}
};
//три класи-нащадки із специфікатором доступу public
class a:public fazer{
private:
int inf;
public:
virtual void prin(){coutclass A";}
a(){inf=13;}
~a(){}
};
class b:public fazer{
private:
char inf;
public:
virtual void prin(){coutclass B";}
b(){inf='A';}
~b(){}
};
class c:public fazer{
private:
double inf;
public:
virtual void prin(){coutclass C";}
c(){inf=3.12;}
~c(){}
};
int main()
{
fazer *head=new fazer;
int ch=1;
cout
cout
cout
cout
cout
while(ch!=5)
{cout
cin>>ch;
cout
switch (ch) {
case 1: {a *d=new a;
head->push(d);
break;}
case 2: { b *f=new b;
head->push(f);
break;}
case 3:{ c *d=new c;
head->push(d);
break;}
case 4:{if (head->Size()) head->pop();
break;}    продолжение
--PAGE_BREAK--
case 5: {return 0;}
}
head->druc();
cout
}
getch();
return 0;
}
При виконанні програми можливі результати:
1: Dodatu element class A do stack
2: Dodatu element class B do stack
3: Dodatu element class C do stack
4: Vudalutu element
5: Exit
vvedit:1
Stack: ->class A
vvedit:2
Stack: ->class B->class A
vvedit:3
Stack: ->class C->class B->class A
vvedit:4
Stack: ->class B->class A
vvedit:4
Stack: ->class A
vvedit:4
Stack:
vvedit:
2.3 Черги
Для роботи з чергою потрібні: покажчик headна початок черги, покажчик lastна кінець черги (можлива реалізація і без покажчика на останній елемент черги) та допоміжний покажчик (наприклад current). Зауважимо, що елементи з черги видаляються за тим самим алгоритмом, що і зі стеку, наведемо алгоритм вставки до черги нового елемента.
Алгоритм вставки елемента до черги
1. Виділити пам’ять для нового елемента черги.
2. Ввести дані до нового елемента.
3. Вважати новий елемент останнім у черзі.
4. Якщо черга порожня, то ініціалізувати її вершину.
5. Якщо черга не порожня, то зв’язати останній елемент черги із новоутворенним.
6. Вважати новий елемент черги останнім.
Графічне представлення алгоритмувставки елемента до черги
Нижче наведено приклад роботи із чергою. Програма пропонує виконати наступні дії на вибір: поставити вузол у чергу (функція enqueue), видалити вузол із черги (функція dequeue), і вийти із програми.
Prog_3.cpp
/*Програма створення простої черги*/
#include
#include
#include
#include
struct queueNode {
char data;
struct queueNode *nextPtr; };
typedef struct queueNode QUEUENODE;
typedef queueNode *QUEUENODEPTR;
/* function prototypes */
void printQueue(QUEUENODEPTR);
int isEmpty(QUEUENODEPTR);
char dequeue(QUEUENODEPTR *, QUEUENODEPTR *);
void enqueue (QUEUENODEPTR *, QUEUENODEPTR *, char);
void instructions (void);
using std::cout;
using std::endl;
main () {
QUEUENODEPTR headPtr = NULL, tailPtr = NULL;
int choice;
char item;
instructions ();
printf ("? ");
scanf("%d", &choice);
while (choice !=3) { switch(choice) {
case 1 :
printf(«Enter a character: „);
scanf(“\n%c», &item);
enqueue(&headPtr, &tailPtr, item);
printQueue(headPtr);    продолжение
--PAGE_BREAK--
break;
case 2 :
if (! isEmpty(headPtr)) {
item = dequeue(&headPtr, &tailPtr);
printf("%c has been dequeued.\n", item);
}
printQueue(headPtr);
break;
default:
printf («Invalid choice.\n\n»); instructions(); break; }
printf ("?"); scanf("%d", &choice); }
printf(«End of run.\n»);
return 0;
}
void instructions(void)
{printf («Enter your choice:\n»
" 1 to add an item to the queue\n"
" 2 to remove an item from the queue\n" " 3 to end\n"); }
void enqueue(QUEUENODEPTR *headPtr, QUEUENODEPTR *tailPtr,char value) {
QUEUENODEPTR newPtr;
newPtr =new QUEUENODE;
if (newPtr != NULL) { newPtr->data = value; newPtr->nextPtr = NULL;
if (isEmpty(*headPtr))
*headPtr = newPtr; else
(*tailPtr)->nextPtr = newPtr;
*tailPtr = newPtr; } else
printf("%c not inserted. No memory available.\n", value);
}
char dequeue(QUEUENODEPTR *headPtr, QUEUENODEPTR *tailPtr) {
char value;
QUEUENODEPTR tempPtr;
value = (*headPtr)->data;
tempPtr = *headPtr;
*headPtr = (*headPtr)->nextPtr;
if (*headPtr == NULL) *tailPtr = NULL;
free(tempPtr); return value; }
int isEmpty(QUEUENODEPTR headPtr) {
return headPtr == NULL; }
void printQueue(QUEUENODEPTR currentPtr) {
if (currentPtr == NULL)
printf(«Queue is empty.\n\n»); else {
printf(«The queue is :\n»);
while (currentPtr != NULL) {
coutdata";
currentPtr = currentPtr->nextPtr; }
printf(«NULL\n\n»); }
}
При виконанні програми можливі результати:
Enter your choice:
1 to add an item to the queue
2 to remove an item from the queue
3 to end? 1
Enter a character: A
The queue is:
A --> NULL
? 1
Enter a character: В
The queue is:
A --> В --> NULL
? 1
Enter a character: Z
The queue is:
A --> В --> Z-->NULL
? 2
A has been dequeued.
The queue is:
B--> Z--> NULL
? 2
В has been dequeued.
The queue is:
Z--> NULL
? 2    продолжение
--PAGE_BREAK--
Zhas been dequeued.
Queue is empty.
? 2
Queue is empty.
? 4
Invalid choice.
Enter your choice:
1 to add an item to the queue
2 to remove an item from the queue
3 to end? 3
End of run.
Функція enqueue одержує від main три аргументи: адресeвказівника на голову черги, адресу вказівника на хвіст черги й значення, яке необхідно поставити в чергу. Виконання функції складається із трьох кроків:
Створення нового вузла: викликати new, присвоїти адреса виділеного блоку пам'яті newPtr, присвоїти newPtr->data значення, що необхідно поставити в чергу, a newPtr->nextPtr присвоїти NULL.
Якщо черга порожня, присвоїти *headPtr покажчик newPtr; в іншому випадку присвоїти цей покажчик (*tailPtr)->nextPtr.
3) І нарешті, присвоїти *tailPtr покажчик newPtr.
Функція dequeueотримує в якості аргументів адрес вказівника на голову черги і адрес вказівника хвоста і видаляє перший вузол черги. Виконання dequeueвідбувається наступним чином:
1. Змінній valueпривласнюється значення (*headPtr)->data(зберегти дані);
2. Присвоїти вказівнику tempPtrзначення *headPtr(tempPtrвикористовується для звільнення вільної пам’яті).
3. Присвоїти вказівнику *headPtrзначення (*headPtr)->nextPtr. (*headPtrзараз вказує на новий перший вузол черги).
4. Якщо *headPtrвказує на NULL, встановити *tailPtrтакож вказуючим на NULL.
5. Вивільнити блок пам’яті, на який вказує tempPtr.
6. Передати значення valueвикликавшій функції (функція dequeueвикликається із main).
Нехай нам потрібно реалізуйте динамічну структуру типу черга, що працювала б із об’єктами довільних класів, програма яку ми напишемо буде подібною до програми реалізації динамічних структури стеку із класами:
Prog_3_1.cpp
#include
#include «stdio.h»
#include «stdlib.h»
#include «conio.h»
using std::cout;
using std::cin;
using std::endl;
//Батьківський клас, що посилається сам на себе
class fazer{
protected:
fazer *n;
public:
//конструктор
fazer(){n=NULL;}
//деструктор
~fazer(){delete n;}
//віртуальна функція, що буде виводити ім’я класу відповідного об’єка
virtual void prin(){};
//занесення об’єкта класу до черги
void push(fazer *l){
if (this->n!=NULL) this->n->push(l);
else this->n=l;}
//перехід по черзі із вивиденням елементів
void druc(){
if (this->n!=NULL) {this->n->prin(); this->n->druc();}
}
//видалення першого елемента черги
void pop(){
this->n=this->n->n;
}
//Перевірка, чи не порожня черга
int Size(){if (this->n!=NULL) return 1; else return 0;}
};
//три класи нащадки із специфікатором доступу public
class a:public fazer{
private:
int inf;
public:
virtual void prin(){cout    продолжение
--PAGE_BREAK--
a(){inf=13;}
~a(){}
};
class b:public fazer{
private:
char inf;
public:
virtual void prin(){cout
b(){inf='A';}
~b(){}
};
class c:public fazer{
private:
double inf;
public:
virtual void prin(){cout
c(){inf=3.12;}
~c(){}
};
int main()
{
fazer *head=new fazer;
int ch=1;
cout
cout
cout
cout
cout
while(ch!=5)
{cout
cin>>ch;
cout
switch (ch) {
case 1: {a *d=new a;
head->push(d);
break;}
case 2: { b *f=new b;
head->push(f);
break;}
case 3:{ c *d=new c;
head->push(d);
break;}
case 4:{if (head->Size()) head->pop();
break;}
case 5: {return 0;}
}
head->druc();
cout
}
getch();
return 0;
}
При виконанні програми можливі результати:
1: Dodatu element class A do queue
2: Dodatu element class B do queue
3: Dodatu element class C do queue
4: Vudalutu element
5: Exit
vvedit:1
Queue: class A
vvedit:2
Queue: class A
vvedit:3
Queue: class A
vvedit:4
Queue: class B
vvedit:4
Queue: class C
vvedit:4
Queue:
vvedit:
Розділ ІІІ. Побудова динамічних структур використовуючи стандартні шаблони
3.1 Використання бібліотеки Stack
Мова програмування С++ містить велику бібліотеку шаблонних класів, функцій а також близько 50 універсальних алгоритмів. Її вміст можна розділити на п’ять категорій. Літератори – узагальнені вказівники, контейнери – структури даних, описані у вигляді шаблонних класів, алгоритми – шаблони функцій, що описують універсальні обчислювальні функції а також функтори і адаптери.    продолжение
--PAGE_BREAK--
Для побудови стека досить підключити шаблонний клас stack, що описує необхідні операції на основі контейнерів послідовностей: vector, listideque. За замовчуванням стек реалізується з контейнером deque. Операціями являються:push– для вставки елемента в вершину стека (реалізується за допомогою функції push_backбазового контейнера), pop–для видалення (функція pop_backбазового контейнера), top– для отримання вказівника на елемент в вершині стека (функція backбазового контейнера), empty– для визначення того, чи є стек пустим (на основі функції emptyбазового контейнера) і size– для отримання числа елементів в стеці на основі функції sizaбазового контейнера), Нижче наведений приклад реалізації стеку на основі всіх трьох контейнерів.
Prog_4.cpp
#include
usingstd::cout;
usingstd::endl;
#include
#include
#include
#include«conio.h»
template
void popElements (T &s );
int main ()
{
std::stack intDequeStack;
std::stack > intVectorStack;
std::stack > intListStack;
for (int i=0; i
intDequeStack.push(i);
intVectorStack.push(i);
intListStack.push(i);
}
cout
popElements (intDequeStack);
cout
popElements (intVectorStack);
cout
popElements (intListStack);
cout
getch();
return 0;
}
template
void popElements ( T &s )
{
while (!s.empty() ){
cout
s.pop();
}
}
Результат роботи програми:
deleteizintdequeStack: 08224
delete iz intVectorStack: 08224
deleteizintListStack: 08224
Дана програма створює 3 стека типу intна основі різних контейнерів
…
std::stack intDequeStack;
std::stack > intVectorStack;
std::stack > intListStack;
…
і демонструє роботу із стеком.
Побудувати стек на основі стандартних засобів можна і іншими способами наприклад:
Prog_4_1.cpp
#include
#include
#include
#include «conio.h»
using namespace std ;
void print (stack &Stack);
int main ()
{
const int SIZE = 5;
int i;
//Пустий стек
stackStack, newStack;
//Заповнюємо стек з допомогою функції-члена push()
for (i = 0; i
{
Stack.push (i) ;    продолжение
--PAGE_BREAK--
newStack.push (i+1);
}
//Виводимо на друк розмір стека
int StackSize = Stack.size ();
printf («2 Size first stack = %d\n», StackSize);
StackSize = newStack.size ();
printf(«2 Size second stack = %d\n», StackSize);
//Порівняння стеків
if (Stack == newStack) printf («Stack = = newstack\n»);
if (Stack > newStack) printf («Stack > newStack\n»);
if (Stack >= newStack) printf («Stack > = newStack\n»);
if (Stack
if (Stack
//Виводимо стек на екран
printf («First stack\n»);
print(Stack);
printf(«Second stack\n»);
print(newStack);
getch();
return 0;
}
void print (stack &Stack)
{
if (Stack.empty () ){
printf ("%s \n","Stack empy");
return;
}
while (!Stack.empty () )
{printf ("%d ", Stack.top () );
Stack.pop (); }
printf ("\n");
}
Результат роботи програми:
Size first stack = 5
Size second stack = 5
Stack
Stack
First stack
43210
Secondstack
54321
Оскільки доступ до елементів стеку можливий лише на його вершину, вивести на екран всі елементи можна, якщо почергово виштовхнути їх із стеку.
3.2 Використання бібліотеки Queue
Аналогічно як і до стека, чергу можна побудувати використовуючи стандартні засоби. Ті ж функції, що використовувалися при побудові стеку використовуються і при побудові черги.
Prog_5.cpp
#include
#include
#include «conio.h»
using std::cout;
using std::endl;
int main()
{ std::queue values;
values.push(3.2);
values.push(9.8);
values.push(5.4);
cout
while(!values.empty()){
cout
values.pop();
}
cout
getch();
return 0;
}
Результат роботи програми
Deleteznachenja: 3.2 9.8 5.4
Prog_5_1.cpp
# include
# include
# include
# include
using namespace std;
void print (queue &Queue);
int main ()    продолжение
--PAGE_BREAK--
{
const int SIZE = 5;
int i;
queue Queue, newQueue;
for (i=0; i
{
Queue.push (i);
newQueue.push (i + 1);
}
int QueueSize = Queue.size();
printf («2 Size first queue = %d\n», QueueSize);
QueueSize = newQueue.size ();
printf («2 Size second queue = %d\n», QueueSize);
// Порівняння черг
if (Queue == newQueue) printf («Queue = = newQueue\n»);
if (Queue > newQueue) printf («Queue > newQueue\n»);
if (Queue >= newQueue) printf («Queue >= newQueue\n»);
if (Queue
if (Queue
// Виводимочергунаекран
printf («First queue\n»);
print (Queue);
printf («Second queue\n»);
print (newQueue);
getch();
return 0;
}
void print (queue &Queue)
{
if (Queue.empty())
{
printf ("%s \n",«Queue clear»);
return;
}
while (!Queue.empty ())
{
printf ("%d ", Queue.front () );
Queue.pop ();
}
printf ("\n");
}
Результат роботи програми
Size first queue = 5
Size second queue = 5
Queue
Queue
First queue
01234
Firstqueue
12345
Висновки
У курсовій роботі було проведено огляд динамічних структур, що широко застосовуються у програмуванні. Розглянуто їх властивості і практичне значення.
У відповідності до мети курсової роботи були виконані наступні завдання:
1. Було проведено детальний аналіз літератури та Інтернет джерел за темою «Динамічні структури», що дало змогу сформувати як теоретичні основи понять стек, черга так і основні алгоритми реалізації та роботи із цими структурами. У курсовій роботі наведено графічне представлення різних структур даних, графічно показано суть алгоритмів вставки, видалення елемента стека, черги;
2. Було проаналізовано застосування черг та стеків на практиці, що дало змогу визначити, в яких цілях і з якою метою є їх найбільш доцільне використання. Було показано, що на даний час існує ряд специфічних задач і областей застосування, де без використання стеку чи черги обійтись практично не можливо. Як наслідок, це дало змогу поставити завдання для реалізації як стеку так і черги з допомогою мови програмування С++;
3. Ми розглянули основні команди і операції мови С++, які є досить специфічними і необхідними для роботи із динамічними структурами. Так, ми провели теоретичний аналіз вказівників, способів їх створення і основних операцій з ними, розглянули ситуації, коли некоректне поводження із вказівниками може призвести до непередбачуваних наслідків, аж до зависання комп’ютера, чи збою у роботі операційної системи. Це було необхідним тому, що саме з допомогою вказівників ми працюємо із динамічною пам’яттю.
4. В курсовій роботі ми поставили за мету створити динамічні структури і показати основні можливості роботи із ними. Тому ми написали ряд програм. Для написання програм ми використовували програму
Dev-C++, яка працює із компілятором версії 4.0. Вибір даної програми зумовлений її україномовним інтерфейсом, підтримкою роботи на Windows-системах і великими можливостями. При реалізації стеків і структур ми намагалися охопити всі можливі способи побудови їх у С++. Так, програми Prog_2.cpp,Prog_3.cppце реалізація динамічних структур лише за допомогою стандартних засобів мови С (батьківська мова по відношенню до С++). Так, програми Prog_2_1.cpp,Prog_3_1.cppдещо кардинально відрізняються від попередніх. Різниця в тому, для виконання цих завдань було реалізовано інший підхід програмування, а саме об’єктно-орієнтоване. В даних завдання реалізовані такі поняття як наслідування, віртуальні функції, батьківські класи і класи нащадки, конструктори, деструктори та функції члени класу для роботи із полями класу. Для написання цих програм ми зумисне поставили завдання і написали їх реалізацію, для наглядності спробували реалізувати всі основні підходи об’єктно-орієнтованого програмування.
Написання програм супроводжується із вказанням можливих результатів їх роботи (оскільки програми реалізують роботу із користувачем у інтерактивному режимі, результати можуть відрізнятися від наведених), по можливості ми пояснили найбільш важливі процедури і функції, їх роль у програмі і необхідність. У програмі було зроблено коментарі, які роблять програму більш зрозумілою для розуміння.
Оскільки С++ — це мова програмування високого рівня, ми не могли оминути той факт, що С++ пропонує свої, вбудовані засоби для побудови динамічних структур. Для цього ми використовували вбудовані шаблонні класи, контейнери. Проте, навіть використовуючи їх, можливі багато способів кінцевої реалізації, саме це ми спробували показати у програмах Prog_4.cpp, Prog_5.cppта Prog_4_1.cpp, Prog_5_1.cpp. Дані програми підключають вже готові розроблені класи, і реалізовано за їх допомогою програма є досить малою за обсягом написання програмного коду.    продолжение
--PAGE_BREAK--
Програми, що написані під час виконання курсової роботи є наглядними, не складними у розумінні і при всьому цьому реалізують всі види дій, які можна проводити над стеком, чергою.
Виконуючи курсову роботу ми не тільки опрацювали роботу із динамічними змінними в мові програмування С++, а й більш детально вивчили її можливості і застосували на практиці.
Література
Айра П. Обьектно-Ориентированное прогрпммирование на С++. М.: Санкт-Петербург, 1999. – 460 с.
Архангельський А.Я. С++Builder6: Справ. Пособие. Кн.1. Язык С++. – М.: Бином, 2004. – 544 с.
Архангельський А.Я. С++Builder6: Справ. Пособие. Кн.2. Классы и компоненты. – М.: Бином, 2004. – 527 с.
Глушаков С.В. Программирование на VisualC++. – М.: АСТ; Х.: Фоліо, 2003. – 726 с.
Дейтел Х. Как программировать на С++. – М.: Бином, 2001. – 1152 с.
Джонс Ж., Харроу К. Решение задач в системе Турбо Паскаль. М, 1991. – 709 с.
Ковалюк Т.В. Основи програмування. Київ: Видавнича група ВНV, 2005. – 385 с.
Культин Н. Б. С/С++ в задачах и примерах. – М., 2002. – 288 с.
Кучеренко В. Языкпрограммирования С++ для начинающих и не только. – М.: Майор, 2001. – 160 с.
Клюшин Д. А. Полный курс С++. Москва: Санкт-Петербург, 2004. –.
Марченко А.И., Марченко Л.А. Программирование в среде TurboPascal7.0. К.: ВЕК, 2000. – 441 с.
Мешков А.В. Visual C++ u MFC. — М, 2003. – 1040 с.
Павловская Т.А. С/С++: Программирование на языке высокого уровня: Учебник для студ. ВУЗ. М, 2002. – 464 с.
Секунов Н.Ю. Самоучитель VisualC++. М., 2002. – 735 с.
Сердюченко В.Я. Розробка алгоритмів та програмування мовоюTurboPascal. Харків: Паритет, 1995. – 350 с.
Франка П. С++: Учебный курс. М., 2002. – 521 с.
Щедріна О.І. Алгоритмізація та програмування процедур обробки інформації. К., 2001. – 240 с.