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

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

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

1) присоединить к каждому ключу дополнительное поле для хранения порядкового номера. Способ не создаёт проблем при поиска номера по значению ключа и при вставке новых ключей, они просто нумеруются по порядку. Удаление ключа требует просмотра всей структуры данных для корректировки номеров, следующих за удаляемым. То же приходится делать при поиске ключа по порядковому номеру (сложность O (n));

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

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

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

Операции над последовательностями:

1. Слияние (MERGE). Объединение двух упорядоченных последовательностей в третью с сохранением упорядоченности. От операции объединения множеств отличается только возможностью появления дубликатов ключей. Если исходные последовательности не упорядочены, можно после их слияния просто упорядочить результат. Исходный порядок ключей в множествах в результате не сохраняется.

2. Сцепление (CONCAT). Вторая последовательность подсоединяется к концу первой, образуя её продолжение.

3. Размножение (MUL). Последовательность сцепляется сама с собой заданное количество раз.

4. Укорачивание (ERASE). Из последовательности исключается часть, ограниченная порядковыми номерами от p ₁ до p ₂.

5. Исключение (EXCL). Вторая последовательность исключается из первой, если она является её частью.

6. Включение (SUBST). Вторая последовательность включается в первую с указанной позиции p. Операция похожа на конкатенацию. Сперва берётся начало первой последовательности до позиции p, затем идёт вторая последовательность, а за ней — остаток первой.

7. Замена (CHANGE). Вторая последовательность заменяет элементы первой, начиная с заданной позиции p.

Пример. Пусть имеются две последовательности A = < 5, 3, 2, 4, 6, 7, 9, 1> и B = < 6, 7, 9>. Позиции считаются от 0.

Тогда операция MERGE даст результат < 1, 2, 3, 4, 5, 6, 6, 7, 7, 9, 9>;

CONCAT — < 5, 3, 2, 4, 6, 7, 9, 1, 6, 7, 9>;

MUL (B, 3) — < 6, 7, 9, 6, 7, 9, 6, 7, 9>;

ERASE (A, 2, 4) — < 5, 3, 7, 9, 1>;

EXCL — < 5, 3, 2, 4, 1>;

SUBST (3) — < 5, 3, 2, 6, 7, 9, 4, 6, 7, 9, 1>;

CHANGE (2) — < 5, 3, 6, 7, 9, 7, 9, 1>.