Liste chaînée

Les listes chaînées s'avérent très pratiques dans certains types de problèmes que l'on a souvent tendance à résoudre par l'utilisation d'un tableau. Par exemple, s'il faut conserver une liste ordonnée, selon un critère précis, d'éléments et qu'il faut fréquement introduire un nouvel élément à sa place dans la liste.

Supposons qu'on dispose d'un type maillon et qu'on souhaite établir une liste chaînée (pour définir une courbe ) d'éléments de ce type. Il est nécessaire alors que chaque élément comporte un pointeur sur l'élément suivant.

       Module maillonmod
          Implicit None  
          !=======================
          ! Declaration du type
          !=======================
          Type maillon
             Integer              :: index
             Real                 :: valeur
             Type(maillon), Pointer :: suivant
          End Type maillon 
       End module maillonmod

On a ainsi créé une structure de type maillon contenant trois champs : index, valeur et suivant qui est un pointer succeptible d'être associé à une autre structure de type maillon (ouf).

 
PROGRAM liste_chainee
  !==============
  ! Les modules
  !==============
  USE module_tp_maillon
  IMPLICIT NONE  
  INTERFACE
      SUBROUTINE lister(debut)
          USE maillonmod
          TYPE(maillon), POINTER ::debut
      END SUBROUTINE lister
  END INTERFACE
  TYPE (maillon), POINTER :: premier, courant, auxp
  !
  !===================
  ! Debut du programme
  !===================
  !
  ALLOCATE (premier)
  premier%valeur = 2.
  premier%index = 2 
  NULLIFY(premier%suivant)
  ! --------------------------------
  ! Ajout d'un element fin de liste
  ! --------------------------------
  ALLOCATE(courant) 
  courant%valeur = 3.
  courant%index = 3      
  NULLIFY(courant%suivant)
  premier%suivant => courant
  ! -------------------------------------
  ! Ajouter element  au debut de la liste
  !--------------------------------------
  ALLOCATE(courant)  
  courant%valeur = 1.
  courant%index = 1    
  courant%suivant => premier
  premier => courant
  ! -------------------------------------
  ! Ajouter element  en queue  de la liste
  !--------------------------------------
  ALLOCATE(auxp)  
  auxp%valeur = 4.
  auxp%index = 4   
  NULLIFY(auxp%suivant)
  !
  ! on parcout la liste jusqu a la fin, puis insertion
  !
  courant => premier
  DO 
     IF (.NOT.ASSOCIATED (courant%suivant)) THEN 
      	courant%suivant => auxp
        EXIT
     ELSE
        courant=> courant%suivant
     ENDIF
  END DO
  !--------------------
  ! Affiche de la liste
  !--------------------
  CALL lister(premier)
END PROGRAM liste_chainee

 
SUBROUTINE lister(debut)
  USE maillonmod
   TYPE(maillon), POINTER :: debut, courant   
   ! -------------------------------
   ! affichage des index de la liste
   ! -------------------------------
    courant => debut
    DO 
      WRITE (*,*) 'courant%index:', courant%index
      IF (.NOT.ASSOCIATED (courant%suivant)) EXIT
         courant => courant%suivant
    END DO
END SUBROUTINE lister

Ainsi nous avons créé une liste chaînée repérée uniquement par le premier élément nommé 'premier' qui indique le début de la liste.

Quelques précisions:

 
       ALLOCATE (premier)

alloue un emplacement mémoire pour un type maillon, puis il associe cet emplacement au pointeur ( premier).

 
       NULLIFY(premier%suivant)

précise que le pointeur premier$\%$suivant est associé à une valeur particulière le pointeur nul. Par contre, si on ne précise pas cet état, alors la valeur de premier$\%$suivant est indéfini et dans ce cas on ne peut pas par exemple répérer la fin d'une liste.

Il est possible de savoir si un pointeur a été associé à une cible ou non. L'expression

 
       ASSOCIATED(courant%suivant)

fournit la valeur .TRUE. si une cible a été associée et .FALSE. sinon. Dire que le pointeur n'est pas associé à une cible veut dire qu'il est associé à l'état NUL.