Comprendre la structure de données des types liste, pile et file
- Fiche de cours
- Quiz et exercices
- Vidéos et podcasts
- Comprendre et utiliser la structure de données de type liste.
- Comprendre et utiliser la structure de données de type pile.
- Comprendre et utiliser la structure de données de type file.
- Une liste est un objet qui peut contenir d’autres
objets de n’importe quel type.
On repère un objet à l’intérieur d’une liste par rapport à sa place, en n’oubliant pas qu’en informatique le premier est à l’indice 0. - Dans une pile, on empile et dépile les données : les dernières données ajoutées à une pile sont les premières à sortir.
- Dans une file, on enfile et défile des données : les premiers éléments ajoutés à une file sont les premiers à être récupérés.
- Notion de liste
- Type abstrait de données et interfaçage
On doit de plus pouvoir parcourir l'intégralité de la structure à l'aide de cette fonction « successeur », sans passer deux fois par le même élément. Cela repose sur une notion nommée « liste chainée ».
Parmi les structures de données linéaires, on trouve notamment les listes, mais aussi les piles et les files. Il est important de savoir distinguer chacune de ces structures, grâce aux méthodes qui les caractérisent.
L’interfaçage de la structure de données de type liste permet de spécifier sa représentation dans un environnement théorique de développement, en décrivant notamment les différentes opérations qu’elle doit respecter (primitives).
En utilisant le langage Python, il faut utiliser les [] pour définir une liste.
- Liste des notes d’un élève : [10, 11.5, 13.1]
- Liste de courses : Course=["tomates", "salade", "beurre"]
-
Course contient 3
éléments, on dit que la liste est de
longueur 3.
Course[0]="tomates" - Liste composite : [2,10,"salade",[11,12]]
- Pour séparer les éléments, on utilise une virgule. Pour écrire un nombre décimal, on utilise l’écriture à l'anglo-saxonne en utilisant un point.
- Pour reconnaitre un caractère ou une chaine de caractères, il faut utiliser les " " en Python.
Une liste est un objet modifiable.
Les données d’une liste doivent permettre de réaliser les opérations suivantes.
- Création d’une liste vide L.
- Ajouter un élément a au début de L.
- Ajouter un élément a à la fin de L.
- Supprimer le premier élément de la liste L, que l’on appelle « en-tête ».
- Supprimer le dernier élément de la liste L.
- Obtenir l’en-tête de la liste L.
- Obtenir la longueur d’une liste.
L'intérêt des listes c’est qu’elles sont mutables, elles sont donc très flexibles d’utilisation.
On crée par exemple une liste pour une liste de course.
La liste est une structure de données qui est nativement présente sur Python, on peut donc directement créer une liste en Python.
Les méthodes de la structure de données de type liste sont les suivantes.
- Création d’une liste vide L : L=[]
- Ajouter un élément a au début de L.
- Ajouter un élément a à la fin de L : L.append(a)
- Supprimer le premier élément de la liste L : L.remove(L[0])
- Supprimer le dernier élément de la liste L : pop(L)
- Obtenir l’en-tête de la liste L : L[0]
- Obtenir la longueur d’une liste L : len(L)
| Python | Explication |
| L=[] | On crée la liste vide L. |
| L.append(5) | On ajoute 5, donc L=[5]. |
| L.append(7) | On ajoute 7, donc L=[5,7]. |
| print(L) | On affiche la liste L. |
L’interfaçage de la structure de données de type pile permet de spécifier sa représentation dans un environnement théorique de développement, en décrivant notamment les différentes opérations qu’elle doit respecter (primitives).
Les dernières données ajoutées à la pile sont les premières à sortir.
La meilleure représentation pour comprendre le fonctionnement d'une pile est celle d’une pile d’assiettes.
Les données d’une pile doivent permettre de réaliser les opérations suivantes.
- Créer une pile vide.
- Tester si une pile est vide.
- Ajouter un élément à la pile = EMPILER (push en anglais).
- Retirer un élément de la pile = DEPILER (pop en anglais).
- Obtenir le sommet de la pile.
- Lorsqu’on surfe sur le net, le navigateur web que l’on utilise crée une pile qui sert à mémoriser les adresses URL des pages visitées. L'adresse de chaque nouvelle page visitée est empilée. Lorsqu’on clique sur « Afficher la page précédente », l’ordinateur dépile la dernière adresse URL.
- Les traitements de texte créent une pile dans laquelle toutes les modifications sont stockées, du coup l’appui sur l'icône « Annuler la frappe » va provoquer le dépilement.
On peut créer une classe Pile, qui va permettre de générer des piles.
Il faut donc implémenter les opérations de cette structure de données en Python : on peut utiliser des méthodes de la structure de données de type liste.
- La méthode append(x) ajoute à la fin de la liste l’élément x : elle correspond au push (empilement) d’une pile.
- La méthode pop(x) permet d’enlever le dernier élément de la liste : elle correspond au pop (dépilement) d’une pile.
- La méthode len retourne la longueur de la liste.
On construit l’implémentation de la classe Pile par étapes.
Voici ci-dessous l’explication de ce code ligne par ligne.
| Python | Explication |
| class Pile: | On crée la classe Pile. |
|
"' classe Pile création d’une instance Pile avec une liste '" |
On documente cette classe. |
| def _init_(self): | On crée le constructeur. |
|
"Initialisation d’une pile vide" |
On documente le constructeur. |
| self.L=[] | On crée une instance vide, à partir d’une liste L. |
Voici ci-dessous l’explication de ce code ligne par ligne.
| Python | Explication |
| def vide(self): | On crée la méthode vide. |
|
"teste si la pile est vide" |
On documente cette méthode. |
| return self.L==[] | On teste si la liste créée (donc la pile) est vide. |
Voici ci-dessous l’explication de ce code ligne par ligne.
| Python | Explication |
| def empiler(self,x): | On crée la méthode empiler. |
| "empile" | On documente cette méthode. |
| self.L.append(x) | On ajoute à la fin de l’instance la valeur x. |
Voici ci-dessous l’explication de ce code ligne par ligne.
| Python | Explication |
| def depiler(self): | On crée la méthode depiler. |
| "dépile" | On documente cette méthode. |
|
assert not self.vide(), "Pile vide" |
On met en place une vérification : si l’instance n’est pas vide, on passe à la ligne suivante, sinon on affiche « Pile vide ». |
| return self.L.pop() | On retourne l’instance en enlevant son dernier élément. |
Pour éviter un message d’erreur si la pile est vide, on intercepte l’erreur à l’aide de la ligne 20.
Voici ci-dessous l’explication de ce code ligne par ligne.
| Python | Explication |
| def sommet(self): | On crée la méthode sommet. |
|
"renvoie le sommet de la pile" |
On documente cette méthode. |
|
assert not self.vide(), "Pile vide" |
On met en place une vérification : si l’instance n’est pas vide, on passe à la ligne suivante, sinon on affiche « Pile vide ». |
| return self.L[–1] | On retourne le dernier élément de l’instance. |
- On ne peut obtenir le sommet que si la pile n’est pas vide : il faut donc le prévoir dans l’écriture de la fonction sommet (ligne 25).
- L’indice « –1 » de la ligne 26 indique que l’on retourne le dernier élément de la liste, donc de la pile.
Pour simplifier l’affichage et la notation, on peut ajouter la méthode suivante avant de faire appel à l’instruction print.
Une fois la classe Pile implémentée en Python grâce aux lignes de code précédentes, on peut créer une pile en ajoutant les lignes de code suivantes.
Voici ci-dessous l’explication de ce code ligne par ligne.
| Python | Explication |
| p=Pile() | On crée une pile p vide. |
| p.empiler(5) | On empile la valeur 5 dans p, donc p=[5]. |
| print(p) | On affiche la pile p. |
L’interfaçage de la structure de données de type file permet de spécifier sa représentation dans un environnement théorique de développement, en décrivant notamment les différentes opérations qu’elle doit respecter (primitives).
Les premiers éléments ajoutés à la file sont les premiers à être récupérés.
La meilleure représentation pour se représenter cette structure de données est l’image d’une file d’attente à une caisse de supermarché.
File d’attente à une caisse de supermarché
Les données d’une file doivent permettre de réaliser les opérations suivantes.
- Créer une file vide.
- Tester si la file est vide.
- Ajouter un élément à la file : enfiler.
- Retirer le premier élément de la file : défiler.
- Obtenir le premier élément de la file.
- La mémorisation temporaire de transactions qui doivent être traitées.
- La mémorisation temporaire des travaux d’impression dans une file d’attente.
On peut créer une classe File, qui va permettre de générer des files.
Il faut donc implémenter les opérations de cette structure de données en Python : on peut utiliser les méthodes de la structure de données de type liste.
- La méthode append(x) ajoute à la fin de la liste l’élément x : elle correspond à l’enfilement d’une file puisqu’on ajoute à la fin l’élément x.
- La méthode pop(x) permet d’enlever le dernier élément de la liste : elle correspond au défilement d’une file.
- La méthode len retourne la longueur de la liste.
On construit l’implémentation de la classe File par étapes.
Voici ci-dessous l’explication de ce code ligne par ligne.
| Python | Explication |
| class File: | On crée la classe File. |
|
"' classe File création d’une instance File avec une liste '" |
On documente cette classe. |
| def _init_(self): | On crée le constructeur. |
|
"Initialisation d’une File vide" |
On documente le constructeur. |
| self.L=[] | On crée une instance vide, à partir d’une liste L. |
Voici ci-dessous l’explication de ce code ligne par ligne.
| Python | Explication |
| def vide(self): | On crée la méthode vide. |
|
"teste si la file est vide" |
On documente cette méthode. |
| return self.L==[] | On teste si l’instance créée est vide. |
Voici ci-dessous l’explication de ce code ligne par ligne.
| Python | Explication |
| def enfiler(self,x): | On crée la méthode enfiler. |
| "enfile" | On documente cette méthode. |
| self.L.append(x) | On ajoute à la fin de l’instance la valeur x. |
Voici ci-dessous l’explication de ce code ligne par ligne.
| Python | Explication |
| def defiler(self): | On crée la méthode defiler. |
| "défile" | On documente cette méthode. |
|
assert not self.vide(), "File vide" |
On met en place une vérification : si l’instance n’est pas vide, on passe à la ligne suivante, sinon on affiche « File vide ». |
| return self.L.pop(0) | On retourne l’instance en enlevant son premier élément. |
Voici ci-dessous l’explication de ce code ligne par ligne.
| Python | Explication |
| def premier(self): | On crée la méthode premier. |
|
'''renvoie le premier élément de la file''' |
On documente cette méthode. |
|
assert not self.vide(), "file vide" |
On met en place une vérification : si l’instance n’est pas vide, on passe à la ligne suivante, sinon on affiche « file vide ». |
| return self.L[0] | On retourne le premier élément de l’instance. |
Pour simplifier l’affichage et la notation, on peut ajouter la méthode suivante avant de faire appel à l’instruction print.
Une fois la classe File implémentée en Python grâce aux lignes de code précédentes, on peut créer une file en ajoutant les lignes de code suivantes.
Voici ci-dessous l’explication de ce code ligne par ligne.
| Python | Explication |
| f=file() | On crée une file f vide. |
| f.enfiler(6) |
On enfile la valeur 6 dans la
file f, donc f=[6]. |
| f.enfiler(7) |
On enfile la valeur 7 dans la
file f, donc f=[6,7]. |
| f.defiler() | On défile, donc on enlève la valeur 6, donc f=[7]. |
| print(f) | On affiche la pile f. |
Évalue ce cours !
Des quiz et exercices pour mieux assimiler sa leçon
La plateforme de soutien scolaire en ligne myMaxicours propose des quiz et exercices en accompagnement de chaque fiche de cours. Les exercices permettent de vérifier si la leçon est bien comprise ou s’il reste encore des notions à revoir.
Des exercices variés pour ne pas s’ennuyer
Les exercices se déclinent sous toutes leurs formes sur myMaxicours ! Selon la matière et la classe étudiées, retrouvez des dictées, des mots à relier ou encore des phrases à compléter, mais aussi des textes à trous et bien d’autres formats !
Dans les classes de primaire, l’accent est mis sur des exercices illustrés très ludiques pour motiver les plus jeunes.
Des quiz pour une évaluation en direct
Les quiz et exercices permettent d’avoir un retour immédiat sur la bonne compréhension du cours. Une fois toutes les réponses communiquées, le résultat s’affiche à l’écran et permet à l’élève de se situer immédiatement.
myMaxicours offre des solutions efficaces de révision grâce aux fiches de cours et aux exercices associés. L’élève se rassure pour le prochain examen en testant ses connaissances au préalable.
Des vidéos et des podcasts pour apprendre différemment
Certains élèves ont une mémoire visuelle quand d’autres ont plutôt une mémoire auditive. myMaxicours s’adapte à tous les enfants et adolescents pour leur proposer un apprentissage serein et efficace.
Découvrez de nombreuses vidéos et podcasts en complément des fiches de cours et des exercices pour une année scolaire au top !
Des podcasts pour les révisions
La plateforme de soutien scolaire en ligne myMaxicours propose des podcasts de révision pour toutes les classes à examen : troisième, première et terminale.
Les ados peuvent écouter les différents cours afin de mieux les mémoriser en préparation de leurs examens. Des fiches de cours de différentes matières sont disponibles en podcasts ainsi qu’une préparation au grand oral avec de nombreux conseils pratiques.
Des vidéos de cours pour comprendre en image
Des vidéos de cours illustrent les notions principales à retenir et complètent les fiches de cours. De quoi réviser sa prochaine évaluation ou son prochain examen en toute confiance !
Fiches de cours les plus recherchées
Fermer
Accédez gratuitement à
