Множества определение размещение в памяти операции процедуры и функции над множествами delphi

Обновлено: 07.07.2024

Еще один структурированный тип данных - это множество ( set ). В нем может содержаться не более 256 элементов.

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

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

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

Элементы могут принадлежать к любому порядковому типу, размер которого не превышает 1 байт (256 элементов). Например:

Множество-константа

Неименованная константа

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

Список элементов может быть задан перечислением элементов нового множества через запятую, интервалом или объединением этих двух способов. Элементы и границы интервалов могут быть переменными, константами и выражениями. Если левая граница интервала окажется больше правой, результатом будет пустое множество .

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

Нетипизированная константа

Множество - это структурированный тип данных, поэтому его невозможно задать нетипизированной константой.

Типизированная константа

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

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

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

Одно из основных неудобств при работе с множествами - это ограничение размера всего лишь 256-ю элементами. Мы приведем здесь два очень похожих способа представления больших множеств массивами. Единственным условием является наличие некоторого внутреннего порядка среди представляемых элементов: без этого невозможно будет их перенумеровать.

Представление множеств линейными массивами

Задав линейный массив достаточной длины, можно "вручную" сымитировать множество для более широкого, чем 256 элементов, диапазона значений. Например, чтобы работать с множеством , содержащим 10 000 элементов, достаточно такого массива:

При таком способе представления возможно задать множество до 65 000 элементов.

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

Посмотрим теперь, какими способами мы вынуждены будем имитировать операции над "массивными" множествами.

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

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

Добавление элемента в множество нужно записывать так:

Удаление элемента из множества записывается аналогичным образом:

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

Проверка двух множеств на включение ( set1<set2 ) тоже не потребует больших усилий:

Представление множеств битовыми массивами

В случае, если 65 000 элементов недостаточно для задания всех необходимых множеств (например, 10 множеств по 10 000 элементов в каждом), это число можно увеличить в 8 раз, перейдя от байтов к битам. Тогда 1 байт будет хранить информацию не об одном, а сразу о восьми элементах: единичный бит будет означать наличие элемента в множестве, а нулевой бит - отсутствие.

Задавая битовый массив , начнем нумерацию его компонент с 0:

Тогда результатом операции <номер_элемента> div 8 будет номер той компоненты массива, в которой содержится информация об этом элементе. А вот номер бита, в котором содержится информация об этом элементе, придется вычислять более сложным образом:

Эти вычисления потребуются нам еще не раз, поэтому запишем их снова, более строго, а затем будем использовать по умолчанию ( element - это "номер" обрабатываемого элемента в нашем множестве):

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

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

Проверка элемента на принадлежность множеству потребует несколько большей изворотливости ведь нам теперь нужно вычленить соответствующий бит:

Поясним, что здесь используется операция "побитовое и" (см. лекцию 2), которая работает непосредственно с битами нужной нам компоненты массива и числа, состоящего из семи нулей и единицы на месте с номером bit .

Добавление элемента в множество теперь будет записано так:

Здесь нельзя использовать обычную операцию сложения ( + ), так как если добавляемый компонент уже содержится в множестве (то есть соответствующий бит уже имеет значение 1 ), то в результате сложения 1+1 получится 10 : единица автоматически перенесется в старший бит, а на нужном месте окажется 0 .

Удаление элемента из множества придется записать более сложным образом:

Операция not превратит все 0 в 1 и наоборот, следовательно, теперь в качестве второго операнда для побитового and будет фигурировать число, состоящее из семи единиц и нуля на месте с номером bit . Единицы сохранят любые значения тех битов, которые должны остаться без изменения, и лишь 0 "уничтожит" значение единственного нужного бита.

Пересечение множеств реализуется теперь при помощи операции "побитовое и":

Объединение множеств реализуется при помощи операции "побитовое или":

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

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

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

Проверка двух множеств на включение ( set1<set2 ) будет производиться по схеме: "Если (A\B)B=A , то BA ", доказательство которой настолько очевидно, что мы не станем на нем задерживаться:

Замечание. Если предстоит многократно выполнять действия с элементами битовых массивов , то используемые для этого значения "единиц" удобнее всего сразу задать в специальном массиве:

И далее вместо громоздкой конструкции 1 shl(bit-1) можно использовать просто ed[bit] .

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

Задача 1. Оставить в строке только первое вхождение каждого символа , взаимный порядок оставленных символов сохранить.

Задача 2. 1) Оставить в строке только последнее вхождение каждого символа , взаимный порядок оставленных символов сохранить.

Задача 3. Выдать первые 100 000 натуральных чисел в случайном порядке без повторений.

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

