Множество является базовой структурой, которая лежит в основании всей математики..
При разработке алгоритмов множества используются как основа многих важных абстрактных типов данных.
Множеством называется некая совокупность элементов, каждый элемент или сам является множеством, или является примитивным элементом, называемым атомом.
Будем предполагать, что все элементы любого множества различны.
Все элементы одного множества имеют одинаковый тип данных (целые, символы, строки символов и т.п.)
Линейно упорядоченное множество Sудовлетворяет условиям:
Для любых элементов a и b из множества S может быть справедливымтолько одно из следующих утверждений: a < b, a = b, a > b
Для любых элементов a, b, c из множества S таких, что a < b и b < c, следует a < c.
Операторы АТД, основанные на множествах:
1.UNION (A, B, C) - объединение множеств C = A È B
2. INTERSECTION (A, B, C)- пересечение множеств
C = A Ç B
3. DIFFERENCE (A, B, C)- разность множеств C = A \ B
4. MERGE (A, B, C)-слияние (объединение) непересекающихся множеств C = A È B. Результат не определен, если A Ç B ≠ Æ
5. функция MEMBER (x, A) имеет аргументами множество A и объект x того же типа, что и элементы множества A, и возвращает булево значение true, если x ÎA, и значение false, если x ÏA
6. MAKENULL(A) – процедура присваивает множеству A значение пустого множества.
7. Процедура INSERT (x, A) делает x элементом множества A.
8. Процедура DELETE (x, A) удаляет элемент x из множества A.
9. Процедура ASSIGN(A, B) присваивает множеству A в качестве значения множество B.
10 Функция MIN (A) возвращает наименьший элемент множества A. Для применения функции необходимо, чтобы множество A было параметризовано и его элементы были линейно упорядочены.
11. Функция EQUAL (A, B) возвращает значение true тогда и только тогда, когда множества A и B состоят из одних и тех же элементов.
12. Функция FIND (x) оперирует в среде, где есть набор непересекающихся множеств. Она возвращает имя (единственное) множества, в котором есть элемент x