Linked Listen

Für Fragen von Einsteigern und Programmieranfängern...
Antworten
Ich_bin_dabei
Beiträge: 8
Registriert: Fr 27. Mär 2015, 10:34

Linked Listen

Beitrag von Ich_bin_dabei »

Hallo Leute!

Das Thema sagt es ja schon, ich würde gerne wissen wie ich Linked Listen in Pascal umsetze.
Dummerweise haben die in Pascal scheinbar auch noch einen anderen Namen. :oops:

Bin jetzt wirklich schon länger am googeln, aber irgendwie finde ich da nix vernünftiges (oder Brett vorm Kopf).

Bin natürlich schon auf "records" und die "Listenklassen" gestoßen, aber alle Tutorials die da gefunden habe waren mehr oder weniger recht knapp.

Hier mal ein kurzes Beispiel in meiner bisherigen Sprache, damit Ihr in etwa wisst was ich meine.

Code: Alles auswählen

;
;
; PureBasic Code
;
;
; .s bedeutet "String"
;
;
 
Structure Person    ;Struktur anlegen
  Name.s
  Vorname.s
EndStructure
 
 
NewList Personen.Person()   ;Linked List anlegen
 
 
AddElement (Personen())   ; Daten in Liste schreiben
Personen()\Name = "Mustermann"
Personen()\Vorname = "Hans"
Ehrlich, daran kanns doch nicht scheitern :!: :?:

Grüße, Michael :)

Mathias
Beiträge: 6906
Registriert: Do 2. Jan 2014, 17:21
OS, Lazarus, FPC: Linux (die neusten Trunk)
CPU-Target: 64Bit
Wohnort: Schweiz

Re: Linked Listen

Beitrag von Mathias »

Mit Records geht es,

Code: Alles auswählen

var
  Person: record
    Name: string;
    Vorname: string;
  end;
 
begin
  Person.Name := 'Mustermann';
  Person.Vorname := 'Hans';
end.                  
Mit Lazarus sehe ich grün
Mit Java und C/C++ sehe ich rot

Benutzeravatar
theo
Beiträge: 10867
Registriert: Mo 11. Sep 2006, 19:01

Re: Linked Listen

Beitrag von theo »

Es gibt schon Linked Lists in Pascal. Aber man verwendet die eher in spezielleren Fällen.
Bist du sicher, dass du Linked Lists brauchst, oder tut's ein dynamisches Array oder eine TList auch?

Ich_bin_dabei
Beiträge: 8
Registriert: Fr 27. Mär 2015, 10:34

Re: Linked Listen

Beitrag von Ich_bin_dabei »

Hallo theo:
Bist du sicher, dass du Linked Lists brauchst
Das ist jetzt ne Frage. :oops: Anders gesagt, in PB gibt es da nicht so viele Alternativen wie in Pascal. An diese größeren Auswahlmöglichkeiten muß ich mich erstmal gewöhnen. :oops:
oder tut's ein dynamisches Array
Ehrlich gesagt habe ich mit Arrays ewig nichts mehr gemacht. Sind nicht sonderlich dynamisch in PB.
oder eine TList auch?
TList ist ja wenn ich das richtig verstanden habe oop, und das bin ich grade erst am lernen. Bzw. verstanden habe ich das, aber um das auch richtig anzuwenden fehlt mir noch die Routine.

Größtenteils erstelle ich GUI-Dantenbankfrontends mit nen bisschen Fakturierung, also nichts sehr komplizertes. Ok, Artikelimport usw. kommt natürlich auch noch mit dazu. Da ich generell nie direkt in die DB schreibe, habe ich die Daten halt immer zunächst in Linked Listen gespeichert, zwecks prüfen usw.

Hallo Mathias:
Dein Code hat mir schon sehr geholfen, ist sogar noch einfacher als mein PB-Beispiel. :D Danke!

Da Pascal da ja wirklich was zu bieten hat, habe ich den einfach mal erweitert.

Code: Alles auswählen

program Project1;
uses
crt;
var
  Person: record
    Name: string [30];
    Vorname: string [30];
    Telefonnummern: Array [1..2] of string [20];
  end;
 
begin
  Person.Name := 'Mustermann';
  Person.Vorname := 'Hans';
  Person.Telefonnummern [1] := '02642/1111111';
  Person.Telefonnummern [2] := '02642/2222222';
 
  WriteLn(Person.Name);
  WriteLn(person.Vorname);
  WriteLn(Person.Telefonnummern[1]);
  WriteLn(Person.Telefonnummern[2]);
  ReadKey;
Erstmal Danke, es kommen aber sicher noch mehr Fragen dazu. :)

Grüße, Michael

ruewa
Beiträge: 153
Registriert: Sa 12. Apr 2014, 14:43

Re: Linked Listen

Beitrag von ruewa »

Ich_bin_dabei hat geschrieben:

Code: Alles auswählen

var
  Person: record
    Name: string [30];
    Vorname: string [30];
    Telefonnummern: Array [1..2] of string [20];
  end;
 
Hallo Michael!
 
Grundsätzlich geht das zwar so, bloß kommst Du damit noch nicht allzu weit. Denn jetzt hast Du zwar eine Person erfaßt, aber Sinn und Zweck z.B. eines Adressbuches ist ja, mehrere Einträge zu verwalten und (das wäre dann der nächste Schritte) weitere nach Belieben hinzufügen zu können. Von "verketteten Listen" bist Du immer noch weit entfernt - aber die würde ich an Deiner Stelle im Moment sowieso mal für eine Weile zurückstellen.
 
Erstmal wäre es jetzt wichtig, Dir den Unterschied zwischen Variablen- und Typdeklaration klarzumachen. Denn für Deinen nächsten Eintrag "Person2" müßtest Du den ganzen Record nochmal neu tippen, wenn Du auch den als Variable deklarieren wolltest. Einfacher wäre es, diesen Record als Typ zu erstellen, und Deine Variablen dann darauf zu beziehen:
 

Code: Alles auswählen

type
  TPerson: record
    Name: string [30];
    Vorname: string [30];
    Telefonnummern: Array [1..2] of string [20];
  end;
 
var
  Person_1,
  Person_2 : TPerson;
 
...
 
begin
  Person_1.Name := 'Mustermann';
  Person_1.Vorname := 'Max';
  Person_2.Name := 'Rampensau';
  Person_2.Vorname := 'Moritz';
  ...
end;
Warum das "T" vorne bei "TPerson"? Das kannst Du auch weglassen, es ist nur eine ganz sinnvolle Konvention, um schon in der Namensgebung anzudeuten, daß es sich hierbei um einen Typ handelt. Wichtig ist aber vor allem, daß Du den Umgang mit Typen und Variablen lernst und verstehst, wieso diese Unterscheidung ganz nützlich ist.
 
Der nächste Schritt wäre dann, herauszufinden, wie Du mehrere Personen erfassen kann, ohne jedesmal eine neue Variable "Person_n" deklarieren zu müssen. Du hast die Telefonnummern ja schon als statischen String-Array definiert. Genauso gut könntest Du nun Deine Personen-Einträge als Array definieren:
 

Code: Alles auswählen

var
  Personen : Array[1..20] of TPerson;
...
begin
  Personen[5].Telefonnummern[9] := '1234567';
end;
Der nächste Schritt wäre, statische Arrays durch dynamische zu ersetzen. Und noch einen Schritt weiter könntest Du Dich dann an eine TList wagen, was gar kein so schlechter Einstieg in das Thema "Objekte" wäre.

Oder Du kannst auch mal den Versuch unternehmen, eine verkettete Liste selbst zu programmieren. Dazu braucht es ja nicht viel: Wenn Du Deiner Record-Deklaration noch ein Feld "NaechstePerson : {Zeiger auf Record:} ^TPerson" hinzufügen würdest, hättest Du schon eine einfach verkettete Liste. Noch ein Feld namens "VorigePerson", und Deine Liste wäre schon doppelt verkettet - okay: Verwalten mußt Du das Ganze dann natürlich auch noch, also die entsprechenden Einträge setzen bzw. aktualisieren. Aber so richtig nützlich ist das Ganze nicht wirklich, denn Du müßtest Dich dann jedemal zu einem bestimmten Eintrag durchhangeln, während Du bei Arrays oder Listen viel einfacher per Index auf jeden einzelnen Eintrag zugreifen kannst. Das wäre also eine ganz nette Übung, mehr aber auch nicht.

Wie kannst Du Dir diese Dinge nun am effizientesten erschließen? Wichtig ist zunächst mal, daß Du Dich mit dem Hilfesystem von Lazarus vertraut machst. Das ist nicht wirklich anfängertauglich, aber Du brauchst es ständig im Hintergrund - das wird später immer wichtiger werden. Ansonsten ist das ständige Googeln auch nicht das beste Mittel: Versuch mal, eine lesbare Einführung in die Sprache Pascal aufzutreiben und arbeite die (systematisch oder auch querbeet, je nach persönlichen Vorlieben) durch . Das an einem Beispiel-Adressbuch durchzuspielen, machst Du schon ganz richtig!

Gruß Rüdiger
Zuletzt geändert von ruewa am Mo 30. Mär 2015, 10:22, insgesamt 1-mal geändert.

mschnell
Beiträge: 3444
Registriert: Mo 11. Sep 2006, 10:24
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ)
CPU-Target: X32 / X64 / ARMv5
Wohnort: Krefeld

Re: Linked Listen

Beitrag von mschnell »