Математическое понятие множества

Вспомним, как определяется множество в математике. Множество - это конечный или бесконечный набор определённых объектов, мыслимый как единое целое. Множество характеризуется своими элементами, а элементы имеют лишь одно свойство - принадлежность к данному множеству. Таким образом, мы можем только сказать, принадлежит элемент данному множеству или не приналдежит. Порядок расположения элементов в множестве никакой роли не играет.

Множества в Delphi

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

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

Перейдём ближе к делу. Множество может быть построено на основе перечислимого типа данных (кто забыл - открываем предыдущий урок). Например, на основе символьного типа Char. По-английски множество называется set (набор) и именно этим словом описывается в Delphi:

В данном примере мы объявили множество A на основе символьного типа Char.

Запомните: множество не может состоять более чем из 255 элементов!

Например, следующее описание:

приведёт к ошибке "Set base type out of range".

Задание множеств

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

Чтобы задать множество, мы можем воспользоваться операцией присваивания, где слева стоит переменная-множество, а справа - нужный нам набор. Например, в описанное выше множество A мы хотим поместить элементы-символы A, B, C, D. Тогда это запишется так:

Теперь множество A содержит 4 элемента.

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

Мы просто указали диапазон значений, который должен находиться во множестве. Результаты одинаковый, но вторая запись короче и красивее. Допустимы, конечно же, комбинации диапазонов и отдельных значений:

Помните, что множество - это виртуальный набор элементов: множество нельзя ввести с клавиатуры и точно так же нельзя вывести на экран. Поэтому добавление элементов во множество делается только программным путём. Безусловно, вы каким-либо образом можете связать элементы интерфейса программы и операцию добавления элементов во множество, но напрямую ввести множество нельзя. Аналогично, вы можете показать множество на экране с помощью каких-либо элементов (например, флажков TCheckBox), но само множество "в чистом виде" вывести нельзя.

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

В программировании, как и в математике, над множествами допустимы некоторые операции. Рассмотрим их.

Находится ли элемент во множестве?

Самая простая операция, для понятия смысла которой даже не нужно задумываться. Чтобы проверить, входит ли элемент во множество, следует использовать специальную конструкцию с оператором in . Слева от него указывается элемент, справа - множество. Результатом, как несложно догадаться, является логичное значение - истина или ложь. True - элемент принадлежит множеству, False - не принадлежит:

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

Если есть два множества, определённые на одном и том же типе данных, то их можно объединить и получить таким образом новое множество.

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

В словесном описании операция объединения - результирующее множество содержит все те элементы, которые есть хотя бы в одном из двух исходных множеств.

Объединение записывается знаком плюс " + ". Пример:

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

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

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

Пересечение обозначается звёздочкой " * ". Пример:

Разность множеств

Операция вычитания удаляет из первого множества те элементы, которые есть во втором множестве:

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

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

Множества находят широкое применение. С помощью множеств удобно задавать набор опций, каждая из которых либо включена, либо выключена. К примеру, поместите на форму кнопку (TButton), перейдите в инспектор объектов, разверните свойство Font (шрифт) и найдите свойство Style. Вот это свойство как раз и реализовано множеством. Во множестве 4 элемента: fsBold, fsItalic, fsUnderline и fsStrikeOut, каждый из которых отвечает за стиль шрифта. Принадлежность элементов ко множеству задаётся указанием значения True или False для каждого из этих пунктов. В строке "Style" находится описание данного множества. Попробуйте изменять стиль и посмотреть, как меняется описание множества Style.

А теперь давайте сделаем простенький интерфейс для доступа к этому свойству. Пусть будет меняться стиль шрифта у этой кнопки (Button1). Поместим на форму 4 TCheckBox - для доступа ко всем значениям и дадим им соответствующие имена. Изменение стиля будем делать при нажатии на саму эту кнопку. Пример реализации:

Чтобы не повторять везде одно и то же "Button1. Font .", эту часть кода можно, что называется, вынести за скобку при помощи специального оператора with . Ранее речь о нём не шла, однако этот оператор очень удобен. Смысл его прост: то, что вынесено вперёд, автоматически применяется ко всему, что находится внутри данного блока. В нашем случае будет так:

Согласитесь, так гораздо удобнее. Используйте оператор with как можно чаще - с его помощью и код по объёму становится меньше и скорость работы увеличивается.

У большинства компонент среди свойств можно найти множества. Например, у диалога открытия файла TOpenDialog (вкладка Dialogs) множеством представлено свойство Options, которое содержит приличное число элементов:

