Удаление элемента из списка.
Удаление элемента из односвязного списка показано на рисунке
Очевидно, что процедуру удаления легко выполнить, если известен адрес элемента, предшествующего удаляемому. Процедура обеспечивает удаления как из середины, так и из начала списка.
{==== Программный пример ====}
{ Удаление элемента из любого места 1-связного списка }
Procedure DeleteSll(
var head : sllptr; { указатель на начало списка, может
измениться в процедуре }
del : sllptr { указатель на эл-т, к-рый удаляется } );
var prev : sllptr; { адрес предыдущего эл-та }
begin
if head=nil then begin { попытка удаления из пустого списка
асценивается как ошибка (в последующих примерах этот случай
учитываться на будет) }
Writeln('Ошибка!'); Halt;
end;
if del=head then { если удаляемый эл-т - 1-й в списке, то
следующий за ним становится первым }
head:=del^.next
else begin { удаление из середины списка }
{ приходится искать эл-т, предшествующий удаляемому; поиск производится перебором списка с самого его начала, пока не будет найдет эл-т, поле next к-рого совпадает с адресом удаляемого элемента }
prev:=head^.next;
while (prev^.next<>del) and (prev^.next<>nil) do
prev:=prev^.next;
if prev^.next=nil then begin
{ это случай, когда перебран весь список, но эл-т не найден, он отсутствует в списке; расценивается как ошибка (в последующих примерах этот случай учитываться на будет) }
Writeln('Ошибка!'); Halt;
end;
prev^.next:=del^.next; { предыдущий эл-т теперь указывает
на следующий за удаляемым }
end;
{ элемент исключен из списка, теперь можно освободить
занимаемую им память }
Dispose(del);
end;
Удаление элемента из двухсвязного списка требует коррекции большего числа указателей, как показано на рисунке.
Процедуру удаления элемента из двухсвязного списка окажется даже проще, чем для односвязного, так как в ней не нужен поиск предыдущего элемента, он выбирается по указателю назад.
Перестановка элементов списка.
Изменчивость динамических структур данных предполагает не только изменения размера структуры, но и изменения связей между элементами. Для связных структур изменение связей не требует пересылки данных в памяти, а только изменения указателей в элементах связной структуры. В качестве примера приведена перестановка двух соседних элементов списка. В алгоритме перестановки в односвязном списке исходили из того, что известен адрес элемента, предшествующего паре, в которой производится перестановка. В приведенном алгоритме также не учитывается случай перестановки первого и второго элементов.
{==== Программный пример ====}
{ Перестановка двух соседних элементов в 1-связном списке }
Procedure ExchangeSll(
prev : sllptr { указатель на эл-т, предшествующий
переставляемой паре } );
var p1, p2 : sllptr; { указатели на эл-ты пары }
begin
p1:=prev^.next; { указатель на 1-й эл-т пары }
p2:=p1^.next; { указатель на 2-й эл-т пары }
p1^.next:=p2^.next; { 1-й элемент пары теперь указывает на
следующий за парой }
p2^.next:=p1; { 1-й эл-т пары теперь следует за 2-ым }
prev^.next:=p2; { 2-й эл-т пары теперь становится 1-ым }
end;
В процедуре перестановки для двухсвязного списка (рис.5.10.) нетрудно учесть и перестановку в начале/конце списка.