Практическая работа 4. Стек. Работа со стеком. Дек

Практическая работа 4. Стек. Работа со стеком. Дек.

 

1.Запустите IDE Borland C++ 5.02. Подготовьте запуск исполнимых файлов в консольном режиме.

2.Откомпилируйте предложенную программу работы со стеком. Измените в потоковых операторах вывода текст на русском языке на транслит или на английский язык.

 

#include<iostream.h>

struct node

{

int elem;

node *sled;

};

class Spisok

{

private:

node *stk;

int klad;

public:

        Spisok () { stk=NULL; }

        int Set_Stack () {return klad;}

        void POSTROENIE();

        void VYVOD();

        void W_S(int);

        void YDALENIE ();

        void OCHISTKA();

};

void main ()

{

Spisok A;

int el;

int t; //Содержимое информационного поля верхушки стека.

 

A.POSTROENIE (); A.VYVOD ();

cout<<"Введите вставляемый элемент: ";

cin>>el;

A.W_S (el); A.VYVOD ();

 

cout<<"Удалим элемент из стека.\n";

A.YDALENIE ();

t=A.Set_Stack();

cout<<"Из стека было извлечено число... "<<t<<endl;

A.VYVOD ();

A.OCHISTKA();

}

void Spisok::POSTROENIE ()

//Построение стека, заданного указателем stk.

{

node *t;

int el;

 

cout<<"Вводите элементы стека: ";

cin>>el;

while (el!=0)

{

t = new (node);

(*t).elem = el; (*t).sled = stk;

stk = t; cin>>el;

}

}

void Spisok::VYVOD ()

//Вывод содержимого стека, заданного указателем stk.

{

node *t;

cout<<"Содержимое стека: "; t = stk;

while (t!=NULL)

{cout<<(*t).elem<<" "; t = (*t).sled;}

cout<<endl;

}

void Spisok::W_S (int el)

//Помещение элемента el в стек stk.

{

node *q;

 

q = new (node);

(*q).elem = el; (*q).sled = stk; stk = q;

}

void Spisok::YDALENIE ()

//Удаление элемента из стека, заданного указателем stk.

//Значение информационного поля удаляемого элемента

//помещается в параметр klad.

{

node *q;

if (stk==NULL)

cout<<"Стек пуст!\n";

else

{

klad = (*stk).elem; q = stk;

stk = (*stk).sled; delete q;

}

}

void Spisok::OCHISTKA()

//Возврат выделенной памяти в "кучу".

{

node *t,*q;

 

t = stk;

if (t!=NULL)

{

q=(*t).sled;

while (q!=NULL)

{

delete t; t = q; q =(*q).sled;

}

delete t;

}

}
3. Формирование дека, просмотр его содержимого, добавление элемента к деку и удаление элемента из дека.

#include<iostream.h>struct node{ int elem; node *sled;};class Spisok{ private: node *ld,*rd; int el_left,el_right; public: void POSTROENIE (); void VYVOD (); void VSTAV1 (int); void VSTAV2 (int); int SetElLeft() {return el_left;} int SetElRight() {return el_right;} void YDALE1 (); void YDALE2 (); void OCHISTKA();}; void main (){ Spisok A; int el;       A.POSTROENIE (); A.VYVOD (); cout<<"Добавим звено справа.\n"; cout<<"Введите элемент добавляемого звена: "; cin>>el; A.VSTAV1 (el); A.VYVOD (); cout<<"Добавим звено слева.\n"; cout<<"Введите элемент добавляемого звена: "; cin>>el; A.VSTAV2 (el); A.VYVOD (); cout<<"Удалим звено справа.\n"; A.YDALE1 (); A.VYVOD (); cout<<A.SetElRight()<<endl; cout<<"Удалим зввено слева.\n"; A.YDALE2 (); A.VYVOD (); cout<<A.SetElLeft()<<endl; A.OCHISTKA();} void Spisok::POSTROENIE ()//Построение дека:// ld - указатель на левый конец дека,// rd - Указатель на правый конец дека.{ node *k; int el;       cout<<"Вводите содержимое звеньев дека: \n"; cin>>el; if (el!=0) { k = new (node); (*k).elem = el; (*k).sled = NULL; ld = k; rd = k; cin>>el; while (el!=0)     {VSTAV1 (el); cin>>el;} } else {rd = NULL; ld = NULL;}} void Spisok::VYVOD ()//Вывод содержимого дека:// ld - указатель на левый конец дека.{ node *k; k = ld; cout<<"Дек: "; while (k!=NULL) {cout<<(*k).elem<<" "; k = (*k).sled;} cout<<endl;} void Spisok::VSTAV1 (int el)// Помещение звена, содержащего элемент el, в дек справа.// ld - указатель на левый конец дека,// rd - указатель на правый конец дека.{ node *k; k = new (node); (*k).elem = el; (*k).sled = NULL;  if (rd!=NULL) {(*rd).sled = k; rd = k;} else {rd = k; ld = k;}}void Spisok::VSTAV2 (int el)//Помещение звена, содержащего элемент el, в дек слева.// ld - указатель на левый конец дека,// rd - указатель на правый конец дека.{ node *k;  k = new (node); (*k).elem = el; (*k).sled = ld; if (ld!=NULL) ld = k; else {ld = k; rd = k;}}void Spisok::YDALE1 ()//Удаление звена из дека справа//с сохранением удаляемого звена в переменной el_right.// ld - указатель на левый конец дека,// rd - указатель на правый конец дека.{ node *z; node *k; if (rd==ld) { el_right = (*rd).elem; delete rd; ld = rd = NULL; cout<<"Дек пуст!\n"; } else { z = ld; k = (*ld).sled; while (k!=rd) {z = k; k = (*k).sled;}  el_right = (*rd).elem; (*z).sled = NULL; delete rd; rd = z; }}void Spisok::YDALE2 ()// Удаление звена из дека слева // с сохранением удаляемого звена в переменной el_left.// ld - указатель на левый конец дека,// rd - указатель на правый конец дека.{ node *q; if (ld!=NULL) { el_left = (*ld).elem; q = ld; ld = (*ld).sled; delete q; } else cout<<"Дек пуст!\n";}void Spisok::OCHISTKA(){ node *k,*q; k = ld; if (k!=NULL) { q = (*k).sled; while (q!=NULL)  {delete k; k = q; q=(*k).sled;} delete k; }} 4. Постройте схемы алгоритмов построения и работы с деком в рабочей тетради. Защитите работу.