Множество как объект

Если некоторая структура данных, например массив, используется как реализация множества, это означает, что программист просто устанавливает для себя некоторые правила для работы с этим массивом и последовательно их придерживается. Часто большего и не требуется. Однако можно рассматривать множество как абстрактную структуру данных — область памяти, доступ к которой возможен только через некоторый интерфейс, т. е. набор функций, специально созданных для работы с этой памятью. Язык С++ поддерживает работу с абстрактными данными через механизм классов: абстрактная структура данных определяются как класс, в котором задаются как данные, так и связанные с ними операции. Определение класса позволяет расширить язык C++, включив в него множество как пользовательский тип данных.

Рассмотрим пример — класс для работы с множеством, представленным массивом символов (строкой):

class Set {

private: // Закрытая часть класса — данные

static int N; // мощность универсума

int n; // мощность множества

char S, *A; // тег и память для множества

public: // Открытая часть — функции для работы с множеством

Set operator | (const Set&) const; // объединение

Set operator & (const Set&) const; // пересечение

Set operator ~ () const; // дополнение до универсума

void Show(); // вывод множества на экран

int power() { return n; } // получение мощности

Set(char); // конструктор множества

Set(); // ещё конструктор — по умолчанию

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

Set operator = (const Set &); // оператор присваивания

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

};

Имя класса Set — это имя нового типа данных. С его помощью мы будем объявлять в программе множества-объекты.

Память для множества находится в закрытой части класса и доступна через член A — указатель на символы. Размер памяти не определён. Кроме этого, в закрытую часть помещены вспомогательные переменные-члены: мощность универсума N, текущая мощность множества n и символ-тег S, с помощью которого мы сможем различать объекты-множества. Мощность универсума N объявлена со спецификатором «static». Это означает, что все объекты класса Set будут использовать единственную копию этой переменной. Переменная N быть дополнительно объявлена вне всех функций, чтобы ей была выделена память. При этом требуется установить и её значение:

int Set ∷ N = 26; // Мощность универсума для множества латинских букв.

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

Для работы с множествами-массивами предполагается использовать такой же синтаксис, как для машинных слов. С этой целью функции объединения, пересечения и дополнения множеств объявлены с именами, содержащими ключевое слово «operator», после которого следует знак соответствующей операции. Операции языка С++ «|», «&» и «~» определены так, чтобы их можно было использовать в выражениях, состоящих из данных типа Set. Такой приём называется перегрузкой операций. Чтобы эти операции действительно можно было использовать в выражениях, функции объявлены так, чтобы была обеспечена совместимость со встроенными операциями языка С++: все функции возвращают объект типа Set, а двуместные операции в качестве аргумента (второго, потому что первый — это сам объект) имеют константную ссылку на объект типа Set. Функции не меняют объект, для которого вызываются. Для контроля за этим в каждом из объявлений после списка параметров помещён спецификатор «const».

Вот так может выглядеть определение двуместной операции «пересечение»:

Set Set:: operator & (const Set & B) const

{ Set C;

for (int i = 0; i < n; i++) {

for (int j = 0; j < B.n; j++)

if (A[ i ] == B.A[ j ]) C.A[ C.n++ ] = A[ i ];

}

C.A[C.n ] = 0; // ограничитель строки

return C;

}

Функции объявляется множество «C», которое конструктор по умолчанию оставляет пустым. Затем в нём формируется результат пересечения основного объекта и множества «B». Поскольку для этого используется двойной цикл по мощности множеств, временная сложность операции — квадратичная.

Операция объединения множеств «|» реализуется похожим алгоритмом:

Set Set:: operator | (const Set & B) const

{ Set C;

memcpy(C.A, A, n); C.n = n;

for(int i = 0; i < B.n; i++) {

int f = 1;

for (int j = 0; j < n; j++)

if (B.A[ i ] == A[ j ]) f = 0;

if (f) C.A[ C.n++ ] = B.A[ i ];

}

C.A[ C.n ] = 0;

return C;

}

В результат копируются элементы исходного множества, затем в него добавляются недостающие элементы из «B».

Операция вычисления дополнения может быть реализована так:

Set Set:: operator ~ () const

{ Set C;

for (char c = 'A'; c <= 'Z'; c++) {

int f = 1;

for (int j = 0; j < n; j++)

if (c == A[ j ]) { f = 0; break; }

if (f) C.A[ C.n++ ] = c;

}

C.A[ C.n ] = 0;

return C;

}

