Методические указания алгоритмы и структуры данных. Методические указания к лабораторным работам, практическим занятиям и курсовому проектированию Часть 2 Выпуск 1606
 Скачать 429.85 Kb.
|
3. ПОДДЕРЖКА ПРОИЗВОЛЬНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ В СТРУКТУРЕ ДАННЫХ ДЛЯ МНОЖЕСТВК одной структуре данных могут применяться операции как для множества, так и для последовательности. Иногда требуется поддерживать в структуре данных для множеств произвольную последовательность элементов этих множеств. Например, можно фиксировать порядок появления элементов в множестве при его создании и работать с этим порядком. Последовательность из структуры данных для множеств может быть получена как результат её обхода. Часто этого бывает достаточно: порядок элементов для результата операции над множествами можно назначить произвольно. Однако для множества мощностью 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.1. Практикум по темеДополнить программу, составленную по теме «Хеш-таблицы» или «Деревья двоичного поиска», операциями над последовательностями, указанными в табл. 3.1 в соответствии с номером задания. Выбрать такой способ доработки структуры данных, чтобы получились эффективные алгоритмы. Таблица 3.1Индивидуальные задания к теме «Последовательности»
3.2. Требования к отчётуВ отчёте по этой теме должно быть обоснование выбора способа дополнения базовой структуры данных для обеспечения возможности выполнения операций с последовательностями. В выводах можно дать заключение, насколько выбор оказался удачным. 3.3. Контрольные вопросы1. Почему для хранения произвольной последовательности структуру данных для множества (хеш-таблицу или ДДП) приходится дорабатывать? 2. Какие доработки возможны? 3. Можно ли предложить оптимальный вариант доработки? 4. Влияет ли доработка структур данных для множеств для поддержки последовательностей на временную сложность операций над множествами? 5. Какую структуру данных проще дорабатывать — хеш-таблицу или ДДП? 6. Какова оптимальная доработка структуры данных и временная сложность для операции исключения части последовательности между указанными позициями? 7. То же — для операции вставки с указанной позиции? 8. То же — для замены? |