Kha-tastrophe.net

Le site kha-tastrophique de Kha

> Cours > Informatique> Algorithmique et Analyse > Structures linéaires

2. Structures linéaires

2.1. Les Listes

Une liste est une séquence¹ 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.

fermer cette précision

La structure de donnée d'un élément de liste est conceptuellement simple :

le champ "clé²" 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.

fermer cette précision
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 "pointeur³ 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.

fermer cette précision

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 :

rechercher la position d'un élément dont on connaît la "valeur-clé",
insérer un élément entre deux éléments, le cas échéant en tête ou en fin de liste ;
ôter un élément.

2.1.1. Première fonction : rechercher la position d'un élément dont on connaît la "valeur-clé"

par exemple, recherche d'une fiche_d_etudiant dont on donne le nom

2.1.1.1. Etape 0 (énoncé du problème)

On suppose qu'on considère :

une liste non vide (pour ne pas avoir à traiter de cas particulier dès le début de l'analyse),
dont les éléments sont ordonnés par valeurs de clé croissantes (cette exigence n'est ni absolumment nécessaire, ni contraignante, elle a l'avantafe de diminuer en moyenne d'un facteur 2 le temps de recherche). On est tenté d'écrire clé(p) < clé(suivant_de(p)), mais on se pose la question "<" ou "". Nous choisirons "" qui permet de gérer des listes dont plusieurs éléments ont la même valeur de clé.

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)
*/

2.1.1.2. Etape 1 (idée de base)

Ici encore, on évite soigneusement les cas particuliers :

on part d'une situation non exceptionnelle : on suppose que p pointe vers un élément,
on précise la relation entre x et clé(p) : c'est le cas ordinaire (on n'a pas encore trouvé), donc on compare à l'élément suivant (on suppose aussi que celui-ci existe).

/* on suppose que le pointeur "p" pointe vers un élément de la liste tel que */
    p  suivant_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

2.1.1.3. Etape 2 (amélioration)

Cette recherche peut servir :

soit pour une recherche pure (pour localiser un élément existant dans la liste ou détecter son absence)
soit pour insérer un nouvel élément ou supprimer un élément existant dans la liste (auquel cas on voit souvent qu'il faudra manipuler le pointeur suivant_de de l'élément précédant) ; il est donc très souvent utile de rendre en même temps un pointeur pp qui pointe vers l'élément précédent de celui qui nous intéresse.

/* 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)
    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

2.1.1.4. Etape 3 (itération)

On répète tant qu'il faut (et tant qu'on peut!), c.-à-d. :

tant qu'il y a un élément suivant dans la liste
et tant que la valeur-clé de cet élément est < x

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  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

2.1.1.5. Etape 4 (débuter)

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 :

liste non vide, c.-à-d. Hd_ptr NIL
et clé(p) < x

On traite ensuite les cas particulier : position avant le début de la liste, liste vide.

p  Hd_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

2.1.1.6. Etape 5 (mise en forme de la procédure)

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 :

savoir s'il existe un élément de valeur-clé égale à x (le cas échéant pointer vers cet élément),
rechercher s'il existe un élément de valeur-clé égale à x ; si il n'existe pas, en insérer un (ou encore, si il en existe un, le supprimer),

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.

fermer cette précision

2.1.2. Les autres fonctions élémentaires : ôter ou insérer un élément

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)

2.1.2.1. Fonction Ôter

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.

Schéma pour ôter un élément d'une liste

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 pp  NIL 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

2.1.2.2. Fonction Insérer

On veut insérer l'élément pointé par p_N juste après l'élément pointé par pp

Schéma pour ajouter un élément à une liste

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_N  NIL 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.

2.1.3. Complexité

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 :

si il existe dans la liste un élément dont la valeur clé est égale à la valeur de x, la recherche aboutit en au moins 1 et, au plus n opérations ; il faut donc, en valeur moyenne, n/2 opérations,
si il n'y a pas dans la liste un élément dont la valeur clé est égale à la valeur de x, il faut explorer toute la liste pour prouver l'absence si la liste n'est pas ordonnée ; par contre, si la liste est ordonnée selon les valeurs de clé, il suffit en moyenne de ne parcourir que la moitié de la liste soit n/2 opérations.

Dans tous les cas la complexité, en moyenne, de l'algorithme est proportionnelle au nombre n des éléments de la liste.

2.1.4. Programmation

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.

2.1.4.1. Représentation "dynamique" en Pascal

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

2.1.4.2. Représentation "statique" en Pascal

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

2.1.4.3. Représentation "statique" en FORTRAN 77

représentation statique en FORTRAN 77

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

2.1.4.4. Représentation "dynamique" en FORTRAN 90

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

2.1.4.5. Représentation "dynamique" en C

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

2.1.4.6. Représentation "statique" en C

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

2.2. Les Piles

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 :

la pile typiques (Stack) des microprocesseurs, où les objets empilés sont tous de même type, en général des "mots", avec des instructions spécialisées dans la gestion de pile (PUSH, POP),
la pile des machines plus grosses (SPARC, par exemple), où ce sont des zones mémoire (Stack Frame) de taille paramétrable qui sont allouées - en pile -, des instructions spécialisées (SAVE, RESTORE) étant destinées à l'allocation de ces zones ;

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 "sommet⁴" 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).

fermer cette précision

Nous étudierons des piles du premier type (≈ homogènes).

Etape préliminaire, structure des données :

Structure des données pour une pile

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 :⁵ : 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).

fermer cette précision

Nous développerons les deux procédures fondamentales suivantes :

empiler (PUSH), c.-à-d. stocker une valeur au sommet de la pile,
dépiler (POP), récupérer la valeur de l'objet qui est au sommet de la pile et libérer sa place.

2.2.1. Empiler

2.2.1.1. Etape 1 (Idée de base)

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 */

