when true =>
COUNT: INTEGER;
when false =>
SUM: FLOAT;
end case;
end record;
4.9. Множества
Переменные множественного типа могут содержать неупорядоченную совокупность отдельных величин, имеющих некоторый порядковый тип, называемый базовым типом. Множественные типы данных часто используются для моделирования множеств в математическом смысле этого термина. Примером может служить анализ текста, для выполнения которого нужно обеспечить хранение и удобное использование таких небольших наборов символов, как знаки пунктуации или гласные буквы.
При разработке множественных типов возникает специфический вопрос: каким может быть максимальное число элементов базового типа во множестве?
4.9.1. Множества в языках Pascal и Modula-2
Среди распространенных императивных языков программирования множества как тип данных существуют только в языках Pascal и Modula-2. Опишем кратко множественные типы в языке Pascal.
Размер множеств в Pascal зависит от реализации. Многие реализации его существенно ограничивают. Причина в том, что множества и операции над ними наиболее эффективно реализуются, если переменная множественного типа представляется в виде строки битов размером в одно машинное слово. Таким образом, пользователи ограничены моделированием небольших множеств, и это усложняет создание программ. Другая проблема заключается в том, что в различных машинах используются слова различных размеров, поэтому программы, созданные на машинах с большими размерами слов, часто нельзя перенести на машины с меньшими размерами слов.
Наличие указанных проблем является следствием того, что максимальный размер базового множества не включается в структуру языка, а выбирается разработчиками средств реализации.
В языке Pascal есть некоторые операции над множествами, в том числе объединение, пересечение и проверка равенства множеств. Приведем пример определения множественного типа и нескольких переменных:
Type
TColors = (red, blue, green, yellow, orange, white, black);
TColorSet = set of TColors;
Var
setl, set2: TColorSet;
Переменным множественного типа можно присвоить значения:
setl:= [red, blue, yellow, white]; set2:= [black, blue];
Множественные типы в языке Modula-2 практически совпадают с соответствующими типами в языке Pascal, за исключением небольших синтаксических изменений и некоторых дополнительных операций. Константные множества заключаются в фигурные скобки ({ }). Скобкам может предшествовать имя типа этих констант. Рассмотрим следующее объявление множественного типа данных:
TYPE
SetTypel = SET OF [red, blue, green, yellow];
SetType2 = SET OF [blue, yellow];
VAR
SetVarl: SetTypel;
В программе, содержащей эти объявления, константа {blue} может определяться неоднозначно. Однако в операторе
SetVarl:= SetTypel {blue};
тип константы {blue} очевиден. В языке Pascal существует лишь одна форма записи этой константы [blue], которая не позволяет указать ее тип.
В языке Modula-2, как и в Pascal, не указано максимальное количество элементов во множестве, и эта величина также определяется реализацией. В Pascal и Modula-2 переменные множественных типов, как и переменные перечислимых типов, не могут участвовать в операциях ввода-вывода.
Множества широко используются для упрощения составных булевских выражений, содержащих оператор OR. Например, оператор Pascal
if (ch = 'a') or (ch = 'е') or (ch = 'i') or (ch = 'o') or (ch = 'u') …
можно заменить оператором
if ch in [ 'a', 'e', 'i', 'o', 'u']...
4.9.2. Реализация множественных типов
Множества обычно содержатся в памяти в виде строки битов. Например, пусть множество имеет в качестве базового следующий порядковый тип:
['а'.. 'p']
В этом случае переменные могут использовать первые 16 бит машинного слова, причем в бите значение 1 представляет присутствующий элемент, а 0 – отсутствующий. При использовании такой схемы значение
['a', 'c', 'h', 'o']
можно представить в виде
Выигрыш от указанного подхода заключается в возможности определить результат операции объединения множеств с помощью одной машинной команды – логического ИЛИ. Если количество элементов базового множества не превышает размера машинного слова, то операцию пересечения или принадлежности множеству также можно вычислить с помощью одной команды. Например, для переменной множественного типа SetChars проверка принадлежности множеству выглядит следующим образом:
'g' in SetChars
Эта проверка может реализоваться с помощью операции логического И между операндами, представленными в виде строк битов.
4.9.3. Резюме
Язык Ada создавался на основе Pascal, однако множественные типы в Ada отсутствуют. Вместо этого разработчики добавили оператор принадлежности переменной множеству переменных перечислимого типа. Это позволило выполнять одну из наиболее важных операций над множествами.
В других языках, не содержащих множественные типы, операции над множествами можно выполнять посредством массивов или битовых строк, но соответствующие команды создаются пользователем. Эта задача не вызывает трудностей, хотя решается более громоздко и обычно менее эффективно.
Например, если множество гласных букв в языке Pascal представлено как массив char, то проверка наличия гласной буквы в данной символьной переменной будет требовать цикла, просматривающего массив с гласными. В то же время, если гласные буквы были представлены в виде множества, то этой же цели можно достичь одним применением оператора in.
В любом случае удобнее обращаться с множеством как единым целым, в то время как массив должен просматриваться поэлементно.
Массивы более гибки, чем множества. Они допускают выполнение значительно большего количества операций и большую свободу выбора типа элементов. Если массивы ограничить максимальной длиной 32 (как это сделано для множеств во многих реализациях языка Pascal), пользователи не сочтут их приемлемыми. Множества предлагают альтернативный вариант, приносящий гибкость в жертву эффективности и предназначенный для соответствующего класса приложений.
Дата добавления: 2014-12-23; просмотров: 72 | Поможем написать вашу работу | Нарушение авторских прав |