Liste chainée, qu'est-ce exactement?

cederavic · Message par **cederavic** » lun. 07/juin/2004 6:50

Il y a eu un tut sur les liste chainée de PB, mais je pense que pour bien comprendre comment elle fonctionne, il faut savoir les faire artisanalement... donc voilas un petit code commenté

Code : Tout sélectionner

Structure Element ; notre structure pour la liste chainée
  *NextElement.l ; pointeur vers l'element suivant
  *PreviousElement.l ; pointeur vers l'element precedant (non utiliser dans cet exemple, mais facilement utilisable si vous avez compris comment marche NextElement
  
  Value.l ; et enfin, une valeur
EndStructure

Test.Element ; ici, notre premier element
Test\NextElement = #NULL ; pas d'element suivant.. donc NULL
Test\PreviousElement = #NULL ; pas d'element precedant.. donc NULL
Test\Value = 10 ; et une valeur


Test2.Element ; notre 2eme element
Test\NextElement = @Test2 ; donc on reprend notre premier element et on fait pointer NextElement vers notre 2eme element
Test2\PreviousElement = @Test ; on fait pointer PreviousElement de notre 2eme element vers notre premier Element
Test2\NextElement = #NULL ; pas d'element suivant donc NULL
Test2\Value = 20 ; encor une valeur (euh... au cas ou vous n'auriez pas compris, value ici ne sert a rien, c'est juste pour apres voir si c'est bon.... :)

Test3.Element ; jamais 2 sans 3... notre 3eme element
Test2\NextElement = @Test3 ; donc on reprend notre 2eme element et on fait pointer NextElement vers notre 3eme element
Test3\PreviousElement = @Test2 ; toujour pareil... on fait pointer PreviousElement de notre 3eme element vers notre 2eme element
Test3\NextElement = #NULL ; pas d'element suivant
Test3\Value = 30 ; encore une valeur (on a dit jamais 2 sans 3 :p)

Procedure Debugtest(*Lst.Element) ; une proc qui va nous faire defiller la chaine (j'aurai bien pu faire un proc AddElement mais bon... si vous avez compris jusque la, pas de soucis :)
  ; donc on a un pointeur vers un element (*Lst)
  EndLst = 0 ; va nous servir a terminer la boucle
  
  Repeat
  
    Debug *Lst\Value ; on debug la valeur de l'element
    If *Lst\Nextelement = #NULL ; ensuite si NextElement de l'element courant est NULL, sa veut dir qu'il n'y a pas d'element suivant, donc on arrete la
      EndLst =1 ; hop
    Else ; sinon
      *Lst = *Lst\NextElement ; et bien l'element courant (*Lst) devient l'element suivant de l'element courant
    EndIf 
    
  Until EndLst = 1 ; finished
  
EndProcedure

Debugtest(@Test) ; on test a partir de l'element Test, et normalement le debug renvoi 10 puis 20 puis 30

logiquement, en faisant vos liste artisanalement, vous devriez pouvoir imbriquer une liste dans une liste (bien que se soit delicat... un movaise boucle, et c'est la boucle infini...) enfin bon, si vous avez des questions, n'hesitez pas

(ou si j'ai fait une connerie dans le code lol)

Wizard_Spike · Message par **Wizard_Spike** » lun. 21/juin/2004 11:41

Alors bah oui j'ai une question ^^
J'ai fait un programme qui créé et utilise une liste chainée. C'est un programme test équivalent au tiens, c'est à dire structure contenant une valeur, un pointeur sur le précédent et un pointeur sur le suivant.
La seule différence (à mes yeux du moins) c'est que j'utilise un pointeur sur ma liste chainée et un allocatememory().
En gros:
J'ai une structure nommée List qui contient:

Code : Tout sélectionner

Structure List
     Valeur.f
     *Suiv.List
     *Prec.List
EndStructure

Ensuite j'ai un pointeur Liste de type List (déclaré donc "Liste.List") qui va pointeur sur le premier élément de ma liste.

Mais pour le moment ce pointeur Liste ne pointe sur rien. Je fais donc:

Code : Tout sélectionner

Liste = AllocateMemory(cptalloc,SizeOf(List),0)

cptalloc étant étant ici un compteur d'objet dans la liste.

enfin, je vérifie si l'alloc a bien fonctionné et si tel est le cas, je tâche de remplir ma liste avec des valeurs à la biiiiip (auto-censure).

Code : Tout sélectionner

If Liste = 0 Or Liste = #NULL    ;Au cas où l'alloc n'aurait pas fonctionné... 
     Erreur.w = 1
Else
     temp = Liste
     *temp\Prec = #NULL ;premier élément de la liste donc le pointeur sur précédent pointe sur NULL
     *temp\Valeur = 7.4   ;valeur à la biiiip
     For i.w=0 To 10
          temp2 = temp
          temp = AllocateMemory(cptalloc,SizeOf(List),0) ;un nouvel objet
          cptalloc + 1
          *temp2\Suiv = temp
          *temp\Prec = temp2
          *temp\Suiv = 0
          *temp\Valeur = i*7.4
     Next i
EndIf

Le 7.4, vous l'aurez compris, est pris complêtement au hazard c'est juste histoire de le faire travailler sur des float.
J'utilise donc deux pointeurs temp et temp2 afin d'avancer dans ma liste. temp est l'élément en cours et temp2 le précédent.

Seulement voila.... La compilation fonctionne mais l'éxécution s'arrête à la ligne "*temp\Prec = #NULL" et me dit: "pointer is NULL"... Pourtant temp n'est pas null car je l'ai déjà affiché avec un Debug ou DrawText... Bizarre bizarre...

En gros il me jete à chaque fois que je fais "*pointeurelement\objet = quelquechose"

Note: Je suis encore sur la version démo de purebasic v3.80

Merci de votre aide ^^

cederavic · Message par **cederavic** » lun. 21/juin/2004 12:02

je vois ou est le probleme, temp et *temp sont 2 chose differente!!

essay comme cela:

Code : Tout sélectionner

If Liste = 0 Or Liste = #NULL    ;Au cas où l'alloc n'aurait pas fonctionné... 
     Erreur.w = 1 
Else 
     *temp = @Liste 
     *temp\Prec = #NULL ;premier élément de la liste donc le pointeur sur précédent pointe sur NULL 
     *temp\Valeur = 7.4   ;valeur à la biiiip 
     For i.w=0 To 10 
          *temp2 = @*temp 
          *temp = AllocateMemory(cptalloc,SizeOf(List),0) ;un nouvel objet 
          cptalloc + 1 
          *temp2\Suiv = @*temp 
          *temp\Prec = @*temp2 
          *temp\Suiv = 0 
          *temp\Valeur = i*7.4 
     Next i 
EndIf

Anonyme2 · Message par **Anonyme2** » lun. 21/juin/2004 12:07

temp et *temp sont 2 variables différentes

essaye ce code et tu verras

Code : Tout sélectionner

*temp = 10
temp  = 20


Debug *temp
Debug temp

Tu dois définir tes variables pointeur (avec le *) comme variables basées sur une structure

Par exemple :

Code : Tout sélectionner

*temp.List

et seulement après tu auras accès aux éléments de la structure

et aussi

Code : Tout sélectionner

*temp2.List = *temp

Dans ton code tu ne devrais avoir aucun temp sans le *

La ligne

Code : Tout sélectionner

If Liste = 0 Or Liste = #NULL

doit être remplacée par

Code : Tout sélectionner

If Liste = #NULL

Car #Null = 0 dont c'est du code qui ne sert à rien.

Anonyme2 · Message par **Anonyme2** » lun. 21/juin/2004 12:08

coiffé sur le poteau par Ced

Wizard_Spike · Message par **Wizard_Spike** » lun. 21/juin/2004 12:36

En effet temp et temp2 avaient été déclarés en *temp.List et *temp2.List... Mais ce que j'avais pas compris c'est que le nom de la variable est *temp et non temp pris comme un pointeur... En cela, c'est différent du C et je me suis fait avoir.... c'est pour ça qu'on voit aussi assez souvent "@*pointeur" qui m'a choqué la première fois que je l'ai vu... je comprend mieux maintenant

Effectivement, ça fonctionne impec' maintenant merci beaucoup!!!

cederavic · Message par **cederavic** » lun. 21/juin/2004 12:38

Denis a écrit :coiffé sur le poteau par Ced