Algorithmique Avancée

Ce laboratoire porte sur les types de données abstraits élémentaires en algorithmique avancée : listes, piles et files. Il permet de comprendre leurs définitions, opérations principales, et différentes mises en œuvre, notamment par tableaux et pointeurs. Pour réaliser ce TP, il est nécessaire de maîtriser les notions de base en programmation et structures de données, ainsi que les concepts d’algorithmique.

Objectifs

• Comprendre la définition et les propriétés des listes, piles et files.
• Apprendre à manipuler les opérations fondamentales sur ces structures (insertion, suppression, accès).
• Mettre en œuvre ces structures à l’aide de tableaux et de pointeurs.
• Écrire des sous-programmes pour gérer ces structures (ex : INSERER, SUPPRIMER, EMPILER, DEPILER, ENFILER, DEFILER).
• Appliquer les notions de listes circulaires pour la gestion efficace des files.

Prérequis et installation

• Connaissances de base en programmation structurée (procédures, fonctions).
• Notions sur les types abstraits de données et les structures linéaires.
• Environnement de programmation permettant la définition de types enregistrements et tableaux (ex : Pascal, langage similaire).
• Compréhension des pointeurs pour la mise en œuvre dynamique des files.

Types de données abstraits élémentaires : listes

Une liste est une structure souple pouvant grandir ou rétrécir à volonté. Ses éléments sont accessibles à tout moment et peuvent être insérés ou supprimés à n'importe quelle position.

Mathématiquement, une liste est une suite d’éléments a1, a2, ..., an où n est la longueur de la liste (entier positif ou nul). Si n = 0, la liste est vide. Les éléments sont ordonnés : ai précède ai+1 et suit ai-1.

Opérations principales sur les listes

• FIN(L) : retourne la position suivant la dernière position d’une liste L de n éléments (FIN(L) = n + 1).
• INSERER(x, p, L) : insère l’élément x à la position p dans la liste L, décalant les éléments à partir de p vers la fin.
• LOCALISER(x, L) : retourne la position de la première occurrence de x dans L, ou FIN(L) si x n’est pas présent.
• ACCEDER(p, L) : retourne l’élément à la position p dans L (p < FIN(L)).
• SUPPRIMER(p, L) : supprime l’élément à la position p dans L (p < FIN(L)).
• SUIVANT(p, L) et PRECEDENT(p, L) : retournent respectivement la position suivante et précédente à p dans L, avec gestion des cas limites.

Exemple d’insertion

Avant insertion, L a 4 éléments (positions 1 à 4), FIN(L) = 5.

INSERER(x, 3, L) déplace les éléments en positions 3 et 4 vers 4 et 5, puis place x en position 3. La nouvelle FIN(L) = 6.

Mise en œuvre par tableau

Une liste est représentée par un enregistrement avec :

• Un tableau d’éléments de type TypeElement, de taille suffisante (LongMax).
• Un entier “dernier” indiquant la position du dernier élément.

La fonction FIN(L) renvoie simplement dernier + 1.

const LongMax = 100
type LISTE = enregistrement
  Elements : tableau [1 .. LongMax] de TypeElement
  Dernier : entier
finenregistrement

fonction FIN(L : LISTE) : entier
début
  FIN ← L.Dernier + 1
fin

Exercices

• Écrire une procédure pour éliminer toutes les répétitions dans une liste L.
• Écrire les sous-programmes SUIVANT, PRECEDENT, INSERER, SUPPRIMER et LOCALISER.

Les piles

Une pile est une liste particulière où les suppressions se font uniquement au sommet (extrémité) de la pile. Elle suit le principe LIFO (Last In, First Out).

Les opérations principales sont :

• RAZ(P) : vider la pile P.
• VIDE(P) : retourne vrai si P est vide, faux sinon.
• SOMMET(P) : retourne l’élément au sommet sans le dépiler.
• DEPILER(P) : supprime l’élément au sommet.
• EMPILER(x, P) : insère l’élément x au sommet.

Mise en œuvre par tableau

Une pile est représentée par un enregistrement :

const LongMax = ...
type PILE = enregistrement
  Elements : tableau [1 .. LongMax] de TypeElement
  Sommet : entier
finenregistrement

Si Sommet = 0, la pile est vide.

Exercice

• Écrire les sous-programmes RAZ(P), VIDE(P), SOMMET(P), DEPILER(P) et EMPILER(x, P).

Les files

Une file est une liste où les éléments sont insérés en queue et supprimés en tête, suivant le principe FIFO (First In, First Out).

Les opérations principales sont :

• RAZ(F) : vide la file.
• TETE(F) : retourne l’élément en tête.
• ENFILER(x, F) : insère l’élément x en queue.
• DEFILER(F) : supprime l’élément en tête.
• VIDE(F) : retourne vrai si la file est vide, faux sinon.

Mise en œuvre par pointeurs

Les noeuds sont définis par :

type noeud = enregistrement
  val : TypeElement
  suiv : ^noeud
finenreg

La file est définie par deux pointeurs :

type FILE = enregistrement
  tête, queue : ^noeud
finenreg

Exemple d’état d’une file :

• F.tête pointe vers le premier noeud (élément X).
• F.queue pointe vers le dernier noeud (élément Y).

Exercice

• Écrire les sous-programmes RAZ(F), VIDE(F), TETE(F), ENFILER(x, F) et DEFILER(F).

Mise en œuvre par tableau circulaire

Pour éviter le déplacement des éléments lors d’une suppression, on utilise un tableau circulaire :

• La position F.tête du premier élément varie dans le temps.
• Lors d’une insertion, F.queue avance d’une position et l’élément est inséré à cette position.
• Lors d’une suppression, F.tête avance d’une position.

La file est définie par :

const LongMax = ...
type FILE = enregistrement
  Elements : tableau [1 .. LongMax] de TypeElement
  tête, queue : entier
finenregistrement

Attention : il est impossible de distinguer une file vide d’une file pleine si tête = queue. Pour pallier cela, on interdit de remplir complètement la file (max LongMax - 1 éléments).

Dans ce cas :

• La file est vide si les positions tête et queue sont adjacentes.
• La file est pleine si la position queue est juste avant tête dans le tableau circulaire.

Exercice

• Écrire une fonction AVANCER permettant d’incrémenter une position p dans un tableau circulaire de taille LongMax.

Résultats attendus

• Compréhension claire des opérations sur listes, piles et files.
• Implémentation correcte des sous-programmes demandés, respectant les contraintes de position et gestion des cas limites.
• Gestion efficace des files circulaires sans décalage excessif.
• Capacité à manipuler les structures dynamiques (pointeurs) pour les files.

Pièges courants

• Confondre les positions dans la liste (p) avec les indices du tableau, notamment lors des insertions et suppressions.
• Ne pas gérer correctement les cas limites : insertion en fin de liste, suppression dans une liste vide, accès hors limites.
• Pour les piles, oublier que DEPILER ne prend pas d’argument et agit toujours sur le sommet.
• Dans les files circulaires, ne pas distinguer correctement file pleine et file vide lorsque tête = queue.
• Oublier d’incrémenter circulairement les indices dans la file (fonction AVANCER).
• En mise en œuvre par pointeurs, ne pas mettre à jour correctement les pointeurs tête et queue lors des opérations ENFILER et DEFILER.