2.2.1.2. Etape 2 (gestion des cas particuliers)

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 :

ne rien voir (et ne rien faire ...) mais de l'information sera perdue et le programme donnera sûrement des résultats faux,
imprimer un message (et puis après qui le verra ?)
tout arrêter...
de nombreux auteurs suggèrent de rendre une valeur de p_top invalide, mais le programme qui utilise des piles n'a pas besoin de connaître de tels détails : il n'est intéressé a priori que par empiler (ou dépiler) la valeur de x, seule l'exécution correcte, ou la non exécution, de l'instruction d'empiler lui importe. De toutes façons, il est important que la valeur de p_top ne puisse être connue (et modifiée) à l'extérieur des outils qui manipulent la pile (encapsulation), ce qui évite tout risque de modification intempestive. (Idéalement, les programmes qui font appel à empiler/dépiler n'ont pas à savoir comment est implémentée la pile).

/* 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_top  TailleMax 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.

2.2.1.3. Etape 3 (mise en forme de la procédure)

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_top  TailleMax 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 :

On se pose souvent la question de savoir à quel moment il faut constater que la pile est pleine : quand on vient de la remplir ou quand on vient d'ajouter un nouvel élément. Il faut se souvenir que l'ordre des appels à empiler et à dépiler est imprévisible (du point de vue des procédures), il est donc toujours possible qu'un appel à dépiler survienne et fasse cesser l'état pile pleine avant un nouvel appel à empiler.
La valeur de l'indice p_top peut-être égale à TailleMax+1, il n'est donc pas pas parfaitement exact d'écrire que p_top est indice pour t_pile.

2.2.2. Dépiler

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).

2.2.2.1. Etape 1 (Idée de base)

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_top  p_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 */

2.2.2.2. Etape 2 (mise en forme de la procédure)

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_top  p_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...)

2.2.3. Initialiser la pile

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_top  1         /* on a encore p_top  1 */
    /* la pile est vide, p_top pointe vers le premier élément libre */
fin_procédure Init_Pile

2.3. Les Files

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 ?

fermer cette précision

Structure des données pour une file

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

2.3.1. Ajouter, retirer

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).

Schéma pour ajouter et retirer d'une file

2.3.1.1. Etape 1 (idée de base) pour "Ajouter"

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)

2.3.1.2. Etape 1 (idée de base) pour "Retirer"

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 */
    x  t_file (p_queue)
    p_tête  suivant(p_tête)

2.3.1.3. Etape 2 (vérifier que c'est possible et gérer les cas particuliers)

Cas particulier d'une file presque pleine

Cas particulier pour l'ajout et la suppression dans une file : file presque pleine

Cas particulier d'une file presque vide

Cas particulier pour l'ajout et la suppression dans une file : 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 :

si nous ajoutons un élément à la file presque pleine, elle devient pleine et on a : p_tête = p_queue
si nous retirons un élément de la file presque vide, elle devient vide et on a : p_tête = p_queue

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 simple⁷ : 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).

fermer cette précision

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

2.3.1.4. Etape 3 (mise en forme de la procédure) pour "Ajouter"

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_file  pleine 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

2.3.1.5. Etape 3 (mise en forme de la procédure) pour "Retirer"

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_file  vide 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

2.3.2. Initialiser une file

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_file  vide
        p_tête  1
        p_queue  p_tête
fin_procédure Init_File

2.3.3. Réalisation de la fonction "suivant"

fonction suivant ( p : pointeur dans t_file, Entrée;
                    ) utilise les éléments de la "file" en usage
    si p < TailleMax alors
        suivant  p + 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é?!

Dessin de Gary Larson : d'abord le pantalon puis les chaussures

Ceci pourrait être une recommandation du dessinateur Gary Larson à l'intention de tous les programmeurs...