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