Основы программирования



              

Множество


Множество — это структура данных, содержащая конечный набор элементов некоторого типа. Каждый элемент содержится только в одном экземпляре, т.е. разные элементы множества не равны между собой. Элементы множества никак не упорядочены. В множество M можно добавить элемент x, из множества M можно удалить элемент x. Если при добавлении элемента x он уже содержится в множестве M, то ничего не происходит. Аналогично, никакие действия не совершаются при удалении элемента x, когда он не содержится в множестве M. Наконец, для заданного элемента x можно определить, содержится ли он в множестве M. Множество — это потенциально неограниченная структура, оно может содержать любое конечное число элементов.

В некоторых языках программирования накладывают ограничения на тип элементов и на максимальное количество элементов множества. Так, иногда рассматривают множество элементов дискретного типа, число элементов которого не может превышать некоторой константы, задаваемой при создании множества. (Тип называется дискретным, если все возможные значения данного типа можно занумеровать целыми числами.) Для таких множеств употребляют название Bitset (``набор битов'') или просто Set. Как правило, для реализации таких множеств используется битовая реализация множества на базе массива целых чисел. Каждое целое число рассматривается в двоичном представлении как набор битов, содержащий 32 элемента. Биты внутри одного числа нумеруются справа налево (от младших разрядов к старшим); нумерация битов продолжается от одного числа к другому, когда мы перебираем элементы массива. К примеру, массив из десяти целых чисел содержит 320 битов, номера которых изменяются от 0 до 319. Множество в данной реализации может содержать любой набор целых чисел в диапазоне от 0 до 319. Число N содержится в множестве тогда и только тогда, когда бит с номером N равен единице (программисты говорят бит установлен). Соответственно, если число N не содержится в множестве, то бит с номером N равен нулю (программисты говорят бит очищен).


Содержание  Назад  Вперед