Eigene LinkedLists

Hier kannst du häufig gestellte Fragen/Antworten und Tutorials lesen und schreiben.
Benutzeravatar
Josef Sniatecki
Beiträge: 657
Registriert: 02.06.2008 21:29
Kontaktdaten:

Eigene LinkedLists

Beitrag von Josef Sniatecki »

Seit einiger Zeit häufen sich geradezu die Threads mit dem Titel "LinkedList in LinkedList?". Daher habe ich mal wieder meine Schreib-Tutorial-Laune bekommen :mrgreen::
PDF-Download (75 KB)

Korrekturen, Kommentare und Fragen bitte posten.
Gruß Josef
PB 4.61 | Windows Vista - 32Bit
Homepage

"Wahrlich es ist nicht das Wissen, sondern das Lernen, nicht das Besitzen sondern das Erwerben, nicht das Dasein, sondern das Hinkommen, was den grössten Genuss gewährt." - Carl Friedrich Gauß
Benutzeravatar
STARGÅTE
Kommando SG1
Beiträge: 6996
Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Kontaktdaten:

Re: Eigene LinkedLists

Beitrag von STARGÅTE »

naja, für n LinkedList fehlen aber noch n ganze menge wichtiger Proceduren ...

Klar wäre nach deinem PDF n Linkedlist funktionsfähig, aber viel machen kann man damit nicht.

Beim Einfügen von Elementen, müssen mehr Situationen abgefragt werden.
Jenachdem ob man nach oder vor einem aktuellen Element einfügen will, und wo sich dann das neue element befindet.

Beim Löschen tritt das dann noch mal auf, wohin wird gesprungen usw.

Was vielleicht ein schritt tiefer ginge wäre n TUT für Bäume ... die kann man ja dann auch nur als Liste missbrauchen oder wirklich als Baum ... in dem man sich bewegen kann, Äste raushemen kann und in andere Baume einfügen kann ...
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
Benutzeravatar
Josef Sniatecki
Beiträge: 657
Registriert: 02.06.2008 21:29
Kontaktdaten:

Re: Eigene LinkedLists

Beitrag von Josef Sniatecki »

tut hat geschrieben:Durch die Funktionen die wir uns vorher definiert haben, besitzen wir schon genug Kenntnisse, um Befehle für das Löschen einer gesamten Liste zu programmieren. Genauso können wir uns auch Befehle programmieren, die Elemente an jede beliebige Stelle hinzufügen. Auch das gezielte Löschen von einzelnen Elementen ist leicht zu realisieren, wenn man sich die Verwaltung der Verweise genauer überdenkt. Und wenn man noch viel mehr machen möchte, so kann man sich z.B. eine Sortierfunktion definieren, die nach dem „Bubblesort“-Algorithmus arbeiten.

Auch wenn es sehr vom Vorteil ist, selbst eine solche Befehlssammlung zu erweitern, stelle ich auch meine Sammlung zu dynamisch verketteten Listen zur Verfügung:
http://sourceforge.net/projects/pb-stl/
Die Quelldatei trägt den Namen „Queue.pbi“.
Klar hast recht Stargate. Das Einfügen und Löschen von Elementen an jeder beliebigen Stelle ist natürlich sehr wichtig, nur da hat meine Schreib-Tutorial-Laune irgendwie aufgehört :D. Trotzdem habe ich einfach mal darauf hingewiesen, was man alles noch machen kann und habe zudem noch meinen vollständigen Quellcode mit angegeben.

Ein Tutorial für Trees wäre natürlich auch sehr vom Nutzen... aber wie gesagt, da fehlt mir ein wenig die Zeit und Laune dafür. Ich wollte einfach nur mal Grundsätzlich erklären, wie so eine Liste funktioniert und dies an einem kleinen, lauffähigen Code-Beispiel zeigen. :wink:
PB 4.61 | Windows Vista - 32Bit
Homepage

"Wahrlich es ist nicht das Wissen, sondern das Lernen, nicht das Besitzen sondern das Erwerben, nicht das Dasein, sondern das Hinkommen, was den grössten Genuss gewährt." - Carl Friedrich Gauß
Benutzeravatar
STARGÅTE
Kommando SG1
Beiträge: 6996
Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Kontaktdaten:

Re: Eigene LinkedLists

Beitrag von STARGÅTE »

Jo klar, aber du solltest wenigstens noch ein paar Hinweise zum richtigen Löschen der erstellten Speicher geben:
LinkedList-Header, LinkedList-Elemente, Strings in Elementen, ...

