19 structures de données dynamiques
On peut maintenant définir des structures de données dynamiques, c'est à
dire dont la structure évolue au cours du temps. Il est gênant de définir
une pile avec un tableau : d'une part, cela borne sa taille 12 et d'autre
part une pile vide occupera autant d'espace qu'une pile pleine... Il vaut
mieux allouer de l'espace mémoire au fur et à mesure des besoins : ajouter
un élément à la pile correspondra à allouer (avec new) de la
mémoire et supprimer reviendra à désallouer l'emplacement de l'objet. Le
contenu de la pile sera donc éclaté dans la mémoire (car les appels
successifs à new n'alloue pas forcément des zones contigues) et il
suffit pour ne pas perdre nos éléments d'indiquer à chaque élément de pile
où (l'adresse) se trouve le prochain élément (0 si il n'y en a pas). Cela
correspond à la notion de liste chaînée.
Un élément de pile d'entiers sera donc un objet de la forme :
struct element {
int val;
element * suivant;
};
c'est-à-dire un couple comprenant un entier (la valeur à stocker dans la
pile) et un pointeur sur le prochain élément de la pile. la classe
pile devient alors juste une classe avec un seul champ de type
element * correspond à l'adresse de la tête de pile. Voir le TD
sur les pointeurs sur la page web.