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

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

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

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