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: