Les structures récursives (mise en œuvre de listes, …)

Un tableau constitue un moyen efficace de stocker et d’accéder à l’information. Mais, pour déclarer une variable de type tableau, il faut impérativement connaître la taille de ce tableau (le nombre d’objets à ranger). Et de plus, cette taille ne peut pas changer durant l’exécution.

La solution la plus souple marie pointeurs, structures et allocation dynamique (malloc) dans le tas.

D'abord, la définition de la cellule

Une liste linéaire est formée de cellules, chacune comportant une valeur d’un certain type. Un pointeur de tête pointe sur une première cellule (sauf si la liste est vide). Cette cellule est soit suivie d’une deuxième cellule, soit elle est la dernière.

De façon récursive, une liste est soit vide, soit est formée d’une cellule suivie d’une liste.

Voici la déclaration d’une cellule d’entier.

struct cellule {

int valeur ;

struct cellule *suivant ;

}

Notez que la déclaration de cellule introduite un champ pointeur sur une cellule.

Attention La déclaration suivante est illicite : struct cellule { int valeur ; struct cellule suivant ; } /* Le champ ne peut pas du type structure que l'on est en train de définir. */

Déclaration incomplète de structure Attention au phénomène suivant : Pour éviter ce genre d’erreurs, utilisez une déclaration incomplète de structure, qui masquera la déclaration globale.

Et maintenant, la liste.

Il est nécessaire de conserver à tout moment l’adresse de la première cellule dans une variable que l’on peut appeler tête et qui sera un pointeur sur une cellule. Dans la dernière cellule, l’adresse du suivant sera mise à NULL.

A chaque fois que l’on a besoin de rajouter une nouvelle cellule à une liste, il suffit d’effectuer une allocation mémoire (par l’intermédiaire de la fonction malloc) en lui passant en paramètre la taille d’une cellule. Voici comment aurait pu être créée la liste de la figure précédente :

#define 0

main () {

struct cellule {

int valeur ;

struct cellule *suivant ;

};

struct cellule * tete, courant ;

tete = malloc (sizeof (struct cellule)) ; /* on crée la 1ère cellule */

/* plus besoin avec ANSI C d'écrire struct cellule malloc (sizeof (struct cellule)) */

courant = tete; courant -> valeur = 10;

courant -> suivant  = malloc (sizeof (struct cellule)) ; /* on en crée une seconde chaînée à la précédente */

courant -> courant -> suivant ; courant -> valeur = 5;

courant -> suivant  = malloc (sizeof (struct cellule)) ; /* on en crée une troisième chaînée à la précédente */

courant -> courant -> suivant ; courant -> valeur = 76;

 courant -> suivant  = malloc (sizeof (struct cellule)) ; /* on en crée unedernière chaînée à la précédente */

courant -> courant -> suivant ; courant -> valeur = 4;

courant -> suivant  = NULL;   /* come c'est la dernière , on met NULL dans le champ suivant */

/* et on l'imprime */

courant = tete ;

while (courant != NULL) {

printf ("valeur = %5d \n", courant -> valeur) ;

courant -> courant -> suivant ;

}

}

L’exemple suivant demande à l’utilisateur d'entrer une suite de nombres strictement positifs, suite terminée par 0 , et de ranger ces nombres dans une liste en insérant à chaque fois la nouvelle cellule en tête de liste (c'est une liste Dernier arrivé - Premier servi (Last In First Out) :

struct cellule {

int valeur ;

struct cellule *suivant ;

};

/* créer une cellule dont la valeur est positionnée à l'aide du nombre passé en paramère */