Множества

Для представления конечных множеств могут быть использованы битовые строки, массивы, линейные списки или деревья.

При использовании битовых строк, каждое множество представляется последовательностью битов, длина которой равна числу элементов в универсальном множестве, то есть в множестве всех возможных элементов. Равенство единице j-го бита строки означает, что элемент с номером j входит в множество. Теоретико-множественные операции над множествами, представ­ленными последовательностями битов, выполняются как побитовые булевы операции. Так, пересечению множеств соответствует конъюнкция, объедине­нию – дизъюнкция, разности x-y, где x,y – множества, соответствует побитовая операция .

Структура данных для множества, хранящегося в массиве, может быть следующей:

const int MAXSIZE=100;

struct SETINARRAY {

int nElem; // число элементов в множестве

int Elem[MAXSIZE]; // элементы множества

};

Здесь предполагается, что элементы множества – целые числа, однако они могут быть любого типа. Элементы в множестве сортированы – это позво­ляет реализовать теоретико-множественные операции как однопроходные. Два этих представления имеют существенный недостаток:

- в первом случае фиксируется объем универсального множества

- во втором – максимально возможное количество элементов в множестве.

Кроме того, если количество элементов в множестве в среднем невелико, то память используется нерационально. От этих недостатков свободно представ­ление множества линейным списком. Ниже приведено определение класса SETINLIST.

#ifndef _SETINLIST_H

#define _SETINLIST_H

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

struct NODE{ // узел списка

int Element; // номер элемента множества

NODE *Next; // указатель на следующий элемент множества

};

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

class SETINLIST{

private:

NODE *Head;

NODE *Insert(NODE *p); // вставка узла после p

void Delete(NODE *p); // удаление узла вслед за p

public:

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) Дайте сравнительную оценку скорости выполнения теоретико-множественных операций для представления множества битовыми строками и списками.

Дата добавления: 2014-12-08