Else begin. Addr:= Addr^.Right; DeleteRight:= Delete(Addr);

Addr: = Addr^.Right; DeleteRight: = Delete(Addr);

end;

end; // function tDCList.DeleteRight

Так же легко исключить элемент, стоящий слева от заданного. В этом случае необходимо проанализировать ситуацию Addr=fHead, которая означает, что исключаемый элемент отсутствует в списке.

Операции исключения элементов из двусвязного списка DeleteRight и Delete неприменимы к пустому списку; при их реализации предполагается, что Addr< > nil, и элемент с заданным адресом присутствует в списке.

Поиск элемента с заданным значением v в двусвязном списке выполняется так же как и поиск элемента в односвязном списке с той разницей, что указатель Next в функции Search заменяется на Right.

11. Циклический двусвязный список

Так же, как и односвязный, двусвязный список может быть циклическим. Для двусвязного циклического списка отпадает необходимость хранения внешнего указателя на последний элемент списка, так как фактически он является элементом, расположенным слева от первого:

Над циклическим двусвязным списком могут быть выполнены все операции, определенные для циклического односвязного списка.

Класс tDCCircleList может быть описан следующим образом:

Type

tDCCircleList= class // класс - циклический двусвязный список

Protected

fHead: pItem; // поле - указатель на начало списка

fSize: Word; // поле - число элементов списка

Public

// Свойство - число элементов списка (доступ по чтению и записи)

property Size: Word read fSize write fSize;

// Свойство - указатель на начало списка (доступ по чтению и записи)

property Head: Word read fHead write fHead;

// Включение элемента со значением v справа от элемента с адресом Addr

procedure InsertRight(Addr: pItem; v: tValue);

// Включение элемента со значением v слева от элемента с адресом Addr

procedure InsertLeft(Addr: pItem; v: tValue);

// Исключение элемента справа от элемента с адресом Addr

function DeleteRight(Addr: pItem): tValue;

// Исключение из списка элемента с адресом Addr

function Delete(Addr: pItem): tValue;

// Включение элемента со значением v в начало списка

procedure InsertHead(v: tValue);

// Включение элемента со значением v в конец списка

procedure InsertRear(v: tValue);

function DeleteHead: tValue; // исключение из начала

function DeleteRear: tValue; // исключение из конца

// Возвращение адреса элемента со значением v

function Search(v: tValue): pItem;

function Empty: Boolean; // возвращение true, если список пуст

procedure Clear; // очистка списка

// Присоединение списка DCList2 справа

procedure Concat(var DCList2: tDCCircleList);

constructor Create; // конструктор - создание пустого списка

destructor Destroy; override; // деструктор - удаление списка

end; // tDCCircleList

Класс tDCCircleList не является в данном описании наследником класса tDCList по следующим причинам:

– поле Rear класса tDCList не используется;

– вводится новая процедура Concat;

– все методы класса tDCCircleList реализуются иначе, чем одноименные методы класса tDCList.

12. Реализация основных операций над двусвязным циклическим списком

В этом разделе рассмотрим только новые для двусвязного циклического списка операции, реализацию методов, одноименных с методами класса tDCList, предлагается выполнить самостоятельно.

Var

NewItem: pItem; // указатель на новый элемент

Begin

NewItem: = New(pItem);

NewItem^.Value: = v;

if Empty

then begin // включение в пустой список

NewItem^.Left: = NewItem;

NewItem^.Right: = NewItem;

fHead: = NewItem; end

else begin // включение в непустой список

NewItem^.Left: = fHead^.Left;

NewItem^.Right: = fHead;

fHead^.Left^.Right: =NewItem;

fHead^.Left: =NewItem;

end;

Inc(fSize); // увеличение числа элементов списка на 1

end; // procedure tDCCircleList.InsertRear

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

procedure tDCCircleList.InsertHead(v: tValue);

Begin

InsertRear(v); // включение элемента в конец

fHead: = fHead^.Left;

end; // procedure tDCCircleList.InsertHead

Метод класса tDCCircleList, реализующий исключение элемента из конца двусвязного циклического списка, имеет вид:

function tDCCircleList.DeleteRear: tValue;

Var

DisItem: pItem;

Begin

DisItem: = fHead^.Left; // исключаемый элемент - последний

DeleteLast: = DisItem^.Value; // чтение последнего элемента списка

if fHead=DisItem

then fHead: = nil // исключается единственный элемент