Wer ist online?
Buchempfehlung
FreeBASIC-Chat
FreeBASIC-Nachrichten jetzt auch über Twitter erhalten. Follow us!fb:porticula NoPaste
Doppelt verkettete Liste - Bugfix
| Uploader: |  MilkFreeze |
| Datum/Zeit: | 26.04.2011 16:00:11 |
' Doppelt verkettete Liste, geschrieben in FreeBASIC
' (c) 2011 MilkFreeze
'
' Funktionen:
' apppend(element) - Anhängen von Elementen an das Ende der Liste
' insert(x, element) - Einfügen von Elementen mitten in die Liste
' item(x) - Zugriff auf ein Element der Liste (Schreiben und Lesen)
' remove(x) - Löschen eines Elementes aus der Liste
' destroy() - Leert die gesamte Liste
#macro makelist(datatype, list_name )
Type ##list_name##_list_el
p_prev as ##list_name##_list_el Ptr
p_next as ##list_name##_list_el Ptr
p_element as datatype ptr
Declare Constructor()
Declare destructor()
End Type
constructor ##list_name##_list_el()
#if datatype = string
this.p_element = callocate(sizeof(datatype))
#else
this.p_element = new datatype
#endif
end constructor
destructor ##list_name##_list_el()
if (this.p_next <> 0) then
delete this.p_next
end if
this.p_next = 0
this.p_prev = 0
#if datatype = string
deallocate this.p_element
#else
delete this.p_element
#endif
end destructor
Type ##list_name##_list
private:
p_first as ##list_name##_list_el Ptr
p_last as ##list_name##_list_el Ptr
i_count as integer
declare function get_element(index as integer) as ##list_name##_list_el Ptr
public:
declare property item (index as integer) as datatype
declare property item (index as integer, value as datatype)
declare property getptr (index as integer) as datatype ptr
declare property getptr (index as integer, value as datatype)
declare property getptr (index as integer, value as datatype ptr)
declare sub append (new_item as datatype) 'Anfügen
declare sub insert (index as integer, new_item as datatype)
declare sub destroy ()
declare sub remove (index as integer)
declare function count () as integer
declare destructor ()
declare operator let (new_list as ##list_name##_list)
declare operator += (new_list as ##list_name##_list)
End Type
destructor ##list_name##_list()
if (this.i_count <> 0) then
delete this.p_first
this.p_first = 0
this.p_last = 0
this.i_count = 0
end if
end destructor
sub ##list_name##_list.destroy()
this.destructor()
end sub
function ##list_name##_list.get_element(index as integer) as ##list_name##_list_el Ptr
'Haben wir einen negativen Index? Dann geben wir einfach das erste Element aus...
if (index < 0) then return this.p_first
dim p_tmp_item as ##list_name##_list_el ptr
dim i as integer
'Dann gucken wir mal ob wir uns in der erste oder zweiten Hälfte befinden...
if (index < (this.i_count-1) / 2) then
'setzen dementsprechend die variablen...
i = 1
p_tmp_item = this.p_first
'und wandern durch die Liste:
while (i < index)
i += 1
p_tmp_item = p_tmp_item->p_next
wend
else
'Hier das Ganze nochmal andersrum:
i = this.i_count
p_tmp_item = this.p_last
'Und rückwärts durch die Liste springen:
while (i > index)
i -= 1
p_tmp_item = p_tmp_item->p_prev
wend
end if
return p_tmp_item
end function
sub ##list_name##_list.remove (index as integer)
'Wenn index einen ungültigen Wert hat, die Sub verlassen:
if (index < 0 or index > this.i_count) then exit sub
dim p_tmp_item as ##list_name##_list_el Ptr
'Wir holen uns das zu Löschende Element:
p_tmp_item = this.get_element(index)
'Ist das Element das Ende der Liste?
if (index = this.i_count) then
? "muh"
'p_last korrigieren:
this.p_last = p_tmp_item->p_prev
'p_last->p_next leeren:
this.p_last->p_next = 0
else
p_tmp_item->p_next->p_prev = p_tmp_item->p_prev
p_tmp_item->p_prev->p_next = p_tmp_item->p_next
end if
if (index = 1) then
p_first = p_tmp_item->p_next
end if
'Das entfernte Element zerstören:
p_tmp_item->p_next = 0 'Damit der desctructor von p_tmp_item nicht die Ganze liste leert.
delete p_tmp_item
'Den Zähler korrigieren:
this.i_count -= 1
end sub
sub ##list_name##_list.insert (index as integer, new_item as datatype)
'Index am Ende der Liste (oder dahinter)?
if (index > this.i_count ) then
'Dann können wir append() nutzen:
this.append(new_item)
elseif (index <= this.i_count and index > 0 ) then
'Wenn Index Innerhalb der Liste liegt...
'Brauchen wir 2 Pointer:
dim p_next_item as ##list_name##_list_el Ptr
dim p_prev_item as ##list_name##_list_el Ptr
dim p_new_item as ##list_name##_list_el Ptr
'p_new_item wird unser neu eingefügtes Element:
p_new_item = new ##list_name##_list_el
'p_next_item ist das Element vor dem wir einfügen wollen:
p_next_item = this.get_element(index)
p_prev_item = p_next_item->p_prev
'Jetzt noch die Pointer korrigieren...
p_new_item->p_next = p_next_item
p_next_item->p_prev = p_new_item
'... den Wert zuweisen...
*p_new_item->p_element = new_item
'... und den Zähler erhöhen...
if (index = 1) then
this.p_first = p_new_item
else
p_prev_item->p_next = p_new_item
p_new_item->p_prev = p_prev_item
end if
this.i_count += 1
'Fertig!
end if
end sub
sub ##list_name##_list.append(new_item as datatype)
'Haben wir schon ein Element oder mehr?
if (this.p_first = 0 ) then
'Wenn nicht: Anlegen!
this.p_first = new ##list_name##_list_el 'Objekt erzeugen
*this.p_first->p_element = new_item 'Wert für das neue Element zuweisen
'Das erste Elemente ist gleichzeitig Beginn und Ende:
this.p_last = this.p_first
'Und damit wir auch Rückwärts durch die Liste kommen:
this.p_last->p_prev = this.p_first
elseif (p_last <> 0) then
'Wir haben schon Element, also ein neues Element an das Ende der Liste:
this.p_last->p_next = new ##list_name##_list_el
'Jetzt den "prev"-pointer des Neuen Elementes setzen
this.p_last->p_next->p_prev = this.p_last
'Dann den Pointer für das Listen-Ende aktualisieren:
this.p_last = this.p_last->p_next
'den passenden Wert zuweisen...
*this.p_last->p_element = new_item
'... und das Element ist angefügt!
end if
'Nachdem wir ein Element eingefügt haben, den Zähler erhöhen
i_count += 1
'Anmk.: Das Spart später durch die Liste zu springen um die Anzahl der
'Elemente zu bestimmen.
end sub
property ##list_name##_list.getptr(index as integer) as datatype ptr
'Wir benutzen get_element() und geben gleich p_element aus:
return (this.get_element(index)->p_element)
end property
property ##list_name##_list.getptr(index as integer, value as datatype)
'Wir benutzen get_element() und schieben den Wert gleich in p_element:
*this.get_element(index)->p_element = value
end property
property ##list_name##_list.getptr(index as integer, value as datatype ptr)
'Wir benutzen get_element() und schieben den Wert gleich in p_element:
this.get_element(index)->p_element = value
end property
property ##list_name##_list.item(index as integer) as datatype
'Wir benutzen get_element() und geben gleich p_element aus:
return (*this.get_element(index)->p_element)
end property
property ##list_name##_list.item(index as integer, value as datatype)
'Wir benutzen get_element() und schieben den Wert gleich in p_element:
*this.get_element(index)->p_element = value
end property
function ##list_name##_list.count() as integer
'Wir brauchen nicht Zählen, die Anzahl der Elemente kennen wir ja schon:
return this.i_count
end function
operator ##list_name##_list.let(new_list as ##list_name##_list)
if (@this = @new_list) then exit operator 'Verhindert die Zuweisung der Liste zu sich selbst.
dim i as integer
'Liste Leeren:
this.destructor()
'Werte Kopieren:
for i as integer = 1 to new_list.count()
'Element aus new_list anfügen:
this.append(new_list.item(i))
next
'Liste kopiert.
end operator
operator ##list_name##_list.+= (new_list as ##list_name##_list)
'Wie bei LET(), aber ohne zu leeren:
dim i as integer
'Werte Kopieren:
for i as integer = 1 to new_list.count()
'Element aus new_list anfügen:
this.append(new_list.item(i))
next
'Liste kopiert.
end operator
#endmacro
'-----
'Ab hier Beispiel:
'-----
'Listentyp erzeugen:
makelist(integer, int)
'Liste erzeugen:
dim test as int_list
'Liste mit 10 Elementen befüllen:
for i as integer = 1 to 10
test.append(100 * i)
next
'Ausgabe:
for i as integer = 1 to 10
print test.item(i)
next
'Zerstören der Liste (ruft den Destructor auf):
test.destroy()