Wer ist online?
Buchempfehlung
FreeBASIC-Chat
FreeBASIC-Nachrichten jetzt auch über Twitter erhalten. Follow us!fb:porticula NoPaste
Doppelt verkettete Liste
| Uploader: |  MilkFreeze |
| Datum/Zeit: | 24.04.2011 20:19:26 |
'
' Doppelt verkettete Liste, geschrieben in FreeBASIC
' 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
#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()
delete this.p_element
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 sub append (new_item as datatype) 'Anfügen
declare sub insert (index as integer, new_item as datatype)
declare sub remove (index as integer)
declare property item (index as integer) as datatype ptr
declare property item (index as integer, value as datatype)
declare function count () as integer
End Type
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 (this.p_last = p_tmp_item) 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
p_tmp_item->p_prev->p_next = p_tmp_item->p_next
end if
'Das entfernte Element zerstören:
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_tmp_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_tmp_item ist das Element hinter dem wir einfügen wollen:
p_tmp_item = this.get_element(index)
'Jetzt noch die Pointer korrigieren...
p_new_item->p_prev = p_tmp_item
p_new_item->p_next = p_tmp_item->p_next
p_tmp_item->p_next = p_new_item
p_new_item->p_next->p_prev = p_new_item
'... den Wert zuweisen...
*p_new_item->p_element = new_item
'... und den Zähler erhöhen...
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.item(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.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
#endmacro
makelist(string, string)
dim test as string_list
test.append("foo")
test.append("bar")
test.append("foobar")
? *test.item(2)
test.item(2) = "Hallo Welt"
? *test.item(2)
makelist(integer, int)
dim test2 as int_list
for i as integer = 1 to 10
test2.append(100 * i)
next
test2.insert(3,1)
test2.insert(test2.count(),2)
for i as integer = 1 to test2.count()
? *test2.item(i)
next
? ""
test2.remove(4)
test2.remove(test2.count())
for i as integer = 1 to test2.count()
? *test2.item(i)
next