Как описать множество?

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

Вам понадобится

• - среда разработки;
• - транслятор с выбранного языка программирования.

Инструкция

Опишите множество при помощи средств языка программирования, если они у него имеются. Например, в языке Pascal существует конструкция set, позволяющая декларировать соответствующие типы. Правда, объем таких множеств не должен превышать 256 элементов. Пример объявлений типов множеств может выглядеть так:type AZLetters = set of 'A'..'Z'; AllLetters = set of char;Декларация переменных и констант типов, являющихся множествами, производится обычным образом. При этом для инициализации могут быть использованы литералы множеств. Например:const LettersSet1: AZLetters = ['A', 'B', 'C' ];

Используйте возможности стандартных библиотек или модулей для описания множеств. Так, библиотека шаблонов C++, которая должна поставляться вместе с компилятором, включает шаблон класса контейнера set, реализующего функционал множеств:template class Key, class Traits=less, class Allocator=allocator >class setКак видно из листинга, аргументами шаблона set являются: тип данных элементов множества, тип функционального объекта для определения порядка следования элементов в наборе и тип объекта-распределителя памяти. При этом только первый аргумент обязателен (в качестве двух других по умолчанию используется стандартный бинарный предикат less и стандартный распределитель).

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

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

Оцените статью!