|
|
Структуры данных и эффективность алгоритмов. 4
Множество (Set). [7 гл.4.1-4; 13 п.10.2; 2 гл.4.]
Множество возможных значений – конечные множества элементов одинакового типа.
Набор операций:
Вставить элемент во множество.
Удалить элемент из множества.
Принадлежать – функция, возвращающая значение true, если элемент принадлежит множеству.
Для такого фундаментального понятия классической математики представляется естественным расширить набор операций до типового классического. Но по ряду причин прагматического характера в программировании такое АТД общего (универсального) вида представляет ограниченный интерес. Например, включение операции объединения пересекающихся множеств, при реализации требует удаления элементов пересечения. Это может значительно усложнить реализацию этой операции. С другой стороны наличие дубликатов может быть некритичным с позиции решаемой задачи, в этом случае АТД представляют собой мультимножества. Фундаментальное значение понятия множества, конечно, проявляется наличием богатого набора специализированных расширений этого базового АТД «Множество», которые широко используются в практике программирования, как благодаря мощной выразительной силе этого инструментария в разработке модели задач и алгоритмов их решения, так и благодаря наличию эффективных методов реализации этих АТД.
Специализированные расширения АТД «Множество» рассматриваются в различных направлениях:
Близким к понятию «множество» является понятие «набор». Набор (Bag, MultiSet) [9] – также как и множество является семейством элементов, безотносительно к тому задано ли на элементах отношение порядка14, но элементы в наборе могут повторяться по значению. Вообще говоря, набор можно представить множеством, например, элементы которого являются парами [значение элемента, количество вхождений в набор].
В практических приложениях часто элементы множеств идентифицируются, т.е. элемент является парой [ключ элемента, собственно значение элемента], АТД «Словарь» - пример такого специализированного расширения АТД «Множество». Предпочтительный случай, когда ключ элемента – уникальный, т.е. множество не может содержать двух элементов с одинаковым ключом. Но возможно, что используемый ключ неуникальный, т.е. неоднозначно идентифицирущий собственно значение элемента. Вообще говоря, множество (и набор) с неуникальным ключом можно представить множеством с уникальным ключом, усложнив тип значения элемента, например, рассматривая в качестве значения элемента множество значений предыдущего типа (с одинаковым ключом).
Естественным представляется задание на множестве отношения порядка, частичного или линейного, АТД «Очередь с приоритетом» - пример такого специализированного расширения АТД «Множество». Аналогично в предметной области решаемой задачи могут представлять интерес и другие отношения на множестве [17].
Фундаментальное положение в математике занимает понятие отношение эквивалентности и соответственно – понятие разбиение множества на классы эквивалентности. Естественно, что это понятие широко используется и в практических разработках моделей решения задач предметных областей. АТД «Семейство непересекающихся множеств» (Disjoint Sets, Partitions, Разбиения) - пример соответствующего специализированного расширения АТД «Множество».
Для специализированных расширений АТД «Множество» естественно соответствующим образом уточняются вышеотмеченные операции и появляются свои новые операции, представляющие интерес.
Словарь (Dictionary, Map), другое название – ассоциативный массив [7 п.4.5-8; 3 гл.12; 2 п.4.10; 13 гл.8.].
Множество возможных значений – конечные множества элементов одинакового типа, вида [Key, Value], где Key – уникальный ключ элемента, Value - собственно значение.
Набор операций:
Вставить элемент (с ключом) во множество.
Удалить элемент (заданный ключом) из множества.
Найти элемент – функция, возвращающая по ключу значение элемента или «пустое» значение, если элемента с таким ключом нет во множестве.
АТД «Словарь» - это специализированный вариант понятия (хранимое) отображение (ключей в значения), широко используемый в практическом программировании. Но для некоторых предметных областей возможно более удобным окажется оформление АТД «Отображение» (Mapping), более близкое классическому математическому определению [7 п.2.5,4.9.].
|
|
|
Скачать 2.32 Mb.