Protected. fHead: pItem; // поле - указатель на текущий элемент списка

fHead: pItem; // поле - указатель на текущий элемент списка

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

Public

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

property Size: Word read fSize write fSize;

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

property Head: Word read fHead write fHead;

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

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

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

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

// Исключение элемента, следующего за элементом с адресом Addr

function DeleteAfter(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;

procedure Concat(var CList2: tCircleList); // сцепление со списком CList2

// Поиск в списке элемента со значением v и возвращение его адреса

function Search(v: tValue): pItem;

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

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

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

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

end; // class tCircleList

Класс tCircleList не объявлен наследником класса tList поскольку реализация практически всех его методов отличается от реализации одноимённых методов для нециклического списка. Отличия, в основном, заключаются в следующем:

– для операций InsertAfter и InsertBefore по-другому осуществляются включение элемента в пустой список и включение в начало и конец циклического списка;

– применение операции DeleteAfter для циклического списка, состоящего из одного элемента, не должно приводить к исключению самого этого элемента;

– методы DeleteAfter и Delete должны восстанавливать указатель на последний элемент циклического списка, если он исключается при выполнении этих операций;

– в методах Search и Clear признаком завершения просмотра циклического списка является достижение вспомогательным указателем того элемента, с которого начался просмотр.

И только конструктор Create и деструктор Destroy реализуются так же как и одноимённые методы класса tList.

Очевидно, что операции включения и исключения справа и слева от текущего элемента (InsertHead, InsertRear, DeleteHead, DeleteRear) выполняют те же действия, что и одноимённые операции для нециклического списка. Отличие заключается в том, что новые операции изменяют значение указателя на последний элемент циклического списка, если список расширился влево или вправо либо сузился слева или справа.

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

Включение элемента в начало циклического списка:

procedure tCircleList.InsertHead(v: tValue);

Var

NewItem: pItem;

Begin

NewItem: = New(pItem); // выделение памяти под новый элемент списка

NewItem^.Value: = v;

if Empty

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

NewItem^.Next: = NewItem;

fHead: = NewItem; end

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

NewItem^.Next: = fHead^.Next;

fHead^.Next: =NewItem

end;

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

end; // procedure tCircleList.InsertHead

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

procedure tCircleList.InsertRear(v: tValue);

Begin

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

// Перенос указателя последнего элемента на следующий элемент:

fHead: = fHead^.Next;

end; // procedure tCircleList.InsertRear

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

function tCircleList.DeleteHead: tValue;

Var

DisItem: pItem;

Begin

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

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

if fHead=DisItem // если в списке был один элемент,

then fHead: = nil // то после исключения список пуст,

else fHead^.Next: = DisItem^.Next; // иначе первым становится второй эл-т.

Dispose(DisItem); // удаление из памяти исключаемого эле мента

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

end; // function tCircleList.DeleteHead

Исключение элемента из конца циклического списка. Поскольку список является циклическим, то можно применить следующий прием. Сначала передвинуть указатель последнего элемента списка fHead на предшествующий ему элемент (предварительно определив указатель на этот элемент). При этом бывший последний элемент (который и нужно исключить) становится первым. Этот элемент можно исключить из списка с использованием метода исключения из начала DeleteHead.

function tCircleList.DeleteRear: tValue;

Var

Item: pItem;

Begin

// Перемещение указателя Item на предпоследний элемент списка

Item: = fHead;

while Item^.Next< > fHead do Item: =Item^.Next;

fHead: = Item; // сдвиг fHead на предпоследний элемент

DeleteRear: = DeleteHead;

end; // function tCircleList.DeleteRear

Операции исключения элементов из списка tCircleList.DeleteHead и tCircleList.DeleteRear неприменимы к пустому списку, поэтому перед их выполнением необходимо анализировать признак «список пуст».

Сцепление циклического списка с другим циклическим списком CList2 (подключение списка CList2 справа).

При реализации этой операции в виде метода класса tCircleList в метод Concat циклического списка необходимо передавать не указатель на первый элемент второго списка, а указатель на сам подсоединяемый список (CList2). При этом в методе нужно избежать прямого обращения к полям fHead и fSize класса CList2. Для обеспечения доступа к этим полям по чтению и записи в классе tCircleList свойства Head и Size должны быть доступны не только по чтению, но и по записи.

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

procedure tCircleList.Concat(var CList2: tCircleList);

Var

Head2, // указатель на начало второго списка

Item: pItem; // указатель на элемент списка

Begin

Head2: =CList2.Head; // получение указателя на начало второго списка

Item: = fHead^.Next; // сохранение указателя на начало общего списка

fHead^.Next: = Head2^.Next; // включение списка с указ. Head2 справа

fHead: = Head2; // перемещение fHead на последний элемент

fHead^.Next: = Item; // восстановление связи с первым элемен том

fSize: =fSize + CList2.Size; // вычисление размера общего списка

CList2.Head: = nil; CList2.Size: = 0; // список CList2 становится пустым

end; //tCircleList.Concat

Если в приведенном выше методе исключить операцию перемещения указателя fHead на последний элемент включенного списка (fHead: = Head2), то список CList2 будет включен в список tCircleList слева.

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

Односвязный список имеет ряд недостатков. Такой список нельзя просматривать в обратном направлении. Располагая только значением указателя на данный элемент, удалить последний невозможно. При необходимости иметь такую возможность можно воспользоваться соответствующей структурой данных, называемой линейным двусвязным списком. Каждый элемент такого списка содержит два указателя. Один указывает на предшествующий элемент, а другой – на последующий. Понятия предшествующего и последующего элементов, начала и конца списка логически эквивалентны, т.к. доступ к каждому элементу может быть осуществлен с любого конца списка и список полностью симметричен. При описании двусвязных списков используют термины «левый» и «правый» для определения элементов, расположенных соответственно слева и справа от текущего элемента.