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

Изменчивость динамических структур данных предполагает не только изменения размера структуры, но и изменения связей между элементами. Для связных структур изменение связей не требует пересылки данных в памяти, а только изменения указателей в элементах связной структуры. В качестве примера приведена перестановка двух соседних элементов списка. В алгоритме перестановки в односвязном списке (рис.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;

В процедуре перестановки для двухсвязного списка (рис.5.10.) нетрудно учесть и перестановку в начале/конце списка.