Как реализовать набор?

Question

Я хочу реализовать набор в C. Можно ли использовать связанный список при создании SET или использовать другой подход?

Как вы обычно реализуете ваш собственный набор (при необходимости).

ПРИМЕЧАНИЕ: Если я использую Linked подход List, я, вероятно, имеют следующие сложности для набора моих операций:

• INIT: O (1);
• уничтожить: O (n);
• Вставка: O (n);
• удалить: O (n);
• объединение: O (n * m);
• пересечение: O (n * m);
• разница: O (n * m);
• Участник: O (n);
• issubset: O (n * m);
• setisequal: O (n * m);

O (n * m) кажется, может быть немного большим, особенно для огромных данных ... Есть ли способ реализовать мой набор более эффективным?

Answer 1

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

Ниже приведены временные сложности, внесенные в статью Википедии.

Space O (п)
Поиск O (журнал N)
Вставьте O (журнал N)
Удалить O (Log п)

Answer 2

std::set часто реализуется в виде красного черного дерева: http://en.wikipedia.org/wiki/Red-black_tree

Такой подход даст вам гораздо лучше сложности на всех перечисленных операций.

Answer 3

Существует множество способов реализации набора. Here - некоторые из них. Кроме того, у MSDN есть очень хорошая статья.

Answer 4

Поскольку у вас уже есть связанный список реализован, самый простой a skip list. Если вы хотите использовать сбалансированные деревья, самым простым на мой взгляд является treap. Это рандомизированные структуры данных, но в целом они столь же эффективны, как и их детерминированные коллеги, если не больше (и список пропусков можно сделать детерминированным).

Answer 5

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

Последний, как правило, реализуется за счет того, что хэш-таблица имеет двойной размер и повторное вставку всех элементов, когда превышен определенный порог производительности (75% работает хорошо). Это означает, что inidividual операции вставки могут быть O (n), но при амортизации по многим операциям это фактически O (1).