Модели и структуры данных




Реализация операций над связными линейными списками - часть 4


{ приходится искать эл-т, предшествующий удаляемому; поиск производится перебором списка с самого его начала, пока не будет найдет эл-т, поле 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-связного списка

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

Перестановка элементов списка.

Изменчивость динамических структур данных предполагает не только изменения размера структуры, но и изменения связей между элементами. Для связных структур изменение связей не требует пересылки данных в памяти, а только изменения указателей в элементах связной структуры. В качестве примера приведена перестановка двух соседних элементов списка. В алгоритме перестановки в односвязном списке (рис.5.9, пример 5.5) исходили из того, что известен адрес элемента, предшествующего паре, в которой производится перестановка. В приведенном алгоритме также не учитывается случай перестановки первого и второго элементов.

Рис.5.9. Перестановка соседних элементов 1-связного списка

{==== Программный пример 5.5 ====} { Перестановка двух соседних элементов в 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;




Содержание  Назад  Вперед