Вопрос 19: Множество и последовательность. Хранение последовательностей в структуре данных для множеств. Варианты: обход, разметка, связи, массив ссылок.

Множество - это совокупность объектов, рассматриваемое как единое целое. Последовательность – это упорядоченное множество. Хранить можно в массивах, списках, хэш таблицах, деревьях.

Способы получения последовательностей:

1. Обход – получение последовательности из структуры данных для множеств

2. Разметка – присоединение к каждому ключу дополнительного поля для хранения порядкового номера. При удалении нужно сдвинуть все последующие номера на -1, в худшем случае придется обходить всю последовательность (вр. $O(n)$).

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

4. Массив указателей – дополнительное поле в ключах с указателем на соответствующие элементы массива (нет дополнительных расходов на определение ключа и наоборот)