Frage zum Sortieren einer verketteten Liste

[Chris P]

Kann mir bitte jemand helfen

[xineohp]

so,

jetzt hab ich 's:

Bei einer einfach verküpften Liste müssen 3! Zeiger verändert werden, du brauchst also zwei Hilfsvariablen.

Delphi-Quellcode:

var
  changed: boolean;
  nav, help1, help2: tListenElement;
begin

  changed := true;
  while changed do   // deine Version mit der zweiten Schleife sollte auch funktionieren, 
  begin              // aber so muss du die Anzahl der Elemente der Liste nicht kennen.
    changed := false;
    nav := root;                            // Zeiger auf den Anfang setzen
    while not (nav^.next = nil) do          // solange wir nicht am Ende sind weiter machen
    begin
      If nav^.name > nav^.next^.name then   // vergleichen 
      begin
        help1 := nav;                       // die zwei Elemente vertauschen. 
        nav := nav^.next;                   // man beachte, dass hierzu drei Zeiger geändert werden müssen!
        help2 := nav^.next;
        nav^.next := ´nav^.next^.next;
        help2^.next := help1;
        changed := true;
        If help1=root then root := nav;     // falls wir gerade das root-Element geändert haben, root neu setzen  
      end;
      nav := nav^.next;                     // auf zum nächsten Element :) 
    end;
  end;

end;

[Chris P]

Funktioniert aber nicht ganz.

Was macht eigentlich der 2. Hilfszeiger.
Ich habe in meiner Liste 5 Elemente.
Die 2. WHILE - Schleife läuft nur 4 mal durch und dann kommt eine Zugriffsverletzung.

Wo liegt der Fehler???

Hast du es schon getestet?

[mytar]

Ersetze die 2. While-Anweisung mit:

Delphi-Quellcode:

while Assigned(nav) and Assigned(nav^.next) do

greetz
mytar :-D

[mytar]

Noch eine Änderung:

Delphi-Quellcode:

var 
  changed: boolean; 
  nav, help1, help2: tListenElement; 
begin 

  changed := False;

  repeat //<<<     
    nav := root; 
    while Assigned(nav) and Assigned(nav^.next) do //<<<
    begin 
      if nav^.name > nav^.next^.name then 
      begin 
        help1 := nav;                     
        nav := nav^.next;                
        help2 := nav^.next; 
        nav^.next := nav^.next^.next; 
        help2^.next := help1; 
        
        changed := True; 
        if help1 = root then
         root := nav;   
      end; 
      nav := nav^.next;                 
    end; 
  until not changed; //<<<

end;

[Chris P]

Danke erstmal, aber ich verstehe immer noch nicht für was der 2. Hilfszeiger "HELP2" gut ist.


Er bekommt doch nur Werte zugewiesen aber mit diesen Werten wird doch gar nichts gemacht.

[xineohp]

so, ich hab noch mal drüber nachgedacht und hoffe nun eine endgültige (und endlich auch richtige) Lösung präsentieren zu können:

Mein letzter Ansatz mit zwei Hilfsvariablen war in sofern falsch, da ich die Problematik der von einander abhänigen Referenzen (siehe Anhang) nicht in letzter Konsequenz beachtet hatte.

Man benötigt nun mehr vier Hilfsvariablen (Erläuterungen hierzu im Anhang):

Delphi-Quellcode:

helpA := nav;
helpB := nav^.next;
helpC := nav^.next^.next;

help  := helpA;
helpA := helpB;
helpB := helpC;
helpC := help;

Die von mytar vorgeschlagenen Änderungen ändern sind nicht zwingend notwendige Verbesserungen. Die erste (Assinged) sichert das ganze zusätzlich ab, sollte aber auch ohne funktionieren (wenn der Tauschvorgang nun endlich stimmt). Die zweite stellt eine kleine Optimierung dar (aber nur wenn sie richtig implementiert wird! das changed := false steht nämlich an falscher Stelle es muss wenn dann innerhalb der repeat-Schleife stehen! Insgesammt spärt die repeat- gegenüber der while-Schleife eine Überprüfung der Abbruchsbedingung -_-
Trotzdem würde ich die Veränderungen übernehmen :mrgreen:

Das Endergebnis sollte also folgendermaßen aussehen:

Delphi-Quellcode:

var
  changed: boolean;
  nav, help, helpA, helpB, helpC: tListenElement;
begin

  repeat
    changed := False;    //<<<
    nav := root;
    while Assigned(nav) and Assigned(nav^.next) do 
    begin
      if nav^.name > nav^.next^.name then
      begin
        helpA := nav;
        helpB := nav^.next;
        helpC := nav^.next^.next;

        help  := helpA;
        helpA := helpB;
        helpB := helpC;
        helpC := help;
       
        changed := True;
        if help = root then
         root := nav;   
      end;
      nav := nav^.next;                 
    end;
  until not changed; 
end;

EDIT: Anhang vergessen ... :wall:

[Chris P]

Danke, werde es gleich mal ausprobieren!

Wenns nicht klappt dann meld ich mich noch ma...

[Chris P]

Das klappt leider gar nicht.

Das Programm hängt sich auf!

Ich verstehe das nicht so ganz mit den Hilfszeigern.

Sie werden untereinander vertauscht aber sonst auch nichts!

Die Variable NAV muss doch nach dem Tauschvoragng wieder einen Werte bekommen.

Nach jedem Schleifendurchlauf verfallen doch die Werte der Hilsvariablen wieder.

Kann mir denn keiner helfen??

[xineohp]

irgendwie dreh ich mich im Kreis :cry:

probiers mal so:

Delphi-Quellcode:

var 
  changed: boolean; 
  nav, help, helpA, helpB, helpC: tListenElement; 
begin 

  repeat 
    changed := False;    //<<< 
    nav := root; 
    while Assigned(nav) and Assigned(nav^.next) do 
    begin 
      if nav^.name > nav^.next^.name then 
      begin 
        helpA := nav; 
        helpB := nav^.next; 
        helpC := nav^.next^.next; 

        help  := helpA; 
        helpA := helpB; 
        helpB := helpC; 
        helpC := help;

        nav := helpA;
        nav^.next := helpB;
        nav^.next^.next := helpC;
        
        changed := True; 
        if help = root then 
         root := nav;    
      end; 
      nav := nav^.next;                  
    end; 
  until not changed; 
end;

wenn's nicht funktioniert häng mal dein Project an, dann probier ich selber mal ein bischen dran rum :cyclops: