type
TKey = integer;
PNode = ^TNode;
TNode = record
key:TKey;
next:PNode;
end;
function getTail(head:PNode):PNode;
var tail:PNode;
begin
tail := head;
while (tail <> NIL)and(tail^.next <> NIL)do
tail := tail^.next;
getTail := tail;
end;
procedure tailins(rec:PNode;var first,last:PNode);
begin
if first = NIL then
first := rec
else
last^.next := rec;
last := rec;
end;
function quickSort(r:PNode;var last:PNode):PNode;
var lowf,lowl,midf,midl,highf,highl:PNode;
begin
if r = NIL then
begin
last :=NIL;
quickSort := r
end
else
begin
lowf := NIL;
midf := NIL;
highf := NIL;
tailins(r,midf,midl);
r := r^.next;
while r <> NIL do
begin
if r^.key < midf^.key then
tailins(r,lowf,lowl)
else if r^.key = midf^.key then
tailins(r,midf,midl)
else
tailins(r,highf,highl);
r := r^.next
end;
if lowf <> NIL then
begin
lowl^.next := NIL;
quickSort := quickSort(lowf,last);
last^.next := midf
end
else
quickSort := midf;
if highf <> NIL then
highl^.next := NIL;
midl^.next := quickSort(highf,last);
if last = NIL then
last := midl
end;
end;
Przypuśćmy że chcemy dopisać do rekordu węzła wskaźnik na poprzednika
Jak ustawić wskaźniki na poprzedników aby funkcja sortowała także listę dwukierunkową ?
Ustawianie poprzedników powinno być zrealizowane przez funkcję sortującą
Jeśli chodzi o ustawienie wskaźników na poprzedników w funkcji wstawiającej istniejący węzeł na koniec listy to
podejrzałem kod przykładowej listy dwukierunkowej i tam proponują do procedury tailins
dopisać instrukcję rec^.prev := last w bloku else zaraz po instrukcji last^.next := rec
else
begin
last^.next := rec;
rec^.prev := last
end;
Jeśli chodzi o ustawienie wskaźników na poprzedników w funkcji sortującej to
próbowałem powstawiać instrukcję
if x^.next <> nil then
x^.next^.prev := x;
w różne miejsca kodu ale nie dawało to oczekiwanego rezultatu