Практическая работа 5. Двунаправленные списки. Работа с производными структурами: кольцами и деком

 

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

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

#include<iostream.h>struct node{ int elem; node *sled; node *pred;};class Spisok{ private: node *nsp,*ksp; public: Spisok() {nsp=ksp=NULL;} void Postroenie (); void VyvodForward (); void VyvodBack (); void Ochistka (); void InsAfter (int,node*); void InsBefore (int,node*); void Delete (node*); void DelAfter (node*); node *PoiskForward (int); node *PoiskBack (int);};void main (){ Spisok A; node *Res; int el,el1;   A.Postroenie (); A.VyvodForward (); A.VyvodBack ();   cout<<"Введите элемент звена, после которого "; cout<<"осуществляется вставка: "; cin>>el; cout<<"Введите элемент вставляемого звена: "; cin>>el1; Res=A.PoiskForward (el); if (Res!=NULL) { A.InsAfter (el1,Res); A.VyvodForward (); A.VyvodBack (); } else cout<<"Звена с заданным элементом в списке нет!\n"; cout<<"Введите элемент звена, перед которым "; cout<<"осуществляется вставка: "; cin>>el; cout<<"Введите элемент вставляемого звена: "; cin>>el1; Res = A.PoiskBack (el); if (Res!=NULL) { A.InsBefore (el1,Res); A.VyvodForward (); A.VyvodBack (); } else cout<<"Звена с заданным элементом в списке нет!\n"; cout<<"Введите элемент звена, после которого "; cout<<"осуществляется удаление: "; cin>>el; Res = A.PoiskForward (el); if (Res!=NULL) { A.DelAfter (Res); A.VyvodForward (); A.VyvodBack (); } else cout<<"Звена с заданным элементом в списке нет!\n"; cout<<"Введите элемент звена, которое "; cout<<"надо удалить: "; cin>>el; Res = A.PoiskForward (el); if (Res!=NULL) { A.Delete (Res); A.VyvodForward (); A.VyvodBack (); } else cout<<"Звена с заданным элементом в списке нет!\n"; A.Ochistka ();} void Spisok::Postroenie ()//Построение двунаправленного списка с заглавным звеном:// nsp - указатель на начало списка,// ksp - указатель на конец списка.{ node *rsp; int el; nsp = new(node); rsp = nsp; (*nsp).pred = NULL; (*nsp).sled = NULL; cout<<"Вводите последовательность:\n"; cin>>el; while (el!=0) { (*rsp).sled = new(node); (*((*rsp).sled)).pred = rsp; rsp = (*rsp).sled; (*rsp).sled = NULL; (*rsp).elem = el; cin>>el; } ksp = rsp;} void Spisok::VyvodForward ()//Вывод содержимого двунаправленного списка от его начала.// nsp - указатель на начало списка, ksp - указатель на конец списка.{ node *rsp; rsp = (*nsp).sled; cout<<"Двунаправленный список содержит: "; while (rsp!=NULL) { cout<<(*rsp).elem<<" "; rsp = (*rsp).sled; } cout<<endl;} void Spisok::VyvodBack ()//Вывод содержимого двунаправленного списка от его конца.// nsp - указатель на начало списка, ksp - указатель на конец списка.{ node *rsp; rsp = ksp; cout<<"Двунаправленный список в обратном порядке: "; while ((*rsp).pred!=NULL) { cout<<(*rsp).elem<<" "; rsp = (*rsp).pred; } cout<<endl;} node *Spisok::PoiskForward (int el)//Функция возвращает указатель на найденный элемент el//двунаправленного списка, заданного указателями nsp// и ksp, или NULL, если элемент в списке не найден.{ node *q; node *Res;   Res = NULL; q = (*nsp).sled; while (q!=NULL && Res==NULL) if ((*q).elem==el) Res = q; else q = (*q).sled; return Res;} node *Spisok::PoiskBack (int el)//Функция возвращает указатель на найденный элемент el//двунаправленного списка, заданного указателями nsp// и ksp, или NULL, если элемент в списке не найден.{ node *q; node *Res; Res = NULL; q = ksp; while (q!=NULL && Res==NULL) if ((*q).elem==el) Res = q; else q = (*q).pred; return Res;} void Spisok::InsAfter (int el,node *Res)//Вставка звена с информационным полем el в//в двунаправленный список, заданный указателями// nsp и ksp, после звена, на которое указывает Res.{ node *q; q = new(node); (*q).elem = el; if ((*Res).sled!=NULL) { (*q).sled = (*Res).sled; (*q).pred = (*(*Res).sled).pred; (*(*Res).sled).pred = q; (*Res).sled = q; } else { (*q).sled = NULL; (*q).pred = Res; ksp = q; (*Res).sled = q; }} void Spisok::InsBefore (int el,node *Res)//Вставка звена с информационным полем el в//в двунаправленный список, заданный указателями// nsp и ksp, перед звеном, на которое указывает Res.{ node *q; q = new(node); (*q).elem = el; (*q).sled = (*(*Res).pred).sled; (*q).pred = (*Res).pred; (*(*Res).pred).sled = q; (*Res).pred = q;} void Spisok::Delete (node *Res)//Удаление звена из двунаправленного списка.// nsp - указатель на начало списка,// ksp - указатель на конец списка,// Res - указатель на удаляемое звено.{ if ((*Res).sled!=NULL) { (*(*Res).sled).pred = (*Res).pred; (*(*Res).pred).sled = (*Res).sled; delete Res; } else { (*(*Res).pred).sled = NULL; ksp = (*ksp).pred; delete Res; }} void Spisok::DelAfter (node *Res)//Удаление звена из двунаправленного списка.// nsp - указатель на начало списка,// ksp - указатель на конец списка,// Res - указатель на звено, предыдущее удаляемому.{ node *q; if ((*Res).sled==NULL) cout<<"Указано последнее звено!\n"; else if ((*(*Res).sled).sled!=NULL) { q = (*Res).sled; (*(*(*Res).sled).sled).pred = Res; (*Res).sled = (*(*Res).sled).sled; delete q; } else { q = (*Res).sled; (*Res).sled = NULL; ksp = (*ksp).pred; delete q; }} void Spisok::Ochistka ()//Удаление двунаправленного списка из памяти.// nsp - указатель на заглавное звено списка,// ksp - указатель на последнее звено списка.{ node *q,*q1; q = nsp; q1 = (*q).sled; while (q1!=NULL) { q = q1; q1 = (*q1).sled; delete q; } delete nsp; nsp = ksp = NULL;}

 

 

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

 

