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 с.

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