2.7 Множества

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

TYPE T = SET OF T₀, где T₀ - базовый тип элементов множества. Помним, что базовым типом может быть только перечислимый или интервальный.

Значениями переменной x типа T являются множества элементов типа T₀. Они составляют множества всех подмножеств T₀. Такое множество называется множеством-степенью. Т.е. можно сказать, что тип T – это мно­жество-степень своего базового типа T₀.

Порядок следования элементов для множества роли не играет.

Максимальное число элементов множества определяется реализацией. Для Паскаля количество элементов множества не должно превышать 256.

TYPE CHIS = SET OF 0..30;

TYPE DSET = SET OF DAY;

TYPE ZNSET = SET OF '*'..'/';

Соответствующие переменные описываются как

VAR CH : CHIS; D : DSET; ZN : ZNSET;

Операции над множествами нам уже известны. Заметим только, что это обычные операции теории мно­жеств.

Присваивание:
СН := [12];	D	:= [SU, FR];
Объединение:
А = [1, 2, 3, 4, 5]
В = [2, 5, 6, 7, 8]
А + В = [1, 2, 3, 4, 5, 6, 7, 8]
Пересечение:
А * В = [2, 5]
Разность
А-В = [1, 3, 4]
Отношение
Паскаль		Математическая значение запись
А = В		(A = B) true false
АОВ		(А* В)
А<=В		(А<В)
А=>В		(А>В)
x IN A		(хе А)
Ранг операций:
1) *
2) +, -
3) IN

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

называемых лексем. При каждом вызове сканер считывает нужное число входных символов и выдает одну вы­ходную лексему. Конкретные правила трансляции следующие:

имеются следующие входные лексемы: "идентификатор", "число", "меньше-равно", "больше-равно", "при­своить" и лексемы, соответствующие отдельным символам: +, -, *, и т.д;

лексема "идентификатор" выдается по прочтении последовательности букв и цифр, начинающихся с бук­вы;

лексема "число" выдается по прочтении последовательности цифр;

лексемы "меньше-равно", "больше-равно" и "присвоить" выдаются по прочтении соответствующих пар символов <=, >=, :=;

пробелы и концы строк опускаются.

При работе программы полученная выходная лексема присваивается глобальной переменной sym. Назна­чение глобальных переменных id и num видно из программы. Глобальная переменная ch содержит текущий символ входной последовательности. Массив лексем S задает отображение символов в лексемы, его индексы ограничены лишь теми символами, которые не являются ни цифрами, ни буквами. Как видим, использование множеств символов позволяет программировать сканер независимо от их упорядоченности.

Текст программы:

VAR CH : CHAR; SYM : SYMBOL; NUM : INTEGER; ID : RECORD

K : 0..MAXK;

A : ARRAY[1..MAXK] OF CHAR END; PROCEDURE SCANNER; VAR CH1 : CHAR; BEGIN {пропуск пробелов}

WHILE CH = ' ' DO READ(CH); IF CH IN ['A'..'Z'] THEN

WITH ID DO BEGIN

SYM := IDENTIFIER; K := 0; REPEAT

IF K < MAXK THEN BEGIN K := K + 1; A[K] := CH END;

READ(CH) UNTIL NOT(CH IN ['A'..'Z','0'..'9']) END ELSE IF CH IN ['0'..'9'] THEN BEGIN

SYM := NUMBER; NUM := 0; REPEAT

NUM := 10 * NUM + ORD(CH) - ORD('0'); READ(CH) UNTIL NOT(CH IN ['0'..'9']) END ELSE

IF CH IN ['<',':','>'] THEN BEGIN CH1 := CH; READ(CH); IF CH = '=' THEN BEGIN IF CH1 = '<' THEN SYM := LEQ ELSE IF CH1 = '>' THEN SYM := GEQ

ELSE SYM := BECOMES; READ(CH) END

ELSE SYM := S[CH1] END ELSE BEGIN {другие символы}

SYM := S[CH]; READ(CH) END END {SCANNER};

Контрольные вопросы

1. Основные типы данных и их представление в памяти ЭВМ.

2. Понятие структуры. Логическая и физическая структуры.

3. Классификация структур.

4. Массив как структура данных.

5. Строка как структура данных.

6. Запись как структура данных. Оператор присоединения.

7. Записи с вариантами.

8. Множество как структура данных.