#include<iostream.h>struct node{ int elem; node *sled; node *pred;}; class Spisok{ private: node *nsp; public: Spisok() {nsp=NULL;} void BuiltRing (); void VyvodLeftRight (); void VyvodRightLeft (); void InsAfter (node*,int); void InsBefore (node*,int); void Delete (node*); void DelAfter (node*); node *SearchRing (int); void Ochistka();}; void main (){ Spisok A; node *Res; int el,el1; A.BuiltRing (); cout<<"Содержимое кольца 'по часовой стрелке': \n"; A.VyvodLeftRight (); cout<<"Содержимое кольца'против часовой стрелки': \n"; A.VyvodRightLeft (); cout<<"Введите элемент звена, после которого "; cout<<"осуществляется вставка: "; cin>>el; cout<<"Введите элемент вставляемого звена: "; cin>>el1; Res = A.SearchRing (el); if (Res!=NULL) {A.InsAfter (Res,el1); A.VyvodLeftRight ();} else cout<<"Звена с таким элементом в списке нет!\n"; cout<<"Введите элемент звена, перед которым "; cout<<"осуществляется вставка: "; cin>>el; cout<<"Введите элемент вставляемого звена: "; cin>>el1; Res = A.SearchRing (el); if (Res!=NULL) { A.InsBefore (Res,el1); A.VyvodLeftRight (); } else cout<<"Звена с таким элементом в списке нет!\n"; cout<<"Введите элемент звена, который "; cout<<"надо удалить: "; cin>>el; Res = A.SearchRing (el); if (Res!=NULL) { A.Delete (Res); A.VyvodLeftRight (); } else cout<<"Звена с таким элементом в списке нет!\n"; cout<<"Введите элемент звена, после которого "; cout<<"осуществляется удаление: "; cin>>el; Res = A.SearchRing (el); if (Res!=NULL) { A.DelAfter (Res); A.VyvodLeftRight (); } else cout<<"Звена с таким элементом в списке нет!\n"; A.Ochistka();} void Spisok::BuiltRing ()// Построение двунаправленного кольцевого списка nsp//     с удаленным заглавным звеном.// nsp - указатель на заглавное звено списка.{ node *r; int el; //Построим заглавное звено кольцевого списка. nsp = new(node); r = nsp; (*nsp).pred = NULL; (*nsp).sled = NULL; cout<<"Вводите элементы списка: \n"; cin>>el; while (el!=0) { (*r).sled = new (node); (*((*r).sled)).pred = r; r = (*r).sled; (*r).sled = NULL; (*r).elem = el; cin>>el; } //А теперь - образуем кольцевой список! if ((*nsp).sled!=NULL) { (*((*nsp).sled)).pred = r; (*r).sled = (*nsp).sled; } else cout<<"Кольцевой список пуст!\n";} void Spisok::VyvodLeftRight ()// Вывод содержимого двунаправленного кольцевого списка// с удаленным заглавным звеном "по часовой стрелке".// nsp - указатель на заглавное звено списка.{ node *r; cout<<"Кольцевой список: "; if ((*nsp).sled!=NULL) { cout<<(*((*nsp).sled)).elem<<" "; r = (*((*nsp).sled)).sled; while (r!=(*nsp).sled) { cout<<(*r).elem<<" "; r = (*r).sled; } cout<<endl; } else cout<<"пуст!";} void Spisok::VyvodRightLeft ()// Вывод содержимого двунаправленного кольцевого списка// с удаленным заглавным звеном "против часовой стрелки".// nsp - указатель на заглавное звено списка.{ node *r; cout<<"Кольцевой список: "; if ((*nsp).sled!=NULL) { cout<<(*((*((*nsp).sled)).pred)).elem<<" "; r = (*((*((*nsp).sled)).pred)).pred; while (r!=(*((*nsp).sled)).pred) { cout<<(*r).elem<<" "; r = (*r).pred; } cout<<endl; } else cout<<"пуст!";} node *Spisok::SearchRing (int el)// Поиск элемента el в кольцевом двунаправленном списке//        с удаленным заглавным звеном.// nsp - указатель на заглавное звено списка.{ node *q; node *p; node *Res; Res = NULL; p = nsp; if ((*((*p).sled)).elem==el) Res = (*p).sled; else { q = (*((*p).sled)).sled; while (q!=(*p).sled && Res==NULL) if ((*q).elem==el) Res = q; else q = (*q).sled; } return Res;} void Spisok::InsAfter (node *Res,int el)// Вставление в кольцевой двунаправленный список звена// с информационным полем el после звена, на которое// указывает ссылка Res.{ node *q; q = new(node); (*q).elem = el; (*q).sled = (*Res).sled; (*q).pred = (*(*Res).sled).pred; (*(*Res).sled).pred = q; (*Res).sled = q;} void Spisok::InsBefore (node *Res,int el)// Вставка в кольцевой двунаправленный список звена// с информационным полем el перед звеном, на которое// указывает ссылка Res.// nsp - указатель на заглавное звено списка.{ node *q; q = new(node); (*q).elem = el; (*q).sled = (*(*Res).pred).sled; (*q).pred = (*Res).pred; (*(*Res).pred).sled = q; (*Res).pred = q; if (Res==(*nsp).sled) (*nsp).sled = q;} void Spisok::Delete (node *Res)// Удаление из кольцевого двунаправленного списка// звена, на которое указывает ссылка Res.// nsp - указатель на заглавное звено списка.{ if ((*Res).sled==Res) { (*nsp).sled = NULL; delete Res; } else { (*(*Res).sled).pred = (*Res).pred; (*(*Res).pred).sled = (*Res).sled; if ((*nsp).sled==Res) // Удаляем "первое" звено кольца. (*nsp).sled = (*Res).sled; delete Res; }} void Spisok::DelAfter (node *Res)// Удаление из кольцевого двунаправленного списка звена,// расположенного после звена, на которое указывает// ссылка Res.// nsp - указатель на заглавное звено списка.{ node *q; if ((*Res).sled==Res) { (*nsp).sled = NULL; delete Res;} else { q = (*Res).sled;  (*(*(*Res).sled).sled).pred = (*(*Res).sled).pred; (*Res).sled = (*(*Res).sled).sled; if ((*(*nsp).sled).pred==Res) // Удаляем "последнее" звено кольца. (*nsp).sled = (*Res).sled; delete q; }} void Spisok::Ochistka(){ node *q,*q1; q = (*((*nsp).sled)).sled; q1 = (*q).sled; while (q1!=(*((*nsp).sled)).sled) { delete q; q=q1; q1=(*q1).sled; } delete q; delete nsp;}

 

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

#include<iostream.h>struct node{ int elem; node *sled; node *pred;}; class Spisok{ private: node *nd;//Указатель на начало дека. node *kd;//Указатель на конец дека. int klad;//Информационное поле удаленного элемента. public: void BuiltDeck (); void VyvodDeck (); void InsLeft (int); void InsRight (int); void DelLeft (); void DelRight (); int Get_Klad () {return klad;} void Ochistka();}; void main (){ Spisok A; int el; A.BuiltDeck (); A.VyvodDeck (); cout<<"Введите элемент звена, вставляемого справа: "; cin>>el; A.InsRight (el); A.VyvodDeck (); cout<<"Введите элемент звена, вставляемого слева: "; cin>>el; A.InsLeft (el); A.VyvodDeck (); cout<<"Удалим звено справа: \n";  A.DelRight (); A.VyvodDeck (); cout<<"Был удален элемент: "<<A.Get_Klad()<<endl; cout<<"Удалим звено слева: \n"; A.DelLeft (); A.VyvodDeck (); cout<<"Был удален элемент: "<<A.Get_Klad()<<endl; A.Ochistka();} void Spisok::BuiltDeck ()// Построение дека на базе двунаправленного// списка с заглавным звеном.// nd - указатель на начало дека,// *kd - указатель на конец дека.{ node *q; node *z; int el; nd = new(node); z = nd; (*nd).pred = (*nd).sled = NULL; cout<<"Введите последовательность: \n"; cin>>el; while (el!=0) { (*z).sled = new (node); (*((*z).sled)).pred = z; z = (*z).sled; (*z).sled = NULL; (*z).elem = el; cin>>el;} if ((*nd).sled!=NULL) { q = nd; nd = (*nd).sled; (*nd).pred = NULL;   kd = z; delete q; } else       { delete nd; nd = kd = NULL; }} void Spisok::VyvodDeck ()// Вывод содержимого дека.// nd - указатель на начало дека.{ node *z; z = nd; cout<<"Содержимое дека: "; if (z!=NULL) while (z!=NULL) { cout<<(*z).elem<<" "; z = (*z).sled; } else cout<<"он пуст!\n"; cout<<endl;}void Spisok::InsLeft (int el)// Добавление звена, содержащего элемент el, в дек слева.// nd - указатель на начало дека,// kd - указатель на конец дека.{ node *q; q = new(node); (*q).elem = el; if (nd==NULL) { nd = q; (*q).sled = (*q).pred = NULL; kd = q; } else { (*q).sled = nd; (*q).pred = NULL; (*nd).pred = q; nd = q; }} void Spisok::InsRight (int el)// Добавление звена, содержащего элемент el, в дек справа.// nd - указатель на начало дека,// kd - указатель на конец дека.{ node *q; q = new(node); (*q).elem = el; if (kd==NULL) { nd = q; (*q).sled = (*q).pred = NULL; kd = q; } else { (*q).sled = NULL; (*q).pred = kd; (*kd).sled = q; kd = q; }} void Spisok::DelLeft ()// Удаление звена из дека слева с помещением// элемента удаляемого звена в переменную klad.// nd - указатель на начало дека,// kd - указатель на конец дека.{ node *q; if ((*nd).sled!=NULL) { q = nd; klad =(*q).elem; nd = (*nd).sled; (*nd).pred = NULL; delete q;} else { // В деке находится один элемент. q = nd; klad =(*q).elem; nd = kd = NULL; delete q;cout<<"Дек пуст!\n"; }} void Spisok::DelRight ()// Удаление звена из дека справа с помещением// элемента удаляемого звена в переменную klad.// nd - указатель на начало дека,// kd - указатель на конец дека.{ node *q; if ((*kd).pred!=NULL) { q = kd; klad =(*q).elem; kd = (*kd).pred; (*kd).sled = NULL; delete q; } else {// В деке находится один элемент. q = kd; klad =(*q).elem; nd = kd = NULL; delete q; cout<<"Дек пуст!\n"; }} void Spisok::Ochistka(){ node *q,*q1; q = nd; q1 = (*q).sled; while (q1!=NULL) { delete q; q = q1; q1 = (*q).sled;} delete q; nd = kd = NULL;} 5. Зарисуйте в рабочей тетради схемы алгоритмов работы с деком.