C - Как реализовать структуру данных Набора?

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

Затем у вас есть простая проверка членства в наборе: бит n равен 1, если элемент n находится в наборе. Вы даже можете считать «обычные» члены от 1 и сделать бит 0 равным 1 только в том случае, если набор содержит сам себя.

Этот подход, вероятно, потребует какой-либо другой структуры данных (или функции) для преобразования из типа данных-члена в позицию в битовом массиве (и обратно), но он выполняет базовые операции над набором (объединение, пересечение, проверка принадлежности , разница, вставка, удаление, принуждение) очень очень просто. И он подходит только для относительно небольших наборов, вы не захотите использовать его для наборов 32-битных целых чисел, я не думаю.

Способ получения общности в C - void *, поэтому вы в любом случае будете использовать указатели, а указатели на разные объекты уникальны. Это означает, что вам нужна хэш-карта или двоичное дерево, содержащее указатели, и это будет работать для всех объектов данных.

Недостатком этого является то, что вы не можете вводить r-значения независимо. Вы не можете иметь набор, содержащий значение 5; вы должны присвоить 5 переменной, что означает, что она не будет соответствовать случайному 5. Вы можете ввести его как (void *) 5, и для практических целей это, вероятно, будет работать с небольшими целыми числами, но если ваши целые числа могут иметь достаточно большие размеры, чтобы конкурировать с указателями, вероятность неудачи очень мала.

Это также не работает со строковыми значениями. Учитывая char a[] = "Hello, World!"; char b[] = "Hello, World!";, набор указателей найдет a и b разными. Вы, вероятно, захотите хэшировать значения, но если вы обеспокоены коллизиями хэшей, вам следует сохранить строку в наборе и выполнить strncmp() для сравнения сохраненной строки со строкой зондирования.

(Аналогичные проблемы возникают и с числами с плавающей точкой, но пытаться представлять числа с плавающей точкой в наборах - изначально плохая идея.)

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

Наборы обычно реализуются в виде некоторой разновидности двоичного дерева . Красно-черные деревья имеют хорошие характеристики в худшем случае.

Их также можно использовать для построения карты , чтобы разрешить поиск ключей / значений.

Этот подход требует определенного порядка элементов набора и ключевых значений на карте.

Я не уверен, как вы будете управлять набором, который может содержать себя, используя двоичные деревья, если вы ограничиваете членство в наборе четко определенными типами в C ... сравнение между такими конструкциями может быть проблематичным. Впрочем, на C ++ это можно сделать достаточно легко.