Algorithmique Avancée - Types de Données et Algorithmique
Algorithmique Avancée - Types de Données et Algorithmique
Computer Science - Data Structures and Algorithms · exam
Voir tous les documents en programmationTous les exercices en programmation
Fiche de révisionCorrigé
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce document présente un examen d'algorithmique avancée portant sur les types de données abstraits élémentaires, notamment les listes, piles et files. Il teste la compréhension des définitions, opérations, mises en œuvre et la capacité à écrire des sous-programmes manipulant ces structures.
La procédure suivante parcourt la liste et élimine les doublons successifs à l'aide de la fonction de comparaison fournie.
Analyse : On travaille sur une liste L d'éléments de type TypeElément. On dispose d'une fonction Identique(x, y) qui retourne vrai si x et y sont identiques.
Solution pas à pas :
Procédure en pseudo-code :
procédure EliminerRepetitions(var L : LISTE)
pour i de 1 à FIN(L) - 1 faire
j ← i + 1
tant que j < FIN(L) faire
si Identique(ACCEDER(i, L), ACCEDER(j, L)) alors
SUPPRIMER(j, L)
sinon
j ← j + 1
fin si
fin tant que
fin pour
fin procédure
Réponse finale : La procédure ci-dessus élimine toutes les répétitions dans la liste L.
Voici les implémentations des opérations de base sur une liste stockée dans un tableau fixe.
Cette fonction retourne la position suivant p dans la liste L.
Si p est la dernière position (p = L.Dernier), alors SUIVANT(p, L) = FIN(L) = L.Dernier + 1.
fonction SUIVANT(p : entier; L : LISTE) : entier
si p <= L.Dernier alors
retourner p + 1
sinon
// SUIVANT non défini si p > L.Dernier
erreur
fin si
fin fonction
Cette fonction retourne la position précédente à p dans la liste L.
Si p = 1, PRECEDENT n'est pas défini.
fonction PRECEDENT(p : entier; L : LISTE) : entier
si p > 1 et p <= FIN(L) alors
retourner p - 1
sinon
// PRECEDENT non défini si p = 1 ou p > FIN(L)
erreur
fin si
fin fonction
Cette procédure insère l'objet x à la position p dans la liste L, en décalant les éléments à partir de p vers la fin.
Étapes :
procédure INSERER(x : TypeElément; p : entier; var L : LISTE)
si p <= FIN(L) alors
pour i de L.Dernier à p faire
L.Eléments[i + 1] ← L.Eléments[i]
fin pour
L.Eléments[p] ← x
L.Dernier ← L.Dernier + 1
sinon
erreur
fin si
fin procédure
Cette procédure supprime l'élément en position p dans la liste L, en décalant les éléments suivants vers la gauche.
Étapes :
procédure SUPPRIMER(p : entier; var L : LISTE)
si (L.Dernier >= 1) et (p < FIN(L)) alors
pour i de p à L.Dernier - 1 faire
L.Eléments[i] ← L.Eléments[i + 1]
fin pour
L.Dernier ← L.Dernier - 1
sinon
erreur
fin si
fin procédure
Cette fonction retourne la position de la première occurrence de x dans L, ou FIN(L) si x n'est pas trouvé.
Étapes :
fonction LOCALISER(x : TypeElément; L : LISTE) : entier
pour p de 1 à L.Dernier faire
si Identique(L.Eléments[p], x) alors
retourner p
fin si
fin pour
retourner FIN(L)
fin fonction
Une pile P est un enregistrement avec un tableau Eléments[1..LongMax] et un entier Sommet indiquant la position du sommet. Si Sommet = 0, la pile est vide.
Cette procédure permet de vider la pile P.
procédure RAZ(var P : PILE)
P.Sommet ← 0
fin procédure
Cette fonction retourne vrai si la pile est vide, faux sinon.
fonction VIDE(P : PILE) : booléen
retourner (P.Sommet = 0)
fin fonction
Cette fonction retourne l'élément au sommet de la pile sans le dépiler. L'opération est impossible si la pile est vide.
fonction SOMMET(P : PILE) : TypeElément
si VIDE(P) alors
erreur
sinon
retourner P.Eléments[P.Sommet]
fin si
fin fonction
Cette procédure supprime l'élément au sommet de la pile. L'opération est impossible si la pile est vide.
procédure DEPILER(var P : PILE)
si VIDE(P) alors
erreur
sinon
P.Sommet ← P.Sommet - 1
fin si
fin procédure
Cette procédure insère l'élément x au sommet de la pile.
procédure EMPILER(x : TypeElément; var P : PILE)
si P.Sommet < LongMax alors
P.Sommet ← P.Sommet + 1
P.Eléments[P.Sommet] ← x
sinon
erreur // pile pleine
fin si
fin procédure
Une file F est un enregistrement avec deux pointeurs tête et queue vers des nœuds. Chaque nœud contient val (TypeElément) et suiv (pointeur vers nœud).
Cette procédure transforme la file en une file vide.
procédure RAZ(var F : FILE)
F.tête ← nil
F.queue ← nil
fin procédure
Cette fonction retourne vrai si la file est vide, faux sinon.
fonction VIDE(F : FILE) : booléen
retourner (F.tête = nil)
fin fonction
Cette fonction retourne l'élément en tête de la file. L'opération est impossible si la file est vide.
fonction TETE(F : FILE) : TypeElément
si VIDE(F) alors
erreur
sinon
retourner F.tête↑val
fin si
fin fonction
Cette procédure insère l'élément x à la fin de la file.
procédure ENFILER(x : TypeElément; var F : FILE)
nouveauNoeud ← allouer noeud
nouveauNoeud↑val ← x
nouveauNoeud↑suiv ← nil
si VIDE(F) alors
F.tête ← nouveauNoeud
F.queue ← nouveauNoeud
sinon
F.queue↑suiv ← nouveauNoeud
F.queue ← nouveauNoeud
fin si
fin procédure
Cette procédure supprime le premier élément de la file. L'opération est impossible si la file est vide.
procédure DEFILER(var F : FILE)
si VIDE(F) alors
erreur
sinon
temp ← F.tête
F.tête ← F.tête↑suiv
libérer temp
si F.tête = nil alors
F.queue ← nil
fin si
fin si
fin procédure
La fonction AVANCER permet d'incrémenter une position p dans un tableau circulaire de taille LongMax.
Analyse : Dans un tableau circulaire, la position suivante de p est p+1 sauf si p = LongMax, auquel cas la position suivante est 1.
fonction AVANCER(p : entier) : entier
si p < LongMax alors
retourner p + 1
sinon
retourner 1
fin si
fin fonction
Ce devoir récompense la maîtrise des définitions précises des types abstraits de données (listes, piles, files) et de leurs opérations fondamentales. Il est essentiel de :
Les erreurs fréquentes à éviter sont :
Une bonne compréhension des structures abstraites et de leur mise en œuvre est la clé pour réussir ce type d'exercices.