Здесь в качестве одного из операндов выступает множество-универсум. Результат — элементы универсума, которых нет в исходном множестве.

Поскольку количество повторений цикла по элементам универсума постоянно, временная сложность операции — O (n). Однако, если учесть, что мощность универсума не может быть меньше мощности его подмножеств: |U| ≥ n,более точной будет оценка O (|U| ^. n), более пессимистическая по сравнению с O (n²).

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

void Set:: Show()

{ cout << ‘\n’ << S << " = [" << A << "]"; }

Для определения мощности множества нужна специальная функция power(). Эта функция просто возвращает значение закрытой переменной n, в которой другие функции поддерживают значение текущей мощности множества. Поскольку функция не только объявлена, но и определена внутри класса, она по умолчанию является встроенной. К объявлению функции неявно добавляется спецификатор «inline». Это означает, что никакой функции не создаётся, вместо этого в каждую точку вызова просто подставляется значение закрытой переменной n. Таким образом, запрет на доступ к n обходится без всяких дополнительных расходов на вызов функции.

Все функции-члены, кроме перечисленных ранее, объявлять и определять не обязательно, компилятор делает это автоматически. Но в данном случае автоматически определяемые функции не подходят.

Так, при создании объекта класса Set выделяется память, после чего вызывается функция-конструктор Set(). По умолчанию эта функция — пустая, она ничего с памятью не делает, и использовать такой объект невозможно. Поэтому конструктор надо определить явно. Сделаем так, чтобы он создавал пустое множество латинских букв, представленное строкой символов:

Set:: Set(): n(0), S ('0')

{ A = new char[ N+1 ]; A[ 0 ] = 0; }

В этом примере одни переменные инициализируются в заголовке, другие — в теле конструктора. Оба способа можно комбинировать произвольным образом, но нужно учитывать, что порядок инициализации переменных полностью определяется порядком их объявления в классе и не может быть изменён. В данном примере значение переменной N используется для создания строки A, поэтому важно, что переменная N объявлена в классе раньше, чем указатель A. Массив символов объявляется на 1 символ длиннее мощности универсума, чтобы резервировать место под ограничивающий нуль. Поскольку строка должна быть пустой, ограничивающий нуль записывается в её начало. Инициализировать остальную часть массива не обязательно.

Если требуется иметь несколько способов создания объекта, для каждого способа объявляется свой конструктор, отличающийся от других типом и/или количеством аргументов. В примере объявлен конструктор с одним символьным аргументом. Это может быть конструктор, генерирующий случайную строку латинских букв. Аргумент используется для инициализации тега. С помощью датчика случайных чисел генерируется N битов, и для каждого единичного бита соответствующий ему элемент добавляется в множество. Одновременно подсчитывается фактическая мощность множества n. По окончании генерации в строку добавляется ограничитель. Сгенерированное множество выводится на экран.

Set:: Set(char s): S(s), n(0)

{ A = new char[ N+1 ];

for (int i = 0; i < N; i++)

if (rand() % 2) A[ n++ ] = i + 'A';

A[n]=0;

cout << ‘\n’ << S << " = [" << A << "]";

}

Следующие две функции-члена — конструктор копирования и перегрузку присваивания — определяют редко. Дело в том, что обе эти функции по умолчанию копируют один объект в другой по принципу «байт в байт». Если ничего другого не требуется, определять эти функции не нужно, так как компилятор наверняка сделает это лучше. В данном же случае такое копирование не годится, потому что в классе есть указатель на дополнительную память, и копирование приведёт к тому, что указатели A в обоих объектах будут указывать на одну и ту же строку.

Конструктор копирования имеет единственный аргумент — константную ссылку на объект того же класса. Определить конструктор можно так:

Set:: Set(const Set & B)

{ N = B.N; S = B.S; n = B.n;

A = new char[N+1];

memcpy(A, B.A, N+1);

}

Здесь переменные N, S и n копируются обычным способом, а для указателя A создаётся новая строка, куда затем копируется содержимое старой.

