Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Алгоритмы и структуры данных

РЕАЛИЗАЦИЯ ОСНОВНЫХ ОПЕРАЦИЙ НАД ОДНОСВЯЗНЫМ ЦИКЛИЧЕСКИМ СПИСКОМ

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

procedure tCircleList.lnsertHead(v:tValue);

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

var

Newltem: pltem;

begin

// выделение памяти под новый элемент Newltem:= New(pltem);

NewltemA.Value:= v; if Empty

then begin

// включение в пустой список NewltemA.Next:= Newltem; fHead:= Newltem;

end

else begin

// включение в непустой список NewltemA.Next:= fHeadA.Next; fHeadA.Next:=Newltem

end;

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

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

procedure tCircleList.lnsertRear(v: tValue);

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

begin

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

// Перенос указателя последнего элемента на следующий элемент: fHead:= fHeadA.Next; end; //procedure tCircleList.lnsertRear

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

function tCircleList.DeleteHead: tValue;

// Исключение элемента из начала списка // и возвращение его значения

var

Disltem: pltem;

begin

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

DeleteHead:= DisltemA.Value;// чтение первого элемента списка if fHead=Disltem // если в списке был один элемент,

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

else fHeadA.Next:= DisltemA.Next; //иначе 1-м становится 2-й эл-т Dispose(Disltem); //удаление из памяти исключаемого элемента Dec(fSize); //уменьшение числа элементов списка на 1

end; //function tCircleList.DeleteHead

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

Сначала передвинуть указатель последнего элемента списка fHead на предшествующий ему элемент (предварительно определив указатель на этот элемент).

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

function tCircleList.DeleteRear: tValue;

// Исключение элемента из конца списка и возвращение его значения varltem: pltem;

begin

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

while ltemA.Next<>fHead do ltem:=ltemA.Next;

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

DeleteRear:= DeleteHead; end; //function tCircleList.DeleteRear

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

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

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

TCircleList CList2

fHead fHead

Сцепление циклического списка TCircleList с циклическим

Рис. 2.6. Сцепление циклического списка TCircleList с циклическим

списком CList2

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

procedure tCircleList.Concat(var CList2: tCircleList);

// Сцепление со списком CList2 - подключение справа

var

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

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

begin

Head2:=CList2.Head; //получение указателя на начало 2-го списка ltem:= fHeadMNlext;// сохранение указателя на начало общего списка fHeadA.Next:= Head2A.Next; //включение списка с указ. Head2 справа fHead:= Head2; //перемещение fHead на последний эл-т

fHeadA.Next:= Item; //восстановление связи с 1-м эл-том

fSize:=fSize + CList2.Size; //вычисление размера общего списка CList2.Head := nil; CList2.Size := 0; //CList2 становится пустым end; // tCircleList. Concat

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

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ   След >
 

Популярные страницы