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 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 F.I.F.O., qui n'est que l'acronyme de «First In First Out», ou pour ceux qui préfèrent le français: Premier Entré, Premier Sorti.
Ce principe est très souvent mis en oeuvre, parfois sans même s'en rendre compte, dans la vie courante:
Chaque fois que vous vous trouvez dans une file d'attente, aux caisses d'un magasin, à un payage autoroutier, à l'entrée d'un cinema ou devant le guichet de votre banque, vous vous trouvez dans un sytème de type FIFO…
Si quelqu'un rentre dans la file après vous, il aura naturellement la position après la vôtre, et vous ne serez servi qu'une fois que tous ceux qui était dans la file avant vous auront été servis.
Contrairement à la pile, nous pouvons être sûr que tout le monde finira par passer, dans l'ordre précis dans laquelle ils seront entrés dans la file.
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 contiendra la donnée qui a été introduite juste après, ou une adresse nulle en attendant qu'un élément suivant soit rajouté à la file.
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 sera introduite juste après (nous le nommerons logiquement "Suivant").
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 |
| Suivant | 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 *Suivant |
}
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, c'est principalement afin de garder une certaine "cohérence entre les différents chapitres de cette section… Mais les remarques faites sur les strucutres même des piles restent parfaitement d'application
Pour pouvoir travailler sereinement, il faudra que l'on dispose principalement d'un pointeur (ici de type Contact) qui prenne l'adresse du premier élément qui a été introduit (le début de la file).
Pour la manipulation de notre file (ajout/suppression d'éléments à la file), nous aurons également besoin d'un pointeur temporaire de travail (toujours de type Contact).
Il peut aussi s'avérer particulièrement utile de disposer d'un dernier pointeur, toujours de type contact, pour les séquences d'ajout d'éléments.
Ce pointeur aurait en permanence l'adresse du dernier élément de la file, et permettrait l'ajout immédiat, sans nécessiter de reparcourir l'intégralité de la file, ce qui risque à la longue de prendre énormément de temps.
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…
C'est d'autant plus nécessaire du fait que, au moment où l'on introduit un élément, l'élément suivant n'existe pas encore.
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 file… (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 schéma ci-dessous vous permettra peut être de mieux comprendre:
Bien évidemment, ce shéma ne présente que l'ajout de trois éléments, mais le principe resterait exactement le même s'il s'agissait d'enfiler deux, dix ou des centaines d'éléments.
De plus, ce schéma représente l'utilisation d'un pointeur gardant en mémoire la fin de la file (ce qui permet d'éviter d'avoir à reparcourrir toute la file lors de l'ajout, afin de trouver le dernier élément)
Tout comme il est impossible de se passer de l'emfilage, il est tout à fait impossible de se passer du défilage (du fait de libérer la mémoire de la totalité de la file) avant de quitter l'application, pour éviter la fuite de mémoire.
Le principe utilisé pour vider notre file sera tout aussi simple que celui qui a été utilisé pour la remplir.
Il utilisera également un pointeur de travail temporaire:
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 le même qu'il s'agisse de libérer la mémoire de deux, de dix ou de cent éléments de la file.
Créer une file 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éfilage, à 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 file à la recherche de l'élément qui nous intéresse:
Voici le dernier petit shéma de principe (du moins, en ce qui concerne la file) qui peut vous permettre de comprendre plus facilement.
Il serait tout à fait possible d'envisager une application qui enfilerait dix éléments (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 file…
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.
Les nassichneiderman ont été créés dans l'idée de l'existance de deux pointeurs du type de la structures déclarés globalement, et définis à la base à 0(NULL):
Comme je l'ai déjà fait remarqué, l'utilisation de variables globales n'est pas vraiment recommandée, mais, dans le cas de ces nassichneiderman, qui n'ont pour seul but de vous présenter le principe, elle me permettait d'éviter le recours aux pointeurs de pointeurs, qui n'aurait eu comme seul résultat de rendre le nassichneiderman un peu plus nébuleux…
Ceci dit, dés le moment où il s'agit de mettre une file en oeuvre dans une application réelle, l'utilisation de variables locales et de pointeurs de pointeurs peut s'avérer précieuse 
Cette procédure servira, vous vous en rendez surment compte, à ajouter des éléments à la file.
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é…
La première chose à faire est bien évidemment d'allouer de la mémoire pour l'élément que l'on souhaite ajouter à la pile et de s'assurer que l'allocation s'est bien déroulée.
Comme nous avons remarqué dans le principe que deux cas de figure sont possibles, selon qu'il y ait déjà un élément dans la file ou non, la première chose à faire est de s'assurer de l'existance éventuelle de cet élément.
Si Premier pointe sur 0(NULL), il n'y a pas d'élément, et donc il faut faire pointer Premier et Dernier sur notre pointeur de travail.
Si, par contre, Premier pointe sur un élément de la file, c'est qu'on sera déjà passé une fois dans le test, et donc, nous somme sûrs que Dernier a déjà une valeur qui nous permette d'accéder à son champs Suivant.
Nous pouvons donc sans risque faire pointer le champs Suivant de dernier sur notre pointeur de travail avant de faire pointer Dernier lui-même dessus.
Nota: L'ordre de travail a ici une réelle importance…
Si nous avions interverti les deux instructions, le champs Suivant de notre pointeur de travail aurait pointé sur… lui-même, et nous aurions "de facto" perdu la fin de la file.
De plus, notre pointeur de travail n'aurait pas été relié à la file (car Dernier représente… le dernier élément de la file (ou si vous préférez: l'élément qui a été rajouté à la file juste avant celui sur lequel on travaille actuellement)
Il ne reste plus qu'à s'assurer de fournir les données à mettre en file.
Nota: rien n'aurait interdit de fournir les données à mettre en file avant de relier notre pointeur de travail à la file, mais l'introduction des données ne peut se faire QUE si l'allocation de mémoire a réussi.
Cette routine aura, vous vous en seriez douté, comme objectif de vider la file.
Telle qu'elle est représentée ici, elle videra intégralement la file, mais il suffirait d'adapter le test de la boucle "tant que", 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.
La première chose qui est faite est de vérifier que Premier n'est pas égal à 0(NULL), condition éventuellement adaptable, qui définit si la boucle doit être effectuée ou non. Si la boucle est effectuée:
nota: Il est primordial, si vous adaptez le test de laisser le test de base vérifiant que premier n'est pas égal à 0 (NULL), 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 file.
L'ordre d'exécution des instructions a, ici aussi, une importance capitale…
En effet, si les instructions venaient à être interverties (libération de la mémoire avant d'avoir récupéré l'adresse de l'élément suivant, par exemple) vous seriez incapable de retrouver le nouveau point de départ de la file…
Cette routine est une simple boucle qui recherche l'élément de la file qui correspond à nos souhaits (représenté par pas trouvé).
La recherche peut s'axer sur le Nième élément de la file, ou sur une valeur donnée d'un des éléments de la structure, mais, pour que cela s'adapte de manière cohérente, il est préférable de transmettre la valeur recherchée en parametre de la fonction…
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 "début" de la file, 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 file .
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 file (le premier 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 file.
En effet, le but premier de la pile est de pouvoir répérer les données dans l'ordre dans lequel elles ont éées introduites…
Rien n'empêcherait d'essayer directement d'accéder au Nième élément de la file avec un code qui ressemblerait à
trouve=Premier->suivant->suivant->suivant //accède au troisième élément de la file
mais à la condition expresse que l'on se soit assuré qu'il y ai effectivement un nombre suffisant d'éléments dans la file (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