Как реализовать набор?
Я хочу реализовать Набор в C. Это в порядке для использования связанного списка, при создании НАБОРА, или я должен использовать другой подход?
Как Вы обычно реализуете свой собственный набор (в случае необходимости).
Примечание: Если я буду использовать подход Связанного списка, то у меня, вероятно, будут следующие сложности для Набора моими операциями:
- init: O (1);
- уничтожьте: O (n);
- вставьте: O (n);
- удалите: O (n);
- объединение: O (n*m);
- пересечение: O (n*m);
- различие: O (n*m);
- ismember: O (n);
- issubset: O (n*m);
- setisequal: O (n*m);
O (n*m) кажется, может быть немного к большому специально для огромных данных... Существует ли способ реализовать мой более эффективный Набор?
5 ответов
В прошлом я использовал красно-черные деревья для создания наборов.
Вот временные сложности из статьи в Википедии.
Пробел O (n)
Поиск O (журнал n)
Вставить O (журнал n)
Удалить O (журнал n)
Существует множество способов реализации набора. Вот некоторые из них. Кроме MSDN есть очень хорошая статья об этом.
std :: set часто реализуется как красно-черное дерево: http : //en.wikipedia.org/wiki/Red-black_tree
Этот подход значительно повысит сложность всех перечисленных операций.
Наборы обычно реализуются либо в виде красно-черных деревьев (что требует, чтобы элементы имели общий порядок), либо в виде хэш-таблицы с автоматическим изменением размера (для чего требуется хеш-функция).
Последнее обычно реализуется путем увеличения размера хэш-таблицы в два раза и повторной вставки всех элементов при превышении определенного порога емкости (75% работает хорошо). Это означает, что отдельные операции вставки могут быть O (n), но при амортизации по многим операциям это фактически O (1).
Поскольку у вас уже реализован связанный список, самым простым является список пропуска . Если вы хотите использовать сбалансированные деревья, на мой взгляд, самый простой - это treap . Это рандомизированные структуры данных, но обычно они столь же эффективны, как и их детерминированные аналоги, если не больше (и список пропусков можно сделать детерминированным).