Массивы и списки
Для начала сосредоточимся на одном списке — например, списке женщин в по- рядке предпочтений некоторого мужчины. Возможно, для хранения списка из n элементов проще всего воспользоваться массивом A длины n, в котором A[i] со- держит i-й элемент списка. Такой массив легко реализуется практически на любом стандартном языке программирования и обладает следующими свойствами.
- Ответ на запрос вида «Какое значение хранится в i-м элементе списка?» можно получить за время O(1), напрямую обратившись к значению A[i].
- Если мы хотим определить, входит ли в список некоторый элемент e (то есть равен ли он A[i] для некоторого i), необходимо последовательно проверить все элементы за время O(n) — при условии, что нам ничего не известно о порядке следования элементов в A.
- Если элементы массива отсортированы в четко определенном порядке (напри- мер, по числовым значениям или по алфавиту), тогда принадлежность элемен- та e списку проверяется за время O(log n) методом бинарного поиска; в алгоритме устойчивых паросочетаний бинарный поиск не используется, но мы вернемся к нему в следующем разделе.
Массив не так хорошо подходит для динамического ведения списка элементов, изменяющихся со временем (например, списка свободных мужчин в алгоритме устойчивых паросочетаний); поскольку мужчины переходят из свободного состо- яния в состояние помолвки (а возможно, и обратно), список свободных мужчин должен увеличиваться и уменьшаться в процессе выполнения алгоритма. Обычно частое добавление и удаление элементов из списка, реализованного на базе масси- ва, реализуется громоздко и неудобно.
Таким образом, в каждом элемента v должен храниться указатель на следу- ющий элемент; если это последний элемент, указателю присваивается null. Также существует указатель First, ссылающийся на первый элемент. Начиная с First и последовательно переходя по указателям на следующий элемент, пока не будет обнаружен указатель null, можно перебрать все содержимое списка за время, пропорциональное его длине.
Обобщенный способ реализации связанного списка, в котором набор возмож- ных элементов не может быть зафиксирован изначально, основан на создании записи e для каждого элемента, включаемого в список. Такая запись содержит поле e.val, в котором хранится значение элемента, и поле e.Next с указателем на следующий элемент списка.
Также можно создать двусвязный список, поддерживающий переходы в обоих направлениях; для этого добавляется поле e.Prev со ссылкой на предыдущий элемент списка. (Для первого элемента в списке e.Prev = null.) Также добавляется указатель Last — аналог First, указывающий на последний элемент в списке.
С двусвязным списком могут выполняться следующие операции.
- Удаление. Чтобы удалить элемент e из двусвязного списка, достаточно «обойти» его так, чтобы предыдущий элемент (на который указывает Prev) и следующий элемент (на который указывает e.Next) указывали друг на друга. Операция уда- ления изображена на рис. 2.1.
- Вставка. Чтобы вставить элемент e между элементами d и f в списке, мы при- сваиваем Next и f.Prev указатель на e, а полям Next и Prev в e — указатели на d и f соответственно. Эта операция, по сути, является обратной по отношению к удалению; чтобы понять происходящее, достаточно просмотреть рис. 2.1 снизу вверх.
При вставке или удалении e в начале списка обновляется указатель First — вместо обновления записи элемента, предшествующего e.
Списки хорошо подходят для ведения динамически изменяемых множеств, но у них имеются свои недостатки. В отличие от массивов, i-й элемент списка невозможно найти за время O(1): переход к i-му элементу потребует перехода по указателям Next, начиная от начала списка, что займет в общей сложности время O(i).
С учетом относительных достоинств и недостатков массивов и списков может оказаться так, что мы получим входные данные задачи в одном из двух форматов и захотим преобразовать их к другому формату.
Как упоминалось ранее, такая пред- варительная обработка часто приносит пользу; и в таком случае преобразование между массивами и списками легко выполняется за время O(n). Это позволит нам свободно выбрать структуру данных, которая лучше подходит для конкретного алгоритма, не привязываясь к той структуре, в которой были получены входные данные.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу