Aller au contenu

Listes et listes chaînées

Listes : interface

Une liste est une structure de donnée permettant de regrouper un nombre fini de données de manière séquentielle.

Par exemple \((0, 1, \pi, 1, -6, 1, \textrm{\texttt{"Bonjour"}} )\) est une liste. De manière générale on préfère que tous les éléments d'une liste soient du même type. Par exemple tous les éléments de la liste \((3, 5, 9)\) sont des entiers.

Interface

On donne ci-dessous la liste des opérations que doit supporter un objet de type liste :

Fonction Description
creer_vide() Renvoie une liste vide.
est_vide(l) Teste si la liste l est vide.
ajoute(l, e) Ajoute au début de la liste l l'élément e.
tete(l) Renvoie le premier élément de la liste l.
queue(l) Renvoie la liste constituée de tous les éléments de l sauf le premier.

Implémentation via des listes chaînées

Définition et exemple d'utilisation

Dans cette implémentation du type liste, les éléments sont chaînés entre eux : chaque élément de la liste est stocké dans un objet Maillon, où il y est accompagné de l'adresse mémoire de l'élément suivant dans la liste.

On décide de représenter un maillon vide par l'élément None.

1
2
3
4
5
6
class Maillon:
    """ Un maillon d'une liste chainée. """
    def __init__(self, v, s):
        """ int, Maillon -> None """
        self.valeur = v
        self.suivant = s
Schéma

Avec cette implémentation, chaque élément de la liste est chaîné au suivant.

1
maillon1 = Maillon(-4, Maillon(123, None))

img

Cela correspond à la liste \((-4, 123)\).

Une liste est représentée par son maillon de tête. On peut alors implémenter les fonctions suivantes de l'interface.

1
2
3
4
5
def creer_vide() -> Maillon: return None
def est_vide(m: Maillon) -> bool: return m is None
def ajoute(m: Maillon, e: int) -> Maillon: return Maillon(e, m)
def tete(m: Maillon) -> int: return m.valeur
def queue(m: Maillon) -> Maillon: return m.suivant
Parcours récursif

Pour écrire une fonction f qui prend en argument une liste l et résout le problème \(\mathcal{P}\) :

  • On traite le cas de base selon le contexte du problème : cela correspond souvent au cas où la liste est vide ou constituée d'un seul élément (singleton).

  • Dans le cas général :

    1. On obtient récursivement une solution partielle en appliquant la fonction f résolvant le problème à la queue de la liste.

    2. On utilise la solution partielle et la tête de la liste pour répondre au problème général.

img

Décrire un algorithme récursif qui prend en argument une liste d'entiers l et qui renvoie une liste composée des éléments de l rangés dans le sens inverse.

On supposera écrite la fonction concatene qui prend en argument deux listes l1 et l2 et qui renvoie la liste constituée des éléments de l1 et de l2 mis bout à bout dans cet ordre.

  • Dans le cas où la liste l est vide : si l = () alors renverse(l) renvoie ().

  • Dans le cas général : par exemple si l = (5, 7, 1, 4, 2).

    Si on note avant = renverse(queue(l)) = (2, 4, 1, 7). Il suffit de concaténer avant avec la liste singleton (5).

    Alors reponse = concatene(avant, singleton(tete(l)))

    On renvoie renverse(l) renvoie reponse = (2, 4, 1, 7, 5).

1
2
3
4
5
6
7
8
9
def renverse(l):
    """ Liste -> Liste
    Renvoie une liste où les éléments apparaissent dans
    l'ordre inverse par rapport à la liste initiale. """
    if est_vide(l):
        return l
    else:
        avant = renverse(queue(l))
        return concatene(avant, singleton(tete(l)))
Parcours itératif

Pour écrire une fonction f qui prend en argument une liste l et résout le problème \(\mathcal{P}\). On parcourt les éléments de la liste les uns après les autres :

  • On initialise une variable maillon_courant qui permet d'accéder à un maillon dans la chaîne.

  • Lors de chaque itération, on remplace maillon_courant par le prochain maillon de la chaine : maillon_courant = maillon_courant.suivant

Lors de ce parcours, on utilise les structures de données et les algorithmes adéquats pour répondre au problème posé.

