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

Множественный тип описывается с помощью служебных слов Set of, например:

Здесь М — множественный тип, В — базовый тип.

Пример описания переменной множественного типа:

Принадлежность переменных к множественному типу может быть определена прямо в разделе описания переменных:

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

Константа вида [ ] означает пустое подмножество. Количество базовых элементов не должно превышать 256. Инициализация величин множественного типа может производиться с помощью типизированных констант:

Порядок перечисления элементов базового типа в константах безразличен.

Значение переменной множественного типа может быть задано конструкцией вида [T], где T — переменная базового типа. Например, вполне допустима конструкция:

Множество включает в себя набор элементов базового типа, все подмножества данного множества, а также пустое подмножество. Так, переменная Т множественного типа

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

К переменным и константам множественного типа применимы операции присваивания(:=), объединения(+), пересечения(*) и вычитания(-):

Результат выполнения этих операций есть величина множественного типа.

К множественным величинам применимы операции: тождественность (=), нетождественность (<>), содержится в ( =). Результат выполнения этих операций имеет логический тип, например:

[‘A’,’B’] = [‘A’,’C’] даст FALSE
[‘A’,’B’] <> [‘A’,’C’] даст TRUE
[‘B’] = [‘A’] даст FALSE.

Кроме этих операций для работы с величинами множественного типа в языке ПАСКАЛЬ используется операция in, проверяющая принадлежность элемента базового типа, стоящего слева от знака операции, множеству, стоящему справа от знака операции. Результат выполнения этой операции — булевский. Операция проверки принадлежности элемента множеству часто используется вместо операций отношения, например:

‘A’ in [‘A’, ‘B’] даст TRUE,
2 in [1, 3, 6] даст FALSE.

Волгоградский государственный педагогический университет
Кафедра алгебры, геометрии и информатики

Программирование. Множества Pascal-Паскаль

  • Скачено бесплатно: 6964
  • Куплено: 414
  • Pascal-Паскаль->Программирование. Множества Pascal-Паскаль

Множества Pascal-Паскаль

Еще одним фундаментальным классом данных являются данные, структурированные в виде множеств.

О перечисляемых типах

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

