Wer ist online?
Buchempfehlung
FreeBASIC-Chat
FreeBASIC-Nachrichten jetzt auch über Twitter erhalten. Follow us!fb:porticula NoPaste
Doppelt verkette Liste - Bugfix 2
| Uploader: |  MilkFreeze |
| Datum/Zeit: | 27.04.2011 16:15:39 |
' 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 function getptr (index as integer) 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
'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
if p_tmp_item->p_prev <> 0 then
p_tmp_item->p_prev->p_next = p_tmp_item->p_next
end if
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
function ##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 function
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
test.remove(0)
test.remove(1)
'Ausgabe:
for i as integer = 1 to 10
print test.item(i)
next
'Zerstören der Liste (ruft den Destructor auf):
test.destroy()