Функция-член для перегрузки присваивания отличается от копирования тем, что объект в левой части оператора уже существует. Более того, он может совпадать с аргументом (самоприсваивание). Поэтому первое, что функция должна сделать — проверить это. Затем текущий объект уничтожается и создаётся новый. В данном случае это делать не надо, можно ограничиться просто переносом содержимого строки в имеющуюся память. Поскольку результат операции присваивания может быть использован в выражении, например в цепочке присваиваний, функция должна возвращать значение объекта, для которого она вызвана. Это делается с помощью встроенного указателя «this». Копировать тег нет смысла: устанавливается некоторое условное значение «R» (от слова «result»).

Set Set:: operator = (const Set& B)

{ if (this!= &B)

{ N = B.N; memcpy(A, B.A, N+1); S = 'R'; }

return *this;

}

Конструктор копирования используется при инициализации объекта содержимым другого объекта в момент объявления, а также при передаче аргумента в функцию как параметра по значению и при возврате объекта как результата работы функции. Функция перегрузки присваивания вызывается соответствующим оператором. Бывают ситуации, когда эти функции в программе не нужны. Чтобы исключить трудно выявляемую ошибку в программе из-за использования функций по умолчанию, рекомендуется объявить ненужные функции в закрытой части класса. Можно даже не определять их. Невольное создание в программе ситуации, когда такая функция вызывается, будет ошибкой, выявляемой компилятором.

Последняя функция-член в объявлении класса — это деструктор, который автоматически вызывается при уничтожении объекта. В нём указано дополнительное действие, которое нужно выполнить перед освобождением памяти из-под объекта: уничтожить строку A. Поскольку деструктор определён внутри класса, он, как и power(), тоже является встроенной функцией. Впрочем, для деструктора это не важно. Его всё равно нельзя использовать как обычную функцию, например получить его адрес. Деструктор вызывается явно в операторе «delete» или неявно — при выходе из блока, в котором объект был определён. Объекты уничтожаются в порядке, обратном порядку их создания.

Программа, использующая объекты класса Set (программа-клиент), может выглядеть так:

#include <string.h>

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <time.h>

#include <iostream>

using namespace std;

#include "Set.h"

int Set ∷ N = 26; // определение статического члена класса

const long q0 = 100000; // количество повторений цикла времени

void main()

{ srand(time(NULL));

Set A('A'), B('B'), C('C'), D('D'), E;

clock_t begin = clock();

for(long q =0; q < q0; q++)

{ E = (A | B) & (C & ~D); }

clock_t end = clock();

E.Out();

cout << " Middle power =" <<

(A.power() + B.power() + C.power() + D.power() + E.power()) / 5 <<

" Time=" << end – begin<< " / " << q0;

_getch();

}

В программе определяются пять множеств. Для исходных множеств A, B, C и D используется конструктор, генерирующий случайное множество с выводом на экран результата. Множество E генерируется конструктором по умолчанию как пустое. Затем множество вычисляется с использованием перегруженных операций, и результат выводится на экран. Далее вычисляются и выводятся средняя мощность всех множеств и время решения задачи.

Объявление класса Set и определения всех функций-членов находятся в подключаемом модуле «Set.h». Определение статического члена — переменной N — помещено сразу после модуля. На самом деле оно является его частью. В самой программе никакой информации об устройстве модуля «Set.h» не имеется. Чтобы использовать другой способ хранения множеств в памяти, достаточно просто подменить модуль.

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

Результат работы программы может выглядеть так:

1.5.1. Практикум по теме

Преобразовать ранее созданные программы так, множества были объектами некоторого класса, а операции над ними — методами этого класса. Сделать по крайней мере два варианта программы с разными способами представления множеств в памяти, например, с помощью массивов элементов и с помощью списков. Добиться, чтобы функция main() во всех вариантах была одинакова.

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

1. Какую выгоду можно получить от применения объектов в программе обработки множеств?

2. Как влияет применение объектов на время выполнения программы

1.6. Отчёт по теме

По теме должен быть оформлен сводный отчёт следующего содержания:

1. Задание на обработку множеств.

2. Формализация задания.

3. Контрольные тесты.

4. Временная сложность (ожидаемая и фактическая) для четырёх способов представления множеств.

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

6. Выводы о результатах испытания способов представления множеств в памяти и рекомендации по их применению в программах для ЭВМ.

7. Список использованных источников (при ссылке на конспект лекций — указать тему и дату: «Способы представления множеств в памяти ЭВМ // Алгоритмы и структуры данных. — Лекция от 03.09.2013. Если использовалась помощь товарища — указать это: студент Петров А. В. Частное сообщение).

8. Приложение: исходные тексты всех программ (на машинном носителе).