Находится ли элемент во множестве? Изучение нового материала

Множества объектов kset Множества kset представляют собой коллекции объектов kobject. Множество kset работает как базовый контейнерный класс для объектов, например, "все блочные устройства". Множества kset очень похожи на типы ktype, и возникает вопрос: "Для чего нужны два разных

Федоренко Сергей

Введение

В 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, 6, .. 12;
["a" .. "p", "u", "z"] - множество, состоящее из перечисленных символов типа char.

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

В отличие от перечислений нельзя говорить о первом, втором и т.п. элементах множества, поскольку для множеств понятие упорядоченности не имеет смысла. Если множество содержит всего три элемента, то общее количество возможных комбинаций составляет 2 * 2 * 2 = 8. Зарезервированное слово set способно определять множество размерностью до 256 элементов, т.е. 1,1579208923731619542357098500869e+77 вариантов. На практике такое количество вариантов никогда не понадобится. В частности, разработчики Delphi рекомендуют использовать множество с количеством элементов не более 16.

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

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

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

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

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

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

a in // Результат True
2 * 4 in // Результат True
"a" + "b" in ["ab", "cd", "ef"] // Результат True
5 in // Результат True
5 in // Результат False

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

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

(c >= "0") and (c <= "9") or (c >= "a") and (c <="z");

Проще записать:

c in ["0" .. "9", "a" .. "z"];

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

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

= // Результат False
<= // Результат True

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

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

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

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

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

Использование множеств

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

program Project1;

{$APPTYPE CONSOLE}

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

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

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

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

Delphi множества

Например:

Type <имя типа> = set of <базовый тип>;
В этом случае <имя типа> выступает в качестве идентификатора. А <базовый тип> является одним из скалярных типов, он задается перечислением или определенным диапазоном. Среди стандартных типов в качестве базового можно использовать char, byte, boolean. Задать тип можно как в части описания программы, так и путем прямого указания в описании множества.

Например: Первый вариант.

Type abc = "c" .. "q"; // Описание типа abc type FG = set of abc; // Описание множественного типа FG с базовым типом abc
Второй вариант.

Type FGH = set of "c" .. "q"; // Прямое включение определения базового типа "c’ .. "q" в описание множественного типа FGH
Рассматривая в delphi множества, стоит отметить тот фат, что нет смысла говорить об упорядоченности. Например, если в определенное множество входит всего три объекта, то общее количество разных вариаций будет равно восьми.

После того, как множество будет определено, с ним можно выполнять разные операции. В delphi множества можно объединить, пересекать. Помимо этого, доступны такие операции, как разность и IN.

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

В Delphi можно использовать операции принадлежности. Одно множество принадлежит другому, если все его элементы входят в состав другого множества.

Например, A >= B равно True, если все элементы множества В есть и во множестве А.

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

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

Применение множеств в реализации той или иной программы, дает возможность программистам в значительной степени улучшить наглядность алгоритма, упростить оператор if, а также сэкономить немного времени. Использовать множества в Delphi очень просто, особенно, если брать за сравнение администрирование linux.

При создании любой серьёзной программы не обойтись без дополнительных, более сложных, чем числа и строки, типов данных. В Delphi программист может для своих целей конструировать собственные типы данных. Чтобы ввести в программу (описать) новый тип данных, применяется оператор с ключевым словом type :
type название_типа = описание_типа;

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

type FootballTeam = (Spartak, Dinamo, CSKA, Torpedo, Lokomotiv);
var MyTeam: FootballTeam;
begin
MyTeam:=Spartak;
end;

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

• все целочисленные типы, для которых всегда можно указать число, следующее за числом N;
• символьные типы (Char): за символом "a" всегда следует "b", за "0" следует "1", и так далее;
• логические типы - тип Boolean также представляет собой перечислимый тип: type Boolean = (false, true);

• массивы
• записи
• множества

type имя_типа_массива = array [диапазон] of тип_элемента;

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

type TMyArray = array of Integer;

Теперь можно описать переменные типа TMyArray:

