Реализация основных операций над односвязным списком
Включение элемента со значением v после элемента с адресом Addr:
Реализация операции приведена ниже. Предполагается, что адрес Addrотличен отnilи элемент с адресомAddrприсутствует в списке (эти ситуации должны быть проверены в вызывающей программе). Если список пуст, то новый элемент включается в начало списка.
proceduretList.InsertAfter(Addr: pItem; v: tValue);
var
NewItem: pItem;// вспомогательный указатель на новый элемент
begin
NewItem:= New(pItem); // выделение памяти под новый элемент списка
NewItem^.Value:=v;
ifEmpty
thenbegin // если список пуст, включаем в его начало
NewItem^.Next:= nil;
fHead:= NewItem;
end
elsebegin // список не пуст - включаем после элемента с адресом Addr
NewItem^.Next:= Addr^.Next;
Addr^.Next:= NewItem;
end;
Inc(fSize);// увеличение числа элементов списка на 1
end;// procedure tList.InsertAfter
Включение элемента со значением v в список перед элементом с адресом Addrможет быть выполнено следующим образом. Сначала новый элемент включается после элемента с адресомAddr, а затем происходит обмен содержательными полями между включенным элементом и элементом с адресомAddr. Предполагается, что адресAddrотличен отnil, и элемент с адресомAddrприсутствует в списке. Если список пуст, то новый элемент включается в начало списка.
proceduretList.InsertBefore(Addr: pItem; v: tValue);
var
NewItem: pItem;// вспомогательный указатель на новый элемент
begin
NewItem:= New(pItem); // выделение памяти под новый элемент списка
ifEmpty
thenbegin // если список пуст, включаем в его начало
NewItem^.Value:= v;
NewItem^.Next:= nil;
fHead:= NewItem;
end
else begin // иначе обмен содержимым элементов NewItem^ и Addr^
NewItem^:= Addr^;
Addr^.Value:= v;
Addr^.Next:=NewItem;
end;
Inc(fSize);// увеличение числа элементов списка на 1
end;// procedure tList.InsertBefore
Исключение элемента, следующего за элементом с адресом Addr:
functiontList.DeleteAfter(Addr: pItem): tValue;
var
DisItem: pItem;// вспомогательный указатель на исключаемый элемент
begin
if Addr^.Next=nil
then begin
WriteLn('Исключаемый элемент отсутствует');
Halt;
end
else begin
DisItem:= Addr^.Next;
DeleteAfter:= DisItem^.Value;
Addr^.Next:= DisItem^.Next;
Dispose(DisItem);
end;
Dec(fSize);// уменьшение числа элементов списка на 1
end;// function tList.DeleteAfter
Исключение из списка элемента с указателем Addr. В этом случае необходимо определить адрес элемента, предшествующего исключаемому, что выполняется проходом по списку от его начала с помощью передвигаемого по элементам списка вспомогательного указателяItemтипаpItem.
functiontList.Delete(Addr:pItem): tValue;
var
Item: pItem;// вспомогательный указатель на элемент списка
begin
ifAddr=fHead
then begin // исключается первый элемент
Delete:= Addr^.Value;
fHead:= Addr^.Next;
Dispose(Addr);
end
elsebegin// поиск элемента, предшествующего исключаемому
Item:= fHead;
while (Item^.Next<>Addr) and (Item<>nil) do Item:= Item^.Next;
ifItem=nil
thenWriteLn('Исключаемый элемент отсутствует')
else begin
Delete:= Addr^.Value;
Item^.Next:= Addr^.Next;
Dispose(Addr);
end;
end;
Dec(fSize);// уменьшение числа элементов списка на 1
end;// function tList.Delete
Операции tList.DeleteAfterиtList.Deleteисключения элементов из списка неприменимы к пустому списку, поэтому перед их выполнением необходимо анализировать значение признака «список пуст». При выполнении этих операций предполагается, что заданный адресAddrотличен отnil, и элемент с заданным адресом присутствует в списке.
Поиск элемента с заданным значением v в списке:
functiontList.Search(v: tValue): pItem;
// Возвращение адреса элемента со значением v
// или nil, если элемент отсутствует
var
Item: pItem;
begin
ifEmpty
then Search:=nil
else begin
Item:= fHead;
while (Item^.Next<>nil) and (Item^.Value<>v) do Item:= Item^.Next;
if Item^.Value=v then Search:= Item else Search:=nil;
end;
end;// function tList.Search
Включение элемента со значением v в начало списка:
proceduretList.InsertHead(v: tValue);
var
NewItem: pItem; // указатель на новый элемент
begin
NewItem:= New(pItem); // выделение памяти под новый элемент
NewItem^.Value:= v; // запись v в поле значения нового элемента
NewItem^.Next:=fHead;// fHead -> в поле ссылки нового элемента
fHead:= NewItem; // перемещение fHead на новый элемент
Inc(fSize);// увеличение числа элементов списка на 1
end;// procedure tList.InsertHead
Включение элемента со значением v в конец списка:
proceduretList.InsertRear(v: tValue);
var
Item:pItem; // указатель на последний элемент
begin
ifEmpty
thenInsertHead(v)// если список пуст, то включение в начало,
elsebegin // иначе поиск адреса последнего элемента
Item:= fHead;
while Item^.Next<>nil do Item:= Item^.Next;
InsertAfter(Item,v);// и вставка после последнего элемента
end;
end;// procedure tList.InsertRear
Исключение элемента из начала списка:
functiontList.DeleteHead: tValue;
begin
DeleteHead:= Delete(fHead)
end;// function tList.DeleteHead
Исключение элемента из конца списка:
functiontList.DeleteRear: tValue;
var
Item:pItem;
begin
Item:= fHead;
while Item^.Next<>nil do Item:= Item^.Next;
DeleteRear:= Delete(Item)
end; // function tList.DeleteRear