Удаление элемента из списка.
Удаление элемента из односвязного списка показано на рис.5.7.
Рис.5.7. Удаление элемента из 1-связного списка
Очевидно, что процедуру удаления легко выполнить, если известен адрес элемента, предшествующего удаляемому (prev на рис.5.7.а). Мы, однако, на рис. 5.7 и в примере 5.4 приводим процедуру для случая, когда удаляемый элемент задается своим адресом (del на рис.5.7). Процедура обеспечивает удаления как из середины, так и из начала списка.
{==== Программный пример 5.4 ====}
{ Удаление элемента из любого места 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;
Удаление элемента из двухсвязного списка требует коррекции большего числа указателей, как показано на рис.5.8.
Рис.5.8. Удаление элемента из 2-связного списка
Процедуру удаления элемента из двухсвязного списка окажется даже проще, чем для односвязного, так как в ней не нужен поиск предыдущего элемента, он выбирается по указателю назад.
Дата добавления: 2016-07-22; просмотров: 1715;