Главная » Java, Структуры данных и алгоритмы » Операции с узлами списки

0

Для доступа к месту расположения элемента в списке может применяться не только понятие разряда. Если имеется список S, реализованный на основе однонаправленного или двусвязного списка, более удобным и эффективным является использование для определения места доступа и обновления списка .узлов вместо разрядов. Рассмотрим абстрактное понятие узла, описывающего определенное «место» в списке, не вдаваясь в детали реализации списка.

Пусть S — линейный список, реализованный с помощью двусвязного списка. Необходимо определить методы для S, которые принимают в качестве параметров узлы списка и возвращают значения узлов. Данные методы значительно быстрее методов, основанных на использовании разрядов, так как для поиска разряда в связном списке необходим последовательный просмотр всех элементов от начала до конна, с подсчетом пройденных элементов.

Например, определим гипотетический метод removeAtNode(v), который удаляет элемент S, хранящийся в узле списка v. Использование узла в качестве параметра позволяет удалить элемент за время 0(1) путем перехода к данному узлу, удаления его и перенаправления соответствующим образом ссылки next и prev соседних узлов. Аналогично можно добавить новый элемент е за время 0(1) с помощью операции insertAfterNode (v,<?), определяющий узел v, после которого необходимо вставить узел нового элемента. В данном случае просто «вплетается» новый узел.

Добавив к методам АТД «список» упомянутые операции с узлами, определим количество информации, которое необходимо задать для непосредственной реализации списка. Безусловно, в лучшем случае можно применить однонаправленный или двусвязный список, не сообщая пользователю деталей. Аналогично пользователю не следует модифицировать внутреннюю структуру списка без особой надобности. Такая модификация, однако, может быть возможна, если предоставленная пользователю ссылка на узел списка разрешает доступ к внутренним данным этого узла (то есть доступ к полям next и prev).

Для абстрагирования и унификации разных способов хранения элементов в различных реализациях списка введем понятие позиции в списке, которое формализует традиционное понятие «места» элемента, связанного с другими элементами в списке.

Позиции

Таким образом, для изучения операций над списками введено абстрактное понятие «позиции», которое позволяет использовать реализации с помощью однонаправленного и двусвязного списка, не нарушая в то же время принципов объектно-ориентированного программирования В данной схеме список рассматривается как контейнер элементов, хранящихся в определенных позициях, и эти позиции линейно упорядочены. Позиция сама по себе является абстрактным типом данных, который поддерживает следующий простой метод:

element(): возвращает элемент, хранящийся в данной позиции.

Input: нет; Output: объект.

Позиции всегда определяются относительно своих соседей. В списке позиция р всегда будет следовать «за» некоторой позицией q и «перед» некоторой позицией s (при условии, что р не является первой или последней позицией). Позиция р, связанная с некоторым элементом е в списке S, остается неизменной даже при изменении разряда е, если е явно не удаляется (и таким образом не уничтожается позиция р). Более того, позиция р не изменится, даже если заменить элемент е, хранящийся в р, на другой элемент. Такие особенности позволяют определить большое число методов, использующих позиции в качестве параметров и возвращающих объекты, хранящиеся в позициях.

Абстрактный тип данных «список»

Используя концепцию позиции для инкапсуляции «узла» списка, опишем еще один тип последовательностей, называемый АТД «список». Этот АТД поддерживает следующие методы, выполняемые над списком S:

first(): возвращает позицию первого элемента списка S\ если список пуст, выдается сообщение об ошибке. Input: нет; Output: позиция.

last(): возвращает позицию последнего элемента списка S\ если список пуст, выдается сообщение об ошибке. Input: нет; Output: позиция. isFirst (/?): возвращает логическое значение, показывающее, является ли данная позиция первой в списке. Input: позиция р; Output: логическое значение. isLast(/?): возвращает логическое значение, показывающее, является ли данная позиция последней в списке. Input: позиция р\ Output: логическое значение. before(/?): возвращает позицию элемента 5, который предшествует элементу позиции р; если является первой позицией, выдается сообщение об ошибке. Input: позиция; Output: позиция, after(/?): возвращает позицию элемента S, который следует за элементом позиции р\ если р является последней позицией, выдается сообщение об ошибке. Input: позиция; Output: позиция.

Данные методы позволяют обращаться к смежным позициям списка, начиная с конца или с начала, а также постепенно перемещаться по всему списку. Позиции можно считать узлами списка, однако обратите внимание, что в этих методах нет особых ссылок к объектам узлов и ссылок next и prev этих методов. Кроме указанных методов, а также общих методов size и isEmpty АТД «список» описывает следующие методы обновления списка:

replaceElement(/?,e): замещает элемент в позиции р на е и возвращает элемент, который до этого был в позиции р. Input: позиция р и объект е\ Output: объект. swapElements(/?,#): меняет местами элементы в позициях р и q таким образом, что элемент в позиции р перемещается в позицию q, а элемент, бывший в позиции q, перемещается в позицию р. Input: две позиции; Output: нет. insertFirst(e): вставляет новый элемент е в S в качестве первого элемента списка.

Input: объект е; Output: позиция вставленного элемента е.

insertLast(e): вставляет новый элемент е в S в качестве последнего элемента списка.

Input: объект е; Output: позиция вставленного элемента е.

insertBefore(/7, е): вставляет новый элемент ев S перед позицией р\ если р является первой позицией, выдается сообщение об ошибке.

Input: позиция р и объект е\ Output: позиция вставленного элемента е. insertAfter(/?, е)\ вставляет новый элемент ев S после позиции /?;

если р является последней позицией, выдается сообщение об ошибке.

Input: позиция р и объект е\ Output: позиция вставленного элемента е. remove(/?): удаляет из ? элемент в позиции р.

Input: позиция; Output: удаленный элемент.

АТД «список» позволяет рассматривать упорядоченные с точки зрения местоположения коллекции объектов, не учитывая, каким именно образом представлены эти места (см. рис. 5.5).

Обратите внимание на большое число операций, выполняемых над списком. В частности, операция isFirst(р) может быть выполнена путем проверки, равно ли р позиции, возвращаемой first(). Точно так же операцию isLast(р) можно выполнить внутри last(). Кроме того, можно выполнить операцию insertFirst(e), вызвав метод insertBefore(first(),e), а операцию

Рис. 5.5. Наглядная демонстрация списка. Текущий порядок позиций: р, <7, г и Например, q является позицией, которая следует после позиции р и перед позицией г,

Состояние ошибки возникает в случае, если отсутствует передаваемая в качестве аргумента позиция. Это может произойти в следующих случаях:

•    р = null,

•    р ранее удалена из списка,

•    р является позицией другого списка.

Для обработки указанных случаев используется исключение Invalid- PositionException.

Продемонстрируем операции АТД «список» на следующем примере.

insertLast(e) можно заменить операцией insertAfter(last(),e). Излишние методы можно рассматривать как сокращенные версии общих операций, облегчающих анализ кода.

Пример 5.2. Ниже приведем операции, выполняемые над изначально пустым списком S. Переменные р\, Р2 и так далее обозначают различные позиции, в скобках указан объект, который в настоящее время хранится в определенной позиции.

Операция

Output

S

insertFirst(8)

P№

(8)

insertAfter (ри 5)

/>2(5)

(8,5)

(insertBefore (р2, 3)

>3(3)

(8,3,5)

insertFirst(9)

/>4(9)

(9,8,3,5)

before,(рз)

Pl(8)

(9,8,3,5)

last() i

/>2(5)

(9,8,3,5)

remove(p4)

9

(8,3,5)

swapElements(pi, p2)

-

(5,3,8)

replaceElement(p3, 7)

3

(5,7,8)

insertAfter (first(),2)

. />5(2)

(5,2,7,8)

АТД «список» вместе с используемым в нем понятием позиции применим в различных контекстах. Например, в программе, моделирующей игру нескольких человек в карты, можно представить карты на руках каждого игрока в виде списка. Так как большинство предпочитает раскладывать карты по мастям, удаление и добавление карт на руках одного игрока может производиться с помощью методов АТД «список», причем позиции определяются естественной последовательностью масти. Другой пример — обычные текстовые редакторы реализуют с помощью АТД «список» позиционную вставку и удаление, поскольку все изменения связаны с курсором, обозначающим текущую позицию в списке символов редактируемого текста.

Существуют и другие способы реализации списка. Вероятно, одним из наиболее естественных и эффективных способов является реализация на основе двусвязного списка. Рассмотрим далее, каким образом проводится эта реализация с использованием принципов объектно-ориентированного программирования.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии