L’écriture sur des exemples simples de plusieurs implémentations d’une même structure de données permet de faire émerger les notions d’interface et d’implémentation, ou encore de structure de données abstraite.
Dans ce cours nous allons aborder la notion de structure de données abstraite.
Nous allons à travers des exemples voir ce qu'est l'interface d'une structure de données. Nous allons par la suite implémenter ces structures en Python.
Structure de données abstraite
Un type abstrait ou une structure de données abstraite est une spécification mathématique d'un ensemble de données et de l'ensemble des opérateurs associés.
On qualifie d'abstrait ce type de données car il correspond à un cahier des charges qu’une structure de données doit ensuite implémenter.
Dans ce cours, nous allons aborder deux structures de données abstraite : la pile et la file.
La structure du tableau est une structure de données non abstraite. Nous verrons une description de cette structure dans la suite de ce cours.
L'étude des structures de données abstraite permettent de choisir des structures qui simplifient la compréhension des algorithmes mais surtout qui permettent d'optimiser en coût de nombreux algorithmes.
Une vidéo en guise d'avant propos :
Pile
Une pile est :
soit vide ;
soit une cellule à deux champs, un champ contenant un élément, et un champ contenant une autre pile.
On dit que cette structure de st de type LIFO : Last In First Out
On pourra représenter une pile de la manière suivante :$$P=(hautDeLaPile,resteDeLaPile).$$
Essayons de comprendre ce que cette définition implique :
Pour pouvoir travailler avec des données structurées en pile, il faut déjà pouvoir créer une pile vide. Nous devons nous doter d'une notation synthétique et compréhensible. Pour créer une pile P vide on écrira :
P=vide()
Créer une Pile vide
La structure pile dispose d'un opérateur pour créer une pile P vide. On notera dans ce cours
P=vide()
Pour appliquer la définition à un objet P, nous devons savoir si P est vide ou non. Il faut donc se doter d'un opérateur estVide
qui a un objet de type pile P renvoie un booleen : Vraie si la P est vide et Faux sinon.
La fonction estVide()
A toute pile $P$ :
$estVide(P)=Vraie$ si $P$ est vide.
$estVide(P)=Faux$ si $P$ n'est pas vide.
Si cette pile n'est pas vide, elle se compose de deux champs : un premier contenant un élément de type élémentaire ( booléen, entier,flottant) et un second de type pile.
Cette définition est donc récursive : une pile est définie à partir d'une pile.
Nous savons ce qu'est une pile vide. C'est une pile dont l'application de l'opérateur
estVide
renvoie vraie.
Une pile a un élément est composé dans le haut de sa pile par l'élément et d'une pile vide. Nous avons ainsi compris ce qu'est une pile à un élément :
(a,vide())
Une pile à deux éléments peut être représentées ainsi :
(hautDeLaPile,(secondElementDeLaPile,vide()))
Prenons un exemple, on aimerait ranger un groupe d'individus dans un objet de type pile :
Anakin ; Boba Fett ; Dark Vador ; Han Solo ; Yoda
Une représentation de ces données en pile serait :
P=(Anakin,(Boba Fett,(Dark Vador,(Han Solo,(Yoda,vide())))))
Le haut de la pile est $Anakin$ et le reste est $(Boba Fett,(Dark Vador,(Han Solo,(Yoda,vide()))))$.
Donner une représentation en pile de cette ensemble de couleur : rouge ; bleu ; vert. On nommera cette pile $P_{couleur}$.
Donner une représentation en pile de cette ensemble de nombre : 12 ; 5 ; 3 ; 6 ; 1. On nommera cette pile $P_{entier}$.
A ce stade, vous avez compris ce qu'est une structure de données pile. Essayons de voir comment manipuler un objet de ce type.
Empiler un élément en haut de pile
Soit $P$ une pile, la pile obtenue en empilant un élément $a$ en haut de $P$ est la pile $(a, P)$.
On notera cet opérateur $empiler(a, P)$
En reprenant l'exemple précédent où $ P =(Anakin,(Boba Fett,(Dark Vador,(Han Solo,(Yoda,vide())))))$; $empiler(Luke,P)$ est la pile :
$(Luke,(Anakin,(Boba Fett,(Dark Vador,(Han Solo,(Yoda,vide()))))))$
Reprendre l'exercice précédent et empiler le violet à $ P _{couleur}$.
Dépiler le haut d'une pile
Soit $P_1$, $P_2$ deux piles et $a$ le haut de la pile de $P_1$, la pile obtenue en dépilant l'élément $a$ de pile de $P_1$ est la pile $P_2$.
On notera cet opérateur $depiler(P_1)$, elle transforme la pile initiale et renvoie l'élément dépiler.
En reprenant l'exemple précédent où $P=(Anakin,(Boba Fett,(Dark Vador,(Han Solo,(Yoda,vide())))))$ ;
la commande $depiler(P)$ transforme la pile $P$ en : $(Boba Fett,(Dark Vador,(Han Solo,(Yoda,vide()))))$ et renvoie Anakin.
Reprendre l'exercice précédent et retirer la première couleur.
Cette structure de pile est utilisée en informatique dès que l'on veut que la dernière donnée arrivée soit la première
à être prise en compte.
On l'utilise ainsi :
la plupart des microprocesseurs gèrent nativement des piles,
une pile stocke les appels successifs lors de l'utilisation d'une fonction récursive,
dans les traitements de texte, la fonction Undo
c'est-à-dire annuler la frappe
(obtenue
sous Windows avec CTRL+Z) supprime le haut de la pile dans laquelle sont mémorisées les modifications apportées
au texte,
L'historique d'un navigateur web utilise une pile,
différents algorithmes utilisent des piles, comme nous le verront par exemple avec l'algorithme de recherche en profondeur dans un graphe.
Interface d'une structure de données abstraite
L'interface d'une structure de données abstraite est l'ensemble des opérateurs nécessaires à la manipulation de cette structure.
L'interface de la structure pile est l'ensemble des opérateurs vus précédemment :
Nous pourrions ajouter d'autres éléments à l'interface mais l'objectif et d'avoir une interface minimale qui permettent de manipuler cette structure.
Il peut être intéressant de connaître le nombre d'éléments dans une pile.
En voila un pseudo-code :
nombreElement=0
while estVide(P) est faux
nombreElement+=1
depiler(P)
renvoyer nombreElement
Nous n'avons donc pas besoin d'ajouter un opérateur qui compterait le nombre d'éléments d'une pile.
Écrire un script en pseudo-code qui permet de supprimer le premier élément du reste d'une pile
(le terme du haut de la pile lui doit rester en haut de la pile obtenue).
L'exécution de ce script va par exemple réduire la pile ("a",("b",("c",("d",vide())))) en celle
("a",("c",("d",vide()))).
La file
Une file est :
soit vide ;
soit une cellule à trois champs, un champ tête , un champ queue et un champ contenant une file.
Une structure de File fonctionne sur le principe premier entré − premier sorti (comme les files d’attentes à un guichet) FIFO : First In First Out.
On pourra représenter une file de la manière suivante :$$F=(teteDeLaFile, queueDeFile, coeurDeFile).$$
Prenons un exemple, on aimerais ranger un groupe d'individu dans un objet de type file
Anakin; Boba Fett; Dark Vador; Han Solo; Yoda
une représentation en ligne de la file correspondante est :
une représentation en colonne de la file correspondante est :
tête : vide
queue : le seul élément
troisième champ : vide
tête : un élément
queue : un élément
troisième champ : vide.
Définir une file vide
Une file est vide si sa queue est vide.
Pour affecter à une variable $F$ une file vide, on notera : $F=vide()$.
définir enfiler(a,F)
la nouvelle file obtenue à l'enfilement de a sur $F$ est la file :
de tête celle de $F$ ;
de queue a ;
et de troisième champ enfiler(queue de $F$,troisième champ de $F$).
Comme le montre l'évolution du troisième champ, cet opérateur est récursif.
enfiler(queue de $F$,troisième champ de $F$) conduit à mettre queue de $F$ à la fin du coeur même si cet argument apparaît en premier lors de l'appel de la fonction enfiler.
En reprenant l'exemple précédent où $F =(Anakin,Yoda,(Boba Fett,Dark Vador,Han Solo)))$; $enfiler(Luke,F)$ est la file :
$F=(Anakin,Luke,(Boba Fett,Dark Vador,Han Solo,Yoda)))$
définir defiler($F$)
la nouvelle file obtenue par défilement de $F$ est la file :
de tête , la tête du troisième champ de $F$ ;
de queue celle de $F$ ;
et de troisième champ défiler(du troisième champ de $F$).
Cet opérateur transforme $F$ et renvoie la tête de $F$
Cet opérateur est lui aussi récursif.
En reprenant l'exemple précédent où $F=(Anakin,Yoda,(Boba Fett,Dark Vador,Han Solo))$; la commande $defiler(F)$ transforme la file $F$ en : $(Boba Fett,Yoda,(Dark Vador,Han Solo))$ et renvoie Anakin.
interface d'une file
L'interface de la structure de file est composée de :
Il peut être intéressant de connaître le nombre d'éléments dans une file.
En voila un pseudo-code :
nombreElement=0
while estVide(F) est faux
nombreElement+=1
defiler(F)
renvoyer nombreElement
Écrire un script en pseudo-code qui permet de supprimer le premier élément du troisième champ.
Cette structure de file est utilisée en informatique pour mémoriser les tâches qui doivent attendre pour être effectuées.
On l'utilise ainsi :
une imprimante va pouvoir traiter les impressions demandées dans l'ordre d'arrivée des requêtes en mémorisant ces demandes dans une file,
un système d'exploitation doit accorder du temps de calcul par les processeurs à chaque tâche. Lorsqu'aucune priorité n'est imposée, une file peut servir à gérer l'octroi du temps-machine aux tâches de même priorité,
La mémoire tampon (buffer en anglais) fonctionne sur le principe d'une file.
Une structure de données abstraites est une description conceptuelle présentant une image des données et des opérations pour les manipuler et les modifier.
L'ensemble des opérations permettant de manipuler et de modifier des données est appelé une interface.
La notion de pile est une structure de données abstraites.
Une pile est :
soit vide,
soit est constituée de deux champs : le haut de la pile et le reste de la pile.
L'interface élémentaire de la pile consiste en :
un constructeur pile()
qui permet de créer une pile vide,
un testeur est_vide(P)
qui permet de tester de tester si une pile est vide ou non,
un empileur empiler(a,P)
qui permet d'ajouter un élément en haut de la pile,
un dépileur depiler(P)
qui permet d'enlever le haut de la pile et de le renvoyer.
La notion de file est une autre structure de données abstraites.
Une file est :
soit vide,
soit est constituée de trois champs : une tête, un corps et une queue.
L'interface élémentaire de la file consiste en :
un constructeur file()
qui permet de créer une file vide,
un testeur est_vide(F)
qui permet de tester de tester si une file est vide ou non,
un enfileur enfiler(a,F)
qui permet d'ajouter un élément en queue de la file,
un défileur defiler(F)
qui permet d'enlever la tête de la file et de le renvoyer.
Implémentation
Implémenter une structure de données à travers une structure existante c'est écrire les éléments de l'interface à l'aide des outils proposées par la structure de données existante.
Tableau
Un tableau est une structure de données avec une taille fixe où chacune des cases est indexée. On peut accéder à une case connaissant son index.
Accès à une valeur d'un tableau
Pour accéder à une valeur indexée $i$ dans un tableau T. On écrira T[i]
.
On peut réaffecter une valeur du tableau par une autre à partir de son index.
Ce tableau a une longueur maximale de 7. T[1]=15. T[5] est vide.
Soit $P$ une pile.
On dispose d'un tableau nommé $T$ avec $n$ emplacements.
Il est possible d’implémenter la pile $P$ d’au plus $n$ éléments avec le tableau $T$.
Le tableau possède un attribut $sommet(P)$ qui indexe l’élément le plus récemment inséré.
La pile est constituée des éléments $T[1 . . sommet(P)]$, tous ceux compris entre $T[1]$, l’élément situé à la base de la pile, et $T[sommet(P)]$, l’élément
situé au sommet.
La donnée de la pile se constitue donc de la donnée de $T$ et de la valeur de $sommet(P)$.
On considère la pile $(9,(2,(6,(15,vide()))))$. Son implémentation se compose de la donnée du tableau T:
et de $sommet(P)=4$.
$sommet(P)$ est un index du tableau, pas un élément de la pile.
Implémentation de la fonction estVide(P)
estVide(paramètre : P)
si sommet(P)=0 //signifie que le tableau est vide
alors retourner VRAI
sinon retourner FAUX
Implémentation de la procédure empiler(a,P)
empiler(paramètres : a,P)
si sommet(P)=n //signifie que le tableau est complet
alors afficher "espace insuffisant"
sinon
sommet(P)←sommet(P)+1
T[sommet(P)]←a
Si on lance empiler(17,P)
puis empiler(3,P)
on obtient cette représentation :
Implémentation de la fonction depiler(P)
depiler(paramètre : P)
si sommet(P)=0
alors afficher "pile vide"
sinon sommet(P)←sommet(P)-1
retourner T[sommet(P)+1]
On observe que la procédure empiler ne renvoie rien alors que la fonction depiler renvoie un élément de la pile.
Si on lance depiler(P)
on obtient :
Observer que T[6]
a encore un sens pour le tableau mais plus pour la pile.
On considère la pile dont la représentation en tableau est :
Pour chaque question, on repartira du tableau de départ.
Qu'obtient-on si on lance successivement depiler(P)
, depiler(P)
,
depiler(P)
et depiler(P)
.
Qu'obtient-on si on lance successivement depiler(P)
, depiler(P)
,
depiler(P)
, depiler(P)
et depiler(P)
.
Qu'obtient-on si on lance successivement empiler(3,P)
, empiler(5,P)
et
depiler(P)
.
On dispose d'un tableau nommé $T$ avec $n$ emplacements.
Il est possible d’implémenter une file $F$ d’au plus $n$ éléments avec le tableau $T$.
Le tableau possède un attribut $tete(F)$ qui indexe l’élément de tête et un attribut $queue(F)$ qui indexe l'emplacement où un nouvel élément sera inséré. $T[queue(F)]$ est vide au sens de la file.
La file est constituée des éléments $T[tête(F) . . queue(F)-1]$.
Avec cette implémentation $T[n+1]$ doit pointer vers $T[1]$ au sens de la file. Une façon de visualiser cette implémentation est un tableau circulaire où le début du tableau et la fin du tableau seraient reliés.
Les éléments de la file se trouvent aux emplacements $tete(F)$, $tete(F) +1$, . . . , $queue(F) − 1$, après quoi l’on « boucle » : l’emplacement 1 suit immédiatement l’emplacement $n$ dans un ordre circulaire.
Dans cette implémentation la queue est vide
La donnée de la file se constitue de la donnée d'un tableau $T$, de la valeur de $tete(F)$ et de $queue(F)$.
Une représentation de l'implémentation avec un tableau $T$ de la file $F=(15,4,(6,9,8))$ est :
Quand $tete(F) = queue(F)$, la file est vide.
Quand $tete(F) = queue(F) + 1$, la file est pleine.
$queue(F)$ est vide au sens de la file. Si $tete(F) = queue(F)$ alors la tête est vide, c'est que la file est vide.
L'emplacement $queue(F)$ doit toujours être vide au sens de la file. Si $tete(F) = queue(F) + 1$, le prochain enfilage fera que $tete(F) = queue(F)$.
Implémentation de la fonction estVide(F)
estVide(P)
si queue(F)=tete(F)
alors retourner VRAI
sinon retourner FAUX
Implémentation de la fonction enfiler(a,F)
enfiler(a,F)
T(queue(F))←a
si queue(F)=n
alors queue(F)←1
sinon queue(F)←queue(F)+1
On dispose d'une file dont la représentation de l'implémentation en tableau est :
Si on lance enfiler(17,F)
puis enfiler(3,F)
et enfin
enfiler(5,F)
, on obtient cette représentation :
Implémentation de la fonction defiler(F)
Dans le pseudo-code suivant, $F$ désigne une file et $n$ correspond à la taille fixe du tableau servant à l'implémentation de la file.
defiler(F)
x←T[tete(F)]
si tete(F)=n
alors tete(F)←1
sinon tete(F)←tete(F)+1
retourner x
On dispose de la file de l'exemple précédent :
Si on lance defiler(F)
, on obtient :
Observer que T[7]
a encore un sens pour le tableau mais plus pour la file.
On considère la file dont la représentation de l'implémentation en tableau est :
Qu'obtient-on si on lance successivement defiler(F)
, defiler(F)
,
defiler(F)
et defiler(F)
.
Qu'obtient-on si on lance successivement defiler(F)
, defiler(F)
,
defiler(F)
, defiler(F)
et defiler(F)
.
Qu'obtient-on si on lance successivement enfiler(3,F)
, enfiler(5,F)
et
defiler(F)
.
Reprendre la fonction $enfiler()$ de la propriété où elle a été implémentée et y ajouter les erreurs de dépassements d'écritures.
On suppose que la structure de données Pile a été implémentée en Python.
On munit les piles des instructions suivantes :
vide()
renvoie une pile vide,
empiler(a,pile)
ajoute un élément a
en au haut de la pile pile
,
depiler(pile)
retourne la valeur retiré en haut de la pile pile
mais génère
un message d'erreur si la pile pile
est vide.
Voici une suite d'instructions :
P1=vide()
P2=vide()
empiler("o",P1)
empiler("u",P1)
empiler(3,P2)
x = depiler(P1)
empiler(x,P2)
empiler("i",P1)
empiler(x,P1)
empiler(depiler(P1),P2)
Que contiennent les piles P1 et P2 à l'issue de l'exécution de la suite d'instructions précédente ?
On suppose que la structure de données Pile a été implémentée en Python.
On munit les piles du même jeu d'instructions qu'à l'exercice précédent.
Voici une suite d'instructions :
P1=vide()
P2=vide()
P3=vide()
for i in range(12):
empiler(i,P1)
for j in range(3):
empiler(depiler(P1),P2)
depiler(P1)
empiler(depiler(P1),P3)
Que contiennent les piles P1, P2 et P3 à l'issue de l'exécution de la suite d'instructions précédente ?
On rajoute au jeu d'instructions précédent sur les piles la fonction est_vide
qui prend en
paramètre une pile et renvoie le booléen True
si la pile donnée en argument est vide et False
sinon.
En utilisant les quatre instructions autorisées sur les piles, proposer une fonction hauteur
,
qui prend en paramètre une pile et renvoie l'entier naturel correspondant au nombre d'élément de la pile
entrée comme argument.
Attention ! Faire en sorte que le contenu de la pile saisie comme argument ne soit pas modifié à l'issue de
l'exécution de la fonction hauteur
.
De même, proposer une fonction renverser
qui prend en paramètre une pile et renvoie une pile
formée des mêmes éléments que la pile saisie comme argument mais dont l'ordre est inversé.
Faire aussi en sorte que la pile saisie comme argument ne soit pas modifiée à l'issue de l'exécution de
cette fonction renverser
.
Implémentation d'une file à l'aide de deux piles
Dans cet exercice, on choisit d'implémenter une file file
à l'aide de d'un couple
(entree,sortie)
où entree
et sortie
sont deux piles.
Ainsi file[0]
correspond à entree
et file[1]
à sortie
.
Par exemple la file ci-contre :
peut être implémentée par les deux piles suivantes :
tout comme par les deux piles suivantes :
Voici le fonctionnement de cette file :
la pile entree
contient les éléments que l'on insère dans la file tandis que la pile
sortie
contient les éléments que l'on retire de la file.
la file est vide lorsque les deux piles entree
et sortie
sont vides.
enfiler un nouvel élément elt
dans la file revient à empiler cet élément dans la pile
entree
.
Voici une illustration de enfiler(elt,file)
:
defiler un élément de la file, il faut que celle-ci ne soit pas vide. Alors, deux cas se présentent :
la pile sortie
n'est pas vide : on dépile cette pile sortie
,
Voici une illustration de defiler(file)
dans ce cas :
la pile sortie
est vide : on dépile alors les éléments de la pile entree
un à un en les empilant dans la pile sortie
jusqu'à ce que entree
soit vide ;
ensuite, on dépile un élément de la pile sortie
.
Voici une illustration de defiler(file)
dasn ce cas :
On suppose que la file file
est dans l'état correspondant à la figure suivante :
On exécute la séquence d'instructions suivantes :
enfiler(1,file)
defiler(file)
defiler(file)
enfiler(2,file)
defiler(file)
Représenter le contenu final des deux piles représentant la file file
à la suite de ces instructions.
A la suite des instructions déjà effectuées précédemment, on exécute la séquence d'instructions suivantes :
defiler(file)
enfiler(3,file)
enfiler(defiler(file),file)
Représenter le contenu final des deux piles représentant la file file
à la suite de ces instructions.
On suppose disposer des fonctions suivantes écrite en langage Python :
empiler(elt,pile)
qui empile l'élément elt
sur la pile pile
,
depiler(pile)
qui dépile le sommet de la pile pile
, si elle n'est pas vide,
et renvoie ce sommet,
pile_vide(pile)
qui renvoie le booléen True
si la pile pile
est vide et False
sinon.
Écrire en langage Python une fonction est_vide(file)
qui prend en argument une file
file
constituée d'un couple de piles et qui renvoie True
si la file
file
est vide et False
sinon.
Écrire en langage Python une fonction enfiler(elt,file)
qui prend en argument
un entier elt
et une file file
constituée d'un couple de piles et qui
ajoute elt
en queue de la file file
.
Écrire en langage Python une fonction defiler(file)
qui prend en argument
une file file
, supposée non vide, constituée d'un couple de piles et qui
renvoie l'élément en tête de la file file
en en le retirant.
Il est possible d'implémenter une pile sous forme d'une liste Python en utilisant la méthode
append()
pour empiler et celle pop()
pour dépiler le sommet.
Programmer les trois fonctions empiler(elt,pile)
, depiler(pile)
et
pile_vide(pile)
de l'exercice précédent en implémentant une pile comme une liste
Python.
Il existe une implémentation spécifique pour les piles et les files dans le module queue (cf. documentation officiel )
Nous verrons au prochain chapitre la programmation objet qui permettra d'implémenter aussi ces types abstraits.
Les différents
auteurs mettent l'ensemble du site à disposition selon les termes de la licence Creative
Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0
International