Вы спросите - а что это за названия элементов у множеств? Ответ прост - это специально объявленный перечислимый тип данных, на основе которого и создано множество. Если немного покопать, то можно найти описание этого типа:

Заключение

Сегодня мы познакомились с множествами - наборами элементов. С помощью множеств реализованы свойства многих компонент. Множества не дают возможности хранить какие-либо значения - они просто позволяют создавать наборы из значений перечислимых типов данных. Но во многих случаях использование множеств - лучший и самый быстрый способ хранения некоторого набора параметров.

Автор: Ерёмин А.А.

Статья добавлена: 18 июля 2008

Рейтинг статьи: 4.80 Голосов: 5 Ваша оценка:

Зарегистрируйтесь/авторизируйтесь,
чтобы оценивать статьи.

Статьи, похожие по тематике

Для вставки ссылки на данную статью на другом сайте используйте следующий HTML-код:

Ссылка для форумов (BBCode):

Поделитесь ссылкой в социальных сетях:

Комментарии читателей к данной статье

Цитата (antoca):

А кто-то говорит про всегда? Есть места, где их просто нужно применять, иначе получится бред, а не код. Множества не всегда удобно применять. Обычно массивы лучше, и не важно будет ли это медленней.

Математическое понятие множества

Множества в Delphi

В данном примере мы объявили множество A на основе символьного типа Char.

Запомните: множество не может состоять более чем из 255 элементов!

Например, следующее описание:

приведёт к ошибке "Set base type out of range".

Задание множеств

Теперь множество A содержит 4 элемента.

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

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

В программировании, как и в математике, над множествами допустимы некоторые операции. Рассмотрим их.

Находится ли элемент во множестве?

Самая простая операция, для понятия смысла которой даже не нужно задумываться. Чтобы проверить, входит ли элемент во множество, следует использовать специальную конструкцию с оператором in. Слева от него указывается элемент, справа - множество. Результатом, как несложно догадаться, является логичное значение - истина или ложь. True - элемент принадлежит множеству, False - не принадлежит:

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

Объединение записывается знаком плюс "+". Пример:

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

Пересечение обозначается звёздочкой "*". Пример:

Разность множеств

Операция вычитания удаляет из первого множества те элементы, которые есть во втором множестве:

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

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

Чтобы не повторять везде одно и то же "Button1.Font.", эту часть кода можно, что называется, вынести за скобку при помощи специального оператора with. Ранее речь о нём не шла, однако этот оператор очень удобен. Смысл его прост: то, что вынесено вперёд, автоматически применяется ко всему, что находится внутри данного блока. В нашем случае будет так:

В Delphi разрешено определять тип объектов-множеств, элементами которых являются значения одного и того же базового типа. Базовый тип определяет перечень всех элементов, которые могут содержаться в данном множестве. Количество элементов, входящих в множество, может меняться в пределах от 0 до 256 (множество, не содержащее элементов, называется пустым).

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

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

Здесь <имя типа> - идентификатор; <базовый тип> - один из скалярных типов, кроме вещественного. Базовый тип задаётся диапазоном или перечислением. Из стандартных типов в качестве базового типа множества могут быть указаны типы byte, char и boolean. Базовый тип вводится либо через предварительное определение в разделе описаний программы, либо с помощью прямого указания после слов set of в описании типа множества, например:

type letter = 'a' .. 'z'; // Описание ограниченного типа letter
type SL = set of letter; // Описание множественного типа SL с базовым типом letter

type SLR = set of 'a' .. 'z'; // Прямое включение определения базового типа 'a .. 'z' в описание множественного типа SLR

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

type intset = set of byte;
var m1, m2: intset; // Переменные описаны через указание принадлежности ранее определённому типу
var m3: set of 1..20; // Определение типа переменной непосредственно включено в её описание

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

[ ] - пустое множество;
[1, 3, 5 .. 12] - множество, содержащее элементы 1, 3, 5, 6, .. 12;
['a' .. 'p', 'u', 'z'] - множество, состоящее из перечисленных символов типа char.

Элементы типа множества могут задаваться в виде выражений, например: [2+4, 3 * 2]. Выражения должны иметь значения из заданного базисного множества порядкового типа. Область значений переменной множественного типа представляет собой набор всевозможных подмножеств, образованных из элементов базового типа.

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

Над переменными множественного типа могут выполняться те же операции, что и над обычными множествами:

1. Объединение ( + );
2. Пересечение ( * );
3. Разность ( - ).

Кроме того, определённые операции проверки принадлежности элемента множеству ( in ), проверки тождественности множеств ( = ), нетождественности, множеств ( <> ), определения принадлежности (вложенности) множеств ( >= или <= ). Примеры:

1. [1, 2, 4] = [1, 4, 2] // Результат True
2. ['a' .. 'z'] = ['a' .. 'p'] // Результат False
3. [1, 2, 5, 6] <> [1, 2] // Результат True
4. ['a', 'b', 'c'] <= ['a' .. 'z'] // Результат True
5. ['a' .. 'k'] >= ['a' .. 'z'] // Результат False
6. [1, 2, 3] + [1, 4, 5] // Результат [1, 2, 3, 4, 5]
7. [1, 2, 3] * [1, 3, 4, 5] // Результат [1, 3]
8. [1, 3, 4, 5] - [1, 4, 6] // Результат [3, 5]

Операция in позволяет определить, принадлежит ли элемент множеству или нет. Первым операндом, стоящим слева от слова in, является выражение базового типа. Второй операнд, стоящий справа от слова in, должен иметь множественный тип, например:

a in [a, b, c, d] // Результат True
2 * 4 in [0 .. 4, 7 .. 10] // Результат True
'a' + 'b' in ['ab', 'cd', 'ef'] // Результат True
5 in [1 * 2, 4, 5] // Результат True
5 in [2, 4, 6, 8] // Результат False

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

Операция in позволяет проводить эффективно сложные проверки условий. Например, вместо:

Причём последняя конструкция будет, как правило, более эффективной.

Операции ( = ) и ( <> ) позволяют проверить, равны ли два множества или нет. С помощью операций ( >= ) и ( <= ) можно определить, является ли одно множество подмножеством другого. Пример:

[red, white] = [red, green] // Результат False
[1] <= [0 .. 4] // Результат True

Замечания:
1. Пустое множество [ ] является подмножеством любого другого множества независимо от базового типа его элементов.
2. Множества-операнды могут иметь непересекающиеся базовые типы. Располагая, например, множествами A: set of 1 .. 99 и B: set of 100 .. 150, можно в результате объединения A+B получить новое множество с базовым типом 1 .. 150.
3. Следует различать конструктор множества [X .. Y] и отрезок порядкового типа X .. Y. При X > Y в первом случае речь идёт о пустом множестве, а во втором компилятор выдаст ошибку. Пример:

['a', 'b'] = ['b' .. 'a'] // Результат False

При проверке на подмножество выполняется тест на "меньше или равно", а не только проверка на собственное подмножество, т.е без "равно". Операции ( < ) и ( > ) не предусмотрены, поэтому при необходимости проверку на собственное подмножество для множеств A и B можно провести следующим образом:

(A <= B) and (A >= B) или (A >= B) and (A <> B)

Для задания правильного порядка выполнения операций следует учитывать принятый порядок старшинства (приоритета) операций над множествами: пересечение ( * ) имеет тот же приоритет, что и арифметические операции умножения и деления; объединение ( + ) и разность ( - ) занимают следующий, более низкий уровень приоритета, аналогично арифметическим операциям сложения и вычитания; на самом нижнем уровне находятся операции сравнения множеств ( =, <>, <=, >=) и проверки принадлежности элемента множеству ( in ). Операции одного приоритета выполняются слева направо. Для изменения порядка выполнения операций используются круглые скобки.

Наиболее эффективно множество может быть использовано для замены операторов if, например, для проверки наличия некоторого ответа в списке разрешённых. Приведённая ниже программа ввода строки символов, содержащей латинские буквы, цифры и пробелы с контролем правильности введённых символов, может служить примером использования множеств:

var
str: string;
L: byte;
t: boolean;

begin
Writeln('Enter string');
readln(str);
L:=length(str); // Число введённых символов
t:=L>0; // True, если не пустая строка
while t and (L>0) do // Проверка с конца строки
begin
t:=str[L] in ['0' .. '9', 'a' .. 'z', 'A' .. 'Z']; // Проверка допустимости символа
dec(L); // Предыдущий символ
end;
if t then writeln('True String') // Правильная строка
else writeln('False string]'); // Неправильная строка
Readln;
end.

Пример процедуры выводящей элементы множества с указанием их числа и её реализация (пример приложен к статье):

var
a: set of char;
s: string[50];
count: integer;
i,l: integer;

procedure Mnogo;
var
ch: char;
begin
for ch:=low(char) to high(char) do
if ch in a then
begin
write(ch, '');
inc(count);
end;
writeln;
writeln('Kol-vo simbol: ', count);
end;

begin
write('Enter the String please: ');
readln(s);
l:=length(s);
for i:=1 to l do a:=a+[s[i]];
mnogo;
readln;
end.

Читайте также: