GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Implémentation procédurale des Listes ======

{{ :nsi:terminales:structures:listes_chainees.fiche.pdf |Fiche à imprimer}}

===== Choix =====

==== Liste chaînée ====

On a vu dans [[nsi:terminales:structures:liste_memoire|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%%''.

{{ :nsi:terminales:linked_list.png?nolink&600 |}}

==== mutable ====

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.

==== RECHERCHE si item absent ====

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.

===== Implémentation =====

==== Maillon ====

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 :

<WRAP group>
<WRAP half column>
<code python linenums>
m0 = { "data":2, "next":None }
m1 = { "data":17, "next":None }
m2 = { "data":5, "next":None }
m0["next"] = m1
m1["next"] = m2
</code>
</WRAP>
<WRAP half column>
<code python linenums>
m0 = { "data":2, "next":None }
m0["next"] = { "data":17, "next":None }
m0["next"]["next"] = { "data":5, "next":None }
</code>

<code python linenums>
m2 = { "data":5, "next":None }
m1 = { "data":2, "next":m2 }
m0 = { "data":17, "next":m1 }
</code>
</WRAP>
</WRAP>

==== entête ====

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.

<code python linenums>
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
</code>

<WRAP tip>Au besoin, on pourrait facilement enrichir l'entête pour lui faire contenir des informations supplémentaires comme un lien vers le dernier élément ou un compte du nombre d'éléments.</WRAP>

==== Notion de pointeur ====

<code python linenums>
m0 = { "data":2, "next":None }
m1 = { "data":17, "next":None }
m0["next"] = m1
</code>

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 [[nsi:langages:c:start|C]].

Pour vous en convaincre, comparons les deux cas suivant :

<WRAP group>
<WRAP half column>
<code python linenums>
a = 5
def f(x):
    x = 12
f(a)
print(a)
</code>
Dans ce cas, l'appel à ''f'' avec l'argument ''a'' crée une copie de ''a''. Ce n'est donc pas ''a'' qui est modifié dans la fonction et ''a'' reste inchangé après l'exécution.

[[https://pythontutor.com/visualize.html#code=a%20%3D%205%0Adef%20f%28x%29%3A%0A%20%20%20%20x%20%3D%2012%0Af%28a%29%0Aprint%28a%29&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false|Visualiser sur Python Tutor]]
</WRAP>

<WRAP half column>
<code python linenums>
a = {"data":5, "next":None}
def f(x):
    x["data"] = 12
f(a)
print(a)
</code>

Dans ce cas aussi, lors de l'appel à ''f'', ''x'' n'est qu'une copie de ''a''. Mais comme ''a'' n'est pas le dictionnaire lui même mais un pointeur vers le dictionnaire, alors ''x'' est une copie de ce pointeur. Donc ''x'' pointe vers le même dictionnaire que ''a'' et la modification de ''x'' dans la fonction a bien un effet sur ''a''.

[[https://pythontutor.com/visualize.html#code=a%20%3D%20%7B%22data%22%3A5,%20%22next%22%3ANone%7D%0Adef%20f%28x%29%3A%0A%20%20%20%20x%5B%22data%22%5D%20%3D%2012%0Af%28a%29%0Aprint%28a%29&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false|Visualiser sur Python Tutor]]
</WRAP>
</WRAP>

==== Pourquoi il faut des pointeurs ====

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.

==== Insérer un maillon ====

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

{{ :nsi:terminales:linked_list_insert.png?nolink&600 |}}

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

[[https://pythontutor.com/visualize.html#code=%23%20initialisation%20manuelle%20de%20la%20liste%20L%20%3D%202%3A17%3A5%0AL%20%3D%20%7B%20%22head%22%3ANone%7D%0AL%5B%22head%22%5D%20%3D%20%7B%22data%22%3A2,%20%22next%22%3ANone%7D%0AL%5B%22head%22%5D%5B%22next%22%5D%20%3D%20%7B%22data%22%3A17,%20%22next%22%3ANone%7D%0AL%5B%22head%22%5D%5B%22next%22%5D%5B%22next%22%5D%20%3D%20%7B%22data%22%3A5,%20%22next%22%3ANone%7D%0A%0A%23%20d%C3%A9but%20de%20l'insertion%0Anew_m%20%3D%20%7B%22data%22%3A29,%20%22next%22%3ANone%7D%0A%23%20on%20le%20branche%20apr%C3%A8s%20l'%C3%A9l%C3%A9ment%20de%20valeur%202,*%0A%23%20c'est%20%C3%A0%20dire%20le%20premier%20de%20la%20liste%0Aprec_m%20%3D%20L%5B%22head%22%5D%0A%23%20brancheemnt%0Anew_m%5B%22next%22%5D%20%3D%20prec_m%5B%22next%22%5D%0Aprec_m%20%5B%22next%22%5D%20%3D%20new_m&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false|Visualiser sur Python Tutor]]
==== Supprimer un maillon ====

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

{{ :nsi:terminales:linked_list_del.png?nolink&600 |}}

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

[[https://pythontutor.com/visualize.html#code=%23%20initialisation%20manuelle%20de%20la%20liste%20L%20%3D%202%3A17%3A5%0AL%20%3D%20%7B%20%22head%22%3ANone%7D%0AL%5B%22head%22%5D%20%3D%20%7B%22data%22%3A2,%20%22next%22%3ANone%7D%0AL%5B%22head%22%5D%5B%22next%22%5D%20%3D%20%7B%22data%22%3A17,%20%22next%22%3ANone%7D%0AL%5B%22head%22%5D%5B%22next%22%5D%5B%22next%22%5D%20%3D%20%7B%22data%22%3A5,%20%22next%22%3ANone%7D%0A%0A%23%20on%20supprime%20l'%C3%A9l%C3%A9ment%20apr%C3%A8s%20l'%C3%A9l%C3%A9ment%20de%20valeur%202,%0A%23%20c'est%20%C3%A0%20dire%20le%20premier%20de%20la%20liste%0Aprec_m%20%3D%20L%5B%22head%22%5D%0Adel_m%20%3D%20prec_m%5B%22next%22%5D%0A%23%20suppression%0Aprec_m%20%5B%22next%22%5D%20%3D%20del_m%5B%22next%22%5D%0Adel_m%5B%22next%22%5D%20%3D%20None&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false|Visualiser sur Python Tutor]]


<WRAP tip>Python s'occupera seul de libérer la mémoire correspondant au maillon inutilisé. Ce genre d'automatisme, présent dans beaucoup de langages modernes est appelé //garbage collector// et simplifie grandement la programmation. Par exemple, en C qui est un langage plus ancien et plus proche de la machine, il faut penser à explicitement libérer la mémoire qu'on n'utilisera plus.</WRAP>

==== Fichier de base ====

Notre objectif est donc de compléter ce fichier

<code python linenums>
"""
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 !")
</code>

<WRAP tip>Pourquoi faut-il ajouter un bloc d'entête à la liste ? Pourquoi ne pas brancher L directement sur le premier maillon ?

On le fait parfois mais cela peut poser une difficulté comme vous pouvez le constater sur cet [[https://pythontutor.com/visualize.html#code=%23%20initialisation%20manuelle%20de%20la%20liste%20L%20%3D%202%3A17%3A5%0A%23%20Mais%20sans%20utiliser%20de%20bloc%20d'ent%C3%AAte%0A%23%20L%20pointe%20directement%20sur%20le%20premier%20maillon%0AL%20%3D%20%7B%22data%22%3A2,%20%22next%22%3ANone%7D%0AL%5B%22next%22%5D%20%3D%20%7B%22data%22%3A17,%20%22next%22%3ANone%7D%0AL%5B%22next%22%5D%5B%22next%22%5D%20%3D%20%7B%22data%22%3A5,%20%22next%22%3ANone%7D%0A%0A%23%20je%20d%C3%A9finis%20maintenant%20une%20fonction%20d'insertion%20en%20premier%0Adef%20insert_first%28L,%20x%29%3A%0A%20%20%20%20new_m%20%3D%20%7B%22data%22%3Ax,%20%22next%22%3ANone%7D%0A%20%20%20%20%23%20branchement%0A%20%20%20%20new_m%5B%22next%22%5D%20%3D%20L%0A%20%20%20%20L%20%3D%20new_m%0A%0A%23%20ex%C3%A9cution%20de%20la%20fonction%0Ainsert_first%28L,29%29&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false|exemple Python Tutor]].</WRAP>
==== Exercice 1 ====

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

==== Exercice 2 ====

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

<code>
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)
</code>

Ajoutez un affichage de la liste pour voir son contenu.

<WRAP tip>
Dans ''listes.py'', on a utilisé le code ''%%if __name__ == '__main__':%%'' qui peut sembler mystérieux. Il faut comprendre que l'exécution de ''listes.py'' dépend du contexte.
  * Si on exécute ''listes.py'' en tant que programme principal (comme dans le premier exercice), c'est donc le //main//, et la condition du ''%%if%%'' est validée. Les tests s'exécutent.
  * Si on exécute ''lises.py'' en tant que module importé (comme dans le second exercice), ''listes.py'' n'est plus le //main//, la condition du ''%%if%%'' n'est plus validée et les tests ne s'exécutent pas.
</WRAP>


===== Dans d'autres langages =====

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

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

Voici une [[..:liste_implementation_go|base de travail]] pour vous aider à démarrer.

Si vous souhaitez juste savoir à quoi cela ressemble, voici une solution toute faite d'implémentation [[nsi:langages:go:solutions:liste|en Go]] et une autre -- plus difficile -- [[nsi:langages:c:solutions:liste|en C]].