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;

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