Двунаправленные линейные списки


Недостатком рассмотренных выше списковых структур является их однонаправленность от первого элемента к последнему. Если при обработке списков часто бывает необходимо переходить от текущего элемента к его предшественнику, то такая односторонняя организация становится неудобной. Выходом является построение двунаправленныхсписков, в которых каждый элемент “знает” обоих своих соседей, как левого, так и правого.

Для этого каждый элемент должен иметь не одно, а два связующих поля: указатель на элемент слева и указатель на элемент справа.

 

               
 
Элем. 1
правый
левый

 

 
Элем. 2
правый
левый

 

 
Элем. 3
правый
левый

 

 
Элем. N
правый
левый

 


 

. . .

 

 

pHead
Аналогично обычным спискам, удобно ввести фиктивный заголовочный элемент, а поскольку двунаправленные списки являются симметричными, удобно сделать их замкнутыми, кольцевыми: правая ссылка последнего элемента указывает на заголовок, а левая ссылка заголовка – на последний элемент. Адрес заголовка определяется указателем pHead.

 

               
 
     
Элем. 2
правый
левый

 

 
Элем. N
правый
левый

 

 

 


. . .

 


Отметим достоинства и недостатки двунаправленных списков. Достоинство – простота перехода от текущего элемента к любому его соседу. Недостатки – увеличиваются затраты памяти и число операций на поддержку дополнительного указателя.

Двунаправленный список можно реализовать как на основе массива (причем – обеими способами), так и динамически.

В последнем случае описание структуры данных выглядит следующим образом:

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, то 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; просмотров: 681;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.011 сек.