Bei einer Linked List muss der Link (Zeiger auf den nächsten) als Element im Record stehen:

Code: Alles auswählen

type
  TPerson = record
    Link: ^TPerson;
    Name: string [30];
    Vorname: string [30];
    Telefonnummern: Array [1..2] of string [20];
  end;    

-Michael

ruewa
Beiträge: 153
Registriert: Sa 12. Apr 2014, 14:43

Re: Linked Listen

Beitrag von ruewa »

mschnell hat geschrieben:Bei einer Linked List muss der Link (Zeiger auf den nächsten) als Element im Record stehen:

Code: Alles auswählen

type
  TPerson = record
    Link: ^TPerson;
...
Oh, Entschuldigung! Natürlich, Michael hat recht, in dem Fall mußt Du Dich dann auch noch in den Umgang mit Zeigern reinfummeln (ich war gedanklich schlampigerweise bei Objekten).

Aber wie gesagt, das Thema "verkettete Listen" solltest Du jetzt erstmal als Übung für später betrachten und im Moment beiseitelegen.

Gruß Rüdiger

Benutzeravatar
theo
Beiträge: 10867
Registriert: Mo 11. Sep 2006, 19:01

Re: Linked Listen

Beitrag von theo »

@Ich_bin_dabei: Ich glaube für dich wäre es im Moment das Beste, mal ein paar Einführungen zu lesen.
Ich hatte dir hier schon mal Links gepostet: http://www.lazarusforum.de/viewtopic.php?p=76506#p76506

Ich glaube das wäre besser geeignet um einen Überblick zu gewinnen, als einzelne Fragen im Forum zu stellen, welche dann doch irgendwie isoliert da stehen.

Ich_bin_dabei
Beiträge: 8
Registriert: Fr 27. Mär 2015, 10:34

Re: Linked Listen

Beitrag von Ich_bin_dabei »

Hallo Rüdiger,
vielen Dank für Deine wirklich sehr ausführliche Antwort. Auf jeden Fall einige sehr schöne Vorschläge.
Habe mich da für den Anfang mal für die dynamischen Arrays entschieden.

Bearbeiten der dyn. Array ist ja in kombination mit SetLength, Length und High sogar recht einfach.
Probleme habe ich damit, der dyn. Array z.B. "Personen" den Type "Person" anzuhängen.

Beispiel:
Das hier klappt, ist aber nicht das was ich möchte: Personen: array of string;
Wäre natürlich zu einfach gewesen hätte das funktioniert: Personen: array of TPerson; :cry:

Damit der Theo mir jetzt nicht ein drittes mal seine Link-Liste postet:
http://de.wikibooks.org/wiki/Programmie ... erzeichnis
@theo: Habe mir dort Arrays und Records angeschaut, leider aber keine Kombination beider gefunden.

Grüße

Benutzeravatar
theo
Beiträge: 10867
Registriert: Mo 11. Sep 2006, 19:01

Re: Linked Listen

Beitrag von theo »

Ich_bin_dabei hat geschrieben: Damit der Theo mir jetzt nicht ein drittes mal seine Link-Liste postet:
http://de.wikibooks.org/wiki/Programmie ... erzeichnis
@theo: Habe mir dort Arrays und Records angeschaut, leider aber keine Kombination beider gefunden.
Wieso nicht? Alles wesentliche steht doch da: http://de.wikibooks.org/wiki/Programmie ... s#Beispiel

Code: Alles auswählen

 TGast = record
    Name, Vorname: string; 
   ...
  end;
 
  TGastListe = array of TGast;
 ...
SetLength(GastListe, 4);
 
GastListe[0].Name := 'Schweiss';
GastListe[0].Vorname := 'Axel';
Ich meinte das mit der Lektüre in einem größeren Rahmen. Einfach mal die Grundlagen aneignen.
Ich gehe auch nicht in ein Mathe Forum und sage: "Ich weiss zwar was eins mal eins gibt, finde aber keine Infos darüber was eins mal zwei gibt."

Records und Array sind nun mal das kleine Einmaleins der Pascal Programmierung und deshalb Grundlagen, die man nicht mühsam (für alle) in einem Forum erarbeiten sollte.
Verstehst du?

Vielleicht in aller Ruhe mal das einwirken lassen: http://www.marcocantu.com/epascal/German/default.htm

Ich_bin_dabei
Beiträge: 8
Registriert: Fr 27. Mär 2015, 10:34

Re: Linked Listen

Beitrag von Ich_bin_dabei »

Hi theo,
hast schon recht! :)
Hätte mal nen bisschen genauer lesen solle (nicht überfliegen) :oops:

Ist angekommen! Grüße, Michael

ruewa
Beiträge: 153
Registriert: Sa 12. Apr 2014, 14:43

Re: Linked Listen

Beitrag von ruewa »

