Тип данных множество

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

Описание типа множества выглядит следующим образом:

Type <имя типа>=set of <базовый тип>;

Количество элементов в множестве (мощность множества) может находиться в интервале от 0 до 256. Это определяется внутренним представлением элементов множества: вхождение элемента в множество определяется значением двоичного разряда (бита). Нулевое значение означает, что соответствующий элемент отсутствует в множестве, единичное значение означает, что элемент присутствует в множестве. Для хранения этой информации всегда отводится 32 байта (256 бит) и нумерация ведется от 0 до 255, поэтому всегда в множестве могут присутствовать элементы с номерами, лежащими в указанном диапазоне (от 0 до 255).

Способ представления элементов множества самым существенным образом влияет на выбор базового типа множества. В качестве базового типа может фигурировать, во-первых, только порядковый тип, во-вторых, тип, у которого максимальный номер элемента не превышает значения, равного 255. Таким образом, в качестве базового типа могут выступать только следующие типы: Byte,Boolean,Char, перечисляемый тип с количеством элементов не более 256.

В множестве элементы повторяться не могут.

Примеры правильных описаний типов:

1. TypeMn1=setofByte;

2. Mn2=set of Boolean;

3. Mn3=set of Char;

4. Mon=(jan,feb,mar,apr,mai,jun,jul,aug,sep,okt,nov,dez);

5. Mn4=set of Mon;

Пример неправильного описания типа:

6. Mn5=set of 2..257;

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

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

Пример:

7. Var A:Mn1; B:Mn2; C:Mn3; D:Mn4;

8. Begin

9. A:=[0,22..40, 50+K div 2..88,250,255];

10. B:=[true];

11. C:=[Chr(10)..Chr(15),'A'..'G', 'К'.. 'Я', '%', '#'];

12. D:=[jan,mar,jun..aug,dez];

13. A:=[]; //пустое множество

14. ……

15. End.

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

Пересечение множеств, обозначается символом * (звездочка). Результатом выполнения этой операции является множество, включающее общие элементы двух множеств. Например, varA1,A2,A3:Mn1;A1:=[2,3,4,7..10];A2:=[3,7,9,12,13];A3:=A1*A2; В результате множествоA3 будет содержать следующие элементы [3,7,9].

Объединение множеств, обозначается символом + (плюс). Результатом выполнения объединения двух множеств является множество, состоящее из элементов обоих множеств, т.е. элементы первого множества дополняются теми элементами второго множества, которых нет в первом. Если выполнить объединение A3:=A1+A2 множеств из предыдущего примера, то получим множество [2,3,4,7..10,12,13].

Разность множеств, обозначается символом – (минус). Результатом выполнения этой операции является множество, состоящее из элементов первого множества, которых нет во втором. Например, в результате выполнения оператора A3:=A1-A2; получим множество, состоящее из следующих элементов [2,4,8,10].

Операции отношения. Проверка эквивалентности двух множеств, обозначается символом = (равенство). Результат операции истина, если два множества содержат одинаковые элементы, и ложь, если два множества содержат неодинаковые элементы. Например, varB:Boolean;B:=A1=A2; переменнаяBполучит значениеfalse. Если же выполнить операторB:=[1,3,..9]=[1,3,..9]; переменнаяBполучит значениеtrue.

Проверка неэквивалентности двух множеств, обозначается символами <> (символы меньше, больше). Результат операции истина, если два множества содержат несовпадающие элементы, и ложь, если множества содержат одинаковые элементы. Например, после выполнения оператора присваивания B:=A1<>A2; переменнаяBполучит значениеtrue. Если же выполнить операторB:=[1,3,..9]<>[1,3,..9]; переменнаяBполучит значениеfalse.

Проверка вхождения первого множества во второе, обозначается символами <= (символы меньше, равно). Результат операции истина, если все элементы первого множества присутствую во втором, и ложь, если не все элементы первого множества присутствуют во втором множестве. Например, если A1:=[2,3,4,7..10];A2:=[2,3..5,7..13]; , то результатом выполнения оператораB:=A1<=A2; будетtrue. ЕслиA1:=[2,3,4,7..10];A2:=[2,3..5,7..9]; , то результатом выполнения оператораB:=A1<=A2; будетfalse.

Проверка вхождения второго множества в первое, обозначается символами >= (символы больше, равно). Результат операции истина, если все элементы второго множества присутствуют в первом, и ложь, если не все элементы второго множества присутствуют в первом множестве. Например, если A1:=[2,3,4,7..10];A2:=[2,3,7..9]; , то результатом выполнения оператораB:=A1>=A2; будетtrue. ЕслиA1:=[2,3,4,7..10];A2:=[2,3..5,7..9]; , то результатом выполнения оператораB:=A1>=A2; будетfalse.

Проверка вхождения элемента в множество, обозначается in. Первый операнд операции – выражение того же базового типа, что и базовый тип множества, являющегося вторым операндом. Результат выполнения операции истина, если элемент входит в множество, и ложь, если элемент отсутствует в множестве. Например, после выполнения оператораB:=5+6div2inA1; переменнаяBполучит значениеtrue(A1:=[2,3,4,7..10];). Если будет выполнен операторB:=5+6div2-7inA1;, то переменнаяBполучит значениеfalse.

Для работы с множествами предназначены две процедуры. Процедура Include(M,L); позволяет включить в множествоMэлементL. ЭлементLдолжен принадлежать тому же типу, что и базовый тип множестваM.

Процедура Exclude(M,L); позволяет исключить из множестваMэлементL. ЭлементLдолжен принадлежать тому же типу, что и базовый тип множестваM.

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

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