Массивы и списки

Для начала сосредоточимся на одном списке — например, списке женщин в по- рядке предпочтений некоторого мужчины. Возможно, для хранения списка из n элементов проще всего воспользоваться массивом A длины n, в котором A[i] со- держит i-й элемент списка.
Такой массив легко реализуется практически на любом стандартном языке программирования и обладает следующими свойствами.

♦ Ответ на запрос вида «Какое значение хранится в i-м элементе списка?» можно получить за время 0(1), напрямую обратившись к значению A[i].

♦ Если мы хотим определить, входит ли в список некоторый элемент e (то есть равен ли он A[i] для некоторого i), необходимо последовательно проверить все элементы за время 0(n) — при условии, что нам ничего не известно о порядке следования элементов в A.

♦ Если элементы массива отсортированы в четко определенном порядке (напри- мер, по числовым значениям или по алфавиту), тогда принадлежность элемен- та e списку проверяется за время О(log n) методом бинарного поиска; в алгоритме устойчивых паросочетаний бинарный поиск не используется, но мы вернемся к нему в следующем разделе.

Массив не так хорошо подходит для динамического ведения списка элементов, изменяющихся со временем (например, списка свободных мужчин в алгоритме устойчивых паросочетаний); поскольку мужчины переходят из свободного состо- яния в состояние помолвки (а возможно, и обратно), список свободных мужчин должен увеличиваться и уменьшаться в процессе выполнения алгоритма. Обычно частое добавление и удаление элементов из списка, реализованного на базе масси- ва, реализуется громоздко и неудобно.

Для ведения таких динамических наборов элементов можно (а часто и жела- тельно) использовать связанные списки. В связанном списке для формирования последовательности элементов каждый элемент указывает на следующий элемент списка. Таким образом, в каждом элемента v должен храниться указатель на следу- ющий элемент; если это последний элемент, указателю присваивается null. Также существует указатель First, ссылающийся на первый элемент. Начиная с First и последовательно переходя по указателям на следующий элемент, пока не будет обнаружен указатель null, можно перебрать все содержимое списка за время, про- порциональное его длине.

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

Такая запись содержит поле e. val, в котором хранится значение элемента, и поле e. Next с указателем на сле-

дующий элемент списка. Также можно создать двусвязный список, поддерживающий переходы в обоих направлениях; для этого добавляется поле e. Prev со ссылкой на предыдущий элемент списка. (Для первого элемента в списке e. Prev = null.) Также добавляется указатель Last — аналог First, указывающий на последний элемент в списке. Схематическое изображение части такого списка представлено в верхней части рис. 2.1.

Рис. 2.1. Схематическое представление двусвязного списка с удалением элемента e


С двусвязным списком могут выполняться следующие операции.

♦ Удаление. Чтобы удалить элемент e из двусвязного списка, достаточно «обойти» его так, чтобы предыдущий элемент (на который указывает e.Prev) и следующий элемент (на который указывает e. Next) указывали друг на друга. Операция уда- ления изображена на рис. 2.1.

♦ Вставка. Чтобы вставить элемент e между элементами d и f в списке, мы при- сваиваем d. Next и f Prev указатель на e, а полям Next и Prev в e — указатели на d и f соответственно. Эта операция, по сути, является обратной по отношению к удалению; чтобы понять происходящее, достаточно просмотреть рис. 2.1 снизу вверх.

При вставке или удалении e в начале списка обновляется указатель First — вместо обновления записи элемента, предшествующего e.

Списки хорошо подходят для ведения динамически изменяемых множеств, но у них имеются свои недостатки. В отличие от массивов, г-й элемент списка невозможно найти за время 0(1): переход к г-му элементу потребует перехода по указателям Next, начиная от начала списка, что займет в общей сложности время 0(г).

С учетом относительных достоинств и недостатков массивов и списков может оказаться так, что мы получим входные данные задачи в одном из двух форматов и захотим преобразовать их к другому формату. Как упоминалось ранее, такая пред- варительная обработка часто приносит пользу; и в таком случае преобразование между массивами и списками легко выполняется за время 0(n). Это позволит нам свободно выбрать структуру данных, которая лучше подходит для конкретного алгоритма, не привязываясь к той структуре, в которой были получены входные данные.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Массивы и списки:

  1. Номер один в списке неправильных действий
  2. 18.5. Права и обязанности держателя (обладателя) по работе с массивами персональных данных
  3. 18.6. Государственное регулирование работы с персональными данными
  4. КОНТАМИНАЦИЯ
  5. Частотный анализ и кодировка.
  6. 1.4. Цель настоящего учебника
  7. 18.7. Уполномоченный по правам субъектов персональных данных
  8. ОПРОСНИК КРЕАТИВНОСТИ
  9. МЕТОДИКА АССОЦИАЦИЙ ПАРНЫХ
  10. 18.3. Правовые основы работы с персональными данными
  11. 18.2. Субъекты и объекты информационных правоотношений
  12. 18.4. Права субъекта персональных данных
  13. Способы практической реализации собственно случайной выборки.
  14. 2.4.2. Систематический отбор
  15. 1.1 Глубинная проблема: амбивалентность
  16. Статья 245. Уничтожение или повреждение объектов растительного мира
  17. Необходимые шаги