A niech stracę - masz prezent:
procedure SplitList(const ALeftHead: PNode; out ARightHead: PNode; ACutAfter: Integer);
var
LLeftLast: PNode;
begin
LLeftLast := ALeftHead;
while ACutAfter > 0 do
begin
LLeftLast := LLeftLast^.Next;
Dec(ACutAfter);
end;
ARightHead := LLeftLast^.Next;
LLeftLast^.Next := nil;
end;
Tak wygląda kod procedury dzielącej jedną listę jednokierunkową na dwie;
W parametrze ALeftHead
podaje się głowę listy wejściowej - parametr ten jest automatycznie wskaźnikiem na głowę pierwszej listy docelowej; W argumencie ARightHead
podaje się pointer na głowę drugiej listy docelowej, a w ACutAfter
indeks węzła, za którym lista zostanie ucięta, a dalsza część wydzielona do drugiej listy;
Powyższy kod nie zawiera zabezpieczeń przed podaniem zbyt dużego indeksu - to sobie dorób, jeśli potrzebujesz; W każdym razie, w ostatnim parametrze podać można indeks od wartości 0
(pierwsza lista otrzyma jeden węzeł, a druga pozostałe) do n-1
(pierwsza lista otrzyma wszystkie węzły, więc nic się nie zmieni), gdzie n
to liczba węzłów w liście;
Aplikacja testowa - http://ideone.com/e2G0bX
Jeśli chodzi o podział listy dwukierunkowej to algorytm niewiele się różni od poprzedniego:
procedure SplitList(const ALeftHead: PNode; out ARightHead: PNode; ACutAfter: Integer);
var
LLeftLast: PNode;
begin
LLeftLast := ALeftHead;
while ACutAfter > 0 do
begin
LLeftLast := LLeftLast^.Next;
Dec(ACutAfter);
end;
ARightHead := LLeftLast^.Next;
ARightHead^.Prev := nil;
LLeftLast^.Next := nil;
end;
Jak widać doszła tylko jedna linijka - wpisanie nil
do Prev
; Kodu nie ma co drugi raz tłumaczyć, dlatego że implementuje dokładnie to samo co wyżej podany, tyle że dla listy dwukierunkowej; Zakres indeksów możliwych do podania w ostatnim parametrze również jest taki sam;
Dla sprawdzenia poprawności ustawień wskaźników w węzłach, wyświetlanie zawartości listy realizowane jest dwa razy - najpierw iterując od głowy do ogona listy, a następnie (w nowej linii) od ogona do głowy; Wszystko gra - nie ma co rozpisywać się;
Aplikacja testowa - http://ideone.com/eyny7f
Tym razem oba programy testowe sprzątają po sobie i robią to prawidłowo, więc wycieków pamięci ze strony testera nie ma; Sprawdziłem poprawność działania za pomocą modułu HeapTrc
i wszystko gra.