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

Ответ 1

Существует несколько способов реализации функций набора (и карты), например:

• древовидный подход (упорядоченный обход)
• хэш-подход (неупорядоченный обход)

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

Остерегайтесь преимуществ и недостатков основанных на хеше или на основе дерева подходов.

Вы можете создать хэш-набор (специальный случай хеш-таблицы) указателей на хеширование POD s, цепочка, внутренне представленная как фиксированный размер массив ведер hashables, где:

• все hashables в ведре имеют одинаковое значение хеша
• ведро может быть реализовано как динамический массив или связанный список хэш-записей
• hashable hash value используется для индексации в массив ведер (массив с индексом хеш-значений)
• одна или несколько из хэш-записей, содержащихся в хэш-наборе, могут быть (указателем на) другим хеш-множеством или даже самим хэш-множеством (т.е. самосоединение возможно)

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

Вам нужно будет реализовать:

• хэш-функция для хэша типа
• функция равенства для типа, используемого для проверки того, равны ли две хэш-строки или нет
• функция хеш-набора contains/insert/remove.

Вы также можете использовать открытую адресацию в качестве альтернативы поддержанию и управлению ковшими.

Ответ 2

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

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

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

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

Ответ 3

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

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

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

Ответ 4

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

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

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

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

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