LINUX.ORG.RU

Множества


0

0

Вспомнил тут дискуссию о паскале. Так вот там утверждалось, что множества в паскале сделаны отвратно и лучше бы их там не было.

Вопрос: как нужно правильно реализовывать множества и где это сделано? ссылки приветствуются.

заранее благодарен за ответы.

anonymous

Re: Множества

Множества в Паскале несколько ущербны. Дело втом, что это могут быть только множества чисел от 0 до 255. В Паскале они реализованы как bitmap то есть, 256 битовый массив. Если бит номер i включен - значит, елемент i в множестве. Более общая реализация, вообще-то, зависит от языка, но принцип такой : держим некое сбалансированое дерево, например AVL или red-black tree, когда мы хотим занести елемент в множество, просто заносим его в узел дерева. Когда мы хотим узнать принадлежит ли елемент множеству, просто производим поиск по дереву. Итого : сложность всех методов множества О(log n), когда n это мощность множества. Кроме того, множество может легко расти и сжиматься. В C++ есть уже готовый контайнер std::set.

Удачи.

the_coder ★★ ()

Re: Множества

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

balbes ()

Re: Множества

>Вопрос: как нужно правильно реализовывать множества и где это сделано?

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

Структур данных навалом. Для начала хорошо бы почитать что-нибудь вроде Кормена.

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.