(3) (2) prev … …Inf next
Inf next
Inf next
Inf next
(1)
Рис. 6.9. Перестановка соседних элементов 1-связного списка.
{ Перестановка двух соседних элементов в 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;
В процедуре перестановки для двухсвязного списка нетрудно учесть и перестановку в начале и конце списка (рис. 6.10).
(5)
(2)
(4)
(6) (3) (1) … …
PREV
INF NEXT … …
PREV
INF NEXT
PREV
INF NEXT
PREV
INF NEXT
Рис. 6.10. Перестановка соседних элементов 2-связного списка.
Копирование части списка.При копировании исходный список сохраняется в памяти, и создается новый список. Информационные поля элементов нового списка содержат те же данные, что и в элементах старого списка, но поля связок в новом списке совершенно другие, поскольку элементы нового списка расположены по другим адресам в памяти. Существенно, что операция копирования предполагает дублирование данных в памяти.
{ Копирование части 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;
Слияние двух списков.Операция слияния заключается в формировании из двух списков одного и аналогична операции сцепления строк. В случае односвязного списка слияние выполняется просто. Последний элемент первого списка содержит пустой указатель на следующий элемент, этот указатель служит признаком конца списка. Вместо пустого указателя в последний элемент первого списка заносится указатель на начало второго списка. Таким образом, второй список становится продолжением первого.
{ Слияние двух списков. head1 и head2 - указатели на начала
списков. На результирующий список указывает head1 }
procedure UniteSll(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;