3.4. определение класса множества

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

Класс множества определим следующим образом:

//параметризированный класс множества

template <class Stype>

class Set

{

   Stype *SetPtr;              // указатель на первый элемент

   int MaxSize;                // максимальное число элементов

   int NumMembers;             // количество элементов множества

   void insert (Stype member); // добавление элемента

   void remove (Stype member); // удаление элемента

   int find(Stype member);     // поиск элемента

   int ismember (Stype member); // принадлежность элемента

public:

   Set();                      // конструкторы

   Set(int size);

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

   ~Set() { delete SetPtr; }   // деструктор

   Set <Stype> &operator = (Set <Stype> &ob); // присваивание

   Set <Stype> operator + (Stype member);     // добавление элемента

   friend Set<Stype> operator + (Stype member, Set <Stype> ob);

   Set <Stype> operator + (Set <Stype> &ob);  // объединение

   Set <Stype> operator - (Stype member);     // удаление элемента

   Set <Stype> operator - (Set <Stype> &ob);  // разность

   Set <Stype> operator & (Set <Stype> &ob);  // пересечение

// опреации сравнения

   int operator == (Set <Stype> &ob);         // 1 если равно

   int operator != (Set <Stype> &);             // 1 если не равно

   int operator < (Set <Stype> &ob);          // 1 если подмножество

   friend int operator < (Stype member, Set <Stype> ob);

                                                    // 1 если элемент множества

   operator int() {return NumMembers;} // преобразование в целое

// ввод - вывод

   friend istream &operator >> (istream &stream, Set<Stype> &ob);

   friend ostream &operator << (ostream &stream, Set<Stype> & ob);

};

Класс Set можно использовать для построения множеств объектов любого типа. Класс содержит три поля, содержащих данные: SetPtr, MaxSize и NumMembers. Область памяти для хранения элементов множества выделяется конструктором. Максимальное число элементов множества хранится в MaxSize. Количество элементов, содержащихся во множестве в текущий момент, равно NumMembers.Эти поля закрыты и доступны лишь для составных и дружественных функций класса, объявленных в теле класса.

Конструкторы. Первый конструктор без аргументов резервирует память для массива, состоящего из элементов, количество которых равно DEFSET. Значение DEFSET определяется с помощью внешней константы, например:

const int DEFSET = 100;

оно используется в конструкторе:

//параметризированный конструктор класса, вызываемый по умолчанию

template <class Stype>

Set <Stype>::Set()

{

   SetPtr = new Stype [DEFSET];                      //выделим память

   if(!SetPtr){ cout << "Нет памяти ";

         exit(1);

       }

   NumMembers = 0; MaxSize = DEFSET;

}

Для построения множества заданного размера будем использовать конструктор:

//параметризированный конструктор с заданным числом элементов

template <class Stype>

Set <Stype>::Set(int size)

{

   SetPtr = new Stype[size];                   //выделим память

   if(!SetPtr){                                          //не удалось

                           cout << "Нет памяти "; exit(1);

       }

   NumMembers = 0; MaxSize = size;

}

Поиск элемента. Приведём подпрограмму find поиска элемента и тест на принадлежность элемента множеству:

//закрытый член класса, обеспечивающий поиск элемента в множестве

template <class Stype>

int Set <Stype>::find(Stype member)

{

   int i;

   for (i = 0; i < NumMembers; i++)       //поиск во всем множестве

   if(SetPtr[i] == member) return i;

   return -1; // если такого элемента нет

}

//закрытый член класса, дающий ответ на вопрос:

//принадлежит ли переданное ему значение множеству

template <class Stype>

int Set <Stype>::ismember(Stype member)

{

   if (find(member) != -1) return 1;         //произведём поиск

   else return 0;                                        //не нашли

}

Функция find() возвращает индекс указанного элемента, если этот элемент принадлежит множеству. В противном случае она возвращает –1.

Добавление и удаление элементов. Приведём подпрограмму добавления (insert()) и удаления (remove()) элементов множества. 

//закрытый член класса, обеспечивающий добавление элемента во множество

template <class Stype>

void Set<Stype>::insert(Stype member)           // добавление

{

   if(NumMembers == MaxSize)            //проверим не переполнено ли множество

   {

               cout << " Переполнение множества"; exit(1);

}

if(!ismember(member))                // если нет такого элемента

{

               SetPtr[NumMembers] = member;       // добавить

               NumMembers++;                                // элементов стало на один больше

}

}

Аргументом этой подпрограммы служит новый элемент множества. Для удаления будем использовать закрытую функцию remove():

//закрытый член класса, обеспечивающий удаление заданного

//элемента множества

template <class Stype>

void Set<Stype>::remove(Stype member)

