Структурированные типы данных: множества. Описание типа. Операции над множествами

Страницы работы

4 страницы (Word-файл)

Фрагмент текста работы

Структурированные типы данных: множества. Описание типа. Операции над множествами.

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

Каждый объект в множестве называется элементом множества. Элементы множества должны принадлежать одному из скалярных типов, кроме вещественного. Тип элементов называется базовым типом множества. Базовый тип задается диапазоном или перечислением. Область значений типа - набор всевозможных подмножеств, составленных из элементов базового типа. В выражениях значения элементов множества указываются в квадратных скобках: [1, 2, 3, 4] , ['a' , 'b' , 'c'] , ['a' .. 'z'].

Если множество не имеет элементов, оно называется пустым и обозначается как [ ].

Для описания  множественного типа используется словосочетание set of (множество из).

Формат записи:

Type

<имя типа> = set of (<элемент1, элемент2,..., элементN>);

Var

<идентификатор1,...> : <имя типа>;

или без предварительного описания:

Var

<идентификатор1,...> : set of (<элемент1, ,..., элементN>);

Пример.

Type

ProstChislo = set of (3,5,7,11,13);

Nomer = set of 1..31;

Var

Pr: ProstChislo;          { множества описаны

N: Nomer;                               в разделе Type}

Bukva: set of ('a', 'b', 'c');       { непосредственное описание}

Переменная Pr может принимать значения всевозможных подмножеств множества (3,5,7,11,13) и т.д.

Помни:

·  Попытка присвоить этим переменным другие значения вызовет программное прерывание.

·  Количество элементов множества не должно превышать 256, соответственно, номера значений базового типа должны находиться в диапазоне от 0 до 255.

·  Объем памяти для переменной типа  множество вычисляется по формуле Объем памяти = (Max div 8) - (Min div 8) + 1, где Max, Min - верхняя и нижняя границы базового типа.

Порядок перечисления элементов роли не играет, а каждый элемент учитывается только один раз. Потому множество {true, false} и множество {false, true} эквивалентны, а [1, 4, 2, 1, 4, 2, 1] эквивалентно [1, 2, 4]. Записи типа [5..5], [9..0] соответствуют [5] и пустому множеству [].

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

Известна теорема: всякое n-элементное множество имеет 2n подмножеств, где подмножество – любая часть множества.

операции над множествами

При работе с множествами допускается использование операций отношения: = ,  <> , >= , <= , объединения, пересечения, разности множеств и операции in. Результат этих выражений имеет булевский тип (т.е. или True, или False).

операция "равно" ( = )

Два множества А и В называются равными, если они состоят из одних и тех же элементов. Порядок следования элементов в сравниваемых множествах значения не имеет.

Пример.

множество А             множество В              операция                    результат

[1,2,3,4]                      [2,3,1,4]                      A = B                          True

['a'..'z']                        ['z'..'a']                        A = B                          True

['a','b','c']                     ['a']                              A = B                          False

операция "неравно" ( <> )

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

Пример.

множество А             множество В              операция                    результат

[1,2,3,4]                      [2,3,5,4]                      A <> B                        True

['a'..'z']                        ['z'..'c']                        A = B                          False

['a','b','c']                     ['a']                              A <> B                        True

операция "больше либо равно" (>=)

Эта операция используется для определения принадлежности множеств. A>=B имеет результат True, если все элементы множества В содержатся в множестве А. В противном случае - результат False.

Пример.

множество А             множество В              операция                    результат

[1,2,3,4]                      [2,3,4]                         A >= B                        True

['a'..'f']                         ['z'..'c']                        A >= B                        False

['a','b','c']                     ['a']                              A >= B                        True

операция "меньше либо равно" (>=)

Эта операция используется для определения принадлежности множеств. A<=B имеет результат True, если все элементы множества A содержатся в множестве B. В противном случае - результат False.

Пример.

множество А             множество В              операция                    результат

[1,2,3]                         [0,1,2,3,4]                   A <= B                        True

['a'..'f']                         ['h'..'p']                                    A <= B                        False

['a']                              ['a','b','c']                     A <= B                        True


операция in

Операция in используется для проверки принадлежности  какого-либо значения указанному множеству. Обычно применяется в условных операторах.

Пример.

А                     выражение                             результат

2                      if A in [2,3,4] then ...              True

'a'                     if A in ['z'..'c'] then ...             False

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

Пример.

if (a=1) or (a=2) or (a=3) or (a=4) then ...

можно заменить более коротким выражением

if a in [1..6] then ...

объединение множеств (+)

Объединением двух множеств называется третье множество, содержащее элементы и множества А и множества В.

Пример.

множество А             множество В              операция                    результат

[1,2,3,4]                      [4,5,6,7]                      A + B                          [1,2,3,4,5,6,7]

['a'..'f']                         ['z'..'c']                        A + B                          ['a',..'z']

['a','b','c']                     ['a']                              A + B                          ['a','b','c']

пересечение множеств (*)

Пересечением двух множеств называется третье множество, содержащее

Похожие материалы

Информация о работе