2014-02-09
2631
В программировании часто приходится иметь дело с множествами, меняющимися в процессе выполнения алгоритма. Существуют структуры данных, предназначенные для хранения изменяющихся
(динамических, по-английски dynamic) множеств.
Разные алгоритмы используют разные операции. Нередко, например, тре-
буется лишь добавлять и удалять элементы в множество, а также проверять,
принадлежит ли множеству данный элемент. Структура данных, поддержива-
ющая такие операции, называется словарём (dictionary). В других ситуациях
могут понадобиться более сложные операции. Например, очереди с приорите-
тами, в связи с кучами, разрешают выбирать
и удалять наименьший элемент (помимо добавления элементов). Понятно, что
выбор реализации динамического множества зависит от того, какие операции
с ним нам потребуются.
Обычно элемент динамического множества – это запись, содержащая раз-
личные поля. Часто одно из полей рассматривается как ключ (key), предназначенный для идентификации элемента, а остальные поля – как дополнительные
данные (satellite data), хранящиеся вместе с ключом. Элемент множества ищется
по ключу; когда элемент найден, мы можем прочесть или изменить дополнительную информацию, имеющуюся в этом элементе. Во многих случаях все ключи
различны, и тогда множество можно рассматривать как функцию, которая каждому существующему ключу ставит в соответствие некоторую дополнительную
информацию.
|
|
|
Многие способы реализации множеств требуют, чтобы вместе с каждым
ключом хранились не только дополнительные данные, но и некоторая служебная
информация (например, указатели на другие элементы множества).
Часто на множестве ключей имеется естественный линейный порядок (на-
пример, ключи могут быть действительными числами или словами, на которых есть лексикографический порядок). В этом случае можно говорить, например, о наименьшем элементе множества или об элементе, непосредственно следующем за данным.
Предполагается, что элементы множества хранятся в некоторой общей
области памяти и для каждого элемента имеется указатель, который позволяет
получить доступ к этому элементу. Обычно в качестве указателя выступает
просто адрес в памяти; если язык программирования этого не предусматривает,
указателем может быть индекс в массиве.
Операции над множествами делятся на запросы (queries), не меняющие множества, и операции, меняющие множество (modifying operations). Перечислим
типичные операции над множествами.
Таблица 1.3 – Основные операции над динамическими множествами (основные словарные операции)
| Search(S,k) (поиск) | Запрос, который по данному множеству S и ключу k возвращает указатель на элемент множества S с ключом k. Если такого элемента в множестве S нет, возвращается NIL. |
| Insert(S,x) (вставить) | Добавляет к множеству S элемент, на который указывает указатель х (подразумевается, что кэтому моменту все поля в записи, на которую указывает х, уже заполнены). |
| Delete(S,x) (удалить) | Удаляет из множества S элемент, на который указывает указатель z (обратите внимание, что х – указатель, а не ключ). |
| Minimum(S) (минимум) | Выдаёт указатель на элемент множества S с наименьшим ключом (считаем, что ключи линейно упорядочены). |
| Maximum(S) (максимум) | Выдаёт указатель на элемент множества S с наибольшим ключом. |
| Successor(S,z) (следующий) | Возвращает указатель на элемент множества S, непосредственно следующий за элементом z (в смысле линейного порядка на ключах). Если х – наибольший элемент, возвращается NIL. |
| Predecessor(S,х) (предыдущий) | Возвращает указатель на элемент множества S, непосредственно предшествующий элементу х (если х – наименьший элемент, возвращается NIL). |
Операции Successor и Predecessor часто используются и при работе с множествами, в которых ключи различных элементов могут совпадать. При этом
разумная реализация гарантирует выполнение различных естественных свойств.
|
|
|
Например, функции Successor и Predecessor взаимно обратны; кроме того, начав с Minimum(S)и применяя функцию Successor, можно осуществить перечисление всех элементов множества в неубывающем порядке.
Стоимость операций над множествами обычно оценивается через размер
множеств, к которым они применяются.
