Aller au contenu

Structure

Avant de parler de l'implémentation, nous allons parler d'abstraction.

Structure

Une structure est une implémentation à partir du moment où toutes les fonctions nécessaires au bon fonctionnement ont été réalisées dans un langage de programmation. Sinon, on parle de Type Abstrait de Données (TAD), et c'est ici que nous définissons les actions pour modifier ou agir sur notre structure.

Étape 1 : Concevoir le cahier des charges (TAD)

Nous devons définir la structure en indiquant ce qu'elle fait et comment elle fonctionne. Pour cela, nous utiliserons une structure de liste abstraite. Il s'agit d'un ensemble de règles qui ne vont pas dépendre de l'implémentation.

L'intérêt de la liste

Une liste est un type abstrait de données contenant un ensemble d'éléments qui sont tous accessibles.

Nous nommons notre structure de liste avec le nom Liste.

Les Primitives

Une primitive est une fonction de base qui définit un concept simple permettant de modifier notre structure (ici la liste).

On distingue deux types de primitives :

Les primitives de base :

  • creerListeVide() : Liste - Crée et renvoie une liste vide
  • estVide() : Liste -> Booléen - Renvoie Vrai si la liste est vide, Faux sinon
  • ajouterTete() : Liste, Élément -> Liste - Modifie la liste en ajoutant un élément en tête de liste
  • retirerTete() : Liste -> Liste, Élément - Supprime l'élément de tête et renvoie sa valeur
  • ajouterQueue() : Liste, Élément -> Liste - Modifie la liste en ajoutant un élément en queue de liste
  • retirerQueue() : Liste -> Liste, Élément - Supprime l'élément de queue et renvoie sa valeur
  • obtenirTete() : Liste -> Élément - Renvoie la valeur de l'élément de tête
  • obtenirQueue() : Liste -> Élément - Renvoie la valeur de l'élément de queue

Les primitives auxiliaires :

  • inserer() : Liste, Élément, Entier -> Liste - Insère l'élément à la position indiquée dans la liste
  • supprimer() : Liste, Entier -> Liste - Supprime l'élément situé à la position indiquée dans la liste

Schéma des primitives

Si on suppose cette structure implémentée en Python, voici ce que cela donnerait :

l = Liste()
l.estVide()       # True
l.ajouterTete(3)  # 3
l.ajouterTete(8)  # 8 3
l.ajouterQueue(9) # 8 3 9
l.estVide()       # False
l.retirerTete()   # 3 9    - Retourne 8
l.ajouterTete(7)  # 7 3 9
l.retirerQueue()  # 7 3    - Retourne 9
l.estVide()       # False
l.ajouterTete(4)  # 4 7 3
l.retirerQueue()  # 4 7    - Retourne 3
l.estVide()       # False

Étape 2 : Proposer une implémentation

Liste Chaînée (simple)

LinkedList

Une Liste Chaînée (Simple), est une implémentation d'une liste dans laquelle :

  • Tous les éléments sont appelés des Cellules et se composent de deux choses :
    • une valeur
    • un lien, en fait un pointeur / référence, vers l'élément suivant / successeur
  • On suppose également connue la référence vers la première Cellule appelée Tête (et seulement cette référence)

Taquet vers le haut

Le symbole ⊥ appelé taquet vers le haut permet de représenter la fin de la liste (la queue) et indique donc qu'il n'y a pas de cellule suivante après le dernier élément la queue.

En Python, on utilise souvent None pour implémenter ce concept.

Variantes des listes chaînées

Il existe plusieurs variantes de listes chaînées, notamment deux que nous aurons l'occasion d'étudier :

  • La liste cyclique où le dernier élément est lié au premier
  • La liste doublement chaînée où chaque élément possède un lien vers l'élément précédent en plus de l'élément suivant

Exo : Représenter ces deux variantes avec un schéma sur la liste [1, 2, 3]

Homogénéité

Dans le cas où tous les éléments de la liste sont du même type, on parle de liste homogène. Il est recommandé d'avoir des listes homogènes, même si Python autorise l'usage de listes non homogènes.

Implémentation par une classe Cellule

La cellule va nous permettre de représenter nos différents chaînons pour notre liste.

class Cellule:
    """Représente un élément de notre liste"""

    def __init__(self, v, s=None):
        """Crée un élément d'une liste"""
        self.valeur = v
        self.suivante = s

Chaque objet de la classe Cellule contient deux attributs :

  • valeur qui représente la valeur de l'élément de notre liste ;
  • suivante qui représente l'élément suivant dans la liste ou None le cas échéant.

