Hilfe bei doppelter verkettete Liste

[Preddy2005]

Hallo mal wieder! ;-)

Bräuchte mal ein wenig Hilfe...

Und zwar geht es um Erklärungen in Bezug auf eine doppelte verkettete Liste.

Delphi-Quellcode:

procedure TForm1.btnFirstClick(Sender: TObject);
begin
 New(pNeuer_Wert); // Neues Element erzeugen
 pNeuer_Wert^.Zahl := 1; // Zahl auf den Wert eins setzen
 PNeuer_Wert^.Next := nil; // Next - Zeiger zeigt auf kein Element
 PNeuer_Wert^.Prev := nil; // Prev - Zeiger zeigt auf kein Element
 pErster_Wert := pNeuer_Wert; // Erster Wert Zeiger zeigen auf NIL
 pVorheriger_Wert := pNeuer_Wert; // Zweiter Wert Zeiger zeigen auf NIL
 btnFirst.Enabled := false; // Knopf ausblenden 
end;

{*******************************************************************************
*******************************************************************************}

procedure TForm1.btnNextClick(Sender: TObject);
Var
   Temp_Zahl : Integer; // Fürs Inkrementieren der Zahl

begin

 if pNeuer_Wert = nil then btnFirst.Click; // Wenn neue Wert ins Nichts zeigt, dann
  Temp_Zahl := pNeuer_Wert^.Zahl;
  new(pNeuer_Wert); // Neuen Wert Speicher anlegen
  pNeuer_Wert.Zahl := Temp_Zahl + 1;
  pNeuer_Wert^.Prev := pVorheriger_Wert; // Neue Wert am Ende zeigt auf das vorherige Element
  pNeuer_Wert^.Next := nil; // Neue Wert zeigt auf NIL
  pVorheriger_Wert^.Next := pNeuer_Wert; // Zeiger des vorherigen Elementes muss auf das neu erzeugte Element gesetzt werden
  pVorheriger_Wert := pNeuer_Wert; // ??
  btnRead.Click;
end;

{*******************************************************************************
*******************************************************************************}

procedure TForm1.btnReadClick(Sender: TObject);
begin
   if pVorheriger_Wert = nil then Exit; //??
   lbElemente.Clear;
   pAktueller_Wert := pVorheriger_Wert; //??
   While pAktueller_Wert^.Prev <> nil Do //??
    Begin // Solange letzter Wert ungleich nil,
     lbElemente.Items.Add(IntToStr(pAktueller_Wert^.Zahl));
     lbSpeicheradressen.Items.Add('');
     lbSpeicheradressen.Items.Add(Format('Next : x%x', [Integer(pAktueller_Wert^.Next)]));
     lbSpeicheradressen.Items.Add(Format('Prev : x%x', [Integer(pAktueller_Wert^.Prev)]));
     pAktueller_Wert := pAktueller_Wert.Prev; // Letzter Wert dem aktuellen Wert zuweisen
    End; 
end;

{*******************************************************************************
*******************************************************************************}

Alles was ich mit / ?? Markiert habe, ist mir nicht ganz klar.
Ich habe das Grundprinzip verstanden, aber ich verstehe diese Zeilen nicht ganz. Wenn mir jemand verständlich erklären könnte, wieso man diese Zeilen so schreiben muss oder wieso sie so stehen müssen, dann wäre ich euch schon sehr dankbar.

Danke schonmal im voraus für die Hilfe.

Gruß

Matthias

[bttb930]

lass dich einfach nicht von den bezeichnern verwirren: pVorherigerWert ist nicht immer der vorherige Wert sondern in vielen Fällen der aktuelle. ist nicht ganz toll programmiert, aber geht ja scheinbar.

[Preddy2005]

Gibt es bessere Bezeichnungen oder sollte ich mehr Variablen anlegen für die Liste?
Habe das Beispiel des Lehrers ja modifizieren wollen, aber wie man sieht, war das Lehrerbeispiel ja schon nicht wirklich verständlich. Aber im Internet habe ich auch noch kein super brauchbares Tutorials gefunden.

