Algorithmique Avancée
Algorithmique Avancée
Computer Science · lab
Voir tous les documents en programmationTous les exercices en programmation
Fiche de révisionGuide de TP
Rédigée à partir de ce document, puis vérifiée avant publication.
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.
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.
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.
Une liste est représentée par un enregistrement avec :
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
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 :
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.
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 :
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 :
Pour éviter le déplacement des éléments lors d’une suppression, on utilise un tableau circulaire :
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 :