{

   int loc = find(member); //найдём элемент множества

   if(loc != -1)                  // если элемент найден

   {

               for(; loc < NumMembers -1; loc++)

               SetPtr[loc] = SetPtr[loc+1]; //сдвигаем множество

               NumMembers--;                                  //элементов на один стало меньше

}

}

Если такой элемент множества существует, то он удаляется путем сдвига элементов массива на одну позицию влево.

Конструктор копирования. Конструктор копирования класса вызывается каждый раз, когда выполняется копирование объектов, принадлежащих этому классу. В частности, он вызывается, когда объект передается функции по значению, при построении временного объекта как возвращаемого значения функции, а также при использовании объекта для  инициализации другого объекта. Если класс не содержит конструктора копирования, определенного явным образом, то в этом случае при возникновении одной из трех перечисленных выше ситуаций используется побитовое копирование объекта. Побитовое копирование не во всех случаях бывает адекватным. Именно для таких случаев необходимо определять собственный конструктор копирования.

Необходимость испльзования этого конструктора для класса Set вызвана тем, что область памяти для каждого множества выделяется с помощью операции new, а указатель на эту область памяти хранится в указателе SetPtr. При побитовом копировании указатель, содержащийся в переменной SetPtr копии, будет показывать на ту же область памяти, что и указатель SetPtr оригинала. Оба объекта для хранения будут показывать на одну и ту же область памяти. Поэтому изменение одного из объектов может повлечь за собой изменение другого. Если один из объектов будет удален, то область памяти будет освобождена, а эта же область памяти используется и другим объектом. Такие ситуации, как правило, приводят к аварийному завершению программы.

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

// Конструктор копирования

template <class Stype>

Set<Stype>::Set(const Set<Stype> &ob)

{

   int i;

   MaxSize = ob.MaxSize;

   SetPtr = new Stype[MaxSize];                       //выделим память

   if(!SetPtr)                                                        //если не удалось

   {

               cout << " Нет памяти для копирования";

               exit(1);

}

NumMembers = 0;

for(i=0; i < ob.NumMembers; i++)

   insert(ob.SetPtr[i]);                             //производим копирование

}

Конструктор копирования выделяет область память для копии, а затем копирует в новый объект каждый элемент исходного объекта. Указатели SetPtr исходного объекта и копии будут указывать на разные области памяти.

Операция присваивания. Если не определять операцию присваивания, то она будет осуществляться с помощью побитового копирования. В результате может получиться два объекта, использующие одну и ту же область памяти для хранения данных.

Во избежание этой ситуации операция присваивания должна просто переписать содержимое одного множества в другое, не изменяя при этом значения SetPtr каждого из этих множеств:

//операция присваивания

template <class Stype>

Set<Stype> &Set<Stype>::operator = (Set<Stype> &ob)

{

   int i;

   // обработка случая s = s

   if(SetPtr == ob.SetPtr) return *this;

   // проверяем число элементов

   if(ob.NumMembers > MaxSize)

   {

               delete SetPtr;                                      //сначала удалим множество

SetPtr = new Stype[ob.NumMembers];            //затем выделим память

                                                               //под новое множество

               if(!SetPtr)                                                        //если нет памяти

               {

                           cout << " Нет памяти для копирования"; exit(1);

}

MaxSize = ob.NumMembers;

}

NumMembers = 0;                                 // удаляем старое множество

for (i = 0; i < ob.NumMembers; i++)

insert(ob.SetPtr[i]);                    //производим копирование всех элементов

return *this;                               //возврат указателя на текущий экземпляр

//класса

}

Добавление элемента и построение объединения. Перегрузим операцию сложения для двух случаев. В первом случае эта операция обрабатывает ситуацию «множество плюс элемент».

//Операция добавления нового элемента в множество

template <class Stype>

Set<Stype> Set<Stype>::operator+(Stype member)

{

   int i;

   Set<Stype> temp(NumMembers+1);

   // копирование элементов во временное множество

   for(i = 0; i < NumMembers; i++)

               temp.insert(SetPtr[i]);

               temp.insert(member);

               return temp; // возврат нового множества

}

Во втором случае эта операция обрабатывает ситуацию «элемент плюс множество». Она определяется с помощью дружественной функции:

//Ещё одна сигнатура операции добавления

template <class Stype>

Set<Stype> operator+(Stype member, Set<Stype> ob)

{

   int i;

   Set<Stype> temp(ob.NumMembers + 1);

   // копирование элементов во временное множество

   for(i = 0; i < ob.NumMembers; i++)

               temp.insert(ob.SetPtr[i]);

   // вставка нового элемента

   temp.insert(member);

   return temp; // возврат нового множества

}

Перегрузим операцию `+` для объединения множеств:

//операция объединения двух множеств

