5. Множество: функциональная спецификация и логическое описание. Физическое представление множества с помощью стандартного типа, а также в виде линейного списка и характеристического вектора

 

Множества

 

            Множество – это наиболее общая линейная структура данных.

 

Функциональная спецификация

            Над множеством определены следующие операции:

создание:       создать_множество – операция без параметров, создающая пустое множество Æ;

доступ:           найти – операция   проверяет,   принадлежит  ли  эл-т  данному     множеству;

                        пусто – операция проверяет, есть ли элементы в множестве;

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

модификация:

                        включить – операция   формирует    новое  множество,  к  которому добавляет один элемент;

                        убрать – операция    формирует   новое   множество,   из    которого удален данный элемент (если он принадлежит множеству;  иначе операция имеет нулевой эффект);

                        выборка_удаление – операция   возвращает   элемент   множества с данным   свойством   и   новое   множество без удаленного элемента;

                        объединение_множествÈ”;

                        пересечение_множеств      “Ç”;

                        вычитание_множеств       “\”.

 

Логическое описание

            Стандартное описание множества в языках высокого уровня: TYPE T = SET OF T0. Здесь T0 - тип элементов множества.

 

Физическое представление

            Множество можно представить в виде линейного списка (см. §2), массива (см. §4), с помощью стандартного типа SET, а также в виде характеристического вектора. Обсудим достоинства и недостатки каждого способа. Пусть U – это универсальное множество, т. е. такое, что все рассматриваемые в данной задаче множества являются его подмножествами. Пусть также U содержит n элементов, т. е. |U| = n.

 

I способ. Представление множества S в виде линейного списка

            Этот способ удобен, если в процессе работы с множеством S его часто приходится модифицировать (добавлять и удалять элементы), причем мощность этого множества значительно меньше мощности универсального множества: |S|<<|U|.

 

II способ. Представление множества S в виде массива

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

 

III способ. Представление множества S с помощью стандартного типа SET

            Этот способ был бы, пожалуй, лучшим из всех, если бы не ограничение на число элементов множества. Например, в ТурбоПаскале мощность множества S не должна превышать 256.

 

IV способ. Представление множества S в виде характеристического вектора

            В этом случае универсальное множество U линейно упорядочивают U={u1,  u2, … , un}, после чего любое его подмножество S представляется в виде вектора VS из n битов таким образом, что i-й разряд в векторе VS равен 1 тогда и только тогда, когда элемент ui принадлежит множеству S; в противном случае i-й разряд равен 0. VS называют характеристическим вектором для S

 Пример. Пусть U={-7,0,7,14}. Тогда множеству {0,7} соответствует вектор (0,1,1,0), множеству ={-7,7,14} - вектор (1,0,1,1).

            Характеристический вектор универсального множества состоит из одних единиц, а характеристический вектор пустого множества - из одних нулей.

            Представление в виде двоичного вектора удобно тем, что можно определять принадлежность некоторого элемента uk множеству S за время, не зависящее от мощности этого множества, т. е. от |S|. Кроме того, основные операции над множествами (объединение “È”, пересечение “Ç”, разность “\”) могут быть реализованы элементарными логическими операциями (дизъюнкцией “”, конъюнкцией “&”, отрицанием  ”). Однако выполнение всех этих операций требует времени, пропорционального |U|, а не размерам рассматриваемых множеств; объем памяти, необходимый для хранения множества S, также пропорционален |U|, а не |S|, поэтому этот способ рекомендуется использовать, когда |S|~|U|.