Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
end;
Метод сортировки слиянием вызывается с указанием начального узла сортируемого списка и количества узлов в списке. Имея такие входные данные, за счет прохождения списка и подсчета узлов можно определить, где начинается вторая половина списка. В качестве возвращаемого параметра после сортировки первой половины списка используется последний узел первой половины, который служит фиктивным начальным узлом для второй половины. В любом случае нам приходится
И последняя часть реализации сортировки - сама функция слияния. Ее код приведен в листинге 5.21. Она не представляет никаких трудностей для понимания. Начальным узлом объединенного списка будет служить родительский узел первого подсписка. Функция возвращает последний элемент объединенного списка (он будет использоваться в качестве родительского узла для несортированной части подсписка).
Листинг 5.21. Фаза слияния при сортировке слиянием односвязного списка
function TtdSingleLinkList.sllMerge( aCompare : TtdCompareFunc;
aPriorNode1 : PslNode; aCount1 : longint;
aPriorNode2 : PslNode; aCount2 : longint): PslNode;
var
i : integer;
Node1 : PslNode;
Node2 : PslNode;
LastNode : PslNode;
Temp : PslNode;
begin
LastNode := aPriorNode1;
{извлечь первые два узла}
Node1 := aPriorNode1^.slnNext;
Node2 := aPriorNode2^.slnNext;
{повторять цикл до исчерпания элементов одного из списков}
while (aCount1 <> 0) and (aCount2<> 0) do
begin
if (aCompare(Node1^.slnData, Node2^.slnData) <= 0) then begin
LastNode := Node1;
Node1 := Node1^.slnNext;
dec(aCount1);
end
else begin
Temp := Node2^.slnNext;
Node2^.slnNext := Node1;
LastNode^.slnNext := Node2;
LastNode := Node2;
Node2 := Temp;
dec(aCount2);
end;
end;
{если закончились элементы в первом списке, связать последний узел с оставшейся частью второго списка и пройти список до последнего узла}
if (aCount1 = 0) then begin
LastNode^.slnNext := Node2;
for i := 0 to pred(aCount2) do LastNode := LastNode^.slnNext;
end
{если закончились элементы во втором списке, то Node2 будет первым узлом в оставшемся списке; пройти список до последнего узла и связать его с узлом Node2}
else begin
for i := 0 to pred(aCount1) do
LastNode := LastNode^.slnNext;
LastNode^.slnNext := Node2;
end;
{вернуть последний узел}
Result := LastNode;
end;
Обратите внимание, что в односвязном списке сортировка слиянием не требует выполнения обратного прохода. Мы не были в ситуации, когда требовалось знание родительского узла определенного узла, а он не был известен. Это означает, что сортировка слиянием в двухсвязном списке может выполняться точно так же, как и в односвязном, но после сортировки нужно будет пройти весь список и восстановить обратные ссылки.
Листинг 5.22. Сортировка слиянием для двухсвязного списка
function TtdDoubleLinkList.dllMerge(aCompare : TtdCompareFunc;
aPriorNode1: PdlNode;
aCount1 : longint;
aPriorNode2: PdlNode;
aCount2 : longint);
PdlNode;
var
i : integer;
Node1 : PdlNode;
Node2 : PdlNode;
LastNode : PdlNode;
Temp : PdlNode;
begin
LastNode := aPriorNode1;
{извлечь первые два узла}
Node1 := aPriorNode1^.dlnNext;
Node2 := aPriorNode2^.dlnNext;
{повторять до тех nop, пока один из списков не опустеет}
while (aCount1 <> 0) and (aCount2 <> 0) do
begin
if (aCompare(Node1^.dlnData, Node2^.dlnData) <= 0) then begin
LastNode := Node1;
Node1 := Node1^.dlnNext;
dec(aCount1);
end
else begin
Temp := Node2^.dlnNext;
Node2^.dlnNext := Node1;
LastNode^.dlnNext := Node2;
LastNode := Node2;
Node2 := Temp;
dec(aCount2);
end;
end;
{если закончились элементы в первом списке, связать последний узел с оставшейся частью второго списка и пройти список до последнего узла}
if (aCount1 = 0) then begin
LastNode^.dlnNext := Node2;
for i := 0 to pred(aCount2) do LastNode := LastNode^.dlnNext;
end
{если закончились элементы во втором списке, то Node2 будет первым узлом в оставшемся списке;пройти список до последнего узла и связать его с узлом Node2}
else begin
for i := 0 to pred(aCount1) do LastNode := LastNode^.dlnNext;
LastNode^.dlnNext := Node2;
end;
{вернуть последний узел}
Result := LastNode;
end;
function TtdDoubleLinkList.dllMergesort(aCompare : TtdCompareFunc;
aPriorNode : PdlNode; aCount : longint): PdlNode;
var
Count2 : longint;
PriorNode2 : PdlNode;
begin
{сначала обрабатывается простой случай: если в списке всего один элемент, он отсортирован, поэтому выполнение функции завершается}
if (aCount = 1) then begin
Result := aPriorNode^.dlnNext;
Exit;
end;
{разбить список на две части}