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

БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Списки, стеки, очереди в C++

Списки, стеки, очереди в 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.3 Черги

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

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

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

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

Інакше кажучи, у черги є голова (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 ні на що не вказує.

Для вказівників характерні ряд операцій, так поряд із ними використовується операція адресації або ж &, - унарна операція, що повертає адрес свого операнда. Наприклад, якщо маємо оголошення

int y=5;

int *yP;

то операнд

yP-&y;

присвоює адрес змінної у вказівнику уР. Кажуть, що змінна уР «вказує» на у.

Операція *, зазвичай називається операцією побічною адресацією або операцією розіменування, повертає значення об'єкта, на який вказує її операдн (тобто вказівник). Наприклад, оператор

cout<<*yP<<endl;

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

*уР=9;

де 9 присвоюється у. Розіменований вказівник може також використовуватися для отримання вхідної величини, наприклад,

cin<<*yP;

Нижче наведемо приклад програми, що буде виконувати всі перераховані вище операції:

Prog_1.cpp

#include <iostream>

#include "conio.h"

using std::cout;

using std::endl;

int main(void)

{

int a=7; // a - ціле

int *aP; // *аР - вказівник на ціле число

aP=&a; // аР - отримує адрес а

cout<<"Adres a= "<<&a<<endl<<"Znachena aP= " <<aP<<endl;

cout<<"Znachena a= "<<a<<endl<<"Znachena *aP= " <<*aP<<endl;

*aP=10; // розіменовується вказівник і отримує значення 10

cout<<"Znachena aP= "<<aP<<endl<<"Znachena *aP= "<<*aP<<endl;

getch();

return 0;

}

Результат роботи програми:

Adres a= 0хfff4

Znachena aP= 0хfff4

Znachena a= 7

Znachena *aP= 7

Znachena aP= 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 = new int(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);

2) вилучає значення зі стека (функція pop);

3) завершує роботу.

Prog_2.cpp

/*Програма створення простого стеку*/

#include <iostream>

#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;

}

/*Друк стеку*/

void printStack(STACKNODEPTR currentPtr)

