1. Множества

Множество — абстрактная структура данных, для которой определена операция принадлежности. Новые множества создаются из существующих с помощью операций объединения, пересечения, разности, симметрической разности.

1. Представление множества набором элементов

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

Пример. Объявление и инициализация массива для множества десятичных цифр.

сonst int Nmax = 10;

char A[ Nmax+1 ] = {'1', '3', '4', '7', '\0'};

В память, выделяемую под универсум, помещено множество-константа. Множество символов предполагается обрабатывать как строку, поэтому пришлось позаботиться об ограничивающем нуле. Если множество расширяться не будет, размер памяти можно не указывать:

char A[ ] = {"1347"};

Выделяется память под множество из четырёх элементов и ограничивающий нуль.

Мощность множества, заданного константой, рекомендуется вычислять:

int nA = strlen(A);

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

Таких проблем нет, если для представления множества в памяти используется односвязный список. Память в этом случае выделяется под каждый элемент множества отдельно, и её ровно столько, сколько необходимо. Так, под пустое множество-список память вообще не выделяется. Память от удаляемых элементов списка легко использовать под вновь создаваемые элементы. Перенос элемента из одного множества в другое вообще не требует дополнительной памяти.

Главный недостаток способа — необходимость хранить с каждым элементом множества указатель на следующий элемент и тратить время на работу с ним. Так, создание копии списка в другом месте памяти требует не только отдельной обработки каждого элемента множества, но и создания вновь всех указателей. Имеются и скрытые потери: минимальная область, выделяемая в динамической памяти, часто больше, чем требуется для хранения одного элемента множества вместе с указателем.

Реализация алгоритмов для работы с множествами, представленным массивами или списками, отличается только способом перебора этих структур данных. Подтвердим это примером реализации операции принадлежности элемента множеству десятичных цифр.

Для массива используем объявление из предыдущего примера. Множество-список объявим так:

struct Set{ char el;

Set * next;

}

Set *LA; // Указатель на начало списка для множества A.

Результатом вычислений будет значение булевской переменной b.

bool b = false;

char s = getche( ); // Символ вводится с клавиатуры

for (int i = 0; i < nA; i++) // Вариант 1: перебор элементов массива

if (A[i] == s) b = true;

for (Set * p = LA; p; p = p->next) //Вариант 2: просмотр списка

if (p->el == s) b = true;

Очевидно, что оба варианта реализации имеют линейную временную сложность по мощности множества: O(nA). Оценка не меняется и в том случае, если при обнаружении элемента в множестве цикл прерывается.