1. Способы реализации множества

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

Помимо встроенных средств языка, разработчик может написать собственную реализацию типа «множество» (например, используя записи record ). Для простых типов данных, таких как символы (char), на практике чаще всего применяются два основных подхода: на основе логического и на основе символьного массива.

1. Реализация на основе логического (булевского) массива

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

• Принцип хранения: Создается одномерный массив логического типа (например, boolean), где индексы массива соответствуют всем возможным элементам множества. Если элемент присутствует в множестве, по его индексу хранится значение True. Если отсутствует — False.
• Применение к символам: Универсум типа char обычно составляет 256 символов (коды от 0 до 255). Для такого множества выделяется массив из 256 логических элементов.
• Сложность операций:
• Добавление элемента: Константное время $O(1)$. Достаточно напрямую обратиться по индексу символа и присвоить True (например, SetArr['A'] := True).
• Удаление элемента: Константное время $O(1)$ путем присвоения False.

• Проверка принадлежности: Константное время $O(1)$ (например, if SetArr['A'] = True).

• Преимущества: Максимальная скорость выполнения всех базовых операций.

• Недостатки: Неэффективный расход памяти при разреженных множествах (если универсум огромен, а хранится всего пара элементов, память всё равно выделяется под весь универсум).

2. Реализация на основе символьного массива

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

• Принцип хранения: Создается структура (например, запись record ), которая включает сам символьный массив для хранения данных и целочисленную переменную-счетчик, указывающую на текущее количество элементов в множестве.

• Сложность операций (например, при вызове процедуры add ):

• Проверка принадлежности: Требует линейного поиска по массиву (от первого до последнего добавленного элемента). Время выполнения — $O(N)$, где $N$ — текущее количество элементов в множестве.

• Добавление элемента: Сначала выполняется проверка принадлежности. Если символа в массиве еще нет, он записывается в первую свободную ячейку (в конец массива), а счетчик элементов увеличивается на 1. Общее время — $O(N)$ из-за необходимости проверки дубликатов.

• Удаление элемента: Выполняется поиск удаляемого символа. Если он найден, на его место копируется последний элемент из массива, а счетчик уменьшается на 1 (это позволяет избежать долгого сдвига всех остальных элементов). Время поиска — $O(N)$.

• Преимущества: Позволяет экономить память, если универсум элементов очень велик, а фактический размер множества мал. Также такой подход удобен, если нужно быстро перебрать (вывести) все существующие элементы множества, не проверяя пустые слоты.

• Недостатки: Существенное падение производительности ($O(N)$) при добавлении, поиске и удалении по мере увеличения количества элементов в множестве.