|
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 |
Muttonhead
Anmeldungsdatum: 26.08.2008 Beiträge: 563 Wohnort: Jüterbog
|
Verfasst am: 13.07.2019, 10:53 Titel: Position Swap in einer Double Linked List? |
|
|
Hallo @ all.
Ich will meine DLL mit einer solchen "Funktion" ausstatten. Also zwei Nodes tauschen ihre Plätze innerhalb der Liste.
Ich stoße da grad auf diverse Probleme, mit dem Vertauschen der Vor- und Nachfolger Links innerhalb der betreffenden Nodes ist es ja nun nicht getan.
auch in den beiden Nachbarn der zu tauschenden Nodes muß ja die Verlinkung geändert werden.
Sind beide zu tauschende Nodes direkte Nachbarn, wird das dann extrem Pain...usw...
Hat jemand von euch nen Inspirationsschub? Vielleicht denke ich dabei auch viel zu kompliziert.
Jedenfalls war bei meinen bisherigen Versuchen die Liste "zerstört", oder zumindest eine Referenzrichtung funktionierte nicht mehr
Mutton |
|
Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007 Beiträge: 4603 Wohnort: ~/
|
Verfasst am: 13.07.2019, 22:07 Titel: |
|
|
Mal so eine Idee (ich denke gerade während des Schreibens ...)
Du hast
... <-> vor1 <-> knoten1 <-> nach1 <-> ...
und
... <-> vor2 <-> knoten2 <-> nach2 <-> ...
Zunächst einmal ein
SWAP knoten1.vorgaenger, knoten2.vorgaenger
SWAP knoten1.nachfolger, knoten2.nachfolger
Dann muss der Vorgänger von knoten1 auf knoten1 verweisen usw.
knoten1.vorgaenger.nachfolger = knoten1
knoten1.nachfolger.vorgaenger = knoten1
und dasselbe nochmal mit knoten2.
Müsste doch funktionieren?
Ansonsten kannst du auch deine Idee mal zur Fehlersuche posten. _________________ Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
Nach oben |
|
|
grindstone
Anmeldungsdatum: 03.10.2010 Beiträge: 1215 Wohnort: Ruhrpott
|
Verfasst am: 15.07.2019, 15:35 Titel: |
|
|
Endlich mal wieder was zum Knobeln!
Hier ein einfaches Beispiel. Entscheidend ist die richtige Reihenfolge der Tauschaktionen: Code: | Type tNode
As Integer number
As tNode Ptr parent
As tNode Ptr child
End Type
Dim As tNode Ptr root = New tNode
Dim As tNode Ptr np, nodeA, nodeB
'liste erzeugen
np = root
For x As Integer = 1 To 10
np->child = New tNode
np->child->parent = np
np->child->number = x
np = np->child
Next
np = root
Do
Print np->number
If np->number = 3 Then nodeA = np 'pointer auf Knoten A
If np->number = 9 Then nodeB = np 'pointer auf Knoten B
np = np->child
Loop Until np = 0
'knoten A und B vertauschen
nodeA->parent->child = nodeB
nodeB->parent->child = nodeA
nodeA->child->parent = nodeB
nodeB->child->parent = nodeA
Swap nodeA->child, nodeB->child
Swap nodeA->parent, nodeB->parent
Print
np = root
Do
Print np->number
If np->number = 3 Then nodeA = np
If np->number = 6 Then nodeB = np
np = np->child
Loop Until np = 0
Sleep
'liste löschen
np = root
Do
root = np
np = np->child
Delete root
Loop Until np = 0
|
Gruß
grindstone _________________ For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen! |
|
Nach oben |
|
|
Muttonhead
Anmeldungsdatum: 26.08.2008 Beiträge: 563 Wohnort: Jüterbog
|
Verfasst am: 15.07.2019, 18:40 Titel: |
|
|
in meiner dll hab ich das ganze nun anders gelöst, zwei getrennte "Bewegungen"...
@grindstone:
Code: | Type tNode
As Integer number
As tNode Ptr parent
As tNode Ptr child
End Type
Dim As tNode Ptr root = New tNode
Dim As tNode Ptr np, nodeA, nodeB
'liste erzeugen
np = root
For x As Integer = 1 To 10
np->child = New tNode
np->child->parent = np
np->child->number = x
np = np->child
Next
np = root
Do
Print np->number,
if np->parent then print np->parent->number,
if np->child then print np->child->number
If np->number = 3 Then nodeA = np 'pointer auf Knoten A
If np->number = 4 Then nodeB = np 'pointer auf Knoten B
np = np->child
Loop Until np = 0
'knoten A und B vertauschen
nodeA->parent->child = nodeB
nodeB->parent->child = nodeA
nodeA->child->parent = nodeB
nodeB->child->parent = nodeA
Swap nodeA->child, nodeB->child
Swap nodeA->parent, nodeB->parent
Print:print
np = root
Do
Print np->number,
if np->parent then print np->parent->number,
if np->child then print np->child->number
np = np->child
Loop Until np = 0
Sleep
'liste löschen
np = root
Do
root = np
np = np->child
Delete root
Loop Until np = 0
|
liefert:
Code: | 0 1
1 0 2
2 1 3
3 2 4
4 3 5
5 4 6
6 5 7
7 6 8
8 7 9
9 8 10
10 9
0 1
1 0 2
2 1 4
4 4 3
3 3 5
5 3 6
6 5 7
7 6 8
8 7 9
9 8 10
10 9 |
1. Spalte der Node selbst
2.Spalte der im Node verlinkte Vorgänger/Parent
3.Spalter der im Node verlinkte Nachfolger/Child
3 und 4 tauschen die Positionen. Über den Child-Link ist die Liste intakt, jedoch nicht mehr rückwärts, über den Parent-Link
Muttom |
|
Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007 Beiträge: 4603 Wohnort: ~/
|
Verfasst am: 15.07.2019, 19:47 Titel: |
|
|
So wie ich es sehe, funktioniert die Methode hervorragend*, solange die beiden zu vertauschenden Elemente nicht aufeinander folgen. Für den Fall aufeinanderfolgender Knoten fällt mir aber keine Möglichkeit ein, bei der nicht die Gefahr besteht, dass ein Knoten in irgendeiner Richtung auf sich selbst verweist (ist natürlich möglich, dass ich was übersehe, aber mein Gehirn-RAM ist dazu nicht ausreichend ...). Daher mein Vorschlag einer Fallunterscheidung:
Code: | parentA = nodeA->parent
parentB = nodeB->parent
childA = nodeA->child
childB = nodeB->child
IF childA = nodeB THEN
parentA ->child = nodeB
childB->parent = nodeA
nodeA->parent = nodeB
nodeA->child = childB
nodeB->parent = parentA
nodeB->child = nodeA
ELSEIF childB = nodeA THEN
' modifizierte Form davon
ELSE
' wie in obigen Posts vorgeschlagen
END IF |
edit:
*) Da gibt es noch ein Problem, wenn einer der vertauschten Knoten der letzte auf der Liste ist. Leider muss ich dringend weg, keine Zeit zum Suchen. _________________ Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
Nach oben |
|
|
grindstone
Anmeldungsdatum: 03.10.2010 Beiträge: 1215 Wohnort: Ruhrpott
|
Verfasst am: 16.07.2019, 08:14 Titel: |
|
|
nemored hat Folgendes geschrieben: | So wie ich es sehe, funktioniert die Methode hervorragend*, solange die beiden zu vertauschenden Elemente nicht aufeinander folgen...
...*) Da gibt es noch ein Problem, wenn einer der vertauschten Knoten der letzte auf der Liste ist... |
Und wenn einer der Knoten der Erste ist, wird es noch lustiger...
Um alle möglichen Varianten abzudecken, sind ein paar Fallunterscheidungen nötig: Code: | Type tNode
As Integer number
As tNode Ptr parent
As tNode Ptr child
End Type
Dim As tNode Ptr root = New tNode
Dim As tNode Ptr np, nodeA, nodeB
'liste erzeugen
np = root
For x As Integer = 1 To 10
np->child = New tNode
np->child->parent = np
np->child->number = x
np = np->child
Next
np = root
Do
Print np->number, np->parent, np, np->child
If np->number = 0 Then nodeA = np 'pointer auf Knoten A
If np->number = 10 Then nodeB = np 'pointer auf Knoten B
np = np->child
Loop Until np = 0
'zeiger vom jeweiligen parent auf die knoten vertauschen
If (nodeA->parent <> 0) AndAlso (nodeB->parent <> 0) Then 'keiner der knoten ist anfangsknoten
Swap nodeA->parent->child, nodeB->parent->child
ElseIf nodeA->parent <> 0 Then 'nodeB ist anfangsknoten
nodeA->parent->child = nodeB
root = nodeA
Else 'nodeA ist anfangsknoten
nodeB->parent->child = nodeA
root = nodeB
EndIf
'zeiger vom jeweiligen child auf die knoten vertauschen
If (nodeA->child <> 0) AndAlso (nodeB->child <> 0) Then 'keiner der Knoten ist endknoten
Swap nodeA->child->parent, nodeB->child->parent
ElseIf nodeA->child <> 0 Then 'nodeB ist endknoten
nodeA->child->parent = nodeB
Else 'nodeA ist endknoten
nodeB->child->parent = nodeA
EndIf
Swap nodeA->child, nodeB->child 'zeiger von den knoten auf jeweiligen child vertauschen
Swap nodeA->parent, nodeB->parent 'zeiger von den knoten auf jeweiligen parent vertauschen
Print
np = root
Do
Print np->number, np->parent, np, np->child
np = np->child
Loop Until np = 0
Sleep
'liste löschen
np = root
Do
root = np
np = np->child
Delete root
Loop Until np = 0
|
Gruß
grindstone
EDIT:
@Muttonhead: Stimmt, rückwärts funktioniert es nicht. Mal noch 'n bisschen weiterknobeln... _________________ For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen! |
|
Nach oben |
|
|
grindstone
Anmeldungsdatum: 03.10.2010 Beiträge: 1215 Wohnort: Ruhrpott
|
Verfasst am: 16.07.2019, 13:05 Titel: |
|
|
So, das müsste jetzt funktionieren (vor- und rückwärts, an den Enden und mit Knoten, die direkt hintereinanderliegen). Den Großteil der Probleme kann man umgehen, indem man vor dem Tauschen vorne und hinten je einen Dummyknoten an die Liste anhängt und hinterher wieder entfernt. Code: | Type tNode
As Integer number
As tNode Ptr parent
As tNode Ptr child
End Type
Dim As tNode Ptr root = New tNode, dummyRoot = New tNode, dummyTail = New tNode
Dim As tNode Ptr np, nodeA, parentA, nodeB, childB, tail
'liste erzeugen
np = root
For x As Integer = 1 To 10
np->child = New tNode
np->child->parent = np
np->child->number = x
np = np->child
tail = np
Next
'vorwärts
np = root
Do
Print np->number, IIf(np->parent, Str(np->parent->number), "-"); " <-"; np->number; " -> "; IIf(np->child, Str(np->child->number), "-")
If np->number = 4 Then nodeA = np 'pointer auf Knoten A
If np->number = 1 Then nodeB = np 'pointer auf Knoten B
np = np->child
Loop Until np = 0
'rückwärts
Print
np = tail
Do
Print np->number, IIf(np->parent, Str(np->parent->number), "-"); " <-"; np->number; " -> "; IIf(np->child, Str(np->child->number), "-")
np = np->parent
Loop Until np = 0
'vorne und hinten dummyknoten anfügen
dummyroot->child = root
root->parent = dummyroot
dummytail->parent = tail
tail->child = dummytail
If ((nodeA->child = nodeB) And (nodeB->parent = nodeA)) OrElse _
((nodeB->child = nodeA) And (nodeA->parent = nodeB)) Then 'knoten liegen direkt hintereinander
parentA = nodeA->parent
childB = nodeB->child
'pointer vertauschen
parentA->child = nodeB
nodeA->child = childB
nodeB->child = nodeA
childB->parent = nodeA
nodeB->parent = parentA
nodeA->parent = nodeB
Else
Swap nodeA->parent->child, nodeB->parent->child 'pointer vom jeweiligen parent auf die knoten vertauschen
Swap nodeA->child->parent, nodeB->child->parent 'pointer vom jeweiligen child auf die knoten vertauschen
Swap nodeA->child, nodeB->child 'pointer von den knoten auf jeweiligen child vertauschen
Swap nodeA->parent, nodeB->parent 'pointer von den knoten auf jeweiligen parent vertauschen
EndIf
'pointer korrigieren und dummyknoten entfernen
root = dummyroot->child
root->parent = 0
tail = dummytail->parent
tail->child = 0
Print
'vorwärts
Print
np = root
Do
Print np->number, IIf(np->parent, Str(np->parent->number), "-"); " <-"; np->number; " -> "; IIf(np->child, Str(np->child->number), "-")
np = np->child
Loop Until np = 0
'rückwärts
Print
np = tail
Do
Print np->number, IIf(np->parent, Str(np->parent->number), "-"); " <-"; np->number; " -> "; IIf(np->child, Str(np->child->number), "-")
np = np->parent
Loop Until np = 0
Sleep
'knoten löschen
np = root
Do
root = np
np = np->child
Delete root
Loop Until np = 0
Delete dummyroot
Delete dummytail
|
Gruß
grindstone _________________ For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen! |
|
Nach oben |
|
|
Muttonhead
Anmeldungsdatum: 26.08.2008 Beiträge: 563 Wohnort: Jüterbog
|
Verfasst am: 20.07.2019, 16:36 Titel: |
|
|
Vielen Dank nochmal
wie schon gesagt, meine "Lösung" ist nicht sehr schnell und basiert auf schon vorhandene Routinen
Code: | declare function NewNode(nt as integer) as any ptr
declare sub KillNode(e as any ptr)
'allen UDTs, denen das node type vererbt und damit "listenfähig" gemacht wurden, werden jetzt Typkonstanten zugeordnet
const as integer NodeType=0
const as integer ListObjectType=1
'forward reference
type _ListObject as ListObject
type node 'extends object
prev_node as node ptr'double linked list
next_node as node ptr'double linked list
ntype as integer
Index as integer
Owner as _ListObject ptr
'Data:
'für den einfachsten Fall einer Liste kann man in einem node einen Zeiger hinterlegen
anypointer as any ptr
end type
type ListObject extends node
public:
NumNodes as integer'Anzahl der nodes
private:
first_node as node ptr
last_node as node ptr
public:
declare constructor
declare destructor
declare function AppendNew (nt as integer) as any ptr 'erzeugt einen node und hängt es a n die liste an
declare function PrependNew (nt as integer) as any ptr 'erzeugt einen node und setzt es v o r die liste
declare function GetFirst as any ptr 'liefert erstes Element als Zeiger
declare function GetLast as any ptr 'liefert letztes Element als Zeiger
declare function GetAddr(i as integer )as any ptr 'liefert den Zeiger des Elementes mit dem Index i
declare function GetIndex(e as any ptr)as integer 'liefert den Index des Elementes mit der Adresse e
declare sub MoveToFirst(e as any ptr) 'verschiebt ein Element an die erste Position in der Liste
declare sub MoveToLast(e as any ptr) 'verschiebt ein Element an die letzte Position der Liste
declare sub MoveBehind(e as any ptr, de as any ptr)'verschiebt ein Element hinter das Element de
declare sub MoveBefore(e as any ptr, de as any ptr)'verschiebt ein Element vor das Element de
declare sub SwapIt(a as any ptr, b as any ptr) 'vertauscht zwei Elemente
declare sub PrintList
declare sub DeleteNode(e as any ptr) 'löscht Element e sowohl aus der Liste (also Freistellen) als auch das Element(Objekt) selbst
declare sub DeleteAll 'löscht gesamte Nodeliste und dessen Elemente(Objekte)
private:
declare sub UnLink(n as node ptr) 'stellt einen node frei und modifiziert entsprechend die Liste, ohne es zu löschen!!!
declare sub LinkAsFirst(n as node ptr) 'fügt ein freigestelltes node an den Listenanfang (als first_node) ein
declare sub LinkAsLast(n as node ptr) 'hängt ein freigestelltes node ans Listenende (als last_node) an
declare sub LinkBehindDest(n as node ptr, dest as node ptr)'setzt ein freigestelltes node hinter dest in die Liste
declare sub LinkBeforeDest(n as node ptr, dest as node ptr)'setzt ein freigestelltes node vor dest in die Liste
declare function CheckNode(n as node ptr) as integer 'überprüft node ob er in Liste existiert
declare sub MakeIndex
end type
constructor ListObject
end constructor
destructor ListObject
DeleteAll
end destructor
function ListObject.AppendNew (nt as integer) as any ptr
dim as any ptr e
e=NewNode(nt)
if e then
LinkAsLast cast(node ptr,e)
MakeIndex
cast(node ptr,e)->Owner=@this
function=e
end if
end function
function ListObject.PrependNew (nt as integer) as any ptr
dim as any ptr e
e=NewNode(nt)
if e then
LinkAsFirst cast(node ptr,e)
MakeIndex
cast(node ptr,e)->Owner=@this
function=e
end if
end function
function ListObject.GetFirst as any ptr
function=first_node
end function
function ListObject.GetLast as any ptr
function=last_node
end function
function ListObject.GetAddr(i as integer )as any ptr
function=0
dim as node ptr n,found
found=0
n=first_node
if n then
do
if n->Index = i then found=n
n=n->next_node
loop until (n=0) or (found<>0)
function=found
end if
end function
function ListObject.GetIndex(e as any ptr)as integer
function=0
dim as node ptr n
dim as integer found=0
n=first_node
if n then
do
if n = cast(node ptr,e) then found=n->Index
n=n->next_node
loop until (n=0) or (found>0)
function=found
end if
end function
sub ListObject.MoveToFirst(e as any ptr)
dim as node ptr n=cast(node ptr,e)
if CheckNode(n) then
UnLink n
LinkAsFirst(n)
MakeIndex
end if
end sub
sub ListObject.MoveToLast(e as any ptr)
dim as node ptr n=cast(node ptr,e)
if CheckNode(n) then
UnLink n
LinkAsLast(n)
MakeIndex
end if
end sub
sub ListObject.MoveBehind(e as any ptr, de as any ptr)
dim as node ptr n=cast(node ptr,e)
dim as node ptr dest=cast(node ptr,de)
if (n<>dest) and (CheckNode(n)) and (CheckNode(dest)) then
UnLink n
LinkBehindDest(n, dest)
MakeIndex
end if
end sub
sub ListObject.MoveBefore(e as any ptr, de as any ptr)
dim as node ptr n=cast(node ptr,e)
dim as node ptr dest=cast(node ptr,de)
if (n<>dest) and (CheckNode(n)) and (CheckNode(dest)) then
UnLink n
LinkBeforeDest(n, dest)
MakeIndex
end if
end sub
sub ListObject.SwapIt(a as any ptr, b as any ptr)
dim as node ptr s,d,s_,d_
s=cast(node ptr,a)
d=cast(node ptr,b)
'Vorgänger sichern
s_=s->prev_node
d_=d->prev_node
if s_ then MoveBehind(d, s_) else MoveToFirst(d)
if d_ then MoveBehind(s, d_) else MoveToFirst(s)
end sub
sub ListObject.PrintList
dim as node ptr n
n=first_node
if (n>0) then
do
print n->Index, "this: " & n _
& chr(9) & chr(9) & chr(9) & _
"prev: " & n->prev_node _
& chr(9) & chr(9) & chr(9) & _
"next: " & n->next_node
n=n->next_node
loop until (n=0)
print
end if
end sub
sub ListObject.UnLink(n as node ptr)
dim as integer UnLinkcase
if n then
if (n=first_node) and (n=last_node) then UnLinkcase=1 'es existiert nur ein node(ist damit sowohl erstes als auch letztes), das herausgelöst wird
if (n=first_node) and (n<>last_node) then UnLinkcase=2 'erste node der Liste wird herausgelöst
if (n<>first_node) and (n<>last_node) then UnLinkcase=3'weder erstes noch letztes node(also mittendrin) wird herausgelöst
if (n<>first_node) and (n=last_node) then UnLinkcase=4 'letztes node wird herausgelöst
select case UnLinkcase
case 1
first_node=0
last_node=0
case 2
n->next_node->prev_node=0 'im Nachfolger den Link zum Vorgänger löschen, damit wird auch innerhalb der Liste der Anfang neu definiert (zb. für Rückwärtssuche)
first_node=n->next_node 'Nachfolger von n zum ersten node machen
case 3
' +-----------------+
' B / C D |
' <-a c-> <-b d-> <-c n-> |
' | | node C freistellen
' B | D |
' <-a d-> | <-b n-> |
' \ | \ |
' +-------+ +------+
n->next_node->prev_node = n->prev_node'im Nachfolger den Link zum "Vorvorgänger" setzen
n->prev_node->next_node = n->next_node'im Vorgänger den Link zum "Nachnachfolger" setzen
case 4
n->prev_node->next_node=0 'im Vorgänger den Link zum Nachfolger löschen(=0), damit wird auch innerhalb der Liste das Ende neu definiert
last_node=n->prev_node 'Vorgänger von n zum letzten node machen
end select
n->prev_node=0 'alle Verlinkungen im freigestelltem node n auf 0 setzen
n->next_node=0
end if
end sub
sub ListObject.LinkAsFirst(n as node ptr)
n->prev_node=0 'zur Sicherheit erst einmal alle Verlinkungen im übergebenen node auf 0 setzen
n->next_node=0
'Verlinken
if first_node then 'sollte schon mindestens ein node existieren, dann...
first_node->prev_node=n 'node n dort als Vorgänger definieren
n->next_node=first_node 'im node n bisheriges erstes node als Nachfolger definieren
first_node=n 'node n wird zum ersten der Liste
else 'sollte noch kein node existieren dann...
first_node=n 'sowohl...
last_node=n ' ...als auch
end if
end sub
sub ListObject.LinkAsLast(n as node ptr)
n->prev_node=0 'zur Sicherheit erst einmal alle Verlinkungen im übergebenen node auf 0 setzen
n->next_node=0
'Verlinken
if last_node then 'sollte schon mindestens ein node existieren, dann...
last_node->next_node=n 'node n dort als Nachfolger definieren
n->prev_node=last_node 'im node n bisheriges letzes node als Vorgänger definieren
last_node=n 'node n wird zum letzten der Liste
else 'sollte noch kein node existieren dann...
first_node=n 'sowohl...
last_node=n ' ...als auch
end if
end sub
sub ListObject.LinkBehindDest(n as node ptr, dest as node ptr)
dim as node ptr nn
if dest=last_node then
LinkAsLast(n)
else
nn=dest->next_node'Nachfolger von dest merken
dest->next_node=n 'in dest node n als Nachfolger definieren
nn->prev_node=n 'in Nachfolger von dest node n als Vorgänger definieren
n->prev_node=dest 'in node n dest als Vorgänger definieren
n->next_node=nn 'in node n Nachfolger von dest als Nachfolger definieren
end if
end sub
sub ListObject.LinkBeforeDest(n as node ptr, dest as node ptr)
dim as node ptr pn
if dest=first_node then
LinkAsFirst(n)
else
pn=dest->prev_node'Vorgänger von dest merken
pn->next_node=n 'in dests Vorgänger node n als Nachfolger definieren
dest->prev_node=n 'in dest node n als Vorgänger definieren
n->next_node=dest 'in node n dest als Nachfolger definieren
n->prev_node=pn 'in node n dests ehemaligen Vorgänger als Vorgänger definieren
end if
end sub
function ListObject.CheckNode(n as node ptr) as integer
function=0
dim as node ptr nn
dim as integer found=0
nn=first_node
if (nn>0) and (n>0) then
do
if nn=n then found=1
nn=nn->next_node
loop until (nn=0) or (found<>0)
function=found
end if
end function
sub ListObject.MakeIndex
dim as node ptr n,nn
n=first_node
NumNodes=0
if n then
do
NumNodes +=1 'Anzahl erhöhen,da NumNodes Bestandteil des Listobjektes enthält es die Gesamtzahl der nodes
nn=n->next_node 'Nachfolger von n holen
n->Index=NumNodes 'Index in node schreiben
n=nn 'Nachfolger zum akuellem node machen
loop until n=0 'wenn keine node >>> raus!!!
end if
end sub
sub ListObject.DeleteNode(e as any ptr)
dim as node ptr n=cast(node ptr,e)
if CheckNode(n) then'gibt es den Eintrag/node in der Liste???
UnLink n
KillNode (e)
MakeIndex
else
print "element " & e & " not exist in list"
end if
end sub
sub ListObject.DeleteAll
dim as node ptr n,nn
n=first_Node
if n then
do
nn=n->next_node 'Nachfolger merken
'DeleteNode n 'hierüber wird die Liste nach jedem Löschen korrigiert, sicherer aber eigentlich nicht notwendig
KillNode (n)
n=nn 'Nachfolger zum akuellem node machen
loop until n=0 'wenn keine node >>> raus!!!
end if
'zum Schluß die Zeiger, die auf Listenanfang und -ende verweisen, löschen
first_node=0
last_node=0
end sub
'die folgenden Routinen sind keine Member des LOs
'hier müssen die Types entsprechend ihrer TypenKonstante eingepflegt werden
function NewNode(nt as integer) as any ptr
dim e as any ptr
select case nt
case NodeType
e=new node
case ListObjectType
e=new ListObject
end select
cast(node ptr,e)->ntype=nt
function=e
end function
sub KillNode(e as any ptr)
dim as integer nt
nt=cast(node ptr,e)->ntype
select case nt
case NodeType
delete cast(node ptr,e)
case ListObjectType
delete cast(ListObject ptr,e)
end select
end sub
'******************************************************************************
'******************************************************************************
'******************************************************************************
dim as ListObject ptr list
dim as node ptr n1,n2,n3,n4
list=new ListObject
if list then
n1=list->AppendNew(NodeType)
n2=list->AppendNew(NodeType)
n3=list->AppendNew(NodeType)
n4=list->AppendNew(NodeType)
list->printlist
list->SwapIt(n2,n3)
list->printlist
delete list
end if
sleep |
Mutton |
|
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.
|
|