SETINLIST(); // конструктор пустого списка

SETINLIST(const int *m, int n); // конструктор создающий

// множество по массиву m длиной n

SETINLIST(const SETINLIST &a); //конструктор копирования

~SETINLIST();

SETINLIST operator *(const SETINLIST &x); // пересечение

// множеств

SETINLIST operator -(const SETINLIST &x); // вычитание

// множеств

SETINLIST operator +(const SETINLIST &x); // объединение

// множеств

SETINLIST & operator=(const SETINLIST &x);// оператор

// присваивания

};

#endif

Далее приводится реализация методов класса. При этом предполагается, что элементы множества расположены в списке в порядке возрастания. Голова списка вместо номера элемента содержит значение INT_MAX(см. файл limits.h).

#include "SETINLIST.h"

#include "limits.h"

//-------------------------------------

SETINLIST::SETINLIST(){

this->Head=new NODE;

this->Head->El=INT_MAX;

this->Head->Next=this->Head;

}

//--------------------------------------

SETINLIST::SETINLIST(const int *m, int n){

int i;

NODE *p,*x;

this->Head=new NODE;

this->Head->Next=this->Head;

this->Head->El=INT_MAX;

for(i=0,p=this->Head;i<n;i++,p=p->Next){

x=Insert(p);

x->El=m[i];

}

}

//--------------------------------------

SETINLIST::~SETINLIST(){

NODE *x,*y;

x=this->Head;

do {

y=x->Next;

delete x;

x=y;

} while (x!=Head);

}

//--------------------------------

NODE *SETINLIST::Insert(NODE *p){

NODE *x=new NODE;

x->Next=p->Next;

p->Next=x;

return x;

}

//----------------------------------

void SETINLIST::Delete(NODE *p){

NODE *x=p->Next;

p->Next=x->Next;

delete p;

}

//------------------------------------

SETINLIST SETINLIST::operator *(const SETINLIST &x){

SETINLIST y;

NODE *p,*q, *r /* указатель на хвост результата */,*n;

r=y.Head;

for(p=this->Head->Next,q=x.Head->Next;

p!=this->Head && q!=x.Head;){

if(p->El>q->El){

q=q->Next;

continue;

}

if(p->El<q->El){

p=p->Next;

continue;

}

if(p->El==q->El){

n=new NODE;

n->Next=y.Head;

n->El=p->El;

r->Next=n;

r=n;

p=p->Next;

q=q->Next;

continue;

}

} // for

return y;

}

//------------------------------------

SETINLIST SETINLIST::operator +(const SETINLIST &x){

SETINLIST y;

NODE *p,*q,*r /* указатель на хвост результата */,*n;

r=y.Head;

for(p=this->Head->Next,q=x.Head->Next;

p!=this->Head || q!=x.Head;){

n=new NODE;

n->Next=y.Head;

r->Next=n;

r=n;

if(p->El>q->El){

n->El=q->El;

q=q->Next;

continue;

}

if(p->El<q->El){

n->El=p->El;

p=p->Next;

continue;

}

if(p->El==q->El){

n->El=p->El;

p=p->Next;

q=q->Next;

continue;

}

} // for

return y;

}

//------------------------------------

SETINLIST SETINLIST::operator -(const SETINLIST &x){

SETINLIST y;

NODE *p,*q,*r /* указатель на хвост результата */,*n;

r=y.Head;

for(p=this->Head->Next,q=x.Head->Next;p!=this->Head;){

if(p->El>q->El){

q=q->Next;

continue;

}

if(p->El<q->El){

n=new NODE;

n->Next=y.Head;

n->El=p->El;

r->Next=n;

r=n;

p=p->Next;

continue;

}

if(p->El==q->El){

p=p->Next;

continue;

}

} // for

return y;

}

//-------------------------------

SETINLIST::SETINLIST(const SETINLIST &a){

NODE *p,*q,*x;

this->Head=new NODE;

this->Head->El=INT_MAX;

this->Head->Next=this->Head;

for(p=a.Head->Next,q=this->Head;p!=a.Head;p=p->Next){

x=new NODE;

x->El=p->El;

x->Next=this->Head;

q->Next=x;

q=x;

}

}

//------------------------------------

SETINLIST& SETINLIST::operator=(const SETINLIST &x){

NODE *p,*q;

for(p=this->Head;p!=this->Head;){

q=p->Next;

delete p;

p=q;

}

this->Head->Next=Head;

for(q=this->Head,p=x.Head->Next;p!=x.Head;p=p->Next){

q=this->Insert(q);

q->El=p->El;

}

return *this;

}

Контрольные вопросы

1) Какие методы представления множеств вы знаете?

2) Почему целесообразно хранить элементы множества в массиве или в списке в сортированном порядке?

3) Дайте сравнительную оценку скорости выполнения теоретико-множественных операций для представления множества битовыми строками и списками.