Danke schonmal

Gruß Matthias

[bttb930]

nee, mehr variablen brauchst du nicht.

ich glaube das verständnisproblem kommt einfach daher, dass pVorheigerWert ganz oft nicht den vorherigen Wert speichert, sondern den aktuellen. Ungewöhnlich ist, dass dein lehrer immer am ende der prozedur pVorheriger_wert setzt. Ich würde die Variable einfach pAktuellerWert nennen..,. aber die hat er ja schon.

wie auch immer, die namensgebung und vorgehensweise ist nicht ganz so, wie ich das machen würde.

schreib doch nochmal dazu was btnFirst soll und warum der hinterher disabled wird?

[Meniskusschaden]

Zitat:

Zitat von Preddy2005

Hallo mal wieder! ;-)

Bräuchte mal ein wenig Hilfe...

Und zwar geht es um Erklärungen in Bezug auf eine doppelte verkettete Liste.

Delphi-Quellcode:

procedure TForm1.btnFirstClick(Sender: TObject);
begin
 New(pNeuer_Wert); // Neues Element erzeugen
 pNeuer_Wert^.Zahl := 1; // Zahl auf den Wert eins setzen
 PNeuer_Wert^.Next := nil; // Next - Zeiger zeigt auf kein Element
 PNeuer_Wert^.Prev := nil; // Prev - Zeiger zeigt auf kein Element
 pErster_Wert := pNeuer_Wert; // Erster Wert Zeiger zeigen auf NIL
 pVorheriger_Wert := pNeuer_Wert; // Zweiter Wert Zeiger zeigen auf NIL
 btnFirst.Enabled := false; // Knopf ausblenden 
end;

{*******************************************************************************
*******************************************************************************}

procedure TForm1.btnNextClick(Sender: TObject);
Var
   Temp_Zahl : Integer; // Fürs Inkrementieren der Zahl

begin

 if pNeuer_Wert = nil then btnFirst.Click; // Wenn neue Wert ins Nichts zeigt, dann
  Temp_Zahl := pNeuer_Wert^.Zahl;
  new(pNeuer_Wert); // Neuen Wert Speicher anlegen
  pNeuer_Wert.Zahl := Temp_Zahl + 1;
  pNeuer_Wert^.Prev := pVorheriger_Wert; // Neue Wert am Ende zeigt auf das vorherige Element
  pNeuer_Wert^.Next := nil; // Neue Wert zeigt auf NIL
  pVorheriger_Wert^.Next := pNeuer_Wert; // Zeiger des vorherigen Elementes muss auf das neu erzeugte Element gesetzt werden
  pVorheriger_Wert := pNeuer_Wert; // ?? pVorherigerWert wird auf Listenende gesetzt
  btnRead.Click;
end;

{*******************************************************************************
*******************************************************************************}

procedure TForm1.btnReadClick(Sender: TObject);
begin
   if pVorheriger_Wert = nil then Exit; //?? Zielsetzung unklar. Notausgang für undefinierte Situation oder Behandlung einer leeren Liste?  
   lbElemente.Clear;
   pAktueller_Wert := pVorheriger_Wert; //?? pAktueller_Wert wird auf Listenende gesetzt
   While pAktueller_Wert^.Prev <> nil Do //?? Die Schleife wird durchlaufen, bis es keinen Vorgänger mehr gibt
    Begin // Solange letzter Wert ungleich nil,
     lbElemente.Items.Add(IntToStr(pAktueller_Wert^.Zahl));
     lbSpeicheradressen.Items.Add('');
     lbSpeicheradressen.Items.Add(Format('Next : x%x', [Integer(pAktueller_Wert^.Next)]));
     lbSpeicheradressen.Items.Add(Format('Prev : x%x', [Integer(pAktueller_Wert^.Prev)]));
     pAktueller_Wert := pAktueller_Wert.Prev; // Letzter Wert dem aktuellen Wert zuweisen
    End; 
end;

{*******************************************************************************
*******************************************************************************}