template <class Stype>

Set<Stype> Set<Stype>::operator+(Set<Stype> &ob)

{

   int i;

   Set<Stype> temp(NumMembers+ob.NumMembers);

   for(i = 0; i < NumMembers; i++)

               temp.insert(SetPtr[i]);             //во временное множество копируем

//сначала первое множество

   for(i = 0; i < ob.NumMembers; i++)

               temp.insert(ob.SetPtr[i]);        //а затем второе

   return temp;                                         //возврат нового множества

}

Эта операция используется для выполнения операторов следующего типа:

set1 = set2 + set3;

где set1, set2, set3 – объекты класса set.  

Удаление элемента и разность множеств. Для удаления элемента определим операцию `-`:

//операция удаления элемента из множества

template <class Stype>

Set<Stype> Set<Stype>::operator-(Stype member)

{

   int i;

   Set<Stype> temp = *this;

   temp.remove(member); // удаление элемента

   return temp;         // возврат множества

}

Эта функция позволяет вычислять выражения set1 = set2 – item, где set1 и set2 - объекты класса set, а item – элемент из set2.

Перегрузим операцию вычитания для вычисления разности множеств:

//операция разности двух множеств

template <class Stype>

Set<Stype> Set<Stype>::operator-(Set<Stype> &ob)

{

   int i;

   Set<Stype> temp = *this;

   // удаляем элементы из *this, принадлежащие ob

   for(i = 0; i < NumMembers; i++)

               if(ob.ismember(SetPtr[i]))

                           temp.remove(SetPtr[i]);

   return temp; // возврат результата

}

Например, после выполнения оператора set1 = set2 – set3, множество set1 будет состоять из элементов  set2, не принадлежащих set3.

Пересечение множеств. Для обозначения пересечения будем использовать знак конъюнкции:

//Операция пересечения множеств

template <class Stype>

Set<Stype> Set<Stype>::operator& (Set<Stype> &ob)

{

   int i, j;

   Set<Stype> temp(NumMembers);

   for(i = 0; i < NumMembers; i++)

               if(ob.ismember(SetPtr[i]))

               temp.insert(SetPtr[i]); //вставляем в результат только

                                                               //те элементы, которые принадлежат и

                                                               //первому множеству,

//и второму

   return temp; // возврат результата

}

После выполнения операции set1 = set2 & set3 множество set1 будет содержать элементы из set2, одновременно принадлежащие set3.

Сравнение множеств. Равенство и неравенство для класса Set реализованы перегрузкой операций `==` и `!=`  :

// 1 - если множества равны

template <class Stype>

int Set<Stype>::operator == (Set<Stype> &ob)

{

   if(NumMembers != ob.NumMembers) return 0;

   // множества должны содержать одинаковое число элементов

   return *this < ob; // если первое содержится во втором, то равны

}

// проверка на неравенство

template <class Stype>

int Set<Stype>::operator !=(Set<Stype> &ob)

{

   return !(*this == ob);

}

// проверка на включение

template <class Stype>

int Set<Stype>::operator < (Set<Stype> &ob)

{

   int i;

   for(i = 0; i < NumMembers; i++)

               if(!ob.ismember(SetPtr[i])) return 0;

               // если SetPtr[i] не принадлежит ob

   return 1;

}

Проверка принадлежности. Операцию `<` перегрузим для определения принадлежности элемента множеству:

// 1 - если принадлежит

template <class Stype>

int operator < (Stype member, Set<Stype> ob)

{

   if ( ob.ismember(member) ) return 1;  //если есть такой элемент

   return 0;

}

Преобразование в целое. Преобразование объекта класса set в целое число возвращает число, равное количеству элементов, содержащихся в множестве на текущий момент. Если множество пусто, то возвращается нуль. Функция преобразования нужна для автоматического преобразования к другому, обычно встроенному, типу. Ее текст определен как inline-функция:

operatot int() {return NumMembers;}

Эта функция позволяет выполнять действия, подобные приведенным ниже:

if (set) cout << “Множество не пустое”;

cout << “set1 содержит” << (int) set1 << “ элементов”

Перегрузка операторов ввода-вывода. Определим операции ввода и вывода с помощью `>>` и `<<`, как дружественные функции:

// ввод

template <class Stype>

istream& operator >>(istream& stream, Set <Stype> &ob)

{

   Stype member;

   stream >> member; // ввод элемента

   ob = ob + member; // запись элемента в множество

   return stream;    // возврат результата

}

// вывод

template <class Stype>

ostream &operator << (ostream &stream, Set<Stype> &ob)

{

   int i;

   for(i = 0; i < ob.NumMembers; i++)   //для всех элементов

   stream << ob.SetPtr[i] << ' ';   //вывод

   stream << endl;                                               //после вывода всех элементов

                                                                           //перевод строки

   return stream;

}

