Приведу задание, как оно есть:
"Дек с тремя "хвостами"
Если обычный дек можно представить как открытую трубку, а стек - как трубку, запаянную с одного конца, то трех-хвостовой дек - это открытая трубка в виде тройника. Так что общая логика работы с таким деком сохраняется, за исключением появления особой точки - центра дека. Начните реализацию с обычного дека."
Обычный дек я сделал, но его нужно доделать до треххвостового. По идее, на пересецении "трубок" в нем появляется центральный элемент, который должен хранить указатели на предыдущие элементы, т.е. 3 указателя. И еще один нюанс: например, мы удаляем из одной "трубки" все элементы. Что делать? Очевидно, нам нужен переключатель в центральном элементе, который переключал бы дек на другие "трубки", что бы и в них можно было удалить элементы. Или наоборот - добавить.
Легко в теории, но не столь просто на практике. Как именно это реализовать в коде? Даже и не знаю, с чего начать... Долго лазил по поисковикам, по n-хвостовым декам информации 0 (
Буду рад, если кто-нибудь поможет 
P.S. Код обычного дека (который нужно доделать) прилагаю в файле, а заодно продублирую здесь.
| Код |
#include "stdafx.h"
#include <iostream>
using namespace std;
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 Menu();
};
void main ()
{
Spisok A;
int el;
int term = 10;
A.Menu ();
A.BuiltDeck ();
A.VyvodDeck ();
while (term !=0)
{
cin >> term;
if (term == 1)
{
cout<<"Enter an element of the part, which must be inserted on the right: ";
cin>>el;
A.InsRight (el);
A.VyvodDeck ();
}
else if (term == 2)
{
cout<<"Enter an element of the part, which must be inserted on the left: ";
cin>>el;
A.InsLeft (el);
A.VyvodDeck ();
}
else if (term == 3)
{
A.DelRight ();
A.VyvodDeck ();
cout<<"Was deleted element: "<<A.Get_Klad()<<endl;
}
else if (term == 4)
{
A.DelLeft ();
A.VyvodDeck ();
cout<<"Was deleted element: "<<A.Get_Klad()<<endl;
}
else if (term == 0)
{
break;
}
else
{
cout<<"Unknown command"<<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<<"Enter sequence: \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<<"Contents of a deque: ";
if (z!=NULL)
while (z!=NULL)
{ cout<<(*z).elem<<" "; z = (*z).sled; }
else cout<<"it empty!\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<<"Deque is empty!\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<<"Deque is empty!\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;
}
void Spisok::Menu()
//Построение меню
{
cout << "--------------------------------------"<<endl;
cout << "Deque Builder v0.1 beta "<<endl;
cout << " "<<endl;
cout << "1. Insert element to the right: "<<endl;
cout << "2. Insert element to the left: "<<endl;
cout << "3. Delete last element from the right: "<<endl;
cout << "4. Delete last element from the left: "<<endl;
cout << "0. Exit. "<<endl;
cout << " "<<endl;
cout << "--------------------------------------"<<endl;
}
|
|