{ if (currentPtr == NULL)

printf ("The stack is empty.\n\n");

else { printf("The stack is:\n");

while (currentPtr != NULL) {

cout<<currentPtr->data<<"-->";

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 <iostream>

#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){

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(){cout<<"->class A";}

a(){inf=13;}

~a(){}

};

class b:public fazer{

private:

char inf;

public:

virtual void prin(){cout<<"->class B";}

b(){inf='A';}

~b(){}

};

class c:public fazer{

private:

double inf;

public:

virtual void prin(){cout<<"->class C";}

c(){inf=3.12;}

~c(){}

};

int main()

{

fazer *head=new fazer;

int ch=1;

cout<<"1: Dodatu element class A do stack"<<endl;

cout<<"2: Dodatu element class B do stack"<<endl;

cout<<"3: Dodatu element class C do stack"<<endl;

cout<<"4: Vudalutu element"<<endl;

cout<<"5: Exit"<<endl;

while(ch!=5)

{cout<<"vvedit: ";

cin>>ch;

cout<<" Stack: ";

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<<endl;

}

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 <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

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);

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) {

cout<< currentPtr->data<<"-->";

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

Z has 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 <iostream>

#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<<"class A<-";}

a(){inf=13;}

~a(){}

};

class b:public fazer{

private:

char inf;

public:

virtual void prin(){cout<<"class B<-";}

b(){inf='A';}

~b(){}

};

class c:public fazer{

private:

double inf;

public:

virtual void prin(){cout<<"class C<-";}

c(){inf=3.12;}

~c(){}

};

int main()

{

fazer *head=new fazer;

int ch=1;

cout<<"1: Dodatu element class A do queue"<<endl;

cout<<"2: Dodatu element class B do queue"<<endl;

cout<<"3: Dodatu element class C do queue"<<endl;

cout<<"4: Vudalutu element"<<endl;

cout<<"5: Exit"<<endl;

while(ch!=5)

{cout<<"vvedit: ";

cin>>ch;

cout<<"Queue: ";

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<<endl;

}

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<-class B<-

vvedit: 3

Queue: class A<-class B<-class C<-

vvedit: 4

Queue: class B<-class C<-

vvedit: 4

Queue: class C<-

vvedit: 4

Queue:

vvedit:

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

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

Мова програмування С++ містить велику бібліотеку шаблонних класів, функцій а також близько 50 універсальних алгоритмів. Її вміст можна розділити на п'ять категорій. Літератори - узагальнені вказівники, контейнери - структури даних, описані у вигляді шаблонних класів, алгоритми - шаблони функцій, що описують універсальні обчислювальні функції а також функтори і адаптери.

Для побудови стека досить підключити шаблонний клас stack, що описує необхідні операції на основі контейнерів послідовностей: vector, list i deque. За замовчуванням стек реалізується з контейнером deque. Операціями являються:push - для вставки елемента в вершину стека (реалізується за допомогою функції push_back базового контейнера), pop -для видалення (функція pop_back базового контейнера), top - для отримання вказівника на елемент в вершині стека (функція back базового контейнера), empty - для визначення того, чи є стек пустим (на основі функції empty базового контейнера) і size - для отримання числа елементів в стеці на основі функції siza базового контейнера), Нижче наведений приклад реалізації стеку на основі всіх трьох контейнерів.

Prog_4.cpp

#include <iostream>

using std::cout;

using std::endl;

#include <stack>

#include <vector>

#include <list>

#include "conio.h"

template <class T>

void popElements (T &s );

int main ()

{

std::stack< int > intDequeStack;

std::stack< int, std::vector<int > > intVectorStack;

std::stack< int, std::list<int > > intListStack;

for (int i=0; i<1; ++i) {

intDequeStack.push(i);

intVectorStack.push(i);

intListStack.push(i);

}

cout<<"delete iz intdequeStack: ";

popElements (intDequeStack);

cout<<"\ndelete iz intVectorStack: ";

popElements (intVectorStack);

cout<<"\ndelete iz intListStack: ";

popElements (intListStack);

cout << endl;

getch();

return 0;

}

template<class T>

void popElements ( T &s )

{

while (!s.empty() ){

cout <<s.top()<< ' ';

s.pop();

}

}

Результат роботи програми:

delete iz intdequeStack: 08224

delete iz intVectorStack: 08224

delete iz intListStack: 08224

Дана програма створює 3 стека типу int на основі різних контейнерів

…

std::stack< int > intDequeStack;

std::stack< int, std::vector<int > > intVectorStack;

std::stack< int, std::list<int > > intListStack;

…

і демонструє роботу із стеком.

Побудувати стек на основі стандартних засобів можна і іншими способами наприклад:

Prog_4_1.cpp

#include <iostream>

#include <algorithm>

#include <stack>

#include "conio.h"

using namespace std ;

void print (stack<int> &Stack);

int main ()

{

const int SIZE = 5;

int i;

//Пустий стек

stack<int>Stack, newStack;

//Заповнюємо стек з допомогою функції-члена push()

for (i = 0; i < SIZE; i++)

{

Stack.push (i) ;

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 < newStack) printf ("Stack < newStack\n");

if (Stack <= newStack) printf ("Stack < = newStack\n");

//Виводимо стек на екран

printf ("First stack\n");

print(Stack);

printf("Second stack\n");

print(newStack);

getch();

return 0;

}

void print (stack<int> &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 < newStack

Stack <= newStack

First stack

43210

Second stack

54321

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

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

Аналогічно як і до стека, чергу можна побудувати використовуючи стандартні засоби. Ті ж функції, що використовувалися при побудові стеку використовуються і при побудові черги.

Prog_5.cpp

#include <iostream>

#include <queue>

#include "conio.h"

using std::cout;

using std::endl;

int main()

{ std::queue<double> values;

values.push(3.2);

values.push(9.8);

values.push(5.4);

cout<<"Delete znachenja: ";

while(!values.empty()){

cout<<values.front()<< ' ' ;

values.pop();

}

cout<<endl;

getch();

return 0;

}

Результат роботи програми

Delete znachenja: 3.2 9.8 5.4

Prog_5_1.cpp

# include <iostream>

# include <algorithm>

# include <queue>

# include <conio.h>

using namespace std;

void print (queue <int> &Queue);

int main ()

{

const int SIZE = 5;

int i;

queue <int> Queue, newQueue;

for (i=0; i < SIZE; 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 < newQueue) printf ("Queue < newQUeue\n");

if (Queue <= newQueue) printf ("Queue < = newQueue\n");

// Виводимо чергу на екран

printf ("First queue\n");

print (Queue);

printf ("Second queue\n");

print (newQueue);

getch();

return 0;

}

void print (queue <int> &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 < newQueue

Queue <= newQueue

First queue

01234

First queue

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. Дані програми підключають вже готові розроблені класи, і реалізовано за їх допомогою програма є досить малою за обсягом написання програмного коду.

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

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

Література

1. Айра П. Обьектно-Ориентированное прогрпммирование на С++. М.: Санкт-Петербург, 1999. - 460 с.

2. Архангельський А.Я. С++Builder 6: Справ. Пособие. Кн.1. Язык С++. - М.: Бином, 2004. - 544 с.

3. Архангельський А.Я. С++Builder 6: Справ. Пособие. Кн.2. Классы и компоненты. - М.: Бином, 2004. - 527 с.

4. Глушаков С.В. Программирование на Visual C++. - М.: АСТ; Х.: Фоліо, 2003. - 726 с.

5. Дейтел Х. Как программировать на С++. - М.: Бином, 2001. - 1152 с.

6. Джонс Ж., Харроу К. Решение задач в системе Турбо Паскаль. М, 1991. - 709 с.

7. Ковалюк Т.В. Основи програмування. Київ: Видавнича група ВНV, 2005. - 385 с.

8. Культин Н. Б. С/С++ в задачах и примерах. - М., 2002. - 288 с.

9. Кучеренко В. Язык программирования С++ для начинающих и не только. - М.: Майор, 2001. - 160 с.

10. Клюшин Д. А. Полный курс С++. Москва: Санкт-Петербург, 2004. -.

11. Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0. К.: ВЕК, 2000. - 441 с.

12. Мешков А.В. Visual C++ u MFC. - М, 2003. - 1040 с.

13. Павловская Т.А. С/С++: Программирование на языке высокого уровня: Учебник для студ. ВУЗ. М, 2002. - 464 с.

14. Секунов Н.Ю. Самоучитель Visual C++. М., 2002. - 735 с.

15. Сердюченко В.Я. Розробка алгоритмів та програмування мовою Turbo Pascal. Харків: Паритет, 1995. - 350 с.

16. Франка П. С++: Учебный курс. М., 2002. - 521 с.

17. Щедріна О.І. Алгоритмізація та програмування процедур обробки інформації. К., 2001. - 240 с.