> Quelques cours > Algorithmique et Analyse > 2. Structures linéaires

sommaire chapitre précédent

version imprimable

2. Structure linéaires

2.1. Les Listes

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.

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.

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

  fermer cette précision

Exemple d'élément de liste :

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

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

• Ô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.

  

  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

• Insérer : 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_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 Ôter_élément

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.

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 :

partie exécutable :

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.

3° 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 :

5° représentation "dynamique" en C

6° représentation "statique" en C

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 "sommet4" de la pile.

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

Etape préliminaire, structure des données : 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 :

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.

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

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

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.

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

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

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

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

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

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

2.3.2. Initialiser une file

2.3.3. Réalisation de la 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.

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

version imprimable

retour vers le haut chapitre suivant