К одной структуре данных могут применяться операции как для множества, так и для последовательности. Иногда требуется поддерживать в структуре данных для множеств произвольную последовательность элементов этих множеств. Например, можно фиксировать порядок появления элементов в множестве при его создании и работать с этим порядком.
Последовательность из структуры данных для множеств может быть получена как результат ее обхода. Часто этого бывает достаточно: порядок элементов для результата операции над множествами можно назначить произвольно. Однако для множества мощностью n это будет только одна из n! возможных последовательностей. Если нужно поддерживать любую последовательность, возможны следующие подходы:
1) присоединить к каждому ключу дополнительное поле для хранения порядкового номера. Способ не создает проблем при поиске номера по значению ключа и при вставке новых ключей, они просто нумеруются по порядку. Удаление ключа требует просмотра всей структуры данных для корректировки номеров, следующих за удаляемым. То же приходится делать при поиске ключа по порядковому номеру (сложность O(n));
2) с помощью дополнительных указателей для каждого ключа сформировать из них список, возможно, двунаправленный. Проходом по этому списку можно как восстановить хранящуюся последовательность, так и получить номер для каждого ключа. Доступ к ключу по номеру и наоборот в этом случае имеет линейную сложность. Зато как вставка, так и удаление ключа требуют минимальных накладных расходов;
3) создать массив указателей на ключи. Если одновременно поддерживать в ключах дополнительное поле с обратным указателем на соответствующие элементы массива, можно избежать дополнительных расходов как для определения ключа по номеру, так и номера по ключу. Недостаток способа — необходимо заранее знать объем памяти для создания массива и перемещать часть массива в случае удаления ключей.
Операции над последовательностями, в отличие от операций с множествами, могут приводить к появлению дубликатов ключей. Структура данных для множеств должна обеспечивать соответствующую возможность.
Операции над последовательностями:
1. Слияние (MERGE). Объединение двух упорядоченных последовательностей в третью с сохранением упорядоченности. От операции объединения множеств отличается только возможностью появления дубликатов ключей. Если исходные последовательности не упорядочены, можно после их слияния просто упорядочить результат. Исходный порядок ключей в последовательностях в результате не сохраняется.
2. Сцепление (CONCAT). Вторая последовательность подсоединяется к концу первой, образуя ее продолжение.
3. Размножение (MUL). Последовательность сцепляется сама с собой заданное количество раз.
4. Укорачивание (ERASE). Из последовательности исключается часть, ограниченная порядковыми номерами от p1 до p2.
5. Исключение (EXCL). Вторая последовательность исключается из первой, если она является ее частью.
6. Включение (SUBST). Вторая последовательность включается в первую с указанной позиции p. Операция похожа на конкатенацию. Сперва берется начало первой последовательности до позиции p, затем идет вторая последовательность, а за ней — остаток первой.
7. Замена (CHANGE). Вторая последовательность заменяет элементы первой, начиная с заданной позиции p.
Пример. Пусть имеются две последовательности A = <5, 3, 2, 4, 6, 7, 9, 1> и B = <6, 7, 9>. Позиции считаются от 0.
Тогда операция A.MERGE(B) даст результат <1, 2, 3, 4, 5, 6, 6, 7, 7, 9, 9>;
A.CONCAT(B) — <5, 3, 2, 4, 6, 7, 9, 1, 6, 7, 9>;
B.MUL(3) — <6, 7, 9, 6, 7, 9, 6, 7, 9>;
A.ERASE(2, 4) — <5, 3, 7, 9, 1>;
A.EXCL(B) — <5, 3, 2, 4, 1>;
A.SUBST(B, 3) — <5, 3, 2, 6, 7, 9, 4, 6, 7, 9, 1>;
A.CHANGE(B, 2) — <5, 3, 6, 7, 9, 7, 9, 1>.
3.3.1. Контрольные вопросы
1. Почему для хранения произвольной последовательности структуру данных для множества (хеш-таблицу или ДДП) приходится дорабатывать?
2. Какие доработки возможны?
3. Можно ли предложить оптимальный вариант доработки?
4. Влияет ли доработка структур данных для множеств для поддержки последовательностей на временную сложность операций над множествами?
5. Какую структуру данных проще дорабатывать — хеш-таблицу или ДДП?
6. Какова оптимальная доработка структуры данных и временная сложность для операции исключения части последовательности между указанными позициями?
7. То же — для операции вставки с указанной позиции.
8. То же — для замены.
|
Скачать 0.78 Mb.