einfach verkettete Liste

[malibu85]

Hallo, sorry dass ich an einem Tag wie heute mit Listen nerven muss :nerd:

ich habe versucht eine Liste zu programieren, das Prinzip habe ich verstanden aber das Programm und ich snd uns da nicht ganz einig :gruebel:
ich will mal kurz etwas aus dem Quelltext erklären.

Für die Verkettung sorgt der Zeiger t_zeiger und für di listninhalte habe ich t_inhalt erzeugt

Delphi-Quellcode:

                      TYPE t_Zeiger = ^t_inhalt;
                      t_inhalt = Record
                      inhalt   :string;
                      Next     :t_Zeiger;
                      Position :integer;
                      End;

ich habe außerdem so eine Art Lesekopf erzeugt. Wer es vielleicht aus Turingmaschinen kennt. Dieser Kopf besteht aus

(Kopf->steht auf dem ersten Element,

Aktuell->steht immer auf dem Aktuellen Element und kann verschoben werden.

Ende-> Steht immer auf dem letzten Element;

Delphi-Quellcode:

  Kopf          :t_Zeiger;
  Aktuell       :t_Zeiger;
  Ende          :t_Zeiger ;

Am Anfang des Quelltextes habe ich ein Haufen Ausgabeprozeduren sowie eine leere Liste erzeugt.Was aber nicht so wichtig ist. Es geht also erst so richtig los, sobald man auf Button 1 klickt. Das Programm prüft ob der Kopf leer ist

Delphi-Quellcode:

if (Kopf=NIL) then

. Da dieser leer ist, wird ein Listenfeld (akt) erzeugt. Da akt ein Zeiger ist, kann man in dieses Listenfeld mit den folgenden befehlen Werte zuweisen

Delphi-Quellcode:

           akt^.Next    :=NIL;
           akt^.inhalt  :='Das ist das erste Leisenelement';
           akt^.Position:=1;

wenn jedoch schon ein Listenelement vorhanden ist, springt das Programm in die Else- schleife. Zuvor hatte ich gesagt das der Zeiger, der jedes Element mit seinem nachfolger verknüpfe soll, also

Delphi-Quellcode:

akt^.Next    :=NIL;

ins leere zeigen soll. In der Else-Anweisung wird dieser Zeiger nicht mehr ins leere zeigen (NIL) sondern auf den Lesekopf Aktuell...er könnte auch auf den Lesekopf->Kopf oder auf den Lesekopf->Ende stehen aber Aktuell soll hier nur bewegt werden.

Genauer gesagt soll dieser Wert nicht nur auf Aktuell zeigen sondern auf den Listeninhalt von Aktuell nämlich "next"
Also Zeigt das Listenfeld von akt (dem 1.Listenfeld) auf ein ein mögliches neues Feld wobei es wiederum auf einen einen Zeiger zeigt, der wiederum wieder auf ein Zeiger zeigt (next) um das nicht ins endliche auszulagern wird gleich danach dem dem Zeiger wieder das Listenfeld akt zugeordnet.

Delphi-Quellcode:

     
akt^.next:=Aktuell^.next;
Aktuell^.Next:=Akt;

Wenn also zwei mal auf dem Button geklickt wurde, müsste es meiner Meinung nach zwei Listenfelder geben,welche mit der variablen akt editiert werden können.Wenn man nun noch weitere mal auf den Butten 2 klickt müsste das Programm immer weitere Listeneinträge erzeugen, denn weil Kopf nicht mehr NIL ist springt das Programm gleich in die else anweisung. Da jedes Listenelement, das Zeigerelement

Delphi-Quellcode:

 akt^.next

kann diesem Element auch immer wieder der Wert

Delphi-Quellcode:

 Aktuell1.next

zugeordnet werden.

Mit den Prozeduren am Anfang habe ich die Ausgabe gemacht. Der Lesekopf besteht aus drei Teilen also habe ich drei Ausgaben erzeugt.

Delphi-Quellcode:

             akt^.next:=Aktuell^.next;
             Aktuell^.Next:=Akt;
             inc(akt^.position);

             p_Ausgabe_Kopf(Kopf^);
             p_Ausgabe_Aktuell(Aktuell^);
             p_Ausgabe_Ende(Ende^);

Das Programm funktoniert aber nicht so wie ich mir das gedacht habe. Denn irgendwie habe ich ein denkfehler. Ich habe zum Test in jedem Listenfeld eine ordinale Position eingefügt, welche sich bei jedem erzeugten Listenfeld incrementieren soll. Wenn man das Programm ausführt dann sieht mann, dass sich die Verkettung nicht im Lesekopf ->Aktuell fortsetzt sondern in allen drei. d.h ich bin mir jetzt gar nicht mehr so sicher ob jedes mal ein neues listenfeld erzeugt wird oder einfach nur die Position um 1 erhöht wird ( inc(akt^.position) ) Also eine pseudoverkettung die allein die Ausgabe vorgaukelt aber gar nicht existiert.

Ich will ja eigentlich erreichen, dass nachdem genau ein Listenfeld erzeugt wurde und die Zeigervariablen Kopf,Aktuell,Ende auf eins stehen (weil janur ein Feld vorhanden ist) beim erzeugen eines zusätlichen Listenfelds sich hinter Kopf ein neues Listenfeld einfügt und sich nur für Aktuell und Ende die Position incrementiert. Warum geht das eigentlich nicht. Ich habe doch schließlich den pfad aktuell für die verkettung benutzt und nicht Kopf.


Vielleicht hat ja jemand lust, mir bei meinen Problem zu helfen..ich stelle im folgenden nochmal den kompletten Quellcode rein

Delphi-Quellcode:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Button1: TButton;
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    Label4: TLabel;
    Label5: TLabel;
    Label6: TLabel;
    Button2: TButton;
    procedure Button2Click(Sender: TObject);
    procedure Button1Click(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;


                      TYPE t_Zeiger = ^t_inhalt;
                      t_inhalt = Record
                      inhalt   :string;
                      Next     :t_Zeiger;
                      Position :integer;
                      End;




var
  Form1: TForm1;

  Kopf          :t_Zeiger;
  Aktuell       :t_Zeiger;
  Ende          :t_Zeiger ;





implementation

{$R *.dfm}

procedure p_Ausgabe_Kopf (v_Kopf:t_inhalt);
begin
  with form1 do
  with v_Kopf    do
  begin
  label4.Caption:=IntToStr(position);
  end;
 end;


procedure p_Ausgabe_Aktuell (v_Aktuell:t_inhalt);
begin
  with form1 do
  with v_Aktuell    do
  begin
  label5.Caption:=IntToStr(position);
  end;
 end;


procedure p_Ausgabe_Ende (v_Ende:t_inhalt);
begin
  with form1 do
  with v_Ende    do
  begin
  label6.Caption:=IntToStr(position);
  end;
 end;










procedure TForm1.Button1Click(Sender: TObject);
begin

Kopf       :=NIL;
Aktuell    :=NIL;
Ende       :=NIL;

label4.Caption:='leer';
label5.Caption:='leer';
label6.Caption:='leer';

end;
procedure TForm1.Button2Click(Sender: TObject);

     var akt  :t_Zeiger;
         vor  :t_zeiger;
         pos  :t_zeiger;
           
begin
     
       New(akt);

       if (Kopf=NIL) then
           begin

           Kopf         :=akt;
           Aktuell      :=akt;
           Ende         :=akt;

           akt^.Next    :=NIL;
           akt^.inhalt  :='Das ist das erste Leisenelement';
           akt^.Position:=1;

           p_Ausgabe_Kopf(kopf^);
           p_Ausgabe_Aktuell(Aktuell^);
           p_Ausgabe_Ende(Ende^);


           end

         else   //--------------------------------------------------------------
             begin

             akt^.next:=Aktuell^.next;
             Aktuell^.Next:=Akt;
             inc(akt^.position);

             p_Ausgabe_Kopf(Kopf^);
             p_Ausgabe_Aktuell(Aktuell^);
             p_Ausgabe_Ende(Ende^);

             end;

             akt^.inhalt:='ein listen Element';
             akt^.Position:=2;

             if (aktuell=ende) then
                 begin
                 ende:=akt;
                 aktuell:=akt;
                 end;


            

        end;








end.

[DeddyH]

Ich möchte Dir zunächst die Videos zum 2. Stammtisch ans Herz legen, da ist auch eins zu Zeigern und verketteten Listen dabei. http://www.delphipraxis.net/videos#Stammtisch_2

Guten Rutsch

[dominikkv]

Du solltest deinen Quellcode mehr formatieren und dich auch dran halten, dann wird das debuggen leichter.
Außerdem ist es sinnvoll Zeiger mit einem P zu benennen (also P_Zeiger anstatt t_Zeiger).

So und nun genug Oberlehrerisch :warn:

Du rufst immer

Delphi-Quellcode:

  akt^.inhalt:='ein listen Element'; 
  akt^.Position:=2;

auf, egal ob schon ein Kopf da ist oder nicht.
Kann sein das das der Fehler ist.

Ich würde das so machen:

Delphi-Quellcode:

procedure TForm1.btnNeuClick(Sender: TObject); 
var 
  PNeu  : P_Zeiger;   
  PDummy: P_Zeiger;          
begin 
  New(PNeu); 
  
  if (Kopf = NIL) then 
    begin 
      PNeu^.Next     := NIL; 
      PNeu^.inhalt   := 'Das ist das erste Leisenelement'; 
      PNeu^.Position := 1; 

      Kopf    := PNeu; 
      Aktuell := PNeu; 
    end else begin 
      PNeu^.next     := Aktuell^.next; 
      PNeu^.inhalt   := 'ein listen Element'; 
      PNeu^.Position := Succ(Aktuell^.Position);
       
      Aktuell^.Next := PNeu; 
      
      PDummy := PNeu;
      while PDummy^.next <> nil do
        begin
          PDummy := PDummy^.next;
          Inc(PDummy^.Position);
        end;
    end;    
   
    if (PNeu^.next = nil) then
      Ende := PNeu; 
     
    p_Ausgabe_Kopf(kopf^); 
    p_Ausgabe_Aktuell(Aktuell^); 
    p_Ausgabe_Ende(Ende^); 
end;

[Ghostwalker]

Zum 1.

Warum speicherst du das Ende der Liste in einem extra Zeiger ? Reicht es nicht, wenn der arbeitszeiger auf NIL ist
?

Also..wenn ich das richtig verstehe, willst du bei Button2.click ein neues Element in deine Liste aufnehmen, oder ?

Wenn ja, hier mal ein Beispiel wie ich das machen würde:

Delphi-Quellcode:

procedure TForm1.Button2Click(Sender: TObject);          
begin
  if (Kopf=NIL) then
  begin
    new(Kopf);
    Aktuell := Kopf;
    Aktuell^.position := 1;
    Aktuell^.Inhalt := 'Kopf-Element der Liste';
  end
  else
  begin
    new(Aktuell^.next);
    Aktuell^.next^.position := aktuell^.position+1;
    Aktuell := Aktuell^.next;
    aktuell^.Inhalt := IntToStr(Aktuell^.position)+'. Element in der Liste'; 
  end;  
  p_Ausgabe_Kopf(Kopf^);
  p_Ausgabe_Aktuell(Aktuell^);
end;

Den Zeiger Ende kannst du dir sparen (zumindest was ich vom Quelltext her lese), da aktuell immer der letzte Zeiger in der Kette ist :)

Ich hoffe das hilft dir weiter :)

[DeddyH]

In einer einfach verketteten Liste macht es IMHO keinen Sinn, sich außer dem Anfangselement noch weitere merken zu wollen. Im Normalfall geht man sowieso alle Elemente per Schleife durch.

[dominikkv]

Zitat:

Zitat von Ghostwalker

Den Zeiger Ende kannst du dir sparen (zumindest was ich vom Quelltext her lese), da aktuell immer der letzte Zeiger in der Kette ist :)

So wie ich das verstanden hab kann man den Zeiger Aktuell in der Liste verschieben und der neue Eintrag soll nach dem Aktuellen eingefügt werden, dh nicht immer am Ende!
Allerdings gebe ich dir recht das man sich den Zeiger auf das Ende sparen kann da man das auch ganz leicht mit einer while-Schleife lösen kann:

Delphi-Quellcode:

while Aktuell^.next <> nil do
  Aktuell := Aktuell^.next;

Erst bei doppelt verketteten listen macht das vllt Sinn, da man sich dann auch von hinten durch die Liste hangeln kann (wers braucht^^)

[grenzgaenger]

Zitat:

Zitat von Ghostwalker

Zum 1.

Warum speicherst du das Ende der Liste in einem extra Zeiger ? Reicht es nicht, wenn der arbeitszeiger auf NIL ist
?

