Das deutsche QBasic- und FreeBASIC-Forum Foren-Übersicht Das deutsche QBasic- und FreeBASIC-Forum
Für euch erreichbar unter qb-forum.de, fb-forum.de und freebasic-forum.de!
 
FAQFAQ   SuchenSuchen   MitgliederlisteMitgliederliste   BenutzergruppenBenutzergruppen  RegistrierenRegistrieren
ProfilProfil   Einloggen, um private Nachrichten zu lesenEinloggen, um private Nachrichten zu lesen   LoginLogin
Zur Begleitseite des Forums / Chat / Impressum
Aktueller Forenpartner:

Position Swap in einer Double Linked List?

 
Neues Thema eröffnen   Neue Antwort erstellen    Das deutsche QBasic- und FreeBASIC-Forum Foren-Übersicht -> Allgemeine Fragen zu FreeBASIC.
Vorheriges Thema anzeigen :: Nächstes Thema anzeigen  
Autor Nachricht
Muttonhead



Anmeldungsdatum: 26.08.2008
Beiträge: 561
Wohnort: Jüterbog

BeitragVerfasst am: 13.07.2019, 09:53    Titel: Position Swap in einer Double Linked List? Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden
nemored



Anmeldungsdatum: 22.02.2007
Beiträge: 4594
Wohnort: ~/

BeitragVerfasst am: 13.07.2019, 21:07    Titel: Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden
grindstone



Anmeldungsdatum: 03.10.2010
Beiträge: 1208
Wohnort: Ruhrpott

BeitragVerfasst am: 15.07.2019, 14:35    Titel: Antworten mit Zitat

Endlich mal wieder was zum Knobeln! happy

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
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden
Muttonhead



Anmeldungsdatum: 26.08.2008
Beiträge: 561
Wohnort: Jüterbog

BeitragVerfasst am: 15.07.2019, 17:40    Titel: Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden
nemored



Anmeldungsdatum: 22.02.2007
Beiträge: 4594
Wohnort: ~/

BeitragVerfasst am: 15.07.2019, 18:47    Titel: Antworten mit Zitat

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. happy
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
grindstone



Anmeldungsdatum: 03.10.2010
Beiträge: 1208
Wohnort: Ruhrpott

BeitragVerfasst am: 16.07.2019, 07:14    Titel: Antworten mit Zitat

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... grinsen
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... zwinkern
_________________
For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen!
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden
grindstone



Anmeldungsdatum: 03.10.2010
Beiträge: 1208
Wohnort: Ruhrpott

BeitragVerfasst am: 16.07.2019, 12:05    Titel: Antworten mit Zitat

So, das müsste jetzt funktionieren (vor- und rückwärts, an den Enden und mit Knoten, die direkt hintereinanderliegen). lächeln 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
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden
Muttonhead



Anmeldungsdatum: 26.08.2008
Beiträge: 561
Wohnort: Jüterbog

BeitragVerfasst am: 20.07.2019, 15:36    Titel: Antworten mit Zitat

Vielen Dank nochmal lächeln
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
Benutzer-Profile anzeigen Private Nachricht senden E-Mail senden
Beiträge der letzten Zeit anzeigen:   
Neues Thema eröffnen   Neue Antwort erstellen    Das deutsche QBasic- und FreeBASIC-Forum Foren-Übersicht -> Allgemeine Fragen zu FreeBASIC. Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
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.

 Impressum :: Datenschutz