Правила форума
Лекция №5.4: Символы и строки. МножестваСодержание
Операции с множествами
Все теоретико–множественные операции реализованы и в языке Pascal:
| 1) Пересечение двух множеств s1 и s2: | s := s1 * s2; |
| 2) Объединение двух множеств s1 и s2: | s := s1 + s2; |
| 3) Разность двух множеств s1 и s2 (все элементы, которые принадлежат множеству s1 и одновременно не принадлежат множеству s2)1: | s := s1 - s2; |
| 4) Проверка принадлежности элемента el множеству s (результат этой операции имеет тип Boolean): | el in s |
| 5) Обозначение для пустого множества: | [] |
| 6) Создание множества из списка элементов: | s := [e1, _, eN]; |
| 7) Проверка двух множеств на равенство или строгое включение (результат этих операций имеет тип Boolean): | s1 = s2 s1 > s2 s1 < s2 |
Не существует никакой процедуры, позволяющей распечатать содержимое множества. Это приходится делать следующим образом:
for k := min_type1 to max_type1 do
if k in s then
Write(k, ' ');
Представление множеств массивами
Одно из основных неудобств при работе с множествами — это ограничение размера всего лишь 256–ю элементами. Мы приведём здесь два очень похожих способа представления больших множеств массивами. Единственным условием является наличие некоторого внутреннего порядка среди представляемых элементов: без этого невозможно будет их перенумеровать.
Представление множеств линейными массивами
Задав линейный массив достаточной длины, можно «вручную» сымитировать множество для более широкого, чем 256 элементов, диапазона значений. Например, чтобы работать с множеством, содержащим 10 000 элементов, достаточно такого массива:
При таком способе представления возможно задать множество до 65 000 элементов.
Для простоты изложения мы ограничимся только числовыми множествами, однако всё сказанное ниже можно применять и к множествам, элементы которых имеют другую природу. Итак, признаком того, что элемент k является элементом нашего множества, будет значение True в k–й ячейке этого массива.
Посмотрим теперь, какими способами мы вынуждены будем имитировать операции над «массивными» множествами.
Проверка множества на пустоту может быть осуществлена довольно просто:
pusto := True;
for i := 1 to N do
if set_arr[i] then
begin
pusto := False;
Break
end;Проверка элемента на принадлежность множеству также не вызовет никаких затруднений, поскольку соответствующая компонента массива содержит ответ на этот вопрос:
is_in := set_arr[element];Добавление элемента в множество нужно записывать так:
set_arr[element] := True;Удаление элемента из множества записывается аналогичным образом:
set_arr[element] := False;- Построение пересечения множеств реализуется как проверка вхождения каждого элемента в оба множества и последующее добавление удовлетворивших этому условию элементов в результирующее множество.
- Построение объединения множеств аналогичным образом базируется на проверке вхождения элемента хотя бы в одно из объединяемых множеств и дальнейшем добавлении элементов в результирующее множество.
- Построение разности двух множеств также опирается на проверку вхождения элемента в оба множества, причём добавление элемента в создаваемое множество происходит только в том случае, если элемент присутствует в множестве–уменьшаемом и одновременно отсутствует в множестве–вычитаемом.
Проверка двух множеств на равенство не требует особых пояснений:
equal := True;
for i :=1 to N do
if set1[i] <> set2[i] then
begin
equal := False;
Break
end;Проверка двух множеств на включение (set1 < set2) тоже не потребует больших усилий:
subset := True;
for i := 1 to N do
if set1[i] and not set2[i] then
begin
subset := False;
Break
end;
Примечания
- ^ Если множества s1 и s2 не пересекаются, то результат s будет совпадать с s1.
::
::
::