Приведём пример программы, использующей параметризованный класс множества:

#include <iostream.h>               //библиотека потокового ввода-вывода

#include <conio.h>                                //библиотека консольного ввода-вывода

#include <process.h>                 //необходимо для функции exit

const int DEFSET = 100;

template <class Stype>

class Set

{

   Stype *SetPtr;              // указатель на первый элемент

   int MaxSize;                // максимальное число элементов

   int NumMembers;             // количество элементов множества

   void insert (Stype member); // добавление элемента

   void remove (Stype member); // удаление элемента

   int find(Stype member);     // поиск элемента

   int ismember (Stype member); // принадлежность элемента

public:

   Set();                      // конструкторы

   Set(int size);

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

   ~Set() { delete SetPtr; }   // деструктор

   Set <Stype> &operator = (Set <Stype> &ob); // присваивание

   Set <Stype> operator + (Stype member);     // добавление элемента

   friend Set<Stype> operator + (Stype member, Set <Stype> ob);

   Set <Stype> operator + (Set <Stype> &ob);  // объединение

   Set <Stype> operator - (Stype member);     // удаление элемента

   Set <Stype> operator - (Set <Stype> &ob);  // разность

   Set <Stype> operator & (Set <Stype> &ob);  // пересечение

// операции сравнения

   int operator == (Set <Stype> &ob);         // 1 если равно

   int operator != (Set <Stype> &);             // 1 если не равно

   int operator < (Set <Stype> &ob);          // 1 если подмножество

   friend int operator < (Stype member, Set <Stype> ob);

                                                    // 1 если элемент множества

   operator int() {return NumMembers;} // преобразование в целое

// ввод - вывод

   friend istream &operator >> (istream &stream, Set<Stype> &ob);

   friend ostream &operator << (ostream &stream, Set<Stype> & ob);

};

//параметризованный конструктор класса, вызываемый по умолчанию

template <class Stype>

Set <Stype>::Set()

{

   SetPtr = new Stype [DEFSET];                      //выделим память

   if(!SetPtr){ cout << "Нет памяти ";

         exit(1);

       }

   NumMembers = 0; MaxSize = DEFSET;

}

//параметризованный конструктор с заданным числом элементов

template <class Stype>

Set <Stype>::Set(int size)

{

   SetPtr = new Stype[size];                   //выделим память

   if(!SetPtr){                                          //не удалось

                           cout << "Нет памяти "; exit(1);

       }

   NumMembers = 0; MaxSize = size;

}

//закрытый член класса, обеспечивающий поиск элемента в множестве

template <class Stype>

int Set <Stype>::find(Stype member)

{

   int i;

   for (i = 0; i < NumMembers; i++)       //поиск во всем множестве

   if(SetPtr[i] == member) return i;

   return -1; // если такого элемента нет

}

//закрытый член класса, дающий ответ на вопрос:

//принадлежит ли переданное ему значение множеству

template <class Stype>

int Set <Stype>::ismember(Stype member)

{

   if (find(member) != -1) return 1;         //произведём поиск

   else return 0;                                        //не нашли

}

//закрытый член класса обеспечивающий добавление элемента в множество

template <class Stype>

void Set<Stype>::insert(Stype member)           // добавление

{

   if(NumMembers == MaxSize)            //проверим, не переполнено ли множество

   {

               cout << " Переполнение множества"; exit(1);

}

if(!ismember(member))                // если нет такого элемента

{

               SetPtr[NumMembers] = member;       // добавить

               NumMembers++;                                // элементов стало на один больше

}

}

//закрытый член класса, обеспечивающий удаление заданного

//элемента множества

template <class Stype>

void Set<Stype>::remove(Stype member)

{

   int loc = find(member); //найдём элемент множества

   if(loc != -1)                  // если элемент найден

   {

               for(; loc < NumMembers -1; loc++)

               SetPtr[loc] = SetPtr[loc+1]; //сдвигаем множество

               NumMembers--;                                  //элементов на один стало меньше

}

}

// Конструктор копирования

template <class Stype>

Set<Stype>::Set(const Set<Stype> &ob)

{

   int i;

   MaxSize = ob.MaxSize;

   SetPtr = new Stype[MaxSize];                       //выделим память

   if(!SetPtr)                                                        //если не удалось

   {

               cout << " Нет памяти для копирования";

               exit(1);

}

NumMembers = 0;

for(i=0; i < ob.NumMembers; i++)

   insert(ob.SetPtr[i]);                             //производим копирование

}

//операция присваивания

template <class Stype>

Set<Stype> &Set<Stype>::operator = (Set<Stype> &ob)