Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Двусвязный список




Читайте также:
  1. I. Список экскурсий по Санкт-Петербургу
  2. III. Список экскурсий по пригородам
  3. Quot;Стаття 581. Список присяжних
  4. V. СПИСОК РЕКОМЕНДОВАНИХ ДЖЕРЕЛ
  5. VІІ. Список літератури.
  6. А теперь запишите все самые важные для вас дела, разместив их в порядке приоритетности. Даже простое занесение их в список вызовет у вас чувство уже некоторого контроля над ними.
  7. Атропіну сульфат – список А, перевіряємо дози
  8. БИБЛИОГРАФИЧЕСКИЙ СПИСОК
  9. БИБЛИОГРАФИЧЕСКИЙ СПИСОК
  10. БИБЛИОГРАФИЧЕСКИЙ СПИСОК

Линейные односвязные списки, содержащие только один указатель — на следующий элемент, позволяют двигаться лишь в одном направлении — от начала списка к его концу. Можно построить список, каждый элемент которого содержит два указателя: на следующий элемент и на предыдущий. В этом случае описание типов и переменных будет таким:

type TInfo = integer;

PNode = ^TNode;

TNode = record

Info: TInfo;

Next, // указатель на следующий элемент

Pred: PNode; // указатель на предыдущий элемент

end;

Движение по такому списку может происходить в двух направлениях: от начала к концу — с использованием указателя Next, и от конца к началу, используя указатель Pred. Пример двусвязного списка показан на рис. 9.7.

 

Рис. 9.7. Двусвязный список

Очевидно, что значение поля Next последнего элемента и поля Pred первого элемента линейного двусвязного списка равны Nil.

Включение нового элемента в двусвязный список и удаление элемента происходит и проще, и сложнее, чем в односвязный. Проще — потому что элемент двусвязного списка содержит указатели и на следующий, и на предыдущий элементы, и нет нужды, как при вставке в односвязный список, либо обменивать информационные поля местами, либо тащить, при проходе по списку, дополнительный указатель на предыдущий элемент. Сложнее — потому что требуется переприсвоить и значения указателей Next, и значения указателей Pred. На рис. 9.8 показана вставка элемента в двусвязный список. Прежние значения указателей показаны светло-серым цветом.

Рис. 9.8. Вставка элемента в двусвязный список

Для того чтобы вставить в список новый элемент после элемента p (см. рис. 9.8), необходимы следующие действия:

new(q); // создание нового элемента

with q^ do begin

Info:=34;

Next:=p^.Next;

Pred:=p;

end;

p^.Next^.Pred:=q; // меняется значение поля Pred элемента со значением 44

p^.Next:=q;

Удаление элемента p из двусвязного списка показано на рис. 9.9.

Рис. 9.9. Удаление элемента из двусвязного списка

Удаление производится следующими действиями:

p^.Pred^.Next:=p^.Next; // связать предыдущий элемент со следующим за p

p^.Next^.Pred:=p^.Pred; // связать следующий за p элемент с предыдущим

dispose(p) // удаление элемента




Дата добавления: 2015-09-15; просмотров: 8; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты