template <class T>
struct elem_link1
{ T inf;
elem_link1 *link;
};
template <class T>
class LList
{ public:
LList(); //konstruktor
~LList(); //destruktor
LList(LList const&); //copy-konstruktor
LList& operator=(LList const &); //predifiniran operator =
bool operator<(LList &); //predefiniran operator <
bool operator>(LList &); //predefiniran operator >
void print(); //izvejdane na spisuk na ekrana
void IterStart(elem_link1<T>* = NULL); //ukazva Current kum nachaloto
elem_link1<T>* Iter(); //premestva iteratora vuv sledvashta poziciq
void ToEnd(T const &); //vkliuchva element v kraq na spisuka
void ToStart(T const &);
void InsertAfter(elem_link1<T>*,T const &); //vkliuchvane na element sled ukazan element
void InsertBefore(elem_link1<T>*,T const &);//vkliuchvane na element predi ukazan element
int DeleteAfter(elem_link1<T>*,T &); //iztrivane na element sled ukazan element
int DeleteBefore(elem_link1<T>*,T &); //iztrivane na element predi ukazan element
void DeleteElem(elem_link1<T>*,T &); //iztrivane na element
int len(); //duljina na spisuk
void concat(LList const &); //konkatenaciq na neqvniq spisuk s ukazaniq kato parametur
void reverse(); //obrushta spisuka naopaki
LList<T> mergelists(LList<T>, LList<T>); //slivane na sortirani spisuci
void OddToEven(); //puvo nechetnite, posle chetnite v obraten red
T GetEndInf(); //vrushta inf chastta na End
T GetStartInf(); //vrushta inf chastta na Start
bool empty(); //proverka dali e prazen spisuka
bool member(T); //proverka dali daden element e chast ot spisuka
void DeleteLast(); //iztriva posledniq element v spisuk
LList<T> Is_Longer_Than(LList<T> &); //vrushta po-dulgiq ot *this i daden spisuk
LList<T> Is_Shorter_Than(LList<T> &); //vrushta po-kusiq ot *this i daden spisuk
LList<T> Intersection(LList<T> &); //vrushta sechenieto na tekushtiq spisuk s daden
LList<T> Union(LList<T> &); //vrushta obedinenieto na tekushtiq spisuk s daden
private:
elem_link1<T> *Start; //ukazatel kum nachaloto
elem_link1<T> *End; //ukazatel kum kraq
elem_link1<T> *Current; //ukazatel kum tekusht element
void DeleteList();
void CopyList(LList<T> const &);
};
template <class T> //iztrivane na spisuk
void LList<T>::DeleteList()
{
elem_link1<T> *p;
while (Start)
{
p=Start;
Start=Start->link;
delete p;
}
End=NULL;
}
template <class T> //kopirane na spisuk
void LList<T>::CopyList(LList<T> const & r)
{
Start=End=NULL;
if (r.Start)
{
elem_link1<T> *p = r.Start;
while (p)
{
ToEnd(p->inf);
p=p->link;
}
}
}
template <class T> //G4
LList<T>::LList()
{
Start=NULL;
End=NULL;
}
template <class T> //G4
LList<T>::~LList()
{
DeleteList();
}
template <class T> //G4
LList<T>::LList(LList<T> const& r)
{
CopyList(r);
}
template <class T> //G4
LList<T>& LList<T>::operator=(LList<T> const & r)
{
if (this!=&r)
{
DeleteList();
CopyList(r);
}
return *this;
}
template <class T> //predefiniran operator <
bool LList<T>::operator<(LList<T> &r)
{
return this->len()<r.len()?true:false;
}
template <class T> //predefiniran operator >
bool LList<T>::operator>(LList<T> &r)
{
return this->len()>r.len()?true:false;
}
template <class T> //izvejdane na spisuk na ekrana
void LList<T>::print()
{
elem_link1<T> *p = Start;
while (p)
{
cout<<p->inf<<" ";
p=p->link;
}
cout<<endl;
}
template <class T> //ukazva Current kum nachaloto
void LList<T>::IterStart(elem_link1<T> *p)
{
if (p)
Current=p;
else
Current=Start;
}
template <class T> //premestva iteratora vuv sledvashta poziciq
elem_link1<T>* LList<T>::Iter()
{
elem_link1<T> *p=Current;
if (Current)
Current=Current->link;
return p;
}
template <class T> //vkliuchva element v kraq na spisuka
void LList<T>::ToEnd(T const & x)
{
Current=End;
End = new elem_link1<T>;
End->inf=x;
End->link=NULL;
if (Current)
Current->link=End;
else Start=End;
}
template <class T> //vkliuchvane na element sled ukazan element
void LList<T>::InsertAfter(elem_link1<T> *p,T const & x)
{
elem_link1<T> *q = new elem_link1<T>;
q->inf=x;
q->link=p->link;
if (p==End)
End=q;
p->link=q;
}
template <class T> //vkliuchvane na element predi ukazan element
void LList<T>::InsertBefore(elem_link1<T> *p,T const& x)
{
elem_link1<T> *q = new elem_link1<T>;
*q=*p;
if (p==End)
End=q;
p->inf=x;
p->link=q;
}
template <class T> //iztrivane na element sled ukazan element
int LList<T>::DeleteAfter(elem_link1<T> *p,T & x)
{
if(p->link)
{
elem_link1<T> *q=p->link;
x=q->inf;
p->link=q->link;
if (q==End)
End=p;
delete q;
return 1;
}
else return 0;
}
template <class T> //iztrivane na element
void LList<T>::DeleteElem(elem_link1<T> *p, T & x)
{
if (p==Start)
{
x=p->inf;
if(Start==End)
{ Start=End=NULL;
}
else Start=Start->link;
delete p;
}
else
{
elem_link1<T> *q=Start;
while (q->link!=p)
q=q->link;
DeleteAfter(q, x);
}
}
template <class T> //iztrivane na element predi ukazan element
int LList<T>::DeleteBefore(elem_link1<T> *p, T & x)
{
if (p!=Start)
{
elem_link1<T> *q=Start;
while (q->link!=p)
q=q->link;
DeleteElem(q, x);
return 1;
}
else return 0;
}
template <class T> //duljina na spisuk
int LList<T>::len()
{
int n=0;
IterStart();
elem_link1<T> *p=Iter();
while (p)
{
n++;
p=Iter();
}
return n;
}
template <class T> //konkatenaciq na neqvniq spisuk s ukazaniq kato parametur
void LList<T>::concat(LList<T> const & L)
{
elem_link1<T> *p=L.Start;
while (p)
{
ToEnd(p->inf);
p=p->link;
}
}
template <class T> //obrushta spisuka naopaki
void LList<T>::reverse()
{
elem_link1<T> *p;
elem_link1<T> *q;
elem_link1<T> *temp;
p=Start;
if (p)
{
q=NULL;
temp=Start;
Start=End;
End=temp;
while (p!=Start)
{
temp=p->link;
p->link=q;
q=p;
p=temp;
}
p->link=q;
}
}
template <class T> //sortirane na spisuk
void sortlist(LList<T> & l)
{
element<T> *mp;
element<T> *p;
l.IterStart();
p=l.Iter();
while (p->link)
{
T min=p->inf;
mp=p;
elem_link1<T> *q=p->link;
while (q)
{
if (q->inf<=min)
{
mp=q;
min=q->inf;
}
q=q->link;
}
min=mp->inf;
mp->inf=p->inf;
p->inf=min;
p=p->link;
}
}
template <class T> //slivane na sortirani spisuci
LList<T> mergelists(LList<T> l1, LList<T> l2)
{
LList<T> l;
l1.IterStart();
l2.IterStart();
elem_link1<T> *p=l1.Iter();
elem_link1<T> *q=l2.Iter();
while (p && q)
if (p->inf<=q->inf)
{
l.ToEnd(p->inf);
p=l1.Iter();
}
else
{
l.ToEnd(q->inf);
q=l2.Iter();
}
if (q)
while(q)
{
l.ToEnd(q->inf);
q=l2.Iter();
}
else while(p)
{
l.ToEnd(p->inf);
p=l1.Iter();
}
return l;
}
template <class T> //vrushta inf chastta na End
T LList<T>::GetEndInf()
{
return this->End->inf;
}
template <class T> //vrushta inf chastta na Start
T LList<T>::GetStartInf()
{
return this->Start->inf;
}
template <class T> //proverka dali e prazen spisuka
bool LList<T>::empty()
{
if (Start==NULL)
return true;
else
return false;
}
template <class T> //proverqva dali daden element e ot spisuka
bool LList<T>::member(T x)
{
IterStart();
elem_link1<T> *p = Iter();
while (p)
{
if (p->inf == x)
return true;
p = p->link;
}
return false;
}
template <class T> //iztriva posledniq element v spisuk
void LList<T>::DeleteLast()
{
if (empty())
return;
int x;
IterStart();
elem_link1<T> *p = Iter();
while (p->link)
p = p->link;
DeleteElem(p,x);
}
template <class T> //vrushta po-kusiq ot *this i daden spisuk
LList<T> LList<T>::Is_Shorter_Than(LList<T> &L1)
{
return *this<L1?*this:L1;
}
template <class T> //vrushta po-dulgiq ot *this i daden spisuk
LList<T> LList<T>::Is_Longer_Than(LList<T> &L1)
{
return *this>L1?*this:L1;
}
template <class T> //vrushta sechenieto na tekushtiq spisuk s daden
LList<T> LList<T>::Intersection(LList<T> &L)
{
LList<T> Result;
IterStart();
elem_link1<T> *p = Iter();
L.IterStart();
elem_link1<T> *q = L.Iter();
while (p)
{
while (q)
{
if (p->inf == q->inf)
Result.ToEnd(p->inf);
q = q->inf;
}
p = p->inf;
}
return Result;
}
template <class T> //vrushta obedinenieto na tekushtiq spisuk s daden
LList<T> LList<T>::Union(LList<T> &L)
{
LList<T> Result;
IterStart();
elem_link1<T> *p = Iter();
L.IterStart();
elem_link1<T> *q = L.Iter();
while (p)
{
while (q)
{
if (p->inf != q->inf)
Result.ToEnd(p->inf);
q = q->inf;
}
p = p->inf;
}
return Result;
}
template <class T>
void LList<T>::ToStart(T const & x)
{
if (empty())
ToEnd(x);
else
{
Current = Start;
Start = new elem_link1<T>;
Start->inf = x;
Start->link = Current;
}
}