Хороший средний метод скорости / эффективности памяти для создания набора в C ?:

Question

Допустим, я направляю непустые строки (char [] / char * s) в мою программу.Я хотел бы создать их набор.То есть для любого элемента a в наборе S a уникален в S.

Я думал, что подойти к этому можно несколькими способами, но столкнулся с проблемами.

Если бы я зналколичество элементов n Я хотел бы прочитать, я мог бы просто создать хеш-таблицу со всеми элементами, начинающимися с нуля, одинакового размера и, если произошла коллизия, не вставлять ее в эту таблицу.Когда вставки завершатся, я бы перебрал массив хеш-таблицы, посчитал ненулевые значения, размер, а затем создал массив этого размера, а затем скопировал в него все значения.

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

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

Любые входные данные приветствуются.Пожалуйста, не стесняйтесь задавать вопросы в поле для комментариев ниже, если вам нужна дополнительная информация.Библиотеки были бы очень полезны!(Поиск в Google "Наборы в C" и подобные вещи не очень помогает.)

Answer 1

Хеш-таблица может работать, даже если вы не знали размер количества элементов, которые вы собираетесь вставить ... вы бы просто определили свою хеш-таблицу, чтобы использовать «корзины» (т. Е. Каждая позиция на самом деле это связанный список элементов, которые хэшируются с одним и тем же значением), и вы должны выполнить поиск в каждом «сегменте», чтобы убедиться, что каждый элемент еще не был вставлен в хеш-таблицу. Ключом к тому, чтобы избегать больших "сегментов" для поиска, был бы хороший алгоритм хеширования.

Вы также можете, если вы можете определить слабый порядок ваших объектов, использовать двоичное дерево поиска. Тогда, если! (A Хотя я знаю, что вы используете C, учтите тот факт, что в C ++ STL std::set использует RB-дерево (красно-черное дерево, которое представляет собой сбалансированное двоичное дерево поиска), а std::unordered_set использует хеш -стол.

Использование массива - плохая идея ... операции по изменению размера будут занимать много времени, в то время как вставки в дерево могут выполняться за O (log N), а для хеш-таблицы - амортизированный O (1). ).