var A, B: TMyArray;

Вместо присвоения типа можно явно описать переменные как массивы:

var A, B: array of Integer;

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

var N: Integer;
begin
N:= 65;
A := 101;
A[N] := 165;
A := 200;
B:= A;
end;

Иногда требуется узнать верхнюю или нижнюю границу массива . Для этого служат встроенные функции:

High() - вернёт число, являющееся верхней границей массива;
Low() - вернёт число, являющееся нижней границей массива.

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

Выражение B:= A означает, что каждый элемент массива B будет равен элементу с таким же индексом массива A . Такое присвоение возможно только если оба массива объявлены через некий поименованный тип, или перечислены в одном списке. И в случае:

var A: array of String;
B: array of String;

Его использовать невозможно (но возможно поэлементное присвоение B := A; и т.д.).

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

type MyTable = array of Integer;
var X: MyTable;
Y: Integer;
begin
Y:=X;
end;

Теперь в результате операции присвоения Y будет равен 7 .
Многомерный, например, двумерный массив можно описать как массив массивов:

type TMyArray = array of array of Integer;

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

type TDinArray = array of Integer;
var A: TDinArray;

После создания в динамическом массиве нет ни одного элемента. Необходимый размер задаётся в программе специальной процедурой SetLength . Массив из ста элементов:

begin
SetLength(A, 100);
end;

Нижняя граница динамического массива всегда равна нулю. Поэтому индекс массива A может изменяться от 0 до 99 .
Многомерные динамические массивы описываются именно как массивы массивов . Например, двумерный:

type T3DinArray = array of array of Integer;
var A: T3DinArray;

В программе сначала задаётся размер по первому измерению (количество столбцов):

Чтобы освободить память, выделенную динамическому массиву, нужно массиву как целому присвоить значение nil :
A:=nil;
Ключевое слово nil в Delphi означает отсутствие значения.

Записи очень важный и удобный инструмент. Даже не применяя специальные технологии, с его помощью можно создавать собственные базы данных . Записи - это структура данных, каждый элемент которой имеет собственное имя и тип данных. Элемент записи иначе называют поле . Описание записи имеет вид:
type имя_типа_записи = record
название_поля: тип_поля;
. . .
название_поля: тип_поля;
end;
Названия полей, имеющих одинаковый тип, можно, как и в случае описания переменных, указывать в одну строку через запятую. Для обращения к полю записи сначала указывают имя записи, затем точку, затем имя поля. Например, данные о персонале предприятия могут быть организованы таким типом записи:

type TPers = record
Fam, Name, Par: String;
Year: Integer;
Dep: String;
end;
var Pers: TPers;
begin
Pers. Fam:="Иванов";
Pers. Name:="Иван";
Pers. Par:="Иванович";
Pers. Year:=1966;
Pers. Dep:="Цех №1";
end;

Теперь осталось записать эти данные в файл, предварительно объявив и его тип как TPers , и база данных готова. С файлом в Delphi также ассоциируется переменная, называемая файловой переменной, которая описывается так:
VFile : file of тип_файла;
В качестве типа может использоваться любой ограниченный тип Delphi. При этом не допускается тип String , так как он допускает переменный размер до 2 ГБайт. Его необходимо ограничивать: String[N] , где N - количество символов. Тип TPers из предыдущего примера должен быть описан, например, так:

type TPers = record
Fam, Name, Par: String;
Year: Integer;
Dep: String;
end;

Теперь переменная такого типа занимает строго определённое место в памяти, и может быть записана в файл. Как это сделать, рассказывается во 2-й части Урока №7.

Множество - это группа элементов, объединённая под одним именем, и с которой можно сравнивать другие величины, чтобы определить, принадлежат ли они этому множеству. Количество элементов в одном множестве не может превышать 256. Множество описывается так:

type имя_множества = set of диапазон_значений_множества;

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

type TMySet = set of 0 .. 255;
type TMySet = set of Byte;

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

var MySet: TMySet;
begin
MySet:=;
end;

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

var Key: Char;
Str: String;