Лекция №12. Множественный тип данных

Множества - это наборы однотипных логически связанных друг с другом данных. Количество элементов, входящих в множество, может меняться в пределах от 0 до 255. Именно непостоянством количества своих элементов множества отличаются от массивов.

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

Тип элементов множества называется базовым типом множества. Область значений типа множества – это набор всевозможных подмножеств, составленных из элементов базового типа.

В ТР имеются ограничения на базовый тип. Это может быть только порядковый тип, количество значений которого не превышает 256, из простых типов к таким относятся Char, Byte, Boolean. Разрешается использовать перечисляемый тип и диапазон.

Для ряда задач применение множеств может обеспечить серьезные преимущества по сравнению с использованием других структур данных – массивов или строк.

При задании значений элементов множества используются квадратные скобки. Например: [1,2,3,4], [‘a’..’z’], [‘a’,’b’,’c’]. Множество, не содержащее элементов, называется пустым. Пустое множество может быть включено в любое другое множество.

Описание типа множества имеет вид:

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

Здесь <имя типа> - правильный идентификатор, set of - зарезервированные слова (множество из), <базовый тип> - базовый тип элемента множества, в качестве которого может использоваться любой порядковый тип, кроме Word, Integer, LongInt.

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

Если все элементы одного множества входят также и в другое, говорят о включении первого множества во второе. Пустое множество включается в любое другое.

Пример объявления и определения множества:

Type

MnogChar = set of '0'..'9';

MnogCifr = set of 0..9;

Var

S1, S2, S3: MnogChar;

S4, S5, S6: MnogCifr;

Begin

……

S1:= ['1', '2', '3'];

S2:= ['3', '2', '1'];

S3:= ['2', '3'];

S4:= [0..3, 6];

S5:= [4, 5];

S6:= [3..9];

……

End;

В этом примере множества S1 и S2 эквивалентны, а множество S3 включено в S2, но не эквивалентно ему.

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

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

- * - пересечение множеств; результат содержит элементы, общие для обоих множеств; например, S4*S6 содержит [3], S4*S5 – пустое множество.

- + - объединение множеств; результат содержит элементы первого множества, дополненные недостающими элементами из второго множества:

o S4 + S5 содержит [0,1,2,3,4,5,6];

o S5 + S6 содержит [3,4,5,6,7,8,9];

- - - разность множеств; результат содержит элементы из первого множества, которые не принадлежат второму:

o S6 – S5 содержит [3,6,7,8,9];

o S4 – S5 содержит [0,1,2,3,6];

- = - проверка эквивалентности; возвращает True, если оба множества эквивалентны.

- <> - проверка неэквивалентности; возвращает True, если оба множества неэквивалентны.

- <= - проверка вхождения; возвращает True, если первое множество включено во второе.

- >= - проверка вхождения; возвращает True, если второе множество включено в первое.

- In - проверка принадлежности; в этой операции первый элемент – выражение, а второй – множество одного и того же типа; возвращает True, если выражение имеет значение, принадлежащее множеству;

o 3 in S6 возвращает True;

o 2*2 in S1 возвращает False.

- Дополнительно к этим операциям можно использовать две процедуры.

- Include - включает новый элемент во множество. Обращение к процедуре:

o Include (S, I),

- Здесь S – множество, состоящее из элементов базового типа,

- I – новый элемент, который необходимо включить во множество.

- Exclude – исключает элемент из множества, например:

o Exclude(S, I).

Исходя из особенностей внутреннего представления множеств, можно сделать следующие выводы:

- в множестве не может быть двух одинаковых элементов;

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

 

Пример. Даны два множества M1 и M2 натуральных чисел (множества задаются произвольно). Нужно получить третье множество M3, состоящее из объединенных двух первых множеств, M4 - разность множеств М1 и М2, включить в М4 элемент, равный 22, если такого элемента нет в М4, исключить из М3 элемент, равный 15, если такой элемент есть в М3.

uses crt;

type

mnog = set of 1..100;

var

i,k: integer;

m1,m2,m3,m4: mnog;

begin

clrscr;

m1:= [1..9];

m2:= [1..7,15,18];

m3:= m1+m2;

m4:= m1-m2;

if 22 in m4 then

writeln('число 22 уже есть в M4')

else

include (m4,22);

if 15 in m3 then

exclude (m3,15);

writeln;

for i:= 1 to 100 do

if i in m4 then

write(' M4 - ',i:3);

writeln;

for i:= 1 to 100 do

if i in m3 then

write(' M3 - ',i:3);

readln;

end.