Une liste est une séquence1 de zéro ou plusieurs éléments (de même type). Si la liste ne comprend pas d'élément on dira qu'elle est vide.
1. Par séquence, on entend que les éléménts ne sont accessibles que successivement, l'un après l'autre. Ce mode d'accès est fondamentalement différent de celui des éléments d'un tableau : chaque éléments est accessible individuellement et directement (c'est-à-dire sans avoir à accéder à l'élément précédent) une fois connu son rang, c'est-à-dire la valeur de l'indice.
La structure de donnée d'un élément de liste est conceptuellement simple :
le champ "clé2" contient la "valeur-clé" (c'est-à-dire l'information qui nous intéresse) de l'élément, le type exact de cette valeur-clé est sans importance ; un élément de liste peut, bien sûr, comporter d'autres champs,
2. Le mot "clé" servira souvent dans cet exposé, il nous permettra de singulariser, dans un groupe de valeurs, celle qui nous importe dans le traitement en cours ; par exemple ce pourra être le nom d'une fiche d'étudiant.
un moyen pour accéder à l'élément suivant (chaînage ou autre). Par exemple, si les éléments de la liste sont rangés de manière contiguë dans un tableau, le moyen pour accéder à l'élément suivant l'élément d'indice k est e considérer l'élément d'indice k+1 ; l'accès est simple, par contre il est difficile de modifier la liste. Le plus souvent, le moyen pour accéder à l'élément est fourni par un champ "pointeur3 vers l'élément suivant" qui avec le, ou les, champ "clé" et "autres" constitue l'agrégat "élément de liste"; on est alors en présence d'une "liste chaînée". Le champ "pointeur vers l'élément suivant" du dernier élément d'une liste chaînée contient une valeur conventielle "NIL" indiquant qu'il ne pointe vers rien. On peut concevoir des structures moins simples : liste doublement chaînée (chaque élément comporte deux pointeurs : un vers l'élément suivant, l'autre vers l'élément précédant), liste circulaire (le dernier élément pointe vers le premier)... Le choix du mode de chaînage sera conditionné par la nature du problème à traiter.
3. Le mot "pointeur" sera employé ici avec un sens plus large que celui couramment accepté dans les langages de programmation, ce sera ici : information donnant la position d'un objet ; il pourra donc aussi bien désigner un pointeur au sens habituel (≈ adresse mémoire), qu'un indice dans le cas où l'objet considéré est stocké dans un tableau.
Exemple d'élément de liste :
TYPE ty_fiche_d_étudiant = agrégat_de nom, prénom : textuels, âge : numérique, curriculum : textuels, note_d'informatique : numérique, fin_agrégat ty_fiche_d_étudiant ;
Pour faciliter la compréhension des algorithmes, nous restreindrons au mode de représentation en listes chaînées (rappelons qu'on représentera clé(p) le champ clé de l'élément_de_liste désigné par le pointeur p).
Pour définir une liste, il faut connaître le type des éléments de la liste ; il faut aussi connaître le premier élément ("tête de liste"), le moyen le plus simple est de disposer d'un "pointeur de tête de liste" qui pointe vers ce premier élément.
Liste chaînée : structure de données
TYPE ty_élément_de_liste = agrégat_de clé : ty_clé, le type exact est, ici, de peu d'importance suivant_de : pointeur_vers ty_élément_de_liste autres : "autres informations" éventuellement fin_agrégat ty_élément_de_liste; VARIABLE /* pointe vers le premier élément */ Hd_ptr : pointeur_vers ty_élément_de_liste
Nous choisissons, arbitrairement, de nous intéresser aux 3 opérations élémentaires sur les listes suivantes :
par exemple, recherche d'une fiche_d_etudiant dont on donne le nom
On suppose qu'on considère :
On cherche la place dans cette liste de "x", du type ty_clé ; c.à-d. la valeur du pointeur p tel que x clé(p) et que clé(précédent_de(p)) < x
N.B. Ici la notation "précédent_de(p)" n'est qu'une notation commode pour exprimer notre pensée, elle n'implique pas que l'on dispose d'une liste doublement chaînée, en fait on verra plus loin comment connaître l'élément qui précède l'élément pointé par p.
/* on suppose - une liste (non vide), - dont les éléments sont ordonnés par valeurs croissantes : clé(p)clé (suivant_de (p)) on cherche la place, dans cette liste de "x" de type ty_clé, c.-à-d. la valeur du pointeur "p" tel que clé(pécédent_de(p)) < x
clé (p) */
Ici encore, on évite soigneusement les cas particuliers :
/* on suppose que le pointeur "p" pointe vers un élément de la liste tel que */ psuivant_de(p) si clé (p)
x alors /* on a trouvé "p" */ sinon /* il faut réitérer */ car l'hypothèse, vraie au début, est toujours vérifiée fin_si
Cette recherche peut servir :
/* on suppose que le pointeur "p" pointe vers un élément de la liste tel que clé(p) < x et "pp" pointe vers l'élément précédent de celui pointé par p */ ppp p
suivant_de(p) si clé (p)
x alors /* on a trouvé "p" et "pp"*/ sinon /* il faut réitérer */ car l'hypothèse, vraie au début, est toujours vérifiée fin_si
On répète tant qu'il faut (et tant qu'on peut!), c.-à-d. :
répéter /* on suppose que le pointeur "p" pointe vers un élément de la liste tel que clé(p) < x et "pp" pointe vers l'élément précédent de celui pointé par p */ ppp p
suivant_de(p) tant que p
NIL jusqu'à clé(p)
x /* on a trouvé "p" et "pp" */ /* il faut réitérer */ car l'hypothèse vraie au début de la boucle, l'est encore fin_répéter
On traite la liste depuis son premier élément qui est pointé par Hd_ptr, il est donc normal d'initialiser : p Hd_ptr. il faut avant tout vérifier les hypothèses de début d'itération :
On traite ensuite les cas particulier : position avant le début de la liste, liste vide.
pHd_ptr si p
NIL alors si clé(p) < x alors répéter /* on suppose que le pointeur "p" pointe vers un élément de la liste tel que clé(p) < x et "pp" pointe vers l'élément précédent de celui pointé par p */ pp
p p
suivant_de(p) tant_que p
fin_répéter sinon /* x est le premier élément (ou devant le premier) */ pp
NIL donc il n'y a pas d'élément précédent jusqu'à clé(p)
x /* on a trouvé "p" et "pp" */ fin_si sinon /* la liste est vide, ==> pp n'a pas de sens */ pp
NIL en tout cas, ce n'est pas incohérent! fin_si
Une tâche accessoire : la simplification, en effet la procédure comportait 2 fois les mêmes tests : p NIL et clé(p) < x, une fois avant l'initialisation et une fois en fin de boucle pour contrôler l'itération, il suffit de contrôler l'itération en début de boucle (genre de modification à faire, en général, avec circonspection!).
Une tâche principale, spécifier l'en-tête de la procédure : liste des arguments, types, statuts, rôles (en commentaire). Il y a ici un choix à faire : quelles sont les informations que doit rendre cette procédure? La demande (floue) qui avait été formulée dans l'étape 0 était de déterminer p tel que x clé(p) et clé(précédent_de(p)) < x. En fait, la demande ne pouvait être que floue car on ne sait pas à quoi va servir cette procédure, par exemple :
Dans le premier cas, un argument booléen "trouvé" et la valeur de p feraient l'affaire, dans le second cas ce seraient les valeurs de "trouvé" et de "pp" qui nous intéresseraient.
Ici nous choisirons, arbitrairement, de rendre les valeurs de p et pp.
Enfin on explicite, si ce n'est pas évident, les "valeurs rendues par les arguments de sortie".
Procédure Rechercher ( x : ty_clé, Entréee Hd_ptr : pointeur_vers ty_élément_de_liste, Entrée; p, pp : pointeur_vers ty_élément_de_liste, Sortie) /* on cherche la place de "x" dans la liste pointée par "hd_ptr" : c.-à-d. les valeurs des pointeurs "p" et "pp" tels que clé(pp)x
clé(p) */ p
Hd_ptr pp
NIL répéter tant que p
NIL /* la liste restante est "non vide" */ jusqu'à clé(p)
x /* on a trouvé "p" et "pp" */ pp
p p
suivant_de(p) fin répéter /* en résumé, les valeurs de p et pp donnent la position de x,
*/ fin_procédure rechercher *
* Rappelons que, avec nos notations, fin_procédure indique, comme en Pascal, à la fois la fin du texte de la procédure et l'instruction de retour au programme appelant.
Précisons qu'il s'agit d'insérer dans la liste un élément qui existe déjà (par exemple, quand on change de position un élément de la liste), ce qui entraîne que l'on a pas à se préoccuper des problèmes liés à l'allocation d'espace mémoire pour cet élément. De même, lorsqu'on ôte un élément de la liste, on ne s'occupe pas de rendre au système l'espace occupé. On ne s'occupe pas, non plus, de modifier les champs "valeurs" de l'élément ; en un mot, ces fonctions ne s'occupent que de modifier les chaînages.
On se donne bien sûr des spécifications cohérentes avec celles de la procédure Rechercher (puisqu'il s'agit d'ôter ou d'insérer, on va supposer que l'on dispose de la valeur du pointeur vers l'élément précédent, telle qu'elle a pu être fournie par Rechercher)
On veut retirer un élément, celui-ci faisant partie d'une liste chaînée, il faut rétablir le chaînage ; il faut aussi pouvoir manipuler l'élément retiré, donc rendre son adresse à l'aide d'un pointeur p_O. Le schéma résume les actions à réaliser, elles sont très simples dans le cas ordinaire (qui correspond au cas de la figure) : l'élément à ôter est le suivant de celui pointé par pp ; il faut ensuite ajouter la gestion du cas particulier (ôter en tête de liste), ainsi que le cas "stupide" (liste vide : rien à ôter). Enfin, on peut remarquer qu'ôter en fin de liste n'est pas un cas particulier.
Procédure Ôter_élément ( pp : pointeur_vers ty_élément_de_liste, Entrée; Hd_ptr : pointeur_vers ty_élément_de_liste, Entrée/Sortie; p_O : pointeur_vers ty_élément_de_liste, Sortie) /* pp : pointe vers le précédent de l'élément à ôter */ /* p_O : pointe vers l'élément ôté */ /* Hd_ptr : pointeur sur la tête de liste */ /* ATTENTION ! le champ suivant_de(pp) (ou Hd_ptr) est modifié !!! */ si ppNIL alors p_O
suivant_de(p_O) si p_O
NIL alors suivant_de(pp)
suivant_de(p_O) fin_si sinon p_O
Hd_ptr si p_O
NIL alors Hd_ptr
suivant_de(p_O) fin_si fin_si fin_procédure Ôter_élément
On veut insérer l'élément pointé par p_N juste après l'élément pointé par pp
Procédure Insérer_élément ( p_N : pointeur_vers ty_élément_de_liste, Entrée; pp : pointeur_vers ty_élément_de_liste, Entrée) Hd_ptr : pointeur_vers ty_élément_de_liste, Entrée/Sortie; /* p_N : pointeur sur le nouvel élément, à insérer */ /* pp : pointe sur l'élément précédant la position d'insertion */ /* Hd_ptr : pointeur sur la tête de liste */ /* ATTENTION ! le champ suivant_de(pp) (ou Hd_ptr) est modifié !!! */ si p_NNIL alors si pp
NIL alors /* insérer au sein ou en fin de liste */ suivant_de(p_N)
suivant_de(pp) suivant_de(pp)
p_N sinon /* insérer en tête de liste */ suivant_de(p_N)
Hd_ptr Hd_ptr
p_N fin_si sinon /* ne rien faire car il n'y a rien à ajouter */ fin_si fin_procédure Insérer_élément
REMARQUES
N.B. Le fait que des pointeurs soient indiqués comme arguments d'Entrée indique seulement que ces pointeurs ne sont pas modifiés par les procédures, par contre les objets désignés par ces pointeurs peuvent être modifiés par ces procédures.
Lors de la construction de ces procédures, nous avons fait des choix plus ou moins arbitraires (en particulier dans les listes d'arguments). Ceci est dû au fait que nous avons voulu écrire ces procédures sans que leur écriture ait été rendu nécessaire par la résolution d'un problème précis. Si nous avions eu à les écrire dans le cadre d'un traitement bien défini, les en-têtes (rôles et listes d'arguments) auraient été établis avant l'écriture de procédures! Il faut aussi remarquer que les 3 procédures que nous venons de développer ne sont pas les seules possibles, par exemple, on peut avoir besoin d'une procédure qui soit la combinaison de Rechercher et Insérer_élément.
Essayons d'évaluer le "nombre d'opérations" à effectuer pour rechercher un élément dans un liste de n éléments. La réponse est assez intuitive :
Dans tous les cas la complexité, en moyenne, de l'algorithme est proportionnelle au nombre n des éléments de la liste.
Nous allons nous illustrer la représentation de listes chaînées. Nous prendrons pour exemple quelques déclarations et instructions nécessaires pour créer et gérer la liste des enfants qui participent à la comptine "Am, Stram, Gram ..."
Nous proposons quelques transcriptions des notations algorithmiques suivantes :
Déclarations :
Type ty_Enf = agrégat de p_suiv : pointeur vers ty_Enf; Nom : textuel; fin_agrégat ty_Enf; variables Hd_ptr, p, pp : pointeurs sur ty_Enf;
Partie exécutable :
"allouer 1 élément ty_Enf qui sera pointé par Hd_ptr" "allouer 1 élément ty_Enf qui sera pointé par p" créer une liste de 2 éléments p_suiv(Hd_ptr)p; p_suiv(p)
NIL; ... pp
p parcourir la liste à l'aide du pointeur p p
p_suiv(p)
Les modes de représentation de listes vont différer selon que les éléments de liste sont stockés en mémoire de façon dynamique (les éléments étant créés au fur et à mesure des besoins, chaque élément étant désigné par un pointeur) ou que les éléments sont stockés dans des tableaux statiques.
Déclarations :
const Lx_nom = 15; longueur maximale des noms type ty_p_enf = ↑ty_Enf; définition du type "éléments de liste" ty_Enf = record p_suiv : ty_p_Enf; champ "pointeur vers élément suivant" Nom : string [Lx_nom]; champ "nom" end; var Hd_ptr, p, pp : ty_p_Enf;
Partie exécutable :
new (Hd_ptr); new (p); création d'une liste de 2 éléments Hd_ptr↑.p_suiv := p; p↑.p_suiv := NIL; ... pp := p; p := p↑.p_suiv; parcourir la liste à l'aide du pointeur p
Déclarations :
const Lx_nom = 15; longueur maximale des noms Nx_Enf = 12; nombre maximal d'enfants p_Null = 0; type ty_enf_p = p_Null..Nx_Enf définition du type "pointeur de suivant" ty_pt_Enf = 1..Nx_Enf définition du type "indice d'élément de liste" ty_Enf = record définition du type "élément de liste" p_suiv : ty_Enf_p; champ "pointeur vers élément suivant" Nom : string [Lx_nom]; champ "nom" end; ty_ronde = array[ty_pt_Enf] of ty_Enf tableau de stockage des éléments de liste var Hd_ptr, p, pp : ty_Enf_p la_ronde : ty_ronde;
Partie exécutable :
Hd_ptr := 1; p := 2 création d'une liste de 2 éléments la_ronde[Hd_ptr].p_suiv := p; la_ronde[p].p_suiv := p_Null; ... pp := p; p := la_ronde[p].p_suiv parcourir la liste à l'aide du pointeur p
FORTRAN 77 (standard) n'a ni pointeur, ni allocation dynamique, ni type agrégat, la seule implémentation possible est de gérer, en parrallèle, plusieurs tableaux : les éléments de même indice, pris dans chacun de ces tableaux, constituent l'élément de liste, l'un contenant la valeur de clé, l'autre l'indice de l'élément suivant dans la liste ; on écrira :
Déclarations :
INTEGER Lx_nom longueur maximale des noms INTEGER Nx_Enf nombre maximal d'enfants PARAMETER ( Lx_nom = 15, Nx_Enf = 12 ) CHARACTER *(Lx_nom) t_Nom (1:Nx_enf) tableau des "noms" INTEGER t_p_suiv (1:Nx_enf) tableau des "pointeurs vers élément suivant" INTEGER NIL PARAMETER ( NIL = 0 ) INTEGER Hd_ptr INTEGER p, pp
Partie exécutable :
Hd_ptr = 1 allocation et liaison de 2 éléments de liste p = 2 t_p_suiv(Hd_ptr) = p t_p_suiv(p) = NIL ... pp = p p = t_p_suiv(p) considérer l'élément suivant de celui pointé par p
Déclarations :
IMPLICIT NONE
INTEGER, PARAMETER :: Lx_nom = 15; longueur maximale des noms
TYPE ty_Enf
TYPE (ty_Enf), POINTER :: p_suiv ;
CHARACTER (LEN = Lx_nom) :: Nom ;
END TYPE ty_Enf
TYPE (ty_Enf), POINTER :: Hd_ptr ;
TYPE (ty_Enf), POINTER :: p, pp ;
Partie exécutable :
ALLOCATE (Hd_ptr, p) allocation et Hd_ptr%p_suiv => p ; NULLIFY (p%p_suiv) liaison de 2 éléments de liste ... pp => p la notation "=>" signifie "pp" pointe vers ce quoi pointe "p" p => p%p_suiv
Déclarations :
# include <stddef.h> pour "NULL" # define Lx_nom 15 longueur maximale des noms typdef Struct Enf { définition du type "élément de liste" struct Enf * p_suiv champ "pointeur vers élément suivant" char Nom[Lx_nom] champ "nom" }ty_enf ty_enf * hd_ptr,s * p, * pp;
Partie exécutable :
hd_ptr = (ty_enf *) malloc (sizeof (ty_enf)); création de p = (ty_enf *) malloc (sizeof (ty_enf)); 2 éléments de liste hd_ptr->p_suiv = p; p->p_suiv = NULL; liaison de 2 éléments de liste ... pp = p; p = p>p_suiv; considérer l'élément suivant de celui pointé par p
Déclarations :
#define Lx_nom 15 longueur maximale des noms #define Nx_Enf 12 nombre maximal d'enfants #define p_Null -1 indice de même rôle que NULL typedef struct Enf { définition du type "élément de liste" int p_suiv champ "pointeur vers élément suivant" char Nom[Lx_nom] champ "nom" } ty_enf; int Hd_ptr, p, pp; ty_enf la_ronde[Nx_Enf];
Partie exécutable :
hd_ptr = O; p = 1; allocation et liaison de 2 éléments de liste la_ronde[hd_ptr]->p_suiv = p ; la_ronde[p]->p_suiv = p_Null; ... pp = p; p = la_ronde[p]->p_suiv; considérer l'élément suivant de celui pointé par p
Une pile est un cas particulier de liste, pour laquelle on n'accède qu'à un seul élément : le dernier, d'où l'appelation LIFO (Last In, first Out). Plus qu'une structure de données, il s'agit d'une méthode d'accès. Ce nom vient de l'analogie avec les piles d'assiettes, de dossiers, où il est hasardeux de prendre quelque chose autrement que sur le dessus... Ce type de structure est très utilisé dans de nombreuses fonctions "hardwares" et systèmes.
N.B. (en particulier pour ceux qui ont déjà étudié les microprocesseurs) le mot pile peut prendre deux acceptions différentes :
En dépit de différences notables (dans le premier cas les objets empilés sont homogènes, dans les seconds ils peuvent être de tailles différentes), la structure est la même : on ne peut accéder simplement qu'à l'élément placé au "sommet4" de la pile.
4. En raison de l'analogie traditionnelle avec les piles d'assiettes, on parle ordinairement du "sommet" de la pile ; dans la réalité de nombreuses piles utilisées en informatique croissent du "haut" vers le "bas" (adresses décroissantes).
Nous étudierons des piles du premier type (≈ homogènes).
Etape préliminaire, structure des données :
Structure des données pour une pile
Comme ce cas se rencontre fréquemment, nous étudierons des piles implantées dans des tableaux (statiques). L'indice varie de 1 à TailleMax. Pour connaître la position de l'élément qui est au "sommet" de la pile, il faut disposer d'une variable (indice) qui "pointe" vers ce sommet. Le type ty_structure_de_pile sera donc un agrégat :
TYPE ty_structure_de_pile = agrégat de t_pile : tableau de ty_élément_de_pile, indice [1..TailleMax]; p_top : pointeur de pile /* indice d'un élément de t_pile */ fin_agrégat ty_structure_de_pile
N.B. Le type exact de "ty_élément_de_pile" est pour l'instant sans intérêt, nous dirons de nouveau qu'il s'agit d'un type générique.
Cette définition n'est pas suffisamment précise pour une utilisation pratique, la figure ci-dessus le montre bien ; le rôle du pointeur p_top est ambigu : pointe-t'il vers l'élément présent au sommet de la pile (cellule grisée), ou vers le premier emplacement libre ?
On conviendra que :5 : p_top pointe vers le premier élément "vide" (autrement-dit, libre pour y stocker une information), ceci implique p_top 1.
5. Cette convention est totalement arbitraire, la convention contraire : p_top pointe vers le dernier élément "empilé", ne le serait pas moins. Nous verrons plus loin que, si nos procédures de gestion depiles sont correctement définies, la valeur de p_top (et par conséquent cette convention!) n'a pas besoin d'être connue hors des procédures de gestion de pile (encapsulation).
Nous développerons les deux procédures fondamentales suivantes :
On veut empiler la valeur de x; on suppose que tout se passe sans problème.
/* on suppose que p_top pointe vers le premier élément libre */ t_pile (p_top)x p_top
p_top+1 /* l'hypothèse est toujours vérifiée : p_top pointe (encore) sur le premier élément libre */
Il faut vérifier que p_top pointe vers un élément du tableau. Le cas p_top > TailleMax est un problème difficile : la gestion des "exceptions", on peut décider soit :
/* nous admettons que les outils de gestion de la pile ne fournissent jamais p_top < 1 et en les contruisant, nous nous appliquerons à ce que cette hypothèse reste vérifiée ! */ si p_topTailleMax alors /* on est sûr que p_top pointe vers le premier élément libre */ t_pile (p_top)
x p_top
p_top + 1 /* p_top pointe encore sur le premier élément libre (si le tableau n'est pas plein) */ sinon /* la pile est pleine */ que faire ??? fin_si
Dans le cadre d'une stricte séparation de tâches entre programme appelant et procédure (ce qui constitue la forme rationnelle d'organisation), la décision de ce qu'il faut faire en cas de saturation de la pile n'est pas du ressort des procédures de gestion de piles ; c'est au rédacteur du programme appelant de prévoir l'action à exécuter dans cette situation d'exception (il peut par exemple prévoir une requête au système pour accroître la taille de la pile).
La solution la plus propre est que la procédure rende la valeur d'un indicateur d'état ("status" ou "condition code") qui indique si l'opération s'est bien passée, ce sera notre choix.
Il se peut que le problème traité nécessite la gestion de différentes piles, il faut donc pouvoir préciser, aux outils de manipulation de pile, de quelle pile il s'agit.
Il faut aussi savoir si l'opération s'est déroulée correctement, ici nous avons choisi que la procédure rende ce résultat dans l'argument OK, qui vaut vrai si l'empilement a bien eu lieu et faux sinon. On pourrait aussi choisir que empiler soit une fonction de valeur égale à OK ; c'est la technique utilisée dans la plupart des systèmes (il faut admettre dans ce cas qu'une fonction puisse modifier ses arguments, ce qui est en contradiction avec l'usage habituel qui se modèle sur les fonctions mathématiques et qui prohibe qu'une fonction modifie ses arguments). La langage C ne connaît que la déclaration de fonction, et pas celle de procédure, pour cette raison, en effet il fut conçu pour l'écriture d'un système d'exploitation.
procédure Empiler ( pile : ty_structure_de_pile, Entrée/Sortie x : ty_élément_de_pile, Entrée; /* valeur à empiler */ OK : indicateur booléen, Sortie ) /* on travaille sur les composantes de "pile" */ Il faut bien sûr le préciser /* nous admettons que les outils de gestion de la pile, ne fournissent jamais p_top < 1 on convient que p_top pointe vers l'élément où stocker la valeur à empiler */ si p_topTailleMax alors t_pile (p_top)
x p_top
p_top + 1 /* p_top peut aller jusqu'à TailleMax + 1 */ OK
vrai sinon /* la pile est pleine */ OK
faux fin_si fin_procédure Empiler
Remarques :
L'action est l'inverse de celle d'empiler : on veut récupérer dans x la valeur stockées au sommet de la pile (et libérer le sommet).
On suppose encore une fois que tout se passe sans problème.
/* on suppose que p_top pointe vers le premier élément libre */ p_topp_top -1 x
t_pile (p_top) /* l'hypothèse est toujours vérifiée p_top pointe encore sur le premier élément libre */
Il faut se conformer aux conventions générales : p_top 1 et p_top pointe vers le premier élément libre.
procédure Dépiler ( pile : ty_structure_de_pile, Entrée/Sortie x : ty_élément_de_pile, Sortie OK : indicateur booléen, Sortie ) /* on travaille sur les composantes de "pile" */ Il faut bien sûr le préciser /* nous admettons que les outils de gestion de la pile, ne fournissent jamais p_top < 1 on convient que p_top pointe vers le premier élément libre */ si p_top > 1 alors p_topp_top - 1 x
t_pile(p_top) OK
vrai sinon /* la pile était vide */ OK
faux fin_si /* on a encore p_top
1 */ fin_procédure Dépiler
N.B. Malgré les similitudes d'aspect et de traitement, il y a une différence fondamentale entre le cas où on veut empiler dans une pile pleine et le cas où on veut retirer un élément d'une pile vide. Dans le cas d'une pile saturée, le problème peut, éventuellement, être corrigée (accroissement dynamique de la taille du tableau, par exemple). Le cas d'une pile vide peut n'avoir aucun remède, si il résulte d'une erreur de programmation (c.-à-d. si l'ordre de dépiler a été donné parce que l'on pense qu'il doit y avoir encore des données disponibles dans la pile) ou au contraire constituer une situation normale correspondant < la fin d'une action (traiter, jusqu'à épuisement, les données empilées...)
La variable pile existe, on désire l'initialiser, c.-à-d. écrire qu'elle est vide.
procédure Init_Pile ( pile : ty_structure_de_pile, Entrée/Sortie /* on travaille sur les composantes de "pile" */ Il faut bien sûr le préciser p_top1 /* on a encore p_top
1 */ /* la pile est vide, p_top pointe vers le premier élément libre */ fin_procédure Init_Pile
Une file (ou queue, par analogie avec la queue des spectateurs potentiels devant un cinéma) est un autre cas particulier de liste, pour laquelle on ne peut ajouter de nouvel élément qu'à la fin de la file et on ne peut extraire d'élément qu'en tête. D'où l'appelation FIFO (First In First Out).
Elles sont utilisées, en particulier, lorsqu'interviennent des phénomènes "aléatoires" (c.-à-d. dont l'instant de survenance est imprévisible au moment de l'écriture du programme) que l'on souhaite traiter dans l'ordre de leur arrivée ; par exemple l'arrivée sur un "port série" d'un caractère provenant d'un modem, ou les caractères envoyés par un programme à une imprimante, ou encore les évènements d'origine humaine (frappe d'une touche de clavier, mouvement et clic d'une souris, insertion d'une disquette), file d'attente des travaux sur un "gros système" (nous ne traiterons pas le problème des files d'attente avec "priorité").
Etape préliminaire, structure des données :
Comme pour les piles, et pour les mêmes raisons d'efficacité, les files sont fréquemment implantées dans des tableaux (statiques) dont les indices varient de 1 à TailleMax ; il faut aussi deux "pointeurs" (des indices) qui pointent l'un, vers la "tête" de la file, l'autre, vers la "queue6" ; un ty_structure_de_file sera donc un agrégat. Comme pour les piles, on conviendra que les pointeurs pointent chacun vers le premier élément disponible : p_tête vers le premier élément à extraire, p_queue vers le premier élément libre pour ajouter un nouvel élément.
6. Il serait, bien sûr, possible d'imaginer que, à chaque fois qu'on retire un élément de la file, on fait "avancer" (vers les faibles indices du tableau) tous les éléments en attente, comme les spectateurs devant les guichets du cinéma : le pointeur de tête de file serait inutile, mais quelle serait l'efficacité d'un tel système ?
Structure des données pour une file
TYPE ty_structure_de_file = agrégat de t_file : tableau de ty_élément_de_file indicé (1..TailleMax) p_tête : indice pour t_file /* pointe vers le premier élément à sortir */ p_queue : indice pour t_file /* pointe vers la première place libre */ fin_agrégat ty_structure_de_file
Nous développerons les deux procédures fondamentales "Ajouter" et "Retirer". Chacune aura pour effet de faire croître les valeurs de p_tête et p_queue ; à ce petit jeu, ces deux pointeurs vont s'empresser d'atteindre la valeur TailleMax ; il faut donc prévoir un mécanisme pour que, lorsque l'incrémentation d'un pointeur l'amène à pointer au delà de la fin du tableau, on le fasse pointer vers le début. Pour l'instant, on supposera qu'il existe une fonction suivant(p) qui réalise ce mécanisme (bien sûr, on ne verra que plus tard les détails de sa réalisation).
On veut ajouter la valeur x à la queue de la file ; on suppose, comme toujours à ce stade, que tout se passe sans problème.
/* "p_queue" pointe vers le premier élément libre */ t_file (p_queue)x p_queue
suivant(p_queue)
De même, on veut récupérer dans x la valeur de la tête de la fille (même hypothèse).
/* "p_tête" pointe vers le premier élément à extraire */ xt_file (p_queue) p_tête
suivant(p_tête)
Cas particulier d'une file presque pleine
Cas particulier d'une file presque vide
Comme pour la gestion des piles, on imagine aisément deux situations exceptionnelles : vouloir ajouter à une file pleine et vouloir retirer d'une file vide. On peut déjà penser donner le même genre de réponse (rendre une variable d'état indiquant la bonne fin de l'opération). Par contre la détection de telles situations n'est pas aussi évidente. Les schémas ci-dessus permettent de le comprendre :
il n'est donc pas envisageable de penser détecter l'état vide et l'état plein avec le même test : si p_tête = p_queue alors (de nombreux programmeurs ont souffert sur ce problème et des solutions fort compliquées programmées)
Nous serons simple7 : il suffit que chaque procédure qui modifie la file tienne à jour une variable caractéristique indiquant l'état_de_la_file : vide, pleine ou normale (c.-à-d. ni vide ni pleine). Les procédures ajouter et retirer doivent consulter cette variable avant d'agir et mettre à jour cette variable après chaque action. Cette variable doit faire partie de l'agrégat qui constitue une file.
7. Ce n'est bien sûr pas la seule solution : par exemple, on peut convenir de ne jamais remplir complètement la file ou de tenir à jour un compteur du nombre des éléments en attente (solutions à étudier).
TYPE ty_structure_de_file = agrégat de t_file : tableau de ty_élément_de_file indicé (1..TailleMax) p_tête : indice pour t_file /* pointe vers le premier élément à sortir */ p_queue : indice pour t_file /* pointe vers la première place libre */ état_de_la_file : indicateur à 3 états (vide, pleine, normale) fin_agrégat ty_structure_de_file
Procédure Ajouter ( file : ty_structure_de_file, Entrée/Sortie; x : ty_élément_de_file, Entrée; OK : indicateur booléen, Sortie) /* "p_queue" pointe vers le premier élément libre */ /* on travaille sur les composantes de "file" */ si etat_de_filepleine alors OK
vrai t_file(p_queue)
x p_queue
suivant_de (p_queue) si p_queue
p_tête état_de_la_file
normale sinon état_de_la_file
pleine fin_si sinon OK
faux fin_si fin_procédure Ajouter
Procédure Retirer ( file : ty_structure_de_file, Entrée/Sortie; x : ty_élément_de_file, Sortie; OK : indicateur booléen, Sortie) /* "p_tête" pointe vers le premier élément disponible (à sortir) */ /* on travaille sur les composantes de "file" */ si etat_de_filevide alors OK
vrai x
t_file (p_tête) p_tête
suivant_de (p_tête) si p_queue
p_tête état_de_la_file
normale sinon état_de_la_file
vide fin_si sinon OK
faux fin_si fin_procédure Retirer
Procédure Init_File ( file : ty_structure_de_file, Entrée/Sortie) /* initialisation d'une file */ /* on travaille sur les composantes de "file" */ etat_de_la_filevide p_tête
1 p_queue
p_tête fin_procédure Init_File
fonction suivant ( p : pointeur dans t_file, Entrée; ) utilise les éléments de la "file" en usage si p < TailleMax alors suivantp + 1 sinon suivant
1 fin_si fin_fonction suivant
Il faut remarquer que cette fonction suivant est le seul endroit où les bornes des indices du tableau t_file sont effectivement utilisées.
Les devises Shadoks : pourquoi faire simple quand on peut faire compliqué?!
Ceci pourrait être une recommandation du dessinateur Gary Larson à l'intention de tous les programmeurs...