2014-02-24
564
Рис. 35. Структура элементарного двусвязного кольца
Рис. 34. Структура двусвязного циклического списка
Рис. 33. Структура двусвязного нециклического списка
Нециклическая структура двусвязного списка порождает те же проблемы при включении / исключении первого и последнего узлов, что и структура односвязного нециклического списка.
На практике более широко применяются двусвязные циклические списки. В двусвязном циклическом списке поле связи next его последнего элемента не содержит значения NIL,а указывает на первый узел списка и поле связи prev его первого элемента также не содержит значения NIL,а указывает на последний узел списка. В целях удобства обработки в структуру двусвязного циклического списка включают специальный дополнительный узел с особым содержанием информационного поля (на рис. 34 это поле заштриховано), называемый “головой“ списка или “сторожем“. Заметим, что “левым соседом” первого узла двусвязного циклического списка является его последний узел, а “правым соседом” его последнего узла является первый узел, т.к. информационное поле головного узла имеет особое содержание (а нередко и вовсе не используется). Так что функция “сторожа” в двусвязном циклическом списке оказывается чисто технологической и полностью аналогичной функции “сторожа” в односвязном циклическом списке. Структура двусвязного циклического списка приведена на рис. 34.
|
|
|
 |
| var head: pDlist; | { указатель на голову списка } |
| p: pDlist; | { вспомогательный указатель } |
Выполнение условия head = nil означает, что двусвязный циклический список не существует. Выполнение условия head ^. next = head ^. prev = head означает, что двусвязный циклический список существует, но является пустым, т.е. содержит только головной элемент. Пустой циклический список с головным элементом представляется структурой элементарного кольца (рис. 35).
Для любого узла двусвязного циклического списка, на который установлен указатель p (в том числе, и для головного), справедливо выражение: p^.next^.prev = p^.prev^.next = p;
