Verkettung ? Fragen für Info-Klausur

[Hansa]

Zitat:

Zitat von VeeJay

Ansonsten werde ich das Prinzip wohl auswendig lernen ohne es zu verstehen :roll:

Ja, wohl oder übel. Obwohl es Dir nichts nützen wird. Falls eine solche Frage kommt, macht sie höchstens 10% der Punkte aus. Kümmere dich besser um die restlichen 90% :!:

Gruß
Hansa

[Salomon]

Hallo,
mit deinem Wissen über Pointer, kannst du nun auch einfache verkette Listen erstellen. Wichtig für Ketten sind die While Schleifen, die du bei fast allen Aktionen brauchst (z.B beim Einfügen, Löschen und durchsuchen der Kette)

Delphi-Quellcode:

Type 
   pElementZeiger := ^tElement;
   tElement := object
                 next  :tElementZeiger;
                 inhalt: integer;
               end;

Var
kopf : pElementZeiger; //Globale Variable die immer auf das erste Element der Liste zeigt.

Einfügen in die Liste geht dann z.B so:

Delphi-Quellcode:

Procedure InsertNewElement (content : integer);
Var hilf, newelement : pElementZeiger;
Begin
hilf := kopf^.next;
while (hilf<>nil) do 
 hilf := hilf^.next; //mit der Schleife kommt man ans Ende der Liste, wo dann das neue Element eingefügt wird

new(newelement);
newelement^.inhalt := content;
newelement.^next := nil;
hilf^.next := newelement;
end;

Das Ausgeben der Liste ist genauso einfach:

Delphi-Quellcode:

Procedure ShowList;
Var hilf :pElementZeiger;
Begin
hilf := kopf;
while (hilf^.next <> nil) do
 begin
  memo1.lines.Add (inttostr(hilf^.inhalt));
  hilf := hilf^.next;
 end;
end;

Suchen funktioniert ebenfalls mit der Schleife:

Delphi-Quellcode:

Procedure FindElement (content : integer);
Var hilf : pElementZeiger;
Begin
hilf := kopf;
while (hilf <> nil) do 
 begin
  if hilf^.inhalt = content then
   showmessage('Element gefunden: ' + inttostr(hilf^.inhalt));
   hilf := hilf^.next;
 end;
end;

Das löschen eines Elementes in der Liste ist schon komplizierter, da man darauf achten muss, dass die Zeiger später wieder auf die richtigen Elemente Zeigen und die Kette nicht auseinander bricht.

Delphi-Quellcode:

Procedure LoescheElement (content : integer);
Var hilf1, hilf2 : pelementZeiger;
Begin
Hilf1 := Kopf;
If Kopf^.inhalt = content then
 begin
  Kopf := Kopf^.next;
  Dispose (hilf1);
 end
else
 Repeat
  hilf2 := hilf1; hilf1 := hilf1^.next;
 Until (Hilf1 = nil) or (Hilf1^.inhalt = content);

If Hilf1 <> nil then
 begin 
  Hilf2^.next := Hilf1^.next;
  Dispose (Hilf1);
 end;
end;

So, ich denke das ist schonmal ein kleiner Überblick wie man mit einfach verketten Listen arbeitet. Doppelt verkette Listen haben nicht nur einen Zeiger auf das Nachfolge Elemnet, sondern auch einen Zeiger auf ihren Vorgänger. Dadurch werde Opperationen wie z.B das Löschen einfacher.
Die Quelltexte können Fehler beinhalten, da ich sie eben so aus dem Kopf aufgeschrieben habe. Ist schon wieder etwas her wo ich mich mit Listen beschäftigen musste.

Mfg Salomon

[Neotracer64]

Ich bin auch gerade dabei mich mit Listen zu beschäftigen. :)

Ich habe versucht das wie folgt umzusetzen, orientiert an dem Code über mir:

Delphi-Quellcode:

PZahl = ^TZahl;
TZahl = record
   Item  : Integer;
   Next  : PZahl;
end;


type
  TintList = class
  Zahl : TZahl;
  PFirst : PZahl;
  constructor Create;
  procedure Add(Int: Integer);
  //procedure Delete(Index: Integer);
  //function  Get(index: Integer): Integer;
end;

...

constructor TintList.Create;
begin
  inherited Create;
  Zahl.Item := 0;
  Zahl.Next := nil;
  PFirst := @Zahl;
end;

...

procedure TintList.Add(int: Integer);
var
  Digit: PZahl;
  Silk : PZahl;
begin

  //Silk := PFirst^.next;  <-- IST FALSCH!!!!
    Silk := PFirst; 


  If Silk <> nil Then
     while (Silk^.Next <> nil) do
        Silk := Silk^.next;

  New(Digit);
  Digit^.Item := int;
  Digit^.Next := nil;
  Silk^.Next := Digit; /// <--- Hier WAR er abgestürzt jetz gehts wieder...
end;

Nur wenn ich eine Zahl zu der Liste hinzufügen möchte, stürzt er Mit EAccessViolation ab. :(. An der Adresse 00000004 kann er nicht schreiben steht dann zusätzlich da.

Aber eigentlich sollte die Routine einfach das letzte Element finden, was dann ja Silk sein soll. Und das darf unmöglich auf 00000004 zeigen. :shock:

Wie kann das denn sein. Ich blic da nich durch :cry:

EDIT: Habs rausgefunden. Ich habe es oben korrigiert und die falsche Zeile auskommentiert.