 |
Das deutsche QBasic- und FreeBASIC-Forum
Für euch erreichbar unter qb-forum.de, fb-forum.de und freebasic-forum.de!
|
| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
Fausti
Anmeldungsdatum: 31.07.2005
Beiträge: 7
|
 Verfasst am: 01.08.2005, 18:24 Titel: Linked List in FreeBASIC |
 |
|
Dank dem Typcasting der neuen Freebasic Version habe ich meine Idee für eine allgemein verwendbare linked list wieder aufgegriffen. Natürlich habe ich mir in der Vergangenheit schon tonnenweise Tutorials über dieses Thema gesaugt und durchgearbeitet, aber die waren eher für andere Programmiersprachen (gab auch das eine oder andere gute englische tut für fb  , und obwohl das Grundmuster fast immer gleich ist, setzt jeder Programmierer sie eigentlich doch ein wenig anders um, oder erweitert sie sogar. Es mag auch genügend fertige Umsetzungen für z.B. C geben, die man auch in FB benutzen könnte, aber man lernt doch am besten, wenn man etwas selbst programmiert.
Ich fände es also toll, wenn wir hier unsere Ideen/Umsetzungen/Ratschläge posten würden und darüber dann diskutieren könnten. Vielleicht wird daraus ja dann eine Art Tutorial für FB, oder gar eine Erweiterung für FB, die dann Einzug in spätere Versionen hält?
Mal ein paar Stichpunkte:
- Iteratoren ja/nein/wie/warum?
- Implementation einer Liste für einen bestimmten Datentyp oder lieber allgemein (Any Ptr)?
- Wichtige/Nützliche Funktionen? Funktionen um das Arbeiten intuitiver zu gestalten?
- Optimierungen? Error Checking? |
|
| Nach oben |
|
 |
helium
Anmeldungsdatum: 10.09.2004
Beiträge: 397
Wohnort: Leverkusen
|
| Verfasst am: 02.08.2005, 11:38 Titel: |
|
|
| Zitat: | | - Iteratoren ja/nein/wie/warum? |
Hängt davon ab, wie du die Liste gestaltest. Bei einer einfachen version kommt man ohne Iteratoren aus, sondern verwendt direkt Zeiger auf die entsprechenden Nodes.
| Zitat: | | - Implementation einer Liste für einen bestimmten Datentyp oder lieber allgemein (Any Ptr)? |
Dinge, wie Collections und Algorithmen sollten immer so allgemein wie möglich gehalten werden.
| Zitat: | | - Wichtige/Nützliche Funktionen? Funktionen um das Arbeiten intuitiver zu gestalten? |
- length (länge bestimmen)
- exists (existiert ein bestimmtes Element)
- nth (ntes Element)
- reverse (umdrehen)
Andere wichtige Standardfunktionen wären
- filter (filtern anhand eines bestimmten Kriteriums (Funktion übergeben))
- map (Generieren einer neuen Liste aus der alten, wobei die übergebene Funktion auf jedes Element angewendet wird)
- foldLeft (Falten von links)
- foldRight (Falten von rechts)
sind in FB aber vermutlich nicht sonderlich intuitiv einsetzbar.
| Zitat: | | - Optimierungen? Error Checking? |
Abhängig von konkreten Anforderungen.
Hast du nur einfach Nodes, mit denen der Programmierer arbeitet, oder sind Sie eher Implementationsdetail und du kapselst das ganze nochmal weg? Ist es dann vielleicht sinnvoll die Länge extra mitzuspeichern? ...
_________________
Bevor Sie aufhören sich körperlich zu betätigen sollten Sie ihren Doktor befragen. Körperliche Inaktivität ist abnormal und gefährlich für Ihre Gesundheit. |
|
| Nach oben |
|
|
Fausti
Anmeldungsdatum: 31.07.2005
Beiträge: 7
|
| Verfasst am: 02.08.2005, 14:37 Titel: |
|
|
Zum herumbasteln habe ich einfach mal folgenden Aufbau gewählt:
| Code: |
Type LListItem
_data As Any Ptr ' Pointer auf die gespeicherten Daten
_prev As LListItem Ptr ' vorheriges LListItem
_next As LListItem Ptr ' nächstes LListItem
' _list As LList Ptr ' Pointer auf LList in dem sich das LListItem befindet
End Type
Type LList
_first As LListItem Ptr ' Pointer auf den ersten Listeneintrag
_last As LListItem Ptr ' Pointer auf den letzten Listeneintrag
End Type
Type LListIterator
_list As LList Ptr ' Pointer auf die zugehörige LList
_item As LListItem Ptr ' Pointer auf das aktuelle LListItem
End Type
Function LList_Create() As LList Ptr
Dim temp As LList Ptr
temp = callocate(Len(LList))
temp->_first = 0
temp->_last = 0
Return temp
End Function
Function LListItem_Create() As LListItem Ptr
Dim temp As LListItem Ptr
temp = callocate(Len(LListItem))
temp->_data = 0
temp->_next = 0
temp->_prev = 0
Return temp
End Function
Function LList_AddItem(byval l As LList Ptr, byval d As Any Ptr) As LListItem Ptr
Dim temp As LListItem Ptr
temp = LListItem_Create()
If temp = 0 Then Return 0
If l->_first = 0 Then
l->_first = temp
l->_last = temp
Else
l->_last->_next = temp
temp->_prev = l->_last
l->_last = temp
End If
temp->_next = 0
temp->_data = d
Return temp
End Function
Function LList_RemoveItem(byval l As LList Ptr, byval i As LListItem Ptr) As Any Ptr
Dim pr As LListItem Ptr
Dim ne As LListItem Ptr
Dim da As Any Ptr
pr = i->_prev
ne = i->_next
If pr <> 0 Then pr->_next = ne Else l->_first = ne
If ne <> 0 Then ne->_prev = pr Else l->_last = pr
da = i->_data
deallocate i
Return da
End Function
|
Ist im Moment wirklich nur rudimentär Zum herumspielen mit dem neuen Typcasting hats gereicht (*BEGEISTERT*).
Den Iterator-UDT habe ich nur als kleine Gedächtnisstütze eingebaut. Ich kenne ihn aus der STL von C++ und diversen Tuts, aber bin mir noch nicht wirklich darüber im Klaren, ob ich ihn wirklich brauche, wenn ich dem jetzigen Aufbau treu bleibe, denn LListItem könnte seine Funktion momentan auch übernehmen.
Noch eine Idee wäre es, wenn ich in LListItem noch irgendwie den Typ der gespeicherten Daten speichere, denn dank Any Ptr kann ich ja in ein und derselben Liste Daten mit verschiedenen Typen speichern.
Hatte auch mal vor einiger Zeit probiert, wie man eine Liste (ohne den Typ der gespeicherten Daten zu wissen) in eine Datei speichern könne, um sie später wieder einzulesen so wie es auch in Python geht. Hat bis auf Strings und UDTs mit Stringfeldern und sonstigen Pointern in den UDTs auch funktioniert. Ich konnte leider nicht prüfen, ob die Daten die ich direkt aus dem Speicher gelesen hatte nun Adressen waren, oder Daten. Nach nem Programmneustart waren an den gespeicherten Adressen ja nicht mehr die gewünschten Daten -> BLUESCREEN *lol* Naja, wenn man das noch irgendwie hinbekommen könnte
Könntest du mir das mit foldLeft/Right irgendwie erklären? |
|
| Nach oben |
|
|
helium
Anmeldungsdatum: 10.09.2004
Beiträge: 397
Wohnort: Leverkusen
|
| Verfasst am: 05.08.2005, 13:52 Titel: |
|
|
Ach 'ne doppelt verkettete Liste? Naja, tut ja nicht viel zur Sache.
| Zitat: | | Den Iterator-UDT habe ich nur als kleine Gedächtnisstütze eingebaut. Ich kenne ihn aus der STL von C++ und diversen Tuts, aber bin mir noch nicht wirklich darüber im Klaren, ob ich ihn wirklich brauche, wenn ich dem jetzigen Aufbau treu bleibe, denn LListItem könnte seine Funktion momentan auch übernehmen. |
In der STL gibt es drei Ebenen: Container, Iteratoren, Algorithmen. Algorithmen arbeiten prinzipiell nur mit Iteratoren und sind somit unabhängig von den Containern.
Das wird dir in FB aber nicht gelingen, aa es zur Zeit weder die Template-Fähigkeiten von C++ gibt noch Polymorphie, die als andere Alternative denkbar wäre.
(Natürlich kann man auch in FB mit viel Trickserei zu einem ähnlichen Ergebnis kommen, nur wäre der Aufwand zu groß und das Ergebnis vermutlch nicht bequem einsetzbar.)
Deswegen denke ich, dass du das Iterator-Konzept zunächst außen vor lassen soltest.
| Zitat: | | Noch eine Idee wäre es, wenn ich in LListItem noch irgendwie den Typ der gespeicherten Daten speichere, denn dank Any Ptr kann ich ja in ein und derselben Liste Daten mit verschiedenen Typen speichern. |
Hast du auch 'ne Idee, wie das gehen könnte? AFAIK besitzt FB zur Laufzeit keine Informationen über die Typen.
| Zitat: | Hatte auch mal vor einiger Zeit probiert, wie man eine Liste (ohne den Typ der gespeicherten Daten zu wissen) in eine Datei speichern könne, um sie später wieder einzulesen so wie es auch in Python geht.
|
Python kennt den Typ jedes Objekts.
Ich sehe im Moment keinen Weg, wie du die Daten serialisieren könntest.
| Zitat: | | Könntest du mir das mit foldLeft/Right irgendwie erklären? |
Wenn du Faltung nicht kennst, weiß ich nicht, ob es jetzt besonders sinnvoll ist. Außerdem denke ich sowieso, dass der durchschnitts FB-Programmierer wenig mit Faltung anfangen kann.
_________________
Bevor Sie aufhören sich körperlich zu betätigen sollten Sie ihren Doktor befragen. Körperliche Inaktivität ist abnormal und gefährlich für Ihre Gesundheit.
Zuletzt bearbeitet von helium am 06.08.2005, 13:07, insgesamt einmal bearbeitet |
|
| Nach oben |
|
|
Fausti
Anmeldungsdatum: 31.07.2005
Beiträge: 7
|
| Verfasst am: 05.08.2005, 15:23 Titel: |
|
|
| Zitat: | | Hast du auch 'ne Idee, wie das gehen könnte? AFAIK besitzt FB zur Laufzeit keine Informationen über die Typen. |
Konnte jetzt zwar den Quelltext zu meinem Versuch nicht mehr finden (ist auch schon ne Weile her) aber ich versuche es mal aus dem Gedächtnis so gut es geht.
| Code: |
Const TYP_NPC = 0
Const TYP_OBJ = 1
Const TYP_TILE = 2
Type tNPC
TYP As Byte
X As Byte
Y As Byte
FLAGS As Byte
SCRIPT As Byte
IMG As Byte
ANI As Byte
End Type
Type tOBJ
TYP As Byte
X As Byte
Y As Byte
IMG As Byte
ANI As Byte
FLAGS As Byte
End Type
Type tTILE
TYP As Byte
X As Byte
Y As Byte
IMG As Byte
End Type
|
Das sind jetzt mal einfach 3 verschiedene UDTs die ich mit zufälligen Daten gefüllt und in zufälliger Anzahl/Reihenfolge in einer Liste, ähnlich der aus meinem letzten Posting, gespeichert habe.
Wichtig ist hier in jedem UDT das Feld TYP und das es gleich als erstes in der Typdeklaration steht. Beim Erstellen einer Variable habe ich im TYP Feld immer gespeichert, um welchen UDT es sich handelte. Dann gab es noch ein 4. UDT:
| Code: |
Type tTEMPLATE
TYP As Byte
End Type
|
Beim Speichern der Liste in eine Datei bin ich einfach die gesamte Liste durchgegangen und habe mittels Len() die Länge des Objektes erfragt und mittels seiner Adresse dann seinen Speicherbereich ausgelesen, und in eine Datei geschrieben.
Der "Clou" kam dann beim Einlesen. Als ersten kommt ja von jedem Objekt das TYP Feld. Anhand dessen konnte ich erfahren was für einen UDT ich anlegen musste und wie lang er ist (wieder mit LEN()). Habe dann die jeweilige Anzahl Daten ausgelesen und in eine neue Variable vom jeweiligen Typ gespeichert, und diese dann in die Liste eingefügt.
Wenn ich mit der Prozedur durch war, konnte ich wie gewohnt auf die Daten aus der Liste zugreifen. Funktioniert aber leider wie schon erwähnt nicht, wenn FB anstelle der Daten nur die Adresse der Daten gespeichert hat, wie es bei Strings der Fall ist.
Naja, so super Weltbewegend ist das ganze wohl nicht, denn eigentlich ist es nur nen kleiner Trick um Daten mit verschiedenen Daten in ein und derselben Liste zu speichern, und mittels des vorgetäuschten Castings auf tTEMPLATE zugriff auf den Typ eines Objektes zu bekommen.
Wenn man aber aus irgendwelchen Gründen eh keine Strings oder Pointer auf andere Variablen in den zu speichernden Daten hat, kann man ohne großen Aufwand ne ganze Menge an verschiedenen UDTs in dieser Liste verwalten/speichern und laden, ohne jedesmal erst noch für jeden Typ eigene speichern/laden programmteile zu schreiben. Und Programmteile wo man doch ne unterscheidung braucht lassen sich ganz einfach mit select case realisieren. |
|
| Nach oben |
|
|
|
|
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
|
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
