Was ist der beste Weg eine doppelt verkettete Liste zu sortieren?
Das Problem ist nicht der Sortieralgorythmus selbst [zb: Quicksort, Shellsort,...], sondern der Zugriff auf ein Element in der Liste?
Wenn man ein Array sortiert, hat man ja einen Index und somit einen direkten Zugriff.
Ein paar Lösungen die mir eigefallen sind:
1. Ein weiteres Feld für eine eindeutige ID in den record mitaufnehmen.
Funktion die sequentiell sucht und das Element zurückliefert.
Denke aber das es bei einer großen Liste wohl sehr lange dauert immer sequentiell zu suchen.
2. Einen Record mit 2 Feldern hinzufügen.
Delphi-Quellcode:
type
TDAddress = record
Value : string;
PADR : Pointer;
end;
Ein DynArray von TDAddress anlegen. Dann in einer Schleife die Liste durchlaufen und den Wert nachdem sortiert werden soll in Value schreiben. In PADR kommt dann die Adresse von dem Element.
Das Array sortieren und anschließend die Liste anpassen.
Liste in das Array schreiben:
Delphi-Quellcode:
var
AoTDA : array of TDAddress;
Runner: Pzeiger;
i : integer;
begin
Runner := Root;
i := 0;
while Runner <> NIL do
begin
inc(i);
Setlength(AoTDA, Length(AoTDA)+1);
AoTDA[i-1].PADR := Pointer(Runner);
AoTDA[i-1].Value := Runner^.IRGENDWAS; //Irgendwas ist der Wert nachdem sortiert werden soll
Runner := Runner^.next;
end;
end;
Liste anpassen:
Delphi-Quellcode:
var i : integer;
Runner : PZeiger;
begin
Root := AoTDA[low(AoTDA)].PADR;
Root^.next := AoTDA[low(AoTDA)+1].PADR;
Root^.prev := NIL;
FOR i := low(AoTDA)+1 TO high(AoTDA)-1 DO begin
Runner := AoTDA[i].PADR;
Runner^.prev := AoTDA[i-1].PADR;
Runner^.next := AoTDA[i+1].PADR;
end;
Runner := AoTDA[high(AoTDA)].PADR;
Runner^.next := NIL;
Runner^.prev := AoTDA[high(AoTDA)-1].PADR;
end;
Die 2 Variante benutze ich im moment, allerdings habe ich gehört das man das so nicht machen darf.
Hatte jemand mit sowas schonmal Erfahrungen gemacht? Gibt es eine Muster-, Standartlösung?