Alles was ich mit / ?? Markiert habe, ist mir nicht ganz klar.
Ich habe das Grundprinzip verstanden, aber ich verstehe diese Zeilen nicht ganz. Wenn mir jemand verständlich erklären könnte, wieso man diese Zeilen so schreiben muss oder wieso sie so stehen müssen, dann wäre ich euch schon sehr dankbar.

Danke schonmal im voraus für die Hilfe.

Gruß

Matthias

Ich finde die Implementierung auch nicht so toll. Die Idee ist wohl, dass neue Werte immer an das Listenende gehängt werden und pVorheriger_Wert nach jeder Operation auf das Listenende zeigt. Ich habe die von Dir markierten Bereiche oben kommentiert.

[Der_Unwissende]

Hi,
muss leider mal etwas verkürzt antworten.
Trotzdem möchte ich erstmal darauf hinweisen, dass hier natürlich nur Hilfen gegeben werden, du musst natürlich auch einen guten Teil leisten. Da du sagtest, du hast das Grundprinzip schon verstanden, wäre es hier sehr schön, wenn du einfach mal sagen könntest, was du meinst in welchem Teil gemacht werden muss. Wie legt man denn eine doppelt verkettete Liste an, wie fügt man ein Element ein...?
Hier in diesem Fall werden die Elemente immer nur hinten rangehangen. Deswegen ist die Bezeichnung pVorherigerWert eigentlich falsch. Es ist zwar (wie Preddy schon sagte) immer der aktuelle Wert, vorallem aber ist es der Letzte Werte deiner Liste. Eine (nicht zyklische) Liste hat immer ein erstes und ein letztes Element. Ist sie leer, entfällt das natürlich, ist nur ein Element drin, dann ist dieses Element beides, erstes und letztes Element, sind mind. zwei Elemente drin, gibt es verschiedene Elemente, von denen eines das erste ist und eines das Letzte.

Die Idee der Verkettung in der Liste war dir ja klar? Dann überleg einfach mal, wenn du eine Liste hast, die nicht leer ist, wie du hier ein Element anhängen würdest. Überleg es dir einfach mal in Worten, dann versuche das ganze im Code wiederzufinden und/oder zu verstehen.

Da ich leider gleich weiter muss werde ich hier mal kurz ein wenig dazu sagen, dass findest du dann vielleicht auch gleich im Code wieder (der trotzdem schlecht ist, sorry). Jedenfalls besteht die Idee beim Anhängen einfach darin, dass du das letzte Element nimmst. Das es das letzte ist erkennst du daran, dass es keinen Nachfolger hat (der Zeiger next zeigt auf nil). Jetzt erzeugst du das neue letzte Element. Nennen wir der Einfachheithalber das alte Letzte Element A und das neue B. Du möchtest nun B hinter A in die Liste einfügen. Das heißt, dass der Vorgänger von B A ist und der Nachfolger von A muss B sein. Soweit klar?
Das ganze musst du jetzt noch in Code umsetzen. Das ist an sich sehr einfach, du musst hier ja nur übernehmen, was da steht. Nun hast du aber ein neues letztes Element, also musst du den globalen Zeiger, der immer nur auf das letzte Element zeigt auf B zeigen lassen. Das ist dann schon alles.

Delphi-Quellcode:

A, B : PListElement;
begin
  // hier ist A einfach nur ein Puffer für einen Zeiger
  // Es wird hier einfach der Zeiger auf das im Moment noch letzte Element zwischengespeichert
  A := letztes_Element; // letztes_Element ist ein globaler zeiger auf das letzte Element
 
  new(B); // hier wird ein neues Element erzeugt
  
  // da es hinten ran gehangen wird, kann es keinen Nachfolger geben 
  B.next := nil; 

  // da es rangehangen wird, muss es aber einen Vorgänger geben
  B.prev := A;

  // nun weiß b zwar, wer sein Vorgänger ist und dass es keinen Nachfolger hat,
  // aber der Rest der Liste hat das noch nicht mitbekommen.
  // A hat immer noch keinen Nachfolger und der Zeiger letztes_Element zeigt immer 
  // noch auf A
  
  // also zeigen wir A nun seinen Nachfolger
  A.next := B;

  // und setzen den globalen Zeiger auf das Ende
  letztes_Element := B;
end;

Das ist jetzt nur das Prinzip für das hinten ran hängen. Das erzeugen einer Liste und das auslesen der Liste sind dann zwar noch offen, aber vielleicht komsmt du damit dann auch weiter.
Die erste Frage, die du beim Auslesen hast,

Delphi-Quellcode:

if pVorheriger_Wert = nil then Exit; //??

Ersetz hier einfach wieder pVorheriger_Wert durch pLetzter_Wert, dann ist vielleicht klar, was da gemacht wird. Sauberer ist es hier aber, wenn du das durch eine Bedingung ersetzt, alles was danach kommt sollte nur ausgeführt werden, wenn es eine letztes Element gibt (ansonsten ist die Liste einfach leer).

Gruß Der Unwissende

[EDIT]
Nix roter Kasten, deswegen alles so redundant
[/EDIT]

[Preddy2005]

Hallo Leute!

Danke für eure Hilfe.

Habe erst heute wieder vorbeigeschaut, deswegen kommt die Antwort auch erst jetzt.
Ich werde mir alles genau durchlesen und versuchen das ganze umzusetzen.
Der Ursprungscode kommt von meinem Lehrer und manche Stellen, die ich quasi so in meine Variablen umbenannt habe, haben deswegen auch diese Namen. Ich werde mich mal die Woche jetzt ransetzen und mich mal melden, wenn ich das ganze herausbekommen habe.

Schonmal vielen Dank für die Unterstützung

Gruß Preddy2005

[Preddy2005]

Hallo nochmal!

Ich habe mal ein wenig ausprobiert und habe den Code umgeschrieben. Allerdings ist in dem Code ein Fehler drinne... Denke ich zumindest. Habe auch keine Möglichkeit gefunden, wie ich den Fehler finden kann. Auch mit Debuggen finde ich nix. Ich stelle mal den Code hier rein. Vielleicht kann mir ja jemand helfen.

Delphi-Quellcode:

Type
  PWert = ^TWert;
  TWert = Record
             Zahl : Integer; // Speichert eine Zahl ab
             Prev : PWert; // Zeiger auf vorheriges Element
             Next : PWert; // Zeiger auf nächstes Element
           End;

var
 pLetztes_Element    : pWert; // Zeiger auf das letzte Element
 pListen_Anfang      : pWert; // Listenanfang
 pElement_A          : pWert; // Listenelement zum verketten
 pElement_B          : pWert; // Listenelement zum verketten

implementation

{$R *.DFM}

{*******************************************************************************
*******************************************************************************}

procedure TForm1.btnFirstClick(Sender: TObject);
begin
 pListen_Anfang := nil; // Leere Liste
 New(pElement_A); // Neues Listenelement erzeugen
 pListen_Anfang := pElement_A; // Listenanfang und erste Element verknüpfen
 pListen_Anfang.Next := nil; // Kein Nachfolgerelement
 pListen_Anfang.Prev := nil; // Kein Vorgängerelement
 pListen_Anfang.Zahl := 1; // Wert zuweisen
 pLetztes_Element := pListen_Anfang; // Listenanfang ist auch zugleich das letzte Element
 btnRead.Click; // Werte im Memo ausgeben
end;

{*******************************************************************************
*******************************************************************************}

procedure TForm1.btnNextClick(Sender: TObject);
Var
  Temp : Integer; // Hilfsvariable

begin
  if pLetztes_Element = nil then btnFirst.Click; // Liste ist leer, erste Listenelement erzeugen 

 // pElement_A := pLetztes_Element; // Letztes Element ist ein globaler Zeiger auf das letzte Element
  Temp := pElement_A^.Zahl; // Zahl zwischenspeichern
  pElement_A^.Zahl := Temp + 1; // Zahl erhöhen und zuweisen
  new(pElement_B); // Neues Listenelement erzeugen
  pElement_b.next  := nil; // Kein Nachfolgeelement vorhanden
  pElement_b.prev  := pElement_A; // Vorgänger des Elementes ist A
  pElement_A.next  := pElement_B; // Der Nachfolger von A ist Element B
  pLetztes_Element := pElement_B; // Globale Zeiger wird auf das Listende gesetzt
  btnRead.Click; // Elemente im Memo ausgeben
end;

{*******************************************************************************
*******************************************************************************}

procedure TForm1.btnReadClick(Sender: TObject);
begin

 lbElemente.Clear; // Memo leeren
 pLetztes_Element := pListen_Anfang; // Erste Element ist immer das letzte Element

 if pLetztes_Element = nil then exit; // Liste ist leer, verlassen
  while pLetztes_Element^.Next <> nil do // Solange nicht das Listenende erreicht worden ist,
  begin
   lbElemente.Items.Add(IntToStr(pLetztes_Element^.Zahl)); // Zahl in die Listbox eintragen
   pLetztes_Element := pLetztes_Element^.Next; // Zeiger auf das nächste Listenelement verweisen
  end; 

end;

{*******************************************************************************
*******************************************************************************}

procedure TForm1.btnDeleteClick(Sender: TObject);
begin
 If pListen_Anfang = nil then exit;

 // Noch zu ergänzen
end;

{*******************************************************************************
*******************************************************************************}

procedure TForm1.btnAnAnfangClick(Sender: TObject);

var Editfeld_Zahl : String;
    Wert_Aus_Editfeld : Integer;

begin

 Editfeld_Zahl := edtWertamAnfangEinfuegen.Text; // Wert vor Konvertierung auf Leerwert prüfen
 if Editfeld_Zahl = '' then exit // Wenn Wert leer, dann verlassen
  else Wert_Aus_Editfeld := StrToInt(edtWertamAnfangEinfuegen.Text); // Ansonsten Umkonvertierung durchführen

 if pListen_Anfang = nil then exit; // Keine Liste erzeugt, verlassen

 new(pElement_A); // Neues Listenelement erzeugen
 pElement_A^.Zahl := Wert_Aus_Editfeld;
 pListen_Anfang^.Next := pElement_A; // Listenanfang verweist auf das erzeugt Element
 pElement_A.Next := pElement_B; // Das erzeugte Element verweist auf B
 btnRead.Click; // Werte auslesen
end;

{*******************************************************************************
*******************************************************************************}

end.

Komme aber immer besser mit der Logik klar.. Dank euch. Hoffe hier kann mir nochmal jemand helfen...

Gruß Matthias

[Der_Unwissende]

Hi,
wenn du glaubst einen Fehler gefunden zu haben, dann solltest du einfach mal sagen, worin dieser liegt. Was genau funktioniert denn nicht?


Gruß Der Unwissende

[Preddy2005]

Es erscheint immer nur eine Zahl in der Listbox... Normalerweise sollten die Elemente doch nacheinander und untereinander erscheinen... Das versteh ich daran nicht ganz. Zumindest war es im alten Beispiel so. Muss also im NextClickEreignis liegen oder aber daran, das ich die Liste falsch auslese.

Gruß Matthias

[Meniskusschaden]

Hallo,

Deine ReadClick-Routine unterschlägt immer das letzte Element und die NextClick-Routine hängt das neue Element an die zweite Position und "verliert" dabei das vorherige zweite Element.

Du solltest deine Operationen mal auf dem Papier aufzeichnen. Für jedes Element ein Kästchen, für jeden Zeiger einen Pfeil auf das entsprechende Kästchen. Dann bei jeder Anweisung die Zeiger "umhängen". Dabei siehst Du ziemlich schnell, wo der Fehler liegt. Aber nicht zu früh aufgeben: mindestens drei Elemente durchspielen.

[Preddy2005]

Danke für die Hilfe. Habe mir das Ganze aufgezeichnet und konnte nach und nach alles umsetzen.

Gruß Matthias