Programme officiel
| Contenus | Capacités attendues | Commentaires |
|---|---|---|
| Listes, piles, files : structures linéaires. Dictionnaires, index et clé. | Distinguer des structures par le jeu des méthodes qui les caractérisent. Choisir une structure de données adaptée à la situation à modéliser. Distinguer la recherche d’une valeur dans une liste et dans un dictionnaire. |
On distingue les modes FIFO(first in first out) et LIFO (last in first out) des piles et des files. |
- Dans une liste chaînée, chaque élément :
- prend une place libre quelconque en mémoire.
- connaît l’emplacement de l’élément suivant.
Dans une liste chaînée, ajouter un élément se fait en temps constant. Par contre, pour lire l’élément de rang n, la complexité est linéaire en n.
Information
Une interface est le point de communication entre la structure de données (ici la liste chaînée) et l’utilisateur (ici l’Homme).
- L’interface d’une liste chaînée propose les fonctionnalités pour utiliser la structure :
- vérifier si la liste est vide,
- renvoyer la taille de la liste,
- renvoyer l’élément de rang n,
- insérer un élément.
La programmation orientée objet est un choix d’implémentation possible. Il n’est pas unique.
class Maillon:
"""
Crée un maillon de la liste chaînée
"""
def __init__(self, val: int, suiv: object):
self.valeur = val
self.suivant = suiv
class Liste:
"""
Crée une liste chaînée
"""
def __init__(self):
# selt.tete référence un Maillon
self.tete = None
Les méthodes ajoutées à l’objet Liste implémenteront l’interface proposée.
class Liste:
"""
Crée une liste chaînée
"""
def __init__(self):
# selt.tete référence un Maillon
self.tete = None
def est_vide(self) -> bool:
return self.tete is None
def ajouter(self, val: int) -> None:
self.tete = Maillon(val, self.tete)