Практическая работа 3. Кольца. Операции над кольцами.
1.Запустите IDE Borland C++ 5.02. Подготовьте запуск исполнимых файлов в консольном режиме.
2.Откомпилируйте предложенную программу вывода элементов однонаправленного списка. Измените в потоковых операторах вывода текст на русском языке на транслит или на английский язык. Протестируйте программу для любого количества звеньев кольца.
include<iostream.h>
struct node
{
int elem;
node *sled;
};
class Spisok {
private:
node *phead,*Res;
public:
Spisok () {phead=new(node);Res=NULL;}
~Spisok() {delete phead;}
void POSTROENIE ();
void VYVOD ();
node *POISK (int);
void InsAfter (int);
void InsBefore (int);
void Delete ();
void DelAfter ();
void OCHISTKA();
};
void main ()
{
Spisok A;
int el,el1;
node *Res_Zn;
A.POSTROENIE();
A.VYVOD();
cout<<"\nВведите элемент звена, после которого ";
cout<<"осуществляется вставка: ";
cin>>el;
cout<<"\nВведите элемент вставляемого звена: ";
cin>>el1;
if (A.POISK(el)!=NULL)
{ A.InsAfter (el1); A.VYVOD ();}
else cout<<"Звена с заданным элементом в кольце нет!";
cout<<"\nВведите элемент звена, перед которым ";
cout<<"осуществляется вставка: ";
|
|
cin>>el;
cout<<"Введите элемент вставляемого звена: ";
cin>>el1;
if (A.POISK(el)!=NULL)
{
A.InsBefore(el1); A.VYVOD ();
}
else cout<<"Звена с заданным элементом в кольце нет!";
cout<<"\nВведите элемент удаляемого звена: ";
cin>>el;
if (A.POISK(el)!=NULL)
{
A.Delete (); A.VYVOD ();
}
else cout<<"Звена с заданным элементом в кольце нет!";
cout<<"\nВведите элемент звена, ";
cout<<"после которого нужно удалять: ";
cin>>el;
if (A.POISK(el)!=NULL)
{
A.DelAfter (); A.VYVOD ();
}
else cout<<" Звена с заданным элементом в кольце нет!";
A.OCHISTKA();
}
void Spisok::POSTROENIE ()
//Построение кольцевого списка с удаленным заглавным звеном.
//phead - указатель на заглавное звено.
{
node *t;
int el;
t = phead; (*t).sled = NULL;
cout<<"Вводите элементы кольца: ";
cin>>el;
while (el!=0)
{
(*t).sled = new (node);
t = (*t).sled; (*t).elem = el;
cin>>el;}
(*t).sled = (*phead).sled;
}
void Spisok::VYVOD ()
//Вывод содержимого кольцевого списка с удаленным заглавным звеном.
//phead - указатель на заглавное звено.
{
node *t;
t = (*phead).sled;
cout<<"Кольцо: ";
if (t!=NULL)
{
cout<<(*t).elem<<" "; t = (*t).sled;
while (t!=(*phead).sled)
{ cout<<(*t).elem << " "; t = (*t).sled; }
}
else cout<<"пусто!\n";
}
node *Spisok:: POISK (int el)
//Поиск элемента el в кольцевом списке phead.
//Если элемент найден, то Res содержит указатель на звено,
//содержащее элемент el. В противном случае - NULL.
{
node *t;
Res = NULL; t =(*phead).sled;
while ((*t).sled!=(*phead).sled && Res==NULL)
if ((*t).elem==el) Res = t;
else t = (*t).sled;
if (Res==NULL && (*t).elem==el)
Res = t;
return Res;
}
void Spisok::InsAfter (int el)
//Включение звена с информационным полем el в кольцо
//после звена, на которое указывает ссылка Res.
{
node *q;
q = new (node);
(*q).elem = el; (*q).sled = (*Res).sled;
|
|
(*Res).sled = q;
}
void Spisok::InsBefore (int el)
//Включение звена с информационным полем el в кольцо
//перед звеном, на которое указывает ссылка Res.
{
node *q;
q = new (node);
(*q).elem = (*Res).elem; (*q).sled = (*Res).sled;
(*Res).elem = el; (*Res).sled = q;
}
void Spisok::Delete ()
//Удаление звена, на которое указывает ссылка Res,
//из кольцевого списка с удаленным заглавным звеном,
//заданного указателем phead.
{
node *z,*q;
if ((*Res).sled!=(*phead).sled)
{
q = (*Res).sled;
(*Res).elem = (*((*Res).sled)).elem;
(*Res).sled = (*((*Res).sled)).sled;
delete q;
}
else if ((*Res).sled==Res)
{
//В кольце единственное звено.
q = (*phead).sled; (*phead).sled = NULL;
delete q; cout<<"Кольцо пусто!";
}
else
{
//Удаляется "последнее" звено кольца.
z = phead; q = (*phead).sled;
while (q!=Res)
{ z = q; q = (*q).sled; }
(*z).sled = (*((*z).sled)).sled;
delete q;
}
}
void Spisok::DelAfter ()
//Удаление звена, расположенного после звена,
//на которое указывает ссылка Res,
//из кольцевого списка с удаленным заглавным звеном,
//заданного указателем phead.
{
node *q;
if ((*Res).sled!=(*phead).sled)
{
//Ссылка Res не указывает на последнее звено.
q = (*Res).sled;
(*Res).sled = (*((*Res).sled)).sled;
delete q;
}
else if ((*Res).sled==Res)
{
//Удаляемое звено - единственное в кольце.
q = (*phead).sled; (*phead).sled = NULL;
delete q; cout<<"Кольцо пусто!";
}
else
{
//Удаляемое звено - первое в кольце и не единственное.
q = (*phead).sled;
(*Res).sled = (*((*Res).sled)).sled;
(*phead).sled = (*Res).sled; delete q;
}
}
void Spisok::OCHISTKA()
{
node *q,*q1;// Рабочие указатели.
q = phead;
q1 = (*q).sled; // Указатель q1 "опережает" указатель q.
do {
q = q1;
q1 = (*q1).sled;
delete q;
}
while (q1!=(*phead).sled);
}