Перестановка элементов списка.
Изменчивость динамических структур данных предполагает не только изменения размера структуры, но и изменения связей между элементами. Для связных структур изменение связей не требует пересылки данных в памяти, а только изменения указателей в элементах связной структуры. В качестве примера приведена перестановка двух соседних элементов списка. В алгоритме перестановки в односвязном списке (рис.6, пример 2) исходили из того, что известен адрес элемента, предшествующего паре, в которой производится перестановка. В приведенном алгоритме также не учитывается случай перестановки первого и второго элементов.
Рис. 6: Перестановка соседних элементов 1-связного списка
{==== Программный пример 2 ====}
{ Перестановка двух соседних элементов в 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;
В процедуре перестановки для двухсвязного списка (рис.7.) нетрудно учесть и перестановку в начале/конце списка.
Копирование части списка
При копировании исходный список сохраняется в памяти, и создается новый список. Информационные поля элементов нового списка содержат те же данные, что и в элементах старого списка, но поля связок в новом списке совершенно другие, поскольку элементы нового списка расположены по другим адресам в памяти. Существенно, что операция копирования предполагает дублирование данных в памяти. Если после создания копии будут изменены данные в исходном списке, то изменение не будет отражено в копии и наоборот.
Рис. 7: Перестановка соседних элементов 2-связного списка
Копирование для односвязного списка показано в программном примере 3.
{==== Программный пример 3 ====}
{ Копирование части 1-связного списка. head - указатель на
начало копируемой части; num - число эл-тов. Ф-ция возвращает
указатель на список-копию }
Function CopySll ( head : sllptr; num : integer) : sllptr;
var cur, head2, cur2, prev2 : sllptr;
begin
if head=nil then { исходный список пуст - копия пуста }
CopySll:=nil
else begin
cur:=head; prev2:=nil;
{ перебор исходного списка до конца или по счетчику num }
while (num>0) and (cur<>nil) do begin
{ выделение памяти для эл-та выходного списка и запись в него
информационной части }
New(cur2); cur2^.inf:=cur^.inf;
{ если 1-й эл-т выходного списка - запоминается указатель на
начало, иначе - записывается указатель в предыдущий элемент }
if prev2<>nil then prev2^.next:=cur2 else head2:=cur2;
prev2:=cur2; { текущий эл-т становится предыдущим }
cur:=cur^.next; { продвижение по исходному списку }
num:=num-1; { подсчет эл-тов }
end;
cur2^.next:=nil; { пустой указатель - в последний эл-т
выходного списка }
CopySll:=head2; { вернуть указатель на начало вых.списка }
end; end;
Cлияние двух списков
Операция слияния заключается в формировании из двух списков одного - она аналогична операции сцепления строк. В случае односвязного списка, показанном в примере 4, слияние выполняется очень просто. Последний элемент первого списка содержит пустой указатель на следующий элемент, этот указатель служит признаком конца списка. Вместо этого пустого указатель в последний элемент первого списка заносится указатель на начало второго списка. Таким образом, второй список становится продолжением первого.
{==== Программный пример 4 ====}
{ Слияние двух списков. head1 и head2 - указатели на начала
списков. На результирующий список указывает head1 }
Procedure Unite (var head1, head2 : sllptr);
var cur : sllptr;
begin { если 2-й список пустой - нечего делать }
if head2<>nil then begin
{ если 1-й список пустой, выходным списком будет 2-й }
if head1=nil then head1:=head2
else { перебор 1-го списка до последнего его эл-та }
begin cur:=head1;
while cur^.next<>nil do cur:=cur^.next;
{ последний эл-т 1-го списка указывает на начало 2-го }
cur^.next:=head2;
end; head2:=nil; { 2-й список аннулируется }
end; end;
1 2 3 4 5
8 8 8
| 
*
Обратная связь