Ich_bin_dabei hat geschrieben:Das hier klappt, ist aber nicht das was ich möchte: Personen: array of string;
Wäre natürlich zu einfach gewesen hätte das funktioniert: Personen: array of TPerson; :cry:
Hallo Michael,

doch, klar funktioniert das. Ich nehme mal an, Du meinst mit "es klappt nicht", es ließ sich nicht kompilieren? Das kann ein ganz banaler Tippfehler sein. Du erstellst das doch in der Lazarus IDE. Wenn du kompilierst, gibt es ein Nachrichtenfenster, das Dir den Grund anzeigt, weshalb der Kompiler an der und der Zeile abbricht. Diese Nachricht ist höchst informativ, Du must sie halt lesen - okay und manchmal auch "übersetzen". Z.B. wenn Du einen Tippfehler beim Variablennamen gemacht hast, wird der Kompiler sagen, daß er diesen Bezeichner Soundso nicht kennt. Mach Dir nichts draus, das sind Widrigkeiten, durch die jeder durch muß, das geht aber auch flott voran.

Die andere Sache ist, da hat Theo schon recht: Zuerst müssen die Basics sitzen. Wenn Du Dir zu schnell die anspruchsvolleren Dinge vornimmst, wirst Du immer wieder von einem scheinbar unerklärlichen "es klappt nicht!" ausgebremst werden - mit geringen Chancen, Dir die Erklärung von Fehlern selbst zu erarbeiten. Z.B. sind dynamische Listen schon nicht ganz ohne, wenn Du noch keine rechte Vorstellung davon hast, wie das Zeug intern arbeitet (Stichwort Pointer). SetLength() ist dabei nicht das Problem, aber etwa "Person_1 := Person_2;" kann ganz schnell zum Höllenritt werden, solange Dir nicht klar ist, daß das intern anders organisiert ist als z.B. ein simples "i := 5;". Ist auch kein Hexenwerk, aber ohne die Grundlagen kannst Du an solchen Dingen ziemlich auflaufen. Also besser ein Schritt nach dem anderen!

Gruß Rüdiger

mschnell
Beiträge: 3444
Registriert: Mo 11. Sep 2006, 10:24
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ)
CPU-Target: X32 / X64 / ARMv5
Wohnort: Krefeld

Re: Linked Listen

Beitrag von mschnell »

ruewa hat geschrieben:(ich war gedanklich schlampigerweise bei Objekten).
Auch bei Objekten sind verkettete Listen möglich und absolut sinnvoll. Ungetestetes Beispiel selbst organisierende doppelt verkette Liste siehe unten.

Man könne in das Beispiel leicht Such und Sortier-Funktionen einbauen und es zu einem Binär-Baum und ähnlichen Konstrukten erweitern.

-Michael

Code: Alles auswählen

Type
 
  { TPerson }
 
  TPerson = class
    Next: TPerson;
    Prev: TPerson;
    Name: string [30];
    Vorname: string [30];
    Telefonnummern: Array [1..2] of string [20];
    Constructor Create(P, N: TPerson);
    Destructor Destroy; Override;
    procedure NewPerson;
  end;
 
{ TPerson }
 
constructor TPerson.Create(P, N: TPerson);
begin
  inherited Create;
  Next := N;
  Prev := P;
end;
 
destructor TPerson.Destroy;
begin
  if assigned(Next) then begin
    Next.Prev := Prev;
  end;
  if assigned(Prev) then begin
    Prev.Next := Next;
  end;
  inherited;
end;
 
procedure TPerson.NewPerson;
// hinter dieser Stelle der Kette einen neuen einfuegen
begin
  Next := TPerson.Create(Self, Next);
end;
 

wp_xyz
Beiträge: 5134
Registriert: Fr 8. Apr 2011, 09:01

Re: Linked Listen

Beitrag von wp_xyz »

constructor TPerson.Create(P, N: TPerson);
begin
inherited Create;
Next := N;
Prev := P;
end;
Ich denke, da fehlt noch, dass die gerade erzeugte Instanz bei P als Next und bei N als Prev eingetragen werden muss, sonst ist die Kette unterbrochen:

Code: Alles auswählen

 
constructor TPerson.Create(P, N: TPerson);
begin
  inherited Create;
  Next := N;
  Prev := P;
  P.Next := Self;
  N.Prev := Self;
end;

mschnell
Beiträge: 3444
Registriert: Mo 11. Sep 2006, 10:24
OS, Lazarus, FPC: svn (Window32, Linux x64, Linux ARM (QNAP) (cross+nativ)
CPU-Target: X32 / X64 / ARMv5
Wohnort: Krefeld

Re: Linked Listen

Beitrag von mschnell »

Hat was. Könnte man durchaus so implementieren. Reine Defintionssache :D

Dann müsste man P und N aber natürlich auf "assigned" abfragen.

-Michael

Antworten