Двунаправленные линейные списки
Недостатком рассмотренных выше списковых структур является их однонаправленность от первого элемента к последнему. Если при обработке списков часто бывает необходимо переходить от текущего элемента к его предшественнику, то такая односторонняя организация становится неудобной. Выходом является построение двунаправленныхсписков, в которых каждый элемент “знает” обоих своих соседей, как левого, так и правого.
Для этого каждый элемент должен иметь не одно, а два связующих поля: указатель на элемент слева и указатель на элемент справа.
|
|
|
|
. . .
|
|
| |||||||||||||
. . .
Отметим достоинства и недостатки двунаправленных списков. Достоинство – простота перехода от текущего элемента к любому его соседу. Недостатки – увеличиваются затраты памяти и число операций на поддержку дополнительного указателя.
Двунаправленный список можно реализовать как на основе массива (причем – обеими способами), так и динамически.
В последнем случае описание структуры данных выглядит следующим образом:
type pDin2Item = ^ TDin2Item; {ссылочный тип}
TDin2Item = record{базовый тип}
inf : <тип информационной части>;
left, right : pDin2Item; {адреса соседних элементов}
end;
Если pHead есть указатель на заголовок, то пустой список создается так:
· выделяется память под заголовок, адресуемая указателем pHead
· оба ссылочных поля заголовка устанавливаются в адрес самого заголовка: pHead^.left := pHead; pHead^.right := pHead;
(при этом пустая ссылка nil нигде НЕ используется!)
Набор операций расширяется просмотром и поиском не только в прямом, но и в обратном направлениях. Немного изменяется условие достижения конца списка – вместо условия появления пустой ссылки надо использовать условие получения на текущем шаге адреса заголовка. Например, проход в обратном направлении реализуется так:
· устанавливаем начальное значение указателя текущего элемента на последний элемент списка: pCurrent := pHead^.left;
· организуем цикл прохода до достижения заголовка
while pCurrent <> pHead do pCurrent := pCurrent^.left;
|
Если удаляемый элемент адресуется указателем pCurrent, то pCurrent^.left определяет адрес левого соседа, а pCurrent^.right – адрес правого соседа. Тогда необходимые изменения реализуются так:
pCurrent^.left^.right := pCurrent^.right;
pCurrent^.right^.left := pCurrent^.left;
Аналогично выполняется добавление нового элемента, например – после заданного указателем pCurrent. Пусть как обычно новый элемент определяется указателем pTemp. Тогда для вставки его в список надо настроить оба его ссылочных поля, изменить правое ссылочное поле у текущего элемента и левое ссылочное поле у его правого соседа.
Необходимые присваивания (порядок следования важен!):
pTemp^.right := pCurrent^.right;
pTemp^.left := pCurrent;
pCurrent^.right^.left := pTemp;
pCurrent^.right := pTemp;
Аналогично реализуется добавление нового элемента перед заданным элементом, только вместо правого соседа обрабатывается левый сосед текущего элемента.
Дата добавления: 2020-07-18; просмотров: 669;