Ceci dit elles sont limitées à une profondeur de 1.
On ne peut pas construire un arbre avec.
Les arbres ressemblent aux listes chainées mais peuvent avoir une profondeur infinie.
C'est à dire qu'on a des listes dans des listes.
Un des meilleurs examples est l'exploration d'un dossier comme C:\
ou encore la lecture d'un fichier XML, ou l'analyse hiérarchique d'une base de données...
Donc voici en préambule à un example d'utilisation qui va suivre juste derrière une implémentation très simple / très proche du concept purebasic d'une liste chainée imbricable.
LinkedList2.pbi
Code : Tout sélectionner
;---------------------------------------
; Object: LinkedList2
; Version: Version 0.2
; Author: Flype (flype44@hotmail.fr)
; Date: Mar 2006
; Requir : Purebasic 4.0
;---------------------------------------
; MiniSet.pbi
Global NewList set.l()
Procedure.l Push(value.l)
If AddElement(set())
set() = value
EndIf
EndProcedure
Procedure.l Pop(value.l)
ForEach set()
If set() = value
DeleteElement(set())
EndIf
Next
EndProcedure
Procedure.l NotIn(value.l)
ForEach set()
If set() = value
ProcedureReturn #False
EndIf
Next
EndProcedure
; LinkedList2.pbi
Structure LL
*nextLL
*prevLL
nByte.l
nElement.l
userdata.l
EndStructure
Macro NewTree(STRUCTNAME)
LL_Alloc(SizeOf(STRUCTNAME))
EndMacro
Macro NewList2(STRUCTNAME)
LL_Alloc(SizeOf(STRUCTNAME))
EndMacro
Macro Assert2(element,func)
If element = -1
Debug "[" + func + "] List is empty"
ElseIf element = -2
Debug "[" + func + "] Out of bounds"
ElseIf element = #Null
Debug "[" + func + "] Pointer is null"
End
ElseIf NotIn(element)
Debug "[" + func + "] Not a valid list"
End
EndIf
EndMacro
Procedure.l LL_Alloc(nByte.l=SizeOf(LL))
*list.LL = AllocateMemory(nByte)
Push(*list)
Assert2(*list,"NewList2")
*list\nByte = nByte
ProcedureReturn *list
EndProcedure
Procedure.l LL_Free(*element.LL)
Assert2(*element,"LL_Free")
ZeroMemory_(*element,*element\nByte)
FreeMemory(*element)
Pop(*element)
EndProcedure
Procedure.l LL_Link(*element1.LL,*element2.LL)
Assert2(*element1,"LL_Attach")
*element1\nextLL = *element2
If *element2
*element2\prevLL = *element1
EndIf
EndProcedure
Procedure.l CountList2(*list.LL)
Assert2(*list,"CountList2")
ProcedureReturn *list\nElement
EndProcedure
Procedure.l FirstElement2(*list.LL)
Assert2(*list,"FirstElement2")
If *list\nextLL
ProcedureReturn *list\nextLL
EndIf
Assert2(-1,"FirstElement2")
EndProcedure
Procedure.l LastElement2(*list.LL)
Assert2(*list,"LastElement2")
While *list
If *list\nextLL = #Null
ProcedureReturn *list
EndIf
*list = *list\nextLL
Wend
Assert2(-1,"LastElement2")
EndProcedure
Procedure.l AddElement2(*list.LL,position.l=-1)
Assert2(*list,"AddElement2")
*this.LL = LL_Alloc(*list\nByte)
Assert2(*this,"AddElement2")
*last.LL = LastElement2(*list)
*list\nElement + 1
If *last
*this\prevLL = *last
*last\nextLL = *this
Else
*this\prevLL = *list
EndIf
ProcedureReturn *this
EndProcedure
Procedure.l ClearList2(*list.LL)
Assert2(*list,"ClearList2")
*list\nElement = 0
*list = FirstElement2(*list)
While *list
*this = *list
*list = *list\nextLL
LL_Free(*this)
Wend
EndProcedure
Procedure.l DeleteList2(*list.LL)
Assert2(*list,"DeleteList2")
ClearList2(*list)
LL_Free(*list)
EndProcedure
Procedure.l DeleteElement2(*list.LL,position.l)
Assert2(*list,"DeleteElement2")
*this.LL = FirstElement2(*list)
While *this
If i = position
LL_Link(*this\prevLL,*this\nextLL)
LL_Free(*this)
*list\nElement - 1
ProcedureReturn
EndIf
*this = *this\nextLL
i + 1
Wend
Assert2(-2,"DeleteElement2")
EndProcedure
Procedure.l NextElement2(*list.LL)
Assert2(*list,"NextElement2")
ProcedureReturn *list\nextLL
EndProcedure
Procedure.l PreviousElement2(*list.LL)
Assert2(*list,"PreviousElement2")
*prev.LL = *list\prevLL
If *prev
If *prev\prevLL = #Null
ProcedureReturn #Null
EndIf
EndIf
ProcedureReturn *prev
EndProcedure
Procedure.l SwapElement2(*element1.LL,*element2.LL)
Assert2(*element1,"SwapElement2")
Assert2(*element2,"SwapElement2")
*prev1 = *element1\prevLL
*next1 = *element1\nextLL
*element1\nextLL = *element2\prevLL
*element1\nextLL = *element2\nextLL
*element2\prevLL = *prev1
*element2\nextLL = *next1
EndProcedure
Procedure.l SelectElement2(*list.LL,position.l)
Assert2(*list,"SelectElement2")
*list = FirstElement2(*list)
While *list
If i = position
ProcedureReturn *list
EndIf
*list = *list\nextLL
i + 1
Wend
Assert2(-2,"SelectElement2")
EndProcedure
;---------------------------------------
Correctif: Ligne 7 Assert2(-1,"FirstElement2") au lieu de Assert2(#False,"FirstElement2")
Nouvel alias: NewTree(), même chose que NewList2()
