Programme

Contenus

Listes, piles, files : structures linéaires. Dictionnaires, index et clé.

Capacités attendues

• 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.

Les listes chaînées

Principe

Une liste “traditionnelle” contient des éléments de manière contigue en mémoire (ce sont en fait des tableaux). Ces tableaux ne sont (en théorie) pas performants pour insérer des valeurs à une position donnée, car ils nécessitent de décaler tous les éléments suivants (cout de N pour insérer un élément en première position dans un tableau de N valeurs), voire de recopier l’ensemble des données dans un autre espace mémoire si le bloc réservé initialement pour le tableau n’est pas assez grand.

Pour de meilleures performances (théoriques) en insertion, on peut utiliser des listes chaînées, constituées de “cellules”, chaque cellule contenant la valeur à stocker et l’adresse mémoire de la cellule suivante (Cellule(valeur, suivante)).

La liste est alors représentée par la première cellule (la tête), le reste des cellules formant la queue.

Exemple : la liste [1,2,3] peut alors s’écrire

liste = Cellule(1, Cellule(2, Cellule(3)))
#      tête        queue

Spécification

On voudrait pouvoir effectuer les opérations suivantes sur une liste chaînée :

• créer une nouvelle liste vide : liste = Liste()
• renvoyer sa longueur : liste.longueur()
• ajouter un élément au début de la liste : liste.ajoute_debut(valeur)
• ajouter un élément à la n-ième position dans la liste : liste.insere(n, valeur)
• renvoyer la valeur du n-iéme élément : liste.valeur(n)
• enlever un élément au début de la liste et renvoyer sa valeur : liste.enleve_debut()
• enlever un élément à la n-ième position dans la liste : liste.enleve(n)
• modifier le n-ième élément : liste.change_valeur(n, valeur)
• concaténer deux listes : liste.concatene(liste2) : ajoute liste2 à liste, en modifiant liste, sans reconstruire une nouvelle liste

Lorsque la position n donnée est invalide, les méthodes doivent lever une exception IndexError.

Encapsulation

On peut faire encore plus ressembler notre liste aux listes python en encapsulant ces fonctions dans un objet, et en implémentant les méthodes magiques du python, qui permettent de faire les opérations de la même manière que les listes python : https://docs.python.org/3/reference/datamodel.html#basic-customization

__repr__
__str__
__eq__
__getitem__
__setitem__
__delitem__
__add__
...

Implémentation

A faire ensemble en classe.

Pile (bis)

Principe

Principe LIFO (Last In First Out = Dernier Entré Premier Sorti)

Exemple = pile d’assiettes

Spécification

Définition : structure Pile (classe Pile)

• création d’une nouvelle pile
• ajouter une valeur à la pile Pile.empile(valeur)
• enlever et récupérer la dernière valeur Pile.depile() qui renvoie la dernière valeur entrée ou une erreur si la pile est vide
• (optionnel) nombre d’éléments de la pile : len(pile) via la méthode “magique” Pile.__len__()

Tests

# Exemples de tests
pile = Pile()
assert len(pile) == 0
pile.empile(42)
pile.empile(24)
assert len(pile) == 2
assert pile.depile() == 24
assert len(pile) == 1
# ....

Implémentation (via liste chaînée)

A faire ensemble en classe.

Exemples d’utilisation

• mise en rayon de produits
• rangements de valises (soute)
• annuler les modifications dans un fichier
• sauvegardes dans un jeu

File ou queue (bis)

Principe

Principe : First In First Out (FIFO = Premier Entré Premier Sorti)

Exemple : queue au supermarché

Spécification

Spécification : structure File (classe File)

• création d’une file File
• ajouter un élément dans la file File.enfile(valeur)
• récupérer le premier élément de la file et le supprimer de la file File.defile(), renvoie une erreur si la file est vide.
• (optionnel) nombre d’éléments de la file : len(file) via la méthode “magique” File.__len__()

Tests

# Exemples de tests
file = File()
assert len(file) == 0
file.enfile(42)
file.enfile(24)
assert len(file) == 2
assert file.defile() == 42
assert len(file) == 1
# ....

Implémentation (via liste chaînée)

A faire ensemble en classe.