Je suppose que vous êtes en train de vous dire que ce que je raconte est bien amusant (quoique!), mais que nous ne sommes guère plus avancés, vu que pour l'instant, il faut déclarer autant de pointeurs que de variables dont on aura besoin... d'où un intérêt plutôt limité et une perte de temps évidente, même si c'est cool de réserver de la place soi-même... ce qui serait bien, ce serait de déclarer une seule variable de type pointeur dans le VAR et de pouvoir à partir de cette dernière en créer autant qu'on en veut... ça sent le récursif, tout ça, vous trouvez pas ?
Allez, c'est parti :
type TDonnee=integer;
type PCellule = ^Cellule;
Cellule = record
nb:TDonnee;
next:Pcellule;
end;
Analysons un peu ce qui vient d'être écrit : un pointeur de type PCellule va pointer sur une structure contenant une donnée (du type que l'on veut) et un pointeur sur une autre Cellule (appellée également noeud dans la plupart des livres...) ; Cette structure permet la chose suivante : Le premier élément de la liste comportera un pointeur sur la deuxieme cellule, le deuxième comportera un pointeur sur la troisième cellule et ainsi de suite jusqu'au dernier élément dont le pointeur vaudra NIL, ce qui indiquera la fin de la chaîne de cellule.
Exemple concret ("fait à la main") :
Soit ptr une variable déclarée comme un pointeur de type PCellule.
new(ptr); (* on crée une variable dynamique structurée *) ptr^.nb:=1; (* on affecte la partie donnée *)
ATTENTION,CA SE COMPLIQUE !!! (comme beaucoup de choses récursives !) Remarquez que ptr^.next est lui aussi un pointeur (errant pour le moment) du même type que ptr ; On peut donc lui assigner (si bien entendu il reste de la place sur le heap) une nouvelle variable dynamique ; ceci se fait naturellement de la façon suivante :
new(ptr^.next);
ptr^.next pointe donc à son tour sur un variable (dynamique) structurée ptr^.next^ semblable à ptr^ (c'est à dire à celle pointée par ptr).
On peut également lui affecter sa donnée :
ptr^.next^.nb:=2;
on peut continuer ainsi jusqu'à remplir le heap :
new(ptr^.next^.next);
Remarquez que la notation devient vite très lourde...
Pour se représenter une liste chaînée (c'est le nom qu'on leur donne), un bon moyen est de penser aux poupées russes qui s'emboitent les unes dans les autres, car, de même que pour obtenir la dernière poupée il faut toutes les ouvrir, pour accéder à la cellule n, il faut lire son adresse (=récupérer son pointeur) dans la cellule n-1...
Avant de passer aux algorithmes (récursifs, bien sûr !) permettant d'alléger la gestion de tout ça, je voudrais attirer votre attention sur la difficulté de gérer ces variables chaînées... Prenons l'exemple de la suppression d'une liste chaînée de deux éléments : il faut les supprimer en partant de la fin...
En effet : si vous détruisez ptr avec un dispose(ptr), vous perdez la trace de ptr^.next^ (car ptr^ n'existe plus !) et vous ne pouvez donc plus supprimer ptr^.next^, ne connaissant plus son adresse (qui se trouvait dans ptr^). La phrase précédente est un peu lourde, je m'en excuse ;-)
Ce qui est dit précédemment implique également le fait qu'IL NE FAUT JAMAIS PERDRE LE POINTEUR DE LA PREMIERE CELLULE.
D'ailleurs, dans les algos, nous travaillons toujours depuis la première cellule.
Dernier détail : le dernier élément d'une liste chaînée doit pointer sur NIL pour les deux raisons suivantes :
Voici le programme Pascal commenté contenant les fonctions usuelles pour traiter les listes chaînées... Si tout va bien, vous devriez le retrouver en Annexe (en version non commentée) avec les autres sources... (au pire, je vous laisse le soin d'en faire l'extraction à la main !)
Voir Listing 1, commenté..
Je vous conseille de tracer à la main sur du papier (en dessinant des boites avec leur contenu [les cellules] et des flèches [les pointeurs]) les trois dernières procédures pour bien comprendre leur fonctionnement récursif.
De toute façon, la mise en oeuvre est relativement simple, l'essentiel du code étant constitué de manipulations de pointeurs qui deviennent triviales dès que vous visualisez bien le principe de chaînage des noeuds... Par exemple, pour la suppression d'une cellule, il suffit de "sauter" le noeud à effacer et faire pointer le noeud précédent sur le noeud suivant... (faire en quelque sorte une coupure de chaque coté d'une cellule puis "recoller" les deux bouts de la chaîne...) Une fois ceci fait, le noeud désolidarisé de la liste peut être effacé !
Notez par ailleurs que les routines permettent de gérer plusieurs listes chaînées à la fois; il suffit pour cela d'utiliser plusieurs pointeurs.
N'oubliez pas que l'effacement du premier noeud ne détruit pas la structure... Au pire, si l'effacement est mal fait, vous perdez trace de la seconde cellule (et par conséquent des suivantes !), mais elles sont toujours en mémoire, même si elles sont devenues inaccessibles.
Une application possible des listes chaînées est le calcul en multi-précision (c'est à dire avec autant de chiffres qu'on le veut) en mettant un chiffre par cellule et en représentant chaque nombre par une liste chaînée...
Comme nous l'avons vu, le gros problème des listes chaînées est que si l'on perd le pointeur de la première cellule (en passant par ex. de façon maladroite à la suivante par une affectation du genre l:=l^.next), il devient impossible de la retrouver ; Il existe pour éviter ce genre de problème une structure qui permet de se promener librement sur la chaîne sans jamais en perdre un bout ; Cette structure, similaire à la précédente se nomme Liste Doublement Chaînée ; La principale différence se situe dans la structure d'une cellule : chaque cellule contient deux pointeurs :
Voici un programme qui permettrait de gérer des listes doublement chaînées... Vous le retrouverez également en annexe... Les commentaires seront ici plus rares
Voir Listing 2, commenté..
Voilà ! C'est tout pour les listes chaînées... Notez que les deux petits programmes fournis sont parfaitement incomplets (surtout le deuxième qu'il faut plus prendre comme quelque chose destiné à donner une idée des complications qu'entraine le double chaînage...). Il manque en particulier des tests concernant la place disponible sur le tas. Vous pourrez vous-même programmer des fonctions de recherche et de tri (le travail n'est pas mal maché dans le cas d'un tri par insertion, je crois...). En gros, vous avez maintenant les bases, tout reste à faire (à moins qu'un gentil ROR se dévoue dans un prochain article...).
Il ne nous reste plus à voir pour aujourd'hui les structures de données classiques que sont les piles (encore appelées LIFO) et les files d'attentes (appelées quant à elles LILO)