Écrire une fonction renverse qui prend en argument une liste d'entiers l et qui renvoie une liste composée des éléments de l rangés dans le sens inverse.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def renverse(m):
    """ Maillon -> Maillon
    Renvoie le maillon de tête d'une chaîne dont les éléments
    apparaissent dans l'ordre inverse par rapport à celle dont
    m est le maillon de tête. """
    maillon_courant = m
    rev = None
    while maillon_courant is not None:
        rev = Maillon(maillon_courant.valeur, rev)
        maillon_courant = maillon_courant.suivant
    return rev

Objet mutable

  • Le constructeur Maillon construit un nouveau maillon, indépendant des autres maillons déjà créés.

  • Lorsque m est un maillon, on accède à ses attributs via m.valeur et m.suivant. Si l'on affecte une nouvelle valeur à ces attributs, on modifie en place le maillon m.

1
2
3
m1 = Maillon(1,None)
m2 = Maillon(2, m1)
m1 = Maillon(1, m2)

1
2
3
m1 = Maillon(1, None)
m2 = Maillon(2, m1)
m1.suivant = m2

Pour le moment l'interface donnée ne permet pas de modifier un objet de type Maillon. On peut l'enrichir de deux nouvelles fonctions qui permettent respectivement de modifier l'attribut valeur et l'attribut suivant d'un objet de type Maillon :

1
2
def set_valeur(m:Maillon, e:int) -> None: m.valeur = e
def set_suivant(m:Maillon, m2:Maillon) -> None : m.suivant = m2

Écrire une fonction ajoute_fin qui étant donné une liste l et un entier e et qui renvoie la liste composée des éléments de l à laquelle on a ajouté l'élément e.

La liste initiale ne sera pas modifiée.

1
2
3
4
5
6
7
8
9
def ajoute_fin(l, e):
    """ Liste, int -> Liste
    La liste l n'est pas modifiée """
    # version récursive
    if est_vide(l):
        return singleton(e)
    else:
        avant = ajoute_fin(queue(l), e)
        return ajoute(avant, tete(l))

Écrire une fonction ajoute_fin qui prend en argument un maillon m et un entier e et qui renvoie ajoute à la fin de la liste chaînée dont le premier maillon est m un maillon de valeur e.

On pourra modifier des objets existant.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def ajoute_fin(m, e):
    """ Maillon, int -> None
    Les éléments de la chaîne dont le maillon de tête
    est m peuvent être modifiés. """
    # version itérative
    if m is None:
        return Maillon(e, None)
    maillon_courant = m
    while maillon_courant.suivant is not None:
        maillon_courant = maillon_courant.suivant
    maillon_courant.suivant = Maillon(e, None)
    return m

Encapsulation dans un objet

La classe Liste ci-dessous implémente le type abstrait de données "listes non mutables", définit par l’interface de la section 1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Liste:
    def __init__(self, m = None):
        # Par défaut la liste est vide
        """ Initialise une liste dont le premier maillon est m. """
        self.head = m

    def ajoute(self, e: int):
        """ Ajoute en tête de liste l'élément e. """
        self.head = Maillon(e, self.head) # version mutable

    def queue(self):
        """ Renvoie la queue de la liste """
        return Liste(self.head.suivant) 

    def tete(self):
        """ Renvoie la valeur en tête de liste """
        return self.head.valeur

    def est_vide(self):
        """ Détermine si la liste est vide """
        return self.head is None

    def est_singleton(self):
        """ Détermine si la liste est constituée d'un seul élément """
        return not self.est_vide() and self.queue().est_vide()

    def affiche(self):
        """ Affiche la liste. """
        if self.est_vide():
            print("x")
        else:
            print(f"{self.tete()}", end = " - ")
            self.queue().affiche()

Il est possible d'importer toutes les fonctionnalitées de l'interface avec l'instruction :

1
from data_structures import Liste

Puis, on peut utiliser les objets de type Liste via les méthodes de l'interface.

1
2
3
4
5
l = Liste()
l.ajoute(42)
l.ajoute(3)
l.ajoute(2)
l.affiche()

2 - 3 - 42 - x