© Éditions Eyrolles
201
chapitre n° 11
La gestion dynamique de la mémoire
Si l’on n’a pas besoin d’accéder directement à chacun des éléments, on peut se contenter de
constituer ce que l’on nomme une « liste chaînée », dans laquelle :
●
un pointeur désigne le premier élément ;
●
chaque élément comporte un pointeur sur l’élément suivant.
Dans ce cas, les emplacements des différents éléments peuvent être alloués de façon dynamique,
au fur et à mesure des besoins. Il n’est plus nécessaire de connaître d’avance leur nombre ou une
valeur maximale (ce qui serait le cas si l’on créait un tableau de tels éléments).
Appliquons cela à des éléments de type point, structure comportant les champs suivants :
struct point { int num ;
float x ;
float y ;
} ;
Chaque élément doit donc contenir un pointeur sur un élément de même type. Il y a là une
récursivité des déclarations qui est autorisée en C. Ainsi, nous pourrons adapter notre précédente
structure de la manière suivante :
struct element { int num ;
float x ;
float y ;
struct element * suivant ;
} ;
Vous voyez que nous avons été amené à utiliser dans la description du modèle element un
pointeur sur ce même modèle.
Supposons que nous cherchions à constituer notre liste chaînée à partir d’informations fournies
en données. Deux possibilités s’offrent à nous :
●
ajouter chaque nouvel élément à la fin de la liste. Le parcours ultérieur de la liste se fera
alors dans le même ordre que celui dans lequel les données ont été introduites.
●
ajouter chaque nouvel élément au début de la liste. Le parcours ultérieur de la liste se fera
alors dans l’ordre inverse de celui dans lequel les données ont été introduites.
Nous avons choisi ici de programmer la seconde méthode, laquelle se révèle légèrement plus
simple que la deuxième.
Notez que le dernier élément de la liste (donc, dans notre cas, le premier lu) ne pointera sur
rien. Or, lorsque nous chercherons ensuite à utiliser notre liste, il nous faudra être en mesure
de savoir où elle s’arrête. Certes, nous pourrions, à cet effet, conserver l’adresse de son dernier élément. Mais il est plus simple d’attribuer au champ suivant de ce dernier élément une
valeur fictive dont on sait qu’elle ne peut apparaître par ailleurs. La valeur NULL (0) fait très
bien l’affaire.
Delannoy Livre.book Page 201 Mercredi, 6. mai 2009 4:26 16
201
chapitre n° 11
La gestion dynamique de la mémoire
Si l’on n’a pas besoin d’accéder directement à chacun des éléments, on peut se contenter de
constituer ce que l’on nomme une « liste chaînée », dans laquelle :
●
un pointeur désigne le premier élément ;
●
chaque élément comporte un pointeur sur l’élément suivant.
Dans ce cas, les emplacements des différents éléments peuvent être alloués de façon dynamique,
au fur et à mesure des besoins. Il n’est plus nécessaire de connaître d’avance leur nombre ou une
valeur maximale (ce qui serait le cas si l’on créait un tableau de tels éléments).
Appliquons cela à des éléments de type point, structure comportant les champs suivants :
struct point { int num ;
float x ;
float y ;
} ;
Chaque élément doit donc contenir un pointeur sur un élément de même type. Il y a là une
récursivité des déclarations qui est autorisée en C. Ainsi, nous pourrons adapter notre précédente
structure de la manière suivante :
struct element { int num ;
float x ;
float y ;
struct element * suivant ;
} ;
Vous voyez que nous avons été amené à utiliser dans la description du modèle element un
pointeur sur ce même modèle.
Supposons que nous cherchions à constituer notre liste chaînée à partir d’informations fournies
en données. Deux possibilités s’offrent à nous :
●
ajouter chaque nouvel élément à la fin de la liste. Le parcours ultérieur de la liste se fera
alors dans le même ordre que celui dans lequel les données ont été introduites.
●
ajouter chaque nouvel élément au début de la liste. Le parcours ultérieur de la liste se fera
alors dans l’ordre inverse de celui dans lequel les données ont été introduites.
Nous avons choisi ici de programmer la seconde méthode, laquelle se révèle légèrement plus
simple que la deuxième.
Notez que le dernier élément de la liste (donc, dans notre cas, le premier lu) ne pointera sur
rien. Or, lorsque nous chercherons ensuite à utiliser notre liste, il nous faudra être en mesure
de savoir où elle s’arrête. Certes, nous pourrions, à cet effet, conserver l’adresse de son dernier élément. Mais il est plus simple d’attribuer au champ suivant de ce dernier élément une
valeur fictive dont on sait qu’elle ne peut apparaître par ailleurs. La valeur NULL (0) fait très
bien l’affaire.
Delannoy Livre.book Page 201 Mercredi, 6. mai 2009 4:26 16