(Представление #xxx означает, что должен быть взят символ, чей код в таблице ASCII равен xxx).

Это базовые типы, которые не требуется задавать каждый раз, уже определены в системе именно таким образом. Кроме них имеется еще несколько интервальных типов, с некоторыми из которых мы знакомы:

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

Для работы с перечисляемыми типами существуют следующие функции, которые хранятся в библиотеке системных функций, и программист имеет к ним доступ:

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

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

Например, мы можем описать тип данных color и перечислить семь основных цветов:

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

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

Конструктор множества может содержать диапазон значений базового типа. Тогда во множества включаются все элементы диапазона. Например,

Обе формы конструирования множеств могут сочетаться. Например,

Конструктор вида [] обозначает пустые множества.

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

Можно множественный тип определить как типизированную константу:

При описании множественного тип как констант допускается использование знака “+” (слияние множеств). Например,

Операции над множественными типами Паскаля

С множественными типами Паскаля можно выполнять действия объединения, исключения и пересечения.

Объединение множественных типов содержит элементы, которые принадлежат хотя бы одному множеству, при этом каждый элемент входит в объединение только один раз. Операция объединения множеств обозначается знаком ‘+’.

Пример множественных типов Паскаля

Возможно объединять множественные типы и отдельные элементы. Например,

Исключение определяется как разность множественных типов, в котором из уменьшаемого исключаются элементы, входящие в вычитаемое. Если в вычитаемом есть элементы, отсутствующие в уменьшаемом, то они никак не влияют на результат. Операция исключения обозначается знаком ‘-‘.

Пример исключения множественных типов Паскаля

Пресечение множественных типов– множества, содержащие элементы, одновременно входящие в оба множества. Операция пересечения множеств обозначается знаком ‘*’.

Пример пересечения множественных типов

Операции отношения множественных типов Паскаля

Наряду с рассмотренными выше операциями, над значениями множественного типа определены и некоторые операции отношения. Операндами операций над множественными значениями в общем случае являются множественные выражения. Среди операций отношения над значениями множественного типа особое место занимает специальная операция проверки вхождения элемента во множества, обозначаемая служебным словом in. В отличие от остальных операций отношения, в которых значения обоих операндов относятся к одному и тому же множественному типу значений, в операции in первый операнд должен принадлежать базовому типу, а второй – множественному типу значений, построенному на основе этого базового типа. Результатом операции отношения, как обычно, является логическое значение (true или false).

Операция сравнения на равенство множественных типов Паскаля. Множества считаются равными (эквивалентными), если все элементы одного множества присутствуют в другом и наоборот. Для операции сравнения на равенство или неравенство используются символы ‘=’ и ‘<>’.

Тогда операция A=D имеет значение true, а операция A<>D имеет значение false.

Проверка включения. Одно множество считается включенным в другое (одно множество является подмножеством другого), если все его элементы содержатся во втором множестве. Обратное утверждение может быть и несправедливым. Операции проверки включения обозначаются ‘ =’.

Объявление множеств

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

Размер множества в Turbo Pascal всегда ограничен некоторым предельно допустимым количеством элементов. Во множествах допускаются только такие элементы, порядковые значения которых не выходят за границы 0..255. Для целочисленных множеств это означает, что в них могут присутствовать только числа от 0 до 255. Отрицательные элементы множеств в Turbo Pascal не допускаются. Поэтому базовыми типами не могут быть типы shortint, integer, longint. Если же необходимо множество целочисленных объектов, то базовый тип должен объявлен как диапазон типа byte. Для множеств, содержащих символы, подобных затруднений нет, поскольку базовым типом для них является char (а в нем 256 значений с порядковыми номерами от 0 до 255).

В математике для обозначения множества используют фигурные скобки (например, <4, 7, 12>), в Паскаль — квадратные (например, [1, 3, 5]). Порядок элементов во множестве не имеет значения. Так, записав [3, 6, 9] или [9, 3, 6], мы будем иметь дело с одним и тем же множеством. Более того, многократное повторение одного и того же элемента не меняет множество. Например, [4, 7, 3] и [3, 7, 4, 4] – это одно и то же множество.

По форме записи объявление переменной типа множество сходно с объявлением одномерного массива:

Например, объявление переменной ch , рассматриваемой как множество с базовым типом char, имеет вид:

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

Можно сначала объявить тип множества, а потом использовать его для объявления переменных:

Довольно часто в качестве базового типа множества используется тип перечисления или некоторый его диапазон:

Объявление переменной-множества не дает ей определенного значения.

Построение множества

Чтобы во множестве появились элементы, необходимо выполнить оператор присваивания, в левой части которого стоит имя переменной-множества, а в правой — конструктор множества или некоторое выражение над множествами.

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

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

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

Множество может быть объявлено типизированной константой, для чего в описании после знака равенства следует указать конструктор множества. Например:

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

Конструируя множества, можно использовать и переменные при условии, что их текущие значения попадают в диапазон базового типа множества. Так, если ch1 и ch2 имеют тип char , то допустима следующая последовательность операторов:

В результате получится множество [‘A’, ‘K’, ‘M’].

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

Действия над множествами

Объединение, пересечение и разность множеств

Над множествами выполнимы объединение (+), пересечение (*) и разность (-).

Объединение двух множеств A и B (A + B) – это новое множество, состоящее из элементов, принадлежащих множеству A или B, либо тому и другому одновременно.

Результат: chs3 = [ ‘a’ , ‘b’ , ‘d’ , ‘m’ , ‘e’ , ‘k’ , ‘n’ ] .

Пересечение двух множеств A и B (A * B) – это множество, состоящее из элементов, одновременно принадлежащих множествам A и B.

Результат: chs3 = [‘d’].

Разность двух множеств A и B (A – B) – это новое множество, состоящее из элементов множества A, не вошедших в множество B.

Манипулируя операциями над множествами, можно добавлять элементы к множествам или удалять их.

Для вставки и удаления элементов при работе с множествами в Pascal введены две процедуры:

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

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

Над множествами можно выполнять четыре операции сравнения: =, <>, >=, B), если они отличаются хотя бы одним элементом.

Множество A является подмножеством множества B (A = A), если каждый элемент из A присутствует в B.

Имеется также возможность выяснить, принадлежит ли данный элемент некоторому множеству. Для этого служит операция in. Пусть A – множество элементов некоторого базового типа, а x – переменная (константа, выражение) этого типа. Тогда выражение x in A истинно, если значение x является элементом множества A.

Все операции сравнения множеств, а также операция in возвращают логическое значение true или false.

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