arbeiten mit zeigern

[ferby]

hallo,

ich lerne gerade mit zeigern zu arbeiten und habe ein problem

Delphi-Quellcode:

procedure tform1.ausgabe;
var
i:integer;
begin

  z:=start;
  i:=0;

  repeat
    listbox.items[i]:=z^.name;
    inc(i);
    z:=z^.next;
  until z=nil;

end;

procedure TForm1.closebuttonClick(Sender: TObject);
begin
  close;
end;

procedure TForm1.button_eingebenClick(Sender: TObject);
begin

  new(z);

  z^.name:=edit_eingabe.text;

  if start=nil then start:=z
  else
  begin
    z1:=start;
    while z1^.next<>nil
    do z1:=z1^.next;
    z1^.next:=z;
  end;

  z^.next:=nil;

  ausgabe;

end;

wie schaffe ich es das die zeiger so verbogen werden das die namen in der listbox alphabetisch sotiert werden?
achtung: ich möchte die zeiger verbigen nicht irgendwie anders das sotieren erreichen, ich weiß das es da viel leichtere methoden gibt.

danke für hilfe,
ferby

[Hansa]

Der Vorteil von solchen Listen ist, daß man sie nicht sortieren muß ! Allerdings nur, sofern sie von Anfang an richtig aufgebaut sind. Bei Dir ist hier der Ansatztpunkt :

Delphi-Quellcode:

while z1^.next<>nil
    do z1:=z1^.next;
    z1^.next:=z;

Was bedeutet, daß das Listenelement einfach nur ans Ende angehängt wird. Würde das next nicht bis zum Schluß abgearbeitet, sondern nur bis dahin, wo ein "größeres" Element kommt und du das eben dort einfügst, dann ist die Liste direkt sortiert. Sieht etwas nach einfacher Liste aus. IN diesem Fall brauchst du noch einen Zeiger mehr. Zeige mal noch die Deklaration von dem z-Typ.

[ferby]

Hi,

das weiß ich nur ich weiß nicht wie ich es mach:

hier die variabel:

Delphi-Quellcode:

zeiger=^datensatz;
  datensatz=record
    name:string;
    next:zeiger;
  end;

var
  Form1: TForm1;
  start,z,z1,z_alt:zeiger;

[ferby]

Hi,

kann mir hier keiner helfen????

Muss doch wem geben der sich mit zeigern auskennt????




Ferby

[Hansa]

Es gibt Beispiele genug dafür. Es ist auf Anhieb eben nicht einfach. Du brauchst ein paar Hilfszeiger. Einer läuft immmer weiter und nimmt noch einen mit. Hat der erste nun einen Wert, der schon zu weit in der Liste ist, so muß der alte Wert gespeichert bleiben.

Jetzt legst du mit NEW einen neuen "Zeiger" an. Der hängt aber im luftleeren Raum. Dann kommt von dem "Zeiger", der etwas zurückhängt ein Verweis auf den neuen als NEXT. Der mit new erzeugte hat als NEXT einen Zeiger auf den ersten, der in der Liste am weitesten ist.

Ich zeige hier absichtlich keinen Source, denn wer das Prinzip nicht verstanden hat, der hat sowieso keine Chance solche Strukturen sauber zu programmieren. 8)

[ferby]

Hallo,

klingt kompliziert aber werde mich damit ausernandersetzen.... was ich noch nicht verstanden habe, wie ich das mach, ist, wie ich abfrage ob der eingefügte wert größer oder kleiner (abc) was muss ich da mit was vergelichen????

[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;

[ferby]

Hi,

danke, ich glaube ich habs kapiert, nur versteh ich nicht warum es nicht geht??

Was ist an meinem kleinen Programm nich falsch?

[Hansa]

"Schleppzeiger" ist echt gut. Aber das stimmt schon so. Was auffällt, sind die Kommentare. Um so was zu beschreiben braucht man mehr Kommentar- als Sourcezeilen. Deshalb habe ich mich ja auch gesträubt ein Beispiel zu zeigen. Beim groben lesen fällt mir allerdings ein <= auf. Wird mit new auch an der richtigen Stelle was eingefügt und nicht zu spät ? Ist das getestet ? Falls nicht, so ist das nicht weiter schlimm. Dann muß die Liste eben etwas angepaßt / umgebogen werden.

P.S.: der Text hier war bereits fast geschrieben. Der Anhang von Ferby kam später.

[Niko]

Zitat von ferby:

danke, ich glaube ich habs kapiert, nur versteh ich nicht warum es nicht geht??

Weil ich einen Fehler gemacht habe.
Die letzte Zuweisung muss natürlich so aussehen:
Schleppzeiger^.next := NeueDaten; Ich hab's auch oben ausgebessert.

Was mir an deinem Programm noch aufgefallen ist: Du solltest den Speicher für die Elemente am Programmende auch wieder freigeben.

Zitat von Hansa:

"Schleppzeiger" ist echt gut.

Tja, so hieß das in meiner Algorithmik-Vorlesung.

Was das <= angeht: Dadurch werden neue Elemente die mit bereits vorhandenen übereinstimmen, hinter den vorhandenen eingefügt. Wer's lieber anders hätte, muss das = halt weglassen. Aber bei dem konkreten Beispiel kann das sowieso niemand unterscheiden.