Listes Dynamiques

tmyke · Message par **tmyke** » dim. 04/nov./2007 12:40

Cela a déjà peut-être été déjà fait, mais voici un petit code qui permet la creation et la gestion
de liste dynamques de pointeurs. C'est le genre de code que j'emploi en 3D pour pouvoir gérer
de manière souple un nombre important de pointeurs. (a savoir que ce comme est aisément
modifiable pour des listes de n'importa quelles type de données..)

Code : Tout sélectionner

;{
;   TMyke DList  (liste dynamque pour pointeur)
;   2007  v0.21
;}

;===================================================================
; structure de base -> à quand la POO avec PB :(
;===================================================================
Structure DList
  *mzone
  nbreElement.l
EndStructure													    

;===================================================================
; instructions pour la gestion de la liste dynamique de pointeurs
;===================================================================
;{ creation d'une nouvelle liste
;
Procedure InitDList_(*list.DList)
  *list\mzone=#Null
  *list\nbreElement=0
EndProcedure
; }

;{ libère les ressource lié à la liste
;
Procedure FreeDList_(*list.DList)
  FreeMemory(*list\mzone)
  *list\mzone=#Null
  *list\nbreElement=0
EndProcedure
;}

;{  Allocation memoire
;
Procedure mem_Alloc_(*list.DList)
   *list\mzone = ReAllocateMemory(*list\mzone, *list\nbreElement*4)
EndProcedure
;}

;{ Ajoute n elements en fin de liste sans préciser leur contenu
;
Procedure expand_(*list.DList, nbr.l)
  *list\nbreElement + nbr
  mem_Alloc_(*list)
EndProcedure
;}

;{ Ajoute un element dans la liste pointer
;
Procedure AddDList_(*list.DList, *ptr)
  *list\nbreElement + 1
  mem_Alloc_(*list)
  PokeL(*list\mzone+(*list\nbreElement-1)*4, *ptr)
EndProcedure
;}

;{ change un élément de la liste
; 
Procedure PutDList_(*list.DList, *ptr, index.l)
  PokeL(*list\mzone+(index), *ptr)
EndProcedure
;}



;{ Retourne le nombre d'elements dans la liste
;
Procedure.l CountDList_(*list.DList)
  ProcedureReturn *list\nbreElement
EndProcedure
;}

;{ Retourne le nieme element de la liste pour les pointeurs
; 
Procedure.l GetDList_(*list.DList,index.l)
  ProcedureReturn PeekL(*list\mzone+(index*4))
EndProcedure
;}

;{ Retourne la position dans la liste si on trouve l'élément souhaite
; dans la liste (première occurance trouvée)
;
Procedure FindDList_(*list.DList,*ptr)
  If(*list\nbreElement=0)
    ProcedureReturn -1
  EndIf
  For i = 0 To *list\nbreElement-1
    If( GetDList_(*list, i) = *ptr)
      ProcedureReturn i
    EndIf
  Next
  ProcedureReturn -1
EndProcedure
;}

;{ // Supprime le premier element de la liste trouvé correspondant à *ptr
; première occurance trouvé qui sera supprimée
;
Procedure DelDList_(*list.DList,*ptr)
  index.l = FindDlist_(*list, *ptr)
  ; pas trouvé
  If(index<0) :    ProcedureReturn  : EndIf  
  ; il n'y avait qu'un élément dans la liste
  If(*list\nbreElement<2) 
      FreeDList_(*list)
      ProcedureReturn
  EndIf
  ; transpose la mémoire
  MoveMemory(*list\mzone+(index+1)*4, *list\mzone+index*4,  (*list\nbreElement - (index+1))*4)
  *list\nbreElement-1
  mem_Alloc_(*list)
EndProcedure
;}

;{ // Supprime l'élément dont on fourni l'index
;
Procedure DelIndexDList_(*list.DList,index.l)
  If(index<0) :    ProcedureReturn  : EndIf  
  ; il n'y avait qu'un élément dans la liste
  If(*list\nbreElement<2) 
      FreeDList_(*list)
      ProcedureReturn
  EndIf
  ; transpose la mémoire
  MoveMemory(*list\mzone+(index+1)*4, *list\mzone+index*4,  (*list\nbreElement - (index+1))*4)
  *list\nbreElement-1
  mem_Alloc_(*list)
EndProcedure
;}

;===================================================================
; instruction sous forme de macro, plus simple et plus intuitive
; (sans à passer le pointeur a chaque fois
;===================================================================
Macro InitDlist( name )
   InitDList_(@ name )
EndMacro
Macro AddDlist( name, ptr )
   AddDList_(@ name, ptr )
EndMacro
Macro GetDlist( name, id )
   GetDList_(@ name, id )
EndMacro
Macro PutDlist( name, ptr, id )
   PutDList_(@ name, ptr, id )
EndMacro
Macro FreeDlist( name)
   FreeDList_(@ name)
EndMacro
Macro CountDlist( name)
   CountDList_(@ name)
EndMacro
Macro FindDlist( name, ptr)
   FindDList_(@ name, ptr)
EndMacro
Macro DelDlist( name, ptr)
   DelDList_(@ name, ptr)
EndMacro
Macro DelIndexDlist( name, index)
   DelIndexDList_(@ name, index)
EndMacro

et en guise d'exemple, quelques lignes pour illustrer tout
cela

Code : Tout sélectionner

;OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
;OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
; quelques lignes en guise d'exemple
;OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
;OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

Global mlist.DList
Global Dim tlist.DList(100)

; definition de pointeur en guise d'exemple
*ptr1 = 1234
*ptr2 = 5432
var=666 ; cela peut aussi fonctionner avec les entiers, meme si 
; au départ c'est pas prévu pour cela

; init la structure de la liste
InitDList(mlist)
; ajoute trois éléments
AddDList(mlist, *ptr1)
AddDList(mlist, *ptr2)
AddDList(mlist, var)

; affiche les éléments contenu dans la liste
For i = O To mlist\nbreElement-1
  Debug GetDList(mlist,i)
Next

Debug " "
Debug "find:------"
Debug FindDList(mlist, *ptr2)
Debug " "
Debug "CountList--------"
Debug CountDList(mlist)
Debug "--------"

; éfface un élément, et ré-affiche les éléments restant
DelDlist(mlist, var)
For i = O To mlist\nbreElement-1
  Debug GetDList(mlist,i)
Next

; libération des ressources
FreeDlist(mlist)

Debug "--- exemple avec des tableau de listes---"
; pour un tableau de listes
; init la structure de la liste
InitDList( tlist(2) )
; ajoute trois éléments
AddDList(tlist(2), *ptr1)
AddDList(tlist(2), *ptr2)
AddDList(tlist(2), var)
For i = O To CountDList( tList(2) )-1
  Debug GetDList(tlist(2),i)
Next
FreeDlist(tlist(2))

je ne sais pas si cela servira à quelqu'un , mais sait-on jamais.

lionel_om · Message par **lionel_om** » dim. 04/nov./2007 16:18

Je travaille sur une Lib de listes chainées depuis un bon moment : Lib Vector.
Je vais essayer de la finaliser d'ici peu. Je corrige les derniers bugs et j'essaye d'optimiser quelques fonctions. Elle permet de gérer tous les types de données, plus les structures.

Un post est déjà ouvert : http://www.purebasic.fr/french/viewtopic.php?t=6775. Une fois finalisée, je fournirais une doc complète.

Lio

tmyke · Message par **tmyke** » dim. 04/nov./2007 16:45

En effet très sympa ton code lionel_om, par contre peux-tu faire avec des tableaux
de listes chainées ? (ce que ne peux pas faire PB )

lionel_om · Message par **lionel_om** » dim. 04/nov./2007 21:46

tmyke a écrit :En effet très sympa ton code lionel_om, par contre peux-tu faire avec des tableaux
de listes chainées ? (ce que ne peux pas faire PB )

Des tableaux de listes chainées ? oui :

Code : Tout sélectionner

Dim my_list(6)
For i = 0 to 6
  my_list(i) = Vector_Create(i); Define a #Byte vector, then a #Word vector, #long, #Float, #Quad, #String and finally a #Double vector
Next i

l.l = 125
s.s = "coucou"
Vector_AddElement(my_list(#Long), @l)
Vector_AddElement(my_list(#String), @s)

Lio