arbeiten mit zeigern

[Niko]

Hi,

sortiertes Einfügen könnte man zum Beispiel so implementieren:

Delphi-Quellcode:

procedure SortiereEin(var Start: zeiger; s: String)
var
  NeueDaten: zeiger;  // Zeiger auf den neuen Datensatz
  Suchzeiger, Schleppzeiger: zeiger;  // Zeiger zum Suchen der Einfügeposition
begin
  // neuen Eintrag anlegen
  new(NeueDaten);
  NeueDaten^.name := s;

  // alles auf Anfang
  Suchzeiger = Start;
  Schleppzeiger = Start;

  // Jetzt wird Suchzeiger so lange auf das nächste Element gesetzt, bis dieses nil
  // ist, es also kein weiteres Element gibt oder bis es größer als das neues ist.
  // Man geht also bis zu dem Element, *vor* dem man einfügen muss.
  while (Suchzeiger <> nil) and
        (Suchzeiger^.name <= NeueDaten^.name) do
  begin
    // Da das Element nach dem eingefügt wird, verändert werden muss, wird der Zeiger
    // darauf gespeichert ...
    Schleppzeiger := Suchzeiger;

    // ... bevor Suchzeiger erhöht wird.
    Suchzeiger := Suchzeiger^.next;
  end;

  if Suchzeiger = Start then
  begin
    // Falls vor dem ersten Element eingefügt werden muss oder bisher noch kein Element
    // in der Liste war, muss Start verändert werden.
    // (Es gibt Möglichkeiten diese Abfrage einzusparen, aber ich denke so ist es am
    // verständlichsten.)

    // next muss auf das Element zeigen, auf das bisher Start verwiesen hat, damit die
    // Liste nicht unterbrochen wird.
    NeueDaten^.next = Start;

    // dann kann Start verändert werden
    Start := NeueDaten;
  end
  
  else
  begin
    // Wenn das neue Element in die Mitte oder an's Ende der Liste eingefügt werden soll,
    // muss statt Start next des Vorgängerelements verändert werden (und genau dazu braucht
    // man den Schleppzeiger).

    // next von NeueDaten wird auf das Element gesetzt, vor dem eingefügt wird
    NeueDaten^.next := Suchzeiger;

    // und anschließend next von dem Element verändert, nach dem das neue eingefügt wird
    Schleppzeiger^.next := NeueDaten;
  end;
end;