Fiche à imprimer

On a vu dans le TD précédent que la difficulté avec les listes était surtout leur taille variable et nous avons vu qu'un moyen de gérer cette difficulté était de passer par une liste chaînée.

La liste se présente comme une succession de maillons d'une chaîne. Dans chaque maillon on trouve une donnée et un lien vers le maillon suivant. Partant du premier maillon, on peut parcourir la chaîne jusqu'au bout.

Ci-dessous, la liste 2:17:5.

Une donnée immuable ne peut pas être modifiée, comme les tuple ou les string de Python. Pour les modifier, on crée un copie contenant la version modifiée et l'original reste intact.

Comme l'intérêt de la liste est d'avoir une taille variable, donc d'être modifiable, il me parait plus naturel de la rendre mutable.

Donc les fonction INSERER, SUPPRIMER, MODIFIER auront pour effet de modifier la liste fournie.

Pour plus de simplicité – la gestion des erreurs n'étant pas au programme – si on appelle RECHERCHE pour un élément absent, la fonction renverra -1.

Pour représenter un maillon de la chaîne, nous avons besoin d'une donnée pouvant contenir deux éléments que l'on peut modifier. Je propose d'utiliser un dictionnaire avec les clés “data” et “next”.

“next” contiendra le maillon suivant ou None s'il n'y en a pas.

Trois exemples d'assemblage de maillons pour 2:17:5 – tous également justes :

m0 = { "data":2, "next":None }
m1 = { "data":17, "next":None }
m2 = { "data":5, "next":None }
m0["next"] = m1
m1["next"] = m2

m0 = { "data":2, "next":None }
m0["next"] = { "data":17, "next":None }
m0["next"]["next"] = { "data":5, "next":None }

m2 = { "data":5, "next":None }
m1 = { "data":2, "next":m2 }
m0 = { "data":17, "next":m1 }

L'entête sert à fixer le point de départ de la liste. Ainsi, même si on insère de nouveaux maillons au début, cela ne change pas le point de départ.

Nous adopterons un format semblable aux maillons : un dictionnaire contenant une seule clé, “head”, contenant le premier maillon s'il y en a un, None sinon.

Exemple de la réalisation de L = 2:17:5 – on pourrait varier l'écriture comme dans l'exemple précédent.

L = { "head": None }
m0 = { "data":2, "next":None }
m1 = { "data":17, "next":None }
m2 = { "data":5, "next":None }
L["head"] = m0
m0["next"] = m1
m1["next"] = m2

m0 = { "data":2, "next":None }
m1 = { "data":17, "next":None }
m0["next"] = m1

Dans ce code, m0 et m1 ne sont pas les maillons eux-mêmes mais des références aux maillons, des adresses mémoires, des pointeurs. C'est ce qu'on a représenté par des flèches.

On peut penser que m0 contient vraiment le maillon car si on écrit print(m0), Python affichera le contenu du maillon et pas l'adresse du maillon ! C'est parce que Python cache ces pointeurs, contrairement à d'autres langages comme C.

Pour vous en convaincre, comparons les deux cas suivant :

a = 5
def f(x):
    x = 12
f(a)
print(a)

a = {"data":5, "next":None}
def f(x):
    x["data"] = 12
f(a)
print(a)

Quand on crée le maillon, on initialise "next" à None en sachant que plus tard "next" contiendra un maillon, qui pourra lui-même contenir un maillon…

Si "next" contenait vraiment un maillon, on ne pourrait par anticiper la place nécessaire pour "next" en mémoire. Puisque "next" ne contient en vérité qu'une adresse, on peut anticiper la taille d'une adresse et donc réserver la place nécessaire en mémoire.

Partant de L = 2:17:5, on exécute INSERER(L, 29, 1).

1. créer le nouveau maillon contenant 29, new_m = {"data":29, "next":None},
2. trouver le point d'insertion : soit prec_m le maillon juste avant l'insertion, ici celui contenant 2,
3. brancher new_m["next"] sur le maillon suivant, celui contenant 17, c'est à dire prec_m["next"],
4. brancher le maillon précédent sur le nouveau, c'est à dire prec_m["next"] = new_m.

Visualiser sur Python Tutor

Partant de L = 2:17:5, on exécute SUPPRIMER(L, 1).

1. trouver le maillon à supprimer, appelons le del_m, et celui immédiatement précédent, prec_m,
2. brancher le maillon précédent sur le maillon suivant celui à supprimer : prec_m["next"] = del_m["next"]
3. débrancher la sortie du maillon à supprimer pour éviter tout problème : del_m["next"] = None

Visualiser sur Python Tutor

Notre objectif est donc de compléter ce fichier

"""
liste.py
Module définissant l'interface des listes
"""

def CREER_LISTE_VIDE():
    """
    renvoie une liste vide
    """

def LONGUEUR(L):
    """
    renvoie le nombre d'éléments de la liste L
    """

def RECHERCHER(L, e):
    """
    renvoie l'indice de la première occurrence de e dans L.
    renvoie -1 si e n'est pas dans L
    """
    
def LIRE(L, i:int):
    """
    renvoie la valeur de l'élément d'indice i dans L
    précondition : 0 <= i < LONGUEUR(L)
    """
    
def INSERER(L, e, i:int):
    """
    insère l'élément e à l'indice i dans L
    précondition : 0 <= i <= LONGUEUR(L)
    ne renvoie rien, le contenu de L est modifié
    """

def SUPPRIMER(L, i:int):
    """
    supprime l'élément de rang i dans L
    précondition : 0 <= i < LONGUEUR(L)
    ne renvoie rien, le contenu de L est modifié
    """

def MODIFIER(L, e, i:int):
    """
    dans la liste L, écrit dans la case de rang i la valeur e
    précondition : 0 <= i < LONGUEUR(L)
    ne renvoie rien, le contenu de la liste est modifié
    """
    
def TEXTE(L):
    """
    Renvoie une représentation texte du contenu de la liste
    On utilise la notation, par ex, 4:9:17:12
    """
    
# zone de test
if __name__ == '__main__':    
    # création de L = 4:9:17:12
    L = CREER_LISTE_VIDE()
    INSERER(L, 4, 0)
    INSERER(L, 9, 1)
    INSERER(L, 17, 2)
    INSERER(L, 12, 3)
    
    # tests
    assert LONGUEUR(L) == 4
    assert RECHERCHER(L, 9) == 1
    assert RECHERCHER(L, 25) == -1
    assert LIRE(L, 2) == 17
    assert TEXTE(L) == "4:9:17:12"
    
    MODIFIER(L, 48, 1)
    assert TEXTE(L) == "4:48:17:12"
    assert LIRE(L, 1) == 48
    assert RECHERCHER(L, 9) == -1
    
    SUPPRIMER(L,2)
    assert TEXTE(L) == "4:48:12"
    assert LONGUEUR(L) == 3
    
    # si on arrive là, c'est que tous les test ont été passés avec succès
    print("Succès !")

1. Dans un fichier listes.py, recopier le fichier de base précédent et complétez.
2. Exécutez et corrigez jusqu'à ce que tous les tests passent avec succès.

Écrivez un programme Python qui importe le module listes.py et qui exécute le pseudo-code rencontré dans un exercice précédent.

L = CREER_LISTE_VIDE()
INSERER(L, 'X', 0)
INSERER(L, 'B', 0)
INSERER(L, 'E', 1)
INSERER(L, 'Z', 0)
SUPPRIMER(L, 1)
MODIFIER(L, 'H', 2)

Ajoutez un affichage de la liste pour voir son contenu.

Pour les curieux et les plus à l'aise, vous pouvez essayer de faire l'implémentation dans un autre langage.

Vous pourriez essayer en Javascript, mais ce serait alors très proche de Python. Il me parait plus intéressant d'essayer un langage le style du C. Le Go est une variante simplifiée du C, c'est donc un bon choix.

Voici une base de travail pour vous aider à démarrer.

Si vous souhaitez juste savoir à quoi cela ressemble, voici une solution toute faite d'implémentation en Go et une autre – plus difficile – en C.