La variable lst ci-dessous correspond donc à une liste contenant les valeurs [1, 2, 3].

Cellules Cellules

Exercice : Implémentation d'une Liste Chaînée par une classe Cellule

  1. Implémenter une classe Cellule disposant :
    • d'attributs :
      • un attribut valeur contenant une valeur de la liste (par exemple un entier)
      • un pointeur/attribut suivante vers la Cellule suivante (initialisé à None pour une Cellule n'ayant pas de successeur)
    • de méthodes :
      • un getter get_valeur() qui renvoie la valeur de la Cellule courante
      • un getter get_suivante() qui renvoie le pointeur vers la Cellule suivante
      • un setter set_suivante() qui modifie le pointeur vers la Cellule suivante
  2. Implémenter une Liste Chaînée par cette classe Cellule :
    On peut alors implémenter une Liste Chaînée (Simple) 4 (tête) --> 2 --> 9 --> 5 (queue) par les instructions suivantes : 
    # Version 1 : Créer chaque Cellule puis les relier entre-elles
cell1 = Cellule(4)
cell2 = Cellule(2)
cell3 = Cellule(9)
cell4 = Cellule(5)

cell1.set_suivante(cell2)
cell2.set_suivante(cell3)
cell3.set_suivante(cell4)

liste_finale = cell1

# Version 2 : Créer les Cellules dans l'ordre décroissant
cell4 = Cellule(5)
cell3 = Cellule(9)
cell3.set_suivante(cell4)
cell2 = Cellule(2)
cell2.set_suivante(cell3)
cell1 = Cellule(4)
cell1.set_suivante(cell2)

liste_finale = cell1

# Version 3 : En utilisant le constructeur
liste_finale = Cellule(4, Cellule(2, Cellule(9, Cellule(5))))

Une Liste Chaînée (Simple) peut donc être implémentée par:

  • soit la valeur None
  • soit un objet de classe Cellule contenant:
    • un attribut valeur contenant la valeur de la Cellule
    • un attribut suivante renvoyant vers une Liste (Simplement) Chaînée

Écrire le code de la méthode __len__ qui calcule et affiche la longueur de la liste courante.

Écrire le code de la méthode __getitem__ qui renvoie la valeur de la i-ème cellule de la liste courante.

Implémentation par une classe Liste

Nous ne pouvons pas conserver notre liste comme une Cellule. En effet, on veut pouvoir conserver un accès vers la tête et (pourquoi pas) vers la queue de notre liste. Pour cela, nous allons créer une classe Liste qui sera similaire à notre TAD (Type Abstrait de Données).

class Liste:

    def __init__(self):
        """Crée une liste vide (fonction abstraite creerListeVide())"""
        self.tete = None

Quel est l'intérêt d'une telle implémentation ? Elle cache la représentation de la structure à l'utilisateur : ainsi, en utilisant la classe Liste, l'utilisateur n'a plus à utiliser la classe Cellule.

Exercice : Implémentation d'une Liste Chaînée par une classe Liste

On va utiliser la classe Cellule précédente (qu'il faudra peut-être adapter) pour implémenter une classe Liste.

Implémenter une classe Liste, disposant :

  • de 1 attribut :
    • un attribut tete contenant la référence vers la Cellule en tête ou None si la liste est vide
  • des méthodes suivantes énoncées en TAD :
    • creerListeVide() : Liste - Crée et renvoie une liste vide
    • estVide() : Liste -> Booléen - Renvoie Vrai si la liste est vide, Faux sinon
    • ajouterTete() : Liste, Élément -> Liste - Modifie la liste en ajoutant un élément en tête de liste
    • retirerTete() : Liste -> Liste, Élément - Supprime l'élément de tête et renvoie sa valeur
    • ajouterQueue() : Liste, Élément -> Liste - Modifie la liste en ajoutant un élément en queue de liste
    • retirerQueue() : Liste -> Liste, Élément - Supprime l'élément de queue et renvoie sa valeur

Étape 3 : Améliorer son implémentation

On remarque quelques problèmes sur l'implémentation précédente :

  • L'ajout ou la suppression d'un élément en queue est long, car il faut parcourir la liste en entier
  • De même pour le calcul de la longueur

Listes Chaînées (Doubles)

Une Liste Chaînée Double (comprendre à Double Extrémité) est une Liste Chaînée (Simple) contenant une référence :

  • vers le premier élément (la tête) de la liste (comme d'habitude)
  • vers le dernier élément (la queue) de la liste
class Liste:

def __init__(self):
    """Crée une liste vide (fonction abstraite creerListeVide())"""
    self.tete = None
    self.queue = None