Vernachlässigt man solche Sachen, weil man sich denkt, die paar Bytes schaden schon nicht, und baut solch eine eigene LinkedList wirklich in ein Spiel / Anwendung, dann bekommt man schnell probleme.

Gerade dann wenn man viel mit AllocateMemory() arbeitet, deren RückgabeWert man nicht explizit speichert, sonden nur in anderen Elementen sichert, hat man selber keine direkte kontorlle mehr, wie viele Speicher wirklich erstellt wurden.

wenn dann ein ClearList() nicht richtig funktioniert, hat man schnell n menge String- und Element-Leichen im RAM ...

Da es ja hier um ein Tut geht, sollten solche in manchen augen offensichtlichen Sachen auch mit rein!
Und zwar so früh wie möglich, eh uns morgen einer im Anfänger Forum fragt wieso sein Programm abstürzt wenn er dein TUT umgesetzt hat ...


Auch sollte sowas im Tut verbessert werden:

Code: Alles auswählen

Procedure.i NewInteger(Number.i)
Protected *Memory.Integer
  *Memory = AllocateMemory(SizeOf(Integer))
  *Memory\I = Number
  ProcedureReturn *Memory
EndProcedure
zu

Code: Alles auswählen

Procedure.i NewInteger(Number.i)
  Protected *Memory.Integer
  *Memory = AllocateMemory(SizeOf(Integer))
  If *Memory
    *Memory\I = Number
  EndIf
ProcedureReturn *Memory
EndProcedure
denn man sollte nur dann in einen Speicher schreiben wenn er auch wirklich erstellt wurde.
Auch wenn viele sagen werden, wann tritt der fall schon ein das AllocateMemory fehlschlegt!
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
Benutzeravatar
ts-soft
Beiträge: 22292
Registriert: 08.09.2004 00:57
Computerausstattung: Mainboard: MSI 970A-G43
CPU: AMD FX-6300 Six-Core Processor
GraKa: GeForce GTX 750 Ti, 2 GB
Memory: 16 GB DDR3-1600 - Dual Channel
Wohnort: Berlin

Re: Eigene LinkedLists

Beitrag von ts-soft »

STARGÅTE hat geschrieben:wann tritt der fall schon ein das AllocateMemory fehlschlegt!
Laut Murphys Gesetz immer dann, wenn Du Sicher bist, es kann nicht fehlschlagen :mrgreen:

Deswegen ist diese If auch wichtig!
Benutzeravatar
Josef Sniatecki
Beiträge: 657
Registriert: 02.06.2008 21:29
Kontaktdaten:

Re: Eigene LinkedLists

Beitrag von Josef Sniatecki »

@ts-soft: :mrgreen:

@Stargate:
Danke für deine Kritik. Habe mir beim schreiben keine Gedanken über mögliche Speicherlecks gemacht, die bei Anfängern mit Lists entstehen können.

OK, wie man so gerne sagt: Aus Fehlern lernt man. :) Also dann, noch einen schönen Tag. Werd mal immer wieder ein bisschen was verbessern und erweitern. Vielleicht versuch ich das ganze dann sogar mit LyX zu schreiben. :wink:

Ich werde mich dazu dann mal wieder melden, sobald ich fertig bin.

Gruß Josef
PB 4.61 | Windows Vista - 32Bit
Homepage

"Wahrlich es ist nicht das Wissen, sondern das Lernen, nicht das Besitzen sondern das Erwerben, nicht das Dasein, sondern das Hinkommen, was den grössten Genuss gewährt." - Carl Friedrich Gauß
DarkDragon
Beiträge: 6267
Registriert: 29.08.2004 08:37
Computerausstattung: Hoffentlich bald keine mehr
Kontaktdaten:

Re: Eigene LinkedLists

Beitrag von DarkDragon »

STARGÅTE hat geschrieben:Was vielleicht ein schritt tiefer ginge wäre n TUT für Bäume ... die kann man ja dann auch nur als Liste missbrauchen oder wirklich als Baum ... in dem man sich bewegen kann, Äste raushemen kann und in andere Baume einfügen kann ...
Wieso nicht gleich für Graphen allgemein, wenn es dir eh nur um sowas geht?
Angenommen es gäbe einen Algorithmus mit imaginärer Laufzeit O(i * n), dann gilt O((i * n)^2) = O(-1 * n^2) d.h. wenn man diesen Algorithmus verschachtelt ist er fertig, bevor er angefangen hat.
Antworten