Реализация множеств при помощи последовательностей

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

В основе реализации множества, приведенной ниже, лежит введенная ранее реализация односвязных списков:

#include "integer_set.hpp"

#include "integer_list.hpp"

#include <cassert>

// Структура-множество

structIntegerSet

{

// Внутренний список с данными

IntegerList m_data;

};

// Создание объекта-множества

IntegerSet * IntegerSetCreate ()

{

// Создаем объект-множество в динамической памяти

IntegerSet * pSet = newIntegerSet;

// Инициализируем внутренний список

IntegerListInit( pSet->m_data );

// Возвращаем объект во внешний код

returnpSet;

}

// Уничтожение объекта-множества

voidIntegerSetDestroy ( IntegerSet * _pSet )

{

// Освобождаем ресурсы внутреннего списка

IntegerListDestroy( _pSet->m_data );

// Уничтожаем сам объект-множество

delete_pSet;

}

// Очистка множества

voidIntegerSetClear ( IntegerSet & _set )

{

// Очищаем внутренний список

IntegerListClear( _set.m_data );

}

// Проверка множества на пустоту

boolIntegerSetIsEmpty ( constIntegerSet & _set )

{

// Множество пусто, когда пуст внутренний список

returnIntegerListIsEmpty( _set.m_data );

}

// Возврат количества элементов в множестве

intIntegerSetSize ( constIntegerSet & _set )

{

// Равно размеру внутреннего списка

returnIntegerListSize( _set.m_data );

}

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

boolIntegerSetHasKey ( constIntegerSet & _set, int_key )

{

// Осуществляем поиск ключа с начала списка методом полного перебора

IntegerList::Node * pNode = _set.m_data.m_pFirst;

while( pNode )

{

if( pNode->m_value == _key )

// Ключ найден

return true;

pNode = pNode->m_pNext;

}

// Ключ не найден

return false;

}

// Вставка ключа во множество

voidIntegerSetInsertKey ( IntegerSet & _set, int_key )

{

// Если ключа еще нет во внутреннем списке, его следует вставить в конец списка

if( ! IntegerSetHasKey( _set, _key ) )

IntegerListPushBack( _set.m_data, _key );

}

// Удаление указанного ключа из множества

voidIntegerSetRemoveKey ( IntegerSet & _set, int_key )

{

// Ищем существующий узел с таким ключом

IntegerList::Node * pNode = _set.m_data.m_pFirst;

while( pNode )

{

if( pNode->m_value == _key )

{

// Удаляем найденный узел и завершаем процедуру

IntegerListDeleteNode( _set.m_data, pNode );

return;

}

pNode = pNode->m_pNext;

}

// Ошибка - ключа не существует в данном множестве!

assert( !"Key is unavailble!" );

}

// Вспомогательная функция, копирущая все элементы входного множества в другое

voidIntegerSetInsertAllKeys ( constIntegerSet & _sourceSet, IntegerSet & _targetSet )

{

// Перебираем все элементы исходного множества

IntegerList::Node * pNode = _sourceSet.m_data.m_pFirst;

while( pNode )

{

// Вставляем очередной ключ в целевое множество и движемся далее

IntegerSetInsertKey( _targetSet, pNode->m_value );

pNode = pNode->m_pNext;

}

}

// Объединение двух множеств - результат в третьем множестве

voidIntegerSetUnite ( constIntegerSet & _set1,

constIntegerSet & _set2,

IntegerSet & _targetSet )

{

// Очищаем целевое множество

IntegerSetClear( _targetSet );

// Копируем все элементы первого множества

IntegerSetInsertAllKeys( _set1, _targetSet );

// Копируем все элементы второго множества.

// Функция вставки ключа гарантирует,

// что повторяющиеся значения будут игнорироваться

IntegerSetInsertAllKeys( _set2, _targetSet );

}

// Пересечение двух множеств - результат в третьем множестве

voidIntegerSetIntersect ( constIntegerSet & _set1,

constIntegerSet & _set2,

IntegerSet & _targetSet )

{

// Очищаем целевое множество

IntegerSetClear( _targetSet );

// Перебираем все элементы первого множества

IntegerList::Node * pNode = _set1.m_data.m_pFirst;

while( pNode )

{

// Если выбранный элемент первого множества существует во втором,

// то вставляем его в целевое множество

if( IntegerSetHasKey( _set2, pNode->m_value ) )

IntegerSetInsertKey( _targetSet, pNode->m_value );

pNode = pNode->m_pNext;

}

}

// Разность двух множеств - результат в третьем множестве

voidIntegerSetDifference ( constIntegerSet & _set1,

constIntegerSet & _set2,

IntegerSet & _targetSet )

{

// Очищаем целевое множество

IntegerSetClear( _targetSet );

// Перебираем все элементы первого множества

IntegerList::Node * pNode = _set1.m_data.m_pFirst;

while( pNode )

{

// Если выбранный элемент первого множества НЕ существует во втором,

// то вставляем его в целевое множество

if( ! IntegerSetHasKey( _set2, pNode->m_value ) )

IntegerSetInsertKey( _targetSet, pNode->m_value );

pNode = pNode->m_pNext;

}

}

// Симметрическая разность двух множеств - результат в третьем множестве

voidIntegerSetSymmetricDifference ( constIntegerSet & _set1,

constIntegerSet & _set2,

IntegerSet & _targetSet )

{

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

IntegerSet * pTemp1 = IntegerSetCreate();

IntegerSetDifference( _set1, _set2, * pTemp1 );

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

IntegerSet * pTemp2 = IntegerSetCreate();

IntegerSetDifference( _set2, _set1, * pTemp2 );

// Объединяем результирующие множества

IntegerSetUnion( * pTemp1, * pTemp2, _targetSet );

// Освобождаем ресурсы временных множеств

IntegerSetDestroy( pTemp1 );

IntegerSetDestroy( pTemp2 );

}