Смекни!
smekni.com
Информатика

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

};

//три класи-нащадки із специфікатором доступу 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("&bsol;n%c", &item);

enqueue(&headPtr, &tailPtr, item);

printQueue(headPtr);

break;

case 2 :

if (! isEmpty(headPtr)) {

item = dequeue(&headPtr, &tailPtr);

printf("%c has been dequeued.&bsol;n" , item);

}

printQueue(headPtr);

break;

default:

printf ("Invalid choice.&bsol;n&bsol;n"); instructions(); break; }

printf ("?"); scanf("%d", &choice); }

printf("End of run.&bsol;n");

return 0;

}

void instructions(void)

{printf ("Enter your choice:&bsol;n"

" 1 to add an item to the queue&bsol;n"

" 2 to remove an item from the queue&bsol;n" " 3 to end&bsol;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.&bsol;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.&bsol;n&bsol;n"); else {

printf("The queue is :&bsol;n");

while (currentPtr != NULL) {

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

currentPtr = currentPtr->nextPtr; }

printf("NULL&bsol;n&bsol;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 вказівника на голову черги, адресу вказівника на хвіст черги й значення, яке необхідно поставити в чергу. Виконання функції складається із трьох кроків:

1) Створення нового вузла: викликати new, присвоїти адреса виділеного блоку пам'яті newPtr, присвоїти newPtr->data значення, що необхідно поставити в чергу, a newPtr->nextPtr присвоїти NULL.

2) Якщо черга порожня, присвоїти *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<<"&bsol;ndelete iz intVectorStack: ";

popElements (intVectorStack);

cout<<"&bsol;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 на основі різних контейнерів

 
назад
читать дальше
1
2
3
4
5
НАПИШИТЕ НАМ
Copyright © Smekni.com. All rigths reserved.