2.3. Представление множеств

Существуют два основных подхода к представлению множеств в памяти.

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

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

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

Рис. 2.8. Смежное и связанное представление множества в памяти Как и для последовательностей, наилучший метод представления множеств существенно зависит от операций, которые мы собираемся выполнять над ними. Типичные операции над множествами: выяснить, имеется ли конкретный элемент в данном множестве; добавить в множество новые элементы; удалить элементы из множества; выполнить обычные теоретико—множественные операции, такие как объединение или пересечение двух множеств. Как правило, для представления множеств применяют связанную память.

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

Представление в виде характеристического вектора удобнее тем, что можно определять принадлежность элемента множеству за время, не зависящее от его размера. Основные операции над множествами, такие как объединение и пересечение, можно осуществлять как операции над двоичными векторами. Недостаток этого представления заключается в том, что операции объединение и пересечение занимают время, пропорциональное мощности универсального множества а не рассматриваемого множества Данное представление требует дополнительной памяти для хранения характеристического вектора, что для больших (размер универсального множества бывает практически невыполнимо.

Рис. 2.9. Представление множества характеристическим вектором