ist zwar nicht mein thema. aber das bei 'ner einfach verketten liste, speichert man das ende in 'n eigenen node, um die liste rückwärts abarbeiten zu können. aber ich bin nicht der author davon...

[grenzgaenger]

Delphi-Quellcode:

program ListTest;

{$APPTYPE CONSOLE}

uses
  SysUtils;

type
 pNode = ^tNode;
 tNode = record
  data: integer;
  next: pNode;
 end;

var
 FirstNode: pNode;
 AktNode  : pNode; 

 
function Traverse(p: pNode): pNode;
begin
 Result := p.next;
end; 
procedure KillList;
var
 temp: pNode;
begin
 temp    := FirstNode;
 AktNode := FirstNode;
 While Temp <> NIL do
 begin
  AktNode := Traverse(AktNode);
  dispose(Temp);
  temp    := AktNode;
 end;
end; 
function AddNode(p: pNode): pNode;
begin
 if FirstNode = NIL then
 begin
  FirstNode := p;
 end
 else
 begin
  p.next := FirstNode;
  FirstNode := p;
 end;
 AktNode := p;
 result  :=  AktNode;
end;

var 
 i: integer;  
 t: pNode;
begin
 FirstNode := NIL;
 AktNode   := NIL;
 writeln('AddNodes ...');
 for i := 0 to 3 do
 begin
  New(t);
  t.next  := NIL;
  t.data  := i; //Daten  zuweisen
  AktNode := AddNode(t);
  Writeln('Node mit Data: ', AktNode.data);
 end;
 writeln;

 writeln('TraversNodes...');
 AktNode := FirstNode;
 while AktNode <> NIL do
 begin
  Writeln('Node mit Data: ', AktNode.data);
  AktNode := Traverse(Aktnode); //Geht zum nächsten Knoten
 end;
 
 KillList; //Löscht die Verkettete Liste
 readln;
end.

hier mal 'n kleines demo progy <HTH>

[Ghostwalker]

Rückwärts die Liste durchlaufen geht nicht mit einer einfach verketten Liste, da dir die Vorgänger fehlen ;)

Somit ist das speichern des Endes bei einer einfach verketten Liste nonsens :)

[grenzgaenger]

Zitat:

Zitat von Ghostwalker

Rückwärts die Liste durchlaufen geht nicht mit einer einfach verketten Liste, da dir die Vorgänger fehlen ;)

Somit ist das speichern des Endes bei einer einfach verketten Liste nonsens :)

:angel2: gut hast recht. hatte ich mit der doppelt verketteten liste verwechselt. noch 'n gutes neues :coder2:

[malibu85]

Ein frohes neues Jahr wünsche ich euch,
ich habe mir erstaml das Videotutorial angeschaut welches mir wirklich eine Erleuchtung war. Sehr angenehm auf dieser Internetseite. Ich muss ganz ehrlich zugeben wenn man für so eine Hilfe geld zahlen müßte...ich würde es tun...großes lob auch an euch.

Ich habe die stelle an dem es um einfach verkettete Listen geht nach programmiert und glaube es auch soweit richtig zu haben. Im Prinzip läuft das Programm auch aber ich bekomme eine Fehlermeldung, welche ich erst ignorieren muss. Und zwar habe ich eine Zugriffsverletzung verursacht bei der Adresse 0453....

ich vermute das könnte vielleicht an den Hilfszeiger liegen (wrk bzw be mir work)
im ersten abschnitt erzeugen wir ein root. D.h. ein leeres Listenelement, welches als Markierer eigesetzt wird. Das Zeigerelement NEXT soll ja auf den Nachfolger zeigen aber bei root zeigt dieser ins NIL. Ist ja soweit okay. Danach fangen wir mit dem ersten Listenelement an und bezeichnen es als work- Work enthält den gleichen Inhalt wie root nur, dass work auch ein Nachfolger hat. Dann geht es los...mit der for-schleife werden die Nachfolger erzeugt. Alles soweit okay aber in der Ausgabe der Liste. definieren wir wieder einen Hilfszeiger der ach work heißt. Dieser bekommt die gleichen einstellungen wie der Markierer "root". root ist aber so zu sagen kein wirkliches Listenelement weil es keinen achfolger hat. Work ist ja das erste Listenelement. Bei der Ausgabe setzen wir work auf den Markierer. also ist worrk:=root; dann folgt eine schleife

Delphi-Quellcode:

while (work^.next<>NIL) do
begin
      Memo1.Lines.append(work^.inhalt);
      memo1.Lines.append(IntToStr(work^.Nummer));
      work:=work^.next;
end

Das verstehe ich nicht..wenn work =
root ist und root keinen Nachfolger hat wie soll man dann überhaupt auf de Pfad work^.inhalt kommen? denn work ist zwar mit root verknüpft am Anfang aber root ncht mit work. Okay das verstehe ich nicht so ganz. Sicher wird das auch nicht der Grund der Fehlermeldung sein aber kann es bei der Zugriffsverletung an den Hilfszeiger liegen?

hier noch mal der komplette Quellcode

Delphi-Quellcode:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Edit1: TEdit;
    Button1: TButton;
    Button2: TButton;
    Button3: TButton;
    Button4: TButton;
    Memo1: TMemo;
    procedure Button2Click(Sender: TObject);


    procedure Button1Click(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

                           TYPE T_Zeiger = ^Liste;
                           Liste = Record
                           inhalt   :string;
                           Nummer   :integer;
                           next     :T_Zeiger;
                           end;

var
  Form1: TForm1;

  root        :T_Zeiger;
  Aktuell     :T_Zeiger;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

  var
  work :T_Zeiger;
  I    :Integer;
begin

  NEW(root);//-------------------------Erstes Listenelement erstellen root (Kopf)

      root^.next:=NIL;//---------------du hast keinen Nachfolger
      root^.inhalt:='Root-Element';//--root-Element enthält keine Daten
      root^.Nummer:=0;//---------------Nummer ist 0 da es nicht direkt zur Kette gehört sondern nur den Anfang markiert

      work:=root;//--------------------sagt nichts weiter aus, als das ein weiteres Element, die gleichen Inhalte trägt wie root..noch ist dieses Element nicht in der Liste


      for i:=1 to 10 do
      begin
      New(work^.next);//------------------------------ein neuer Speicherplatz für das neue Element wird erzeugt ..dem Nachfolger von ROOT
      work:=work^.Next;//-----------------------------auf das neu angelegte Element wechseln
      work^.inhalt:='Listenelement'+ IntToStr(i);//---Das Neue Element bekommt ein Inhalt
      work^.nummer:=i;//------------------------------Jedes Element erhält eine Nummer
      end;



end;






procedure TForm1.Button2Click(Sender: TObject);

var work:T_Zeiger;//------------------------------Hilfszeiger

begin

work:=root; //-----------------------------------------Hilfszeiger wird an den Anfang der Kette gesetzt

      while (work^.next<>NIL) do //--------------------Man hangelt sich so lange durch bis der Nachfolger NIL ist
      begin
      Memo1.Lines.append(work^.inhalt);
      memo1.Lines.append(IntToStr(work^.Nummer));
      work:=work^.next;

      end;

end;

end.

[grenzgaenger]

sag mal, hast du dir mein beispiel angesehen? #8 das funktioniert und zeigt die verwendung einer verketteten liste. anlage, traverse und auflösung. das kannst prima als vorlage hernehmen um deine datenstruktur zu erweitern... aber die grundfunktionen bleiben das selbe.

vergleich mal dieses beispiel:

Delphi-Quellcode:

while AktNode <> NIL do
begin
  Writeln('Node mit Data: ', AktNode.data);
  AktNode := Traverse(Aktnode); //Geht zum nächsten Knoten
end;

mit deinem code...

Zitat:

Zitat von malibu85

Delphi-Quellcode:

while (work^.next<>NIL) do
begin
      Memo1.Lines.append(work^.inhalt);
      memo1.Lines.append(IntToStr(work^.Nummer));
      work:=work^.next;
end

fällt dir da bspw. was auf? du travesierst die liste nur unzureichend... hier hätte deine while schleife so auszusiehen ...

Delphi-Quellcode:

while work <> NIL do ...

noch viel erfolg.

[malibu85]

Dein Beispiel ist echt gut. Vor allem hat man dank den funktionen einen besseren Überblick. Sollte ich wieder Listen in einem Projekt einbinden müssen dann werde ich diese Vorlage verwenden. Ich hab boß immer so ne macke, dass es mir irgendwann gar nicht mehr darauf ankommt ne Liste zu programmieren sondern nur noch den Fehler zu finden, warum ein bestimmtes Projekt nicht funktioniert. Den Fehler von Oben also vom Videotutorial habe ich auch gefunden und zwar, wenn ich ein Listenelement mit daten fülle, dann muss für dieses Listenelement der "work^.next"-Zeiger wieder auf NIL gesetzt werden denn wenn ein neues Element eingefügt wird dann sucht sich das Programm diesen Zeiger und reserviert den Speicherplatz und wenn dort schon was drin steht gibts probleme. Wobei das kein Fehler vom Videotutorial war sondern von mir.

[DeddyH]

Mal eine dumme Frage: wieso muss es eigentlich eine verkettete Liste sein, wo man doch auch eine TList verwenden könnte?

[malibu85]

ja das ist so eie sache. wenn in der Klausur eine Aufgabe bekomme, programmieren sie eine verkettete Liste, dann macht sich das nicht so gut, wenn ich schreibe, ich nehme einfach TList :-D

[DeddyH]

Achso, dann will ich nichts gesagt haben :lol:

[DGL-luke]

und vor allem ist TList eine ArrayList. Würde also als Lösung zur Aufgabe nichtmal stimmen.

[mimi]

Bei einer Verketteten Liste dürften auch die Einfüge und Lösch Proceduren schneller sein, als bei einem Array.