Quand on souhaite gérer des données, il est parfois intéressant (voire utile ou nécessaire) de pouvoir disposer de ces données dans l'ordre inverse de celle dans laquelle elles ont été introduites, sans que les données ne soient triées d'une manière ou d'une autre (mis à part l'ordre d'introduction)
Le principe que nous allons utiliser pour y arriver est ce que les gens habitués à la gestion de stock nomment un système L.I.F.O., qui n'est que l'acronyme de «Last In First Out», ou pour ceux qui préfèrent le français: Dernier Entré, Premier Sorti.
C'est un principe relativement simple à mettre en oeuvre, car il "suffit", dans la vie courante, de mettre les objets les uns sur les autres (de les empiler), un peu à la manière de caisses.
Le seul objet auquel on ait un accès sans risquer de tout faire tomber, c'est fatalement celui qui se trouve tout en haut de la pile…
On peut alors retirer l'objet qui est tout au dessus de la pile, puis le suivant (qui sera par conséquent devenu le nouvel objet qui est au dessus de la pile) et ainsi de suite jusqu'à ce qu'il n'y ait plus d'objets à supprimer (le dernier à partir étant celui qui repose sur le sol ou sur l'étagère, et c'est effectivement le premier qui a été mis en place).
Mais on peut aussi décider d'arrêter de retirer des objets, et d'en mettre de nouveaux (c'est ce qui se passe avec vos caleçons, si du moins vous ne choisissez pas le caleçon que vous mettez, quand votre femme ou votre mère vient ranger les caleçons qui ont été lavés).
Evidemment, il se peut très bien, en fonction de la fréquence d'arrivage de nouveaux objets, que les quelques premiers qui ont été rangés ne soient jamais retirés…
Le gros problème en informatique, c'est que, comme nous allons demander d'allouer la mémoire en vue de contenir les informations qui entrent de manière dynamique, on ne sera jamais en mesure de déterminer nous même l'adresse mémoire à laquelle se trouvent ces données…
La solution sera alors de créer une structure qui, non seulement, contiendra les données qui nous sont nécessaires (et certaines de ces données peuvent d'ailleurs être des structures qui contiennent elles-mêmes des données, selon un principe de poupées russes), mais aussi un pointeur vers l'adresse mémoire qui contient la donnée qui a été introduite juste avant.
Chaque élément qui prendra place dans une pile (comme dans toute structure «dynamique») prendra le nom, pour respecter le langage informatique, de «noeud» (node en Anglais).
Imaginons quelques instants que nous souhaitions disposer de la possibilité d'introduire les coordonnées de nos connaissances, contacts et amis.
Pour faire simple, nous considérerons que les coordonnées en question sont le nom, le prénom, et l'adresse.
Toujours dans un soucis de simplicité, nous estimons dans cet exemple que le nom et ne prénom ne dépasseront pas 20 caractères et que l'adresse ne dépassera pas 50 caractères.
Il est très facile de créer une structure (nommons la logiquement Coordonnee) qui nous permette d'introduire ces trois informations pour un contact, sous la forme de:
| Nom | type | Commentaire |
|---|---|---|
| Nom | 20 caractères | Pour garder le nom du contact |
| Prenom | 20 caractères | Pour garder le prénom du contact |
| Adresse | 50 caractères | Pour garder l'adresse du contact |
Et dont l e code pour la créer ressemblera à s'y méprendre à:
structure Coordonnee
{
caracrere Nom[20] |
caractere Prenom[20] |
caractere Adresse[50] |
}
Il devient ensuite facile de créer une autre structure,(que nous nommerons logiquement Contact) dont un des éléments sera de type "Coordonnee" (type dont on dispose, vu qu'on vient de le créer) nommé "Data", et dont un autre élément sera un pointeur vers la structure Contact qui a été précédemment introduite (nous le nommerons logiquement "Precedent").
La forme prise par cette deuxième structure sera donc du genre de
| Nom | Type | Commentaire |
|---|---|---|
| Data | Coordonnee | permettra d'avoir le nom, le prénom et l'adresse de notre contact |
| Precedent | Contact | Pointeur qui contiendra l'adresse à laquelle trouver le contact introduit avant celui sur lequel on travaille |
Le code pour la création de cette structure ressemblera à quelque chose du genre de:
Structure Contact
{
Coordonnee Data|
Contact *Precedent |
}
nota: Au risque de me répéter encore une fois, il n'y a pas de mauvaise solution, mais seulement des solutions plus efficaces que d'autres.
Si j'ai décidé d'utiliser une structure à part pour les informations du contact, ce n'est qu'en suivant une fois de plus l'inspiration du moment, et nous aurions très bien pu décider de ne créer qu'une structure qui aurait contenu les "champs" Nom, Prenom, Adresse et le pointeur Precedent…
L'avantage que l'on peut trouver à travailler comme je l'ai fait sera, par exemple, de disposer d'une structure qui soit en mesure de récupérer ou d'envoyer les informations dans un fichier externe.
Par contre, si le but n'est pas d'utiliser un fichier externe, une structure unique ne présente aucun inconvénient majeur (d'aucuns pourraient estimer qu'il sera plus difficile de s'y retrouver, mais bon)
Pour pouvoir travailler sereinement, il faudra que l'on dispose principalement d'un pointeur (ici de type Contact) qui prenne l'adresse du dernier noeud qui a été rajouté.
Pour la manipulation de notre pile (ajout/suppression d'éléments à la pile), nous aurons également besoin d'un pointeur temporaire de travail (toujours de type Contact).
Oui, je le sais très bien, je radote… Mais j'estime nécessaire de rappeler que pour vous éviter des problèmes, il est toujours préférable d'initialiser un pointeur sur l'adresse mémoire 0(NULL) tant qu'on n'a pas déterminé avec certitude une adresse allouée sur laquel il doive pointer…
Vous serez sans doute d'accord avec moi si je vous dis que le fait de prévoir la possibilité de gérer des données sans introduire de donnée ne sert pas vraiment à grand chose…
Vous serez d'ailleurs tout aussi d'accord avec moi si je vous dis que vous aurez du mal à utiliser des données sans les avoir récupérées (d'une manière ou d'une autre) au préalable
Vous serez donc également d'accord avec moi que la première chose qu'il vous faudra sans doute faire, c'est de remplire une première fois votre pile… (oui, je sais, je viens d'enfoncer trois portes ouvertes)
Ben dans ce cas, qu'attendons nous pour le faire (si ce n'est de savoir la manière de s'y prendre)?
Le principe pour remplir notre pile sera tout simple, et utilisera un pointeur de travail temporaire.
Le shéma ci-dessous vous permettra sans doute de mieux comprendre…
Ce shéma ne présente que l'ajout de trois noeuds, mais le principe reste bien évidemment identique qu'il s'agisse d'enempiler deux, dix ou plusieurs centaines.
Tout comme il est impossible de se passer de l'empilage, il est tout à fait impossible de se passer du dépilage (du fait de libérer la mémoire de la totalité de la pile) avant de quitter l'application, pour éviter la fuite de mémoire.
Le principe utilisé pour vider notre pile sera tout aussi simple que celui qui a été utilisé pour la remplir.
Il utilisera également un pointeur de travail temporaire:
Nous donnons à notre pointeur de travail la valeur du pointeur Precedent du premier élément disponible de la pile (ce qui correspond bien à lui donner comme valeur l'adresse du deuxième noeud).
Nous libérons la mémoire du premier noeud
Nous finissons en signalant que le noeud auquel on a acces est maintenant celui pointé par notre pointeur de travail
Il n'y a plus qu'à recommencer tant qu'il y a des noeuds à supprimer.
Pour ceux qui comprennent plus facilement s'il visualisent, le shéma ci-dessous devrait rendre la compréhension plus facile
Evidemment, le principe restera identique qu'il s'agisse de libérer la mémoire de quatre éléments comme sur le shéma ou d'en libérer dix, cent ou dix mille…
Créer une pile de données sans essayer d'accéder à ces données n'aurait strictement aucun intérêt…
Le principe de l'accès aux données sera sensiblement identique à celui du dépilage, à ceci près qu'il sera alors hors de question de supprimer les données qui n'auraient pas été sélectionnées, pas plus qu'il ne serait question de modifier la valeur du pointeur de référence.
Tout le travail utilisera alors un pointeur de travail temporaire, qui parcourrera la pile à la recherche de l'élément qui nous intéresse:
Le pointeur de travail temporaire prendra alors la valeur de notre pointeur de référence et servira à vérifier si les données sont celles qui nous intéressent
Si les données ne nous intéresserent pas, le pointeur de travail prendra alors la valeur de l'adresse pointée par Precedent, de manière à accéder à ce nouvel élément
Nous retrounons dans la boucle jusqu'à ce que l'on trouve les valeurs qui nous intéressent ou que la valeur de notre pointeur de travail soit 0(NULL), ce qui représente la fin de la pile.
Voici le dernier petit shéma de principe (du moins, en ce qui concerne la pile) qui peut vous permettre de comprendre plus facilement.
Il serait tout à fait possible d'envisager une application qui empilerait dix élements (traiterait ces données), puis en supprimerait trois (retraitement éventuel), en rajouterais cinq nouveaux (nouveau traitement), pour en retirer quatre (encore retraitement), avant d'en rajouter six, etc avant de finir en libérant la mémoire de toute la pile…
Les données auxquelles l'application aurait accès ressembleraient alors à ceci:
Maintenant que ces différents principes sont acquis, il est peut être temps de s'attaquer aux nassichneiderman qui en permettent la mise en oeuvre…
Encore une fois, les nassichneiderman que je vous présente n'ont absolument pas la prétention d'être les meilleurs, mais simplement celle de fonctionner, et suivent en grande partie l'inspiration du moment.
J'ai, dans ce cas, estimé préférable de travailler carrément avec trois routines qui reçoivent comme argument un pointeur vers notre pointeur de référence (qui peut etre nul si la pile est vide) et qui renverront un pointeur vers la structure sélectionnée
Cette routine servira, vous vous en rendez surment compte, à empiler les éléments de la pile.
Le terme Tant que données représente ici un test qui provoquera l'entrée dans la boucle tant qu'il y aura des données fournies à placer dans l'élément à créer (le test en lui même étant à adapter en fonction de l'application), ce qui pourrait se traduire par la réussite de lecture dans un fichier.
Il serait tout à fait envisageable d'utiliser une boucle de type "jusque" si l'introduction des informations devait se faire par exemple, par introduction clavier (avec proposition du choix de continuer)
La variable ok quant à elle permet de s'assurer que l'allocation mémoire précédente (s'il y en a eu une) s'est bien déroulée. Il est en effet inutile de continuer à vouloir allouer de la mémoire pour donner des valeurs dès le moment où une allocation a échoué…
Cette routine aura pour but de vider intégralement la pile, mais il suffirait d'adapter le test de la boucle "jusque", en ajoutant une condition pour qu'elle ne retire de la file qu'un nombre donné d'éléments, ou que les éléments qui se ont été introduits avant celui dont un champs a une valeur donnée.
nota:Il est primordial, si vous adaptez le test de laisser le test de base vérifiant la valeur de actuel, car il s'agit de s'assurer que la boucle sera quittée si on vient à retirer le dernier élément présent dans la pile.
Cette routine est une simple boucle qui recherche l'élément de la pile qui correspond à nos souhaits (représenté par pas trouvé).
Evidemment, la boucle doit d'office être quittée une fois que tous les éléments de la pile ont étés testés…
Important Cette routine ne doit en aucun cas servir à la redéfinition du pointeur de référence (sous peine de perdre le "bout" de la pile, ce qui provoquerait des problèmes majeurs)
Les seules routines qui doivent permettre la modification du pointeur de référence (celui qu'on retrouvera dans la routine principale) sont celles qui gèrent l'allocation et/ou la libération de mémoire pour les différents éléments de la pile
Il est bien sûr envisageable de créer un algorithme qui permettrait le tri des données, mais le principe même de la pile (le dernier ajouté est le premier à partir) rend la manoeuvre inutile.
Essayer de l'implémenter dénoterait la totale incompréhesion du but recherché en utilisant la pile.
Eneffet, le but premier de la pile est de pouvoir répérer les données dans l'ordre inverse de celui dans lequel elles ont éées introduites…
Rien n'empêcherait d'essayer directement d'accéder au Nième élément de la pile avec un code qui ressemblerait à
trouve=Dernier->precedent->precedent->precedent//accède au troisième élément de la pile
mais à la condition expresse que l'on se soit assuré qu'il y ai effectivement un nombre suffisant d'éléments dans la pile (sous peine de provoquer un plantage de l'application)
Copyright (©) 2005 (Philippe Dunski)
Ce cours est libre, vous pouvez le redistribuer et/ou le modifier selon les termes de la Licence Publique Générale GNU publiée par la Free Software Foundation (version 2 ou bien toute autre version ultérieure choisie par vous).
Ce cours est distribué car potentiellement utile, mais SANS AUCUNE GARANTIE, ni explicite ni implicite, y compris les garanties de commercialisation ou d'adaptation dans un but spécifique. Reportez-vous à la Licence Publique Générale GNU pour plus de détails.
Cependant, l'auteur apprécierait grandement que vous lui fassiez part de toute modification apportée à son contnu
Vous pouvez le contacter par mail à l'adresse koala01@free.fr
Vous pouvez trouver une adaptation française de la licence GNU/GPL à l'URL http://www.linux-france.org/article/these/gpl.html