Implémentation par des listes chaînées

Listes chaînées : description¶

Introduction¶

On rappelle que l'interface du type Liste est la suivante :

Fonction	Description
`creer_vide()`	Renvoie une liste vide
`est_vide(l)`	Renvoie `True` si et seulement si la liste est vide
`tete(l)`	Renvoie le premier élément de la liste \(l\) (l'élément dit de tête)
`queue(l)`	Renvoie la liste constituée de tous les éléments de \(l\) à l'exception du premier
`ajoute(l, e)`	Renvoie la liste constituée de l'élément \(e\), suivi des éléments de \(l\)
`affiche(l)`	Affiche la liste des éléments de \(l\) sur la sortie standard, séparés par le caractère `-`.
	La liste vide est représentée par `•`.

On se propose de donner une implémentation de cette interface via un objet nommé liste chaînée. En python, on peut représenter les listes de la manière suivante : chaque élément de la liste est associé à un objet, que nous appelerons un "maillon" (faisant partie d'une "chaîne" de maillons) qui comporte deux attributs :

un attribut valeur qui stocke la valeur de l'élément considéré ;
un attribut suivant qui permet de déterminer quel est le prochain maillon dans la chaîne.

On représente un maillon vide par la valeur spéciale None. Ainsi, on pourra instancier un objet m de type Maillon de trois façons distinctes :

m = None : le maillon est vide ;
m = Maillon(v, None) : le maillon est le seul dans sa chaîne ;
m = Maillon(v, m2) : le prochain maillon de la chaîne est le maillon m2 (supposé ici non vide).

Une chaîne de maillons ainsi constituée représente bien une liste d'éléments. La classe Liste (donnée pour le moment à titre indicatif) possède donc un seul attribut : head une référence vers le premier maillon de la chaîne.

###

class Maillon:bksl-nl """ Un maillon d'une liste chainée. """bksl-nl def py-undpy-undinitpy-undpy-und(self, v, s):bksl-nl """ int, Maillon -> None """bksl-nl self.valeur = vbksl-nl self.suivant = sbksl-nlbksl-nlclass Liste:bksl-nl """ Une liste d'éléments. """bksl-nl def py-undpy-undinitpy-undpy-und(self, m):bksl-nl """ Maillon -> None """bksl-nl self.head = mbksl-nlbksl-nl

À l'aide de l'objet Maillon, on peut représenter la liste \(l = (3, 8, 42, 1)\). Pour chaque élément \(e\) de la liste, on créé un maillon qui contient la valeur de l'élément et le lien vers le maillon suivant.

maillon4 = Maillon(1, None)
maillon3 = Maillon(42, maillon4)
maillon2 = Maillon(8, maillon3)
maillon1 = Maillon(3, maillon2)

print(maillon2.valeur)
print(maillon2.suivant)
print(maillon2.suivant.valeur)

Créer des listes de cette façon est très fastidieux, en raison de l'utilisation de multiples variables. On peut condenser le code de la manière à n'utiliser qu'une seule variable :

m = Maillon(1, None)
m = Maillon(42, m)
m = Maillon(8, m)
m = Maillon(3, m)
# encore plus court :
# m = Maillon(3, Maillon(8, Maillon(42, Maillon(1, None))))

print(m.valeur)
print(m.suivant)
print(m.suivant.valeur)

3
<__main__.Maillon object at 0x7f5c9e8bc460>
8

Premier exemple¶

Écrire les instructions python permettant de stocker à l'aide d'objets de type Maillon, ou de la valeur spéciale None les listes \(l_1 = ()\), \(l_2 = (-1)\), \(l_3 = (5, 6, 9, -1)\), \(l_4 = (-5, 9, 13)\).

###

def testpy-undexemple():bksl-nl """ Tests pour la fonction exemple """bksl-nl print("Tests de exemple passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import exemplebksl-nl# testpy-undexemple()bksl-nlbksl-nl 5/5

maillon4 = Maillon(1, None)bksl-nlmaillon3 = Maillon(42, maillon4)bksl-nlmaillon2 = Maillon(8, maillon3)bksl-nlmaillon1 = Maillon(3, maillon2)bksl-nlbksl-nlprint(maillon2.valeur)bksl-nlprint(maillon2.suivant)bksl-nlprint(maillon2.suivant.valeur)bksl-nlbksl-nlm = Maillon(1, None)bksl-nlm = Maillon(42, m)bksl-nlm = Maillon(8, m)bksl-nlm = Maillon(3, m)bksl-nl# encore plus court :bksl-nl# m = Maillon(3, Maillon(8, Maillon(42, Maillon(1, None))))bksl-nl bksl-nlprint(m.valeur)bksl-nlprint(m.suivant)bksl-nlprint(m.suivant.valeur)bksl-nlbksl-nl# À compléterbksl-nl# m1 = ...bksl-nl# m2 = ...bksl-nl# m3 = ...bksl-nl# m4 = ...bksl-nlbksl-nl

Implémentation de l'interface de base des listes¶

Créer une liste vide¶

Écrire une fonction creer_vide qui renvoie, avec les conventions de l'énoncé, un maillon vide.

###

def testpy-undcreerpy-undvide():bksl-nl """ Tests pour la fonction creerpy-undvide """bksl-nl assert creerpy-undvide() is Nonebksl-nl print("Tests de creerpy-undvide passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import creerpy-undvidebksl-nltestpy-undcreerpy-undvide()bksl-nlbksl-nl 5/5

def creerpy-undvide():bksl-nl """ () -> Maillonbksl-nl Renvoie un maillon vide """bksl-nl passbksl-nlbksl-nl

Tester si un maillon est vide¶

Écrire une fonction est_vide étant donné un maillon m renvoie True si et seulement si celui-ci est vide.

###

def testpy-undestpy-undvide():bksl-nl """ Tests pour la fonction estpy-undvide """bksl-nl assert estpy-undvide(creerpy-undvide()) == Truebksl-nl assert estpy-undvide(Maillon(1, creerpy-undvide())) == Falsebksl-nl print("Tests de estpy-undvide passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import estpy-undvidebksl-nltestpy-undestpy-undvide()bksl-nlbksl-nl 5/5

def estpy-undvide(m):bksl-nl """ Maillon -> boolbksl-nl Renvoie True si et seulement si le maillon m est le maillon vide """bksl-nl passbksl-nlbksl-nl

Élément de tête¶

Écrire une fonction tete qui étant donné un maillon non-vide m, renvoie la valeur stockée dans ce maillon.

###

def testpy-undtete():bksl-nl """ Tests pour la fonction tete """bksl-nl assert tete(Maillon(1, None)) == 1bksl-nl assert tete(Maillon(2, Maillon(1, None))) == 2bksl-nl print("Tests de tete passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import tetebksl-nltestpy-undtete()bksl-nlbksl-nl 5/5

def tete(m):bksl-nl """ Maillon -> intbksl-nl m est non videbksl-nl Renvoie l'attribut valeur du maillon m """bksl-nl passbksl-nlbksl-nl

Élément de queue¶

Écrire une fonction queue qui étant donné un maillon non-vide m, renvoie le maillon suivant de la chaîne de maillons.

###

def testpy-undqueue():bksl-nl """ Tests pour la fonction queue """bksl-nl m0 = Maillon(1, None)bksl-nl m1 = Maillon(2, m0)bksl-nl m2 = Maillon(3, m1)bksl-nl assert queue(m1) is m0bksl-nl assert queue(m2) is m1bksl-nl print("Tests de queue passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import queuebksl-nltestpy-undqueue()bksl-nlbksl-nl 5/5

def queue(m):bksl-nl """ Maillon -> Maillonbksl-nl m est non videbksl-nl Renvoie le maillon suivant dans la chaine de maillon de tête m. """bksl-nl passbksl-nlbksl-nl

Ajout d'un maillon¶

Écrire une fonction ajoute_debut qui étant donné un maillon m et un élément e renvoie le maillon m' dont l'attribut valeur est e et dont l'attribut suivant est m.

###

def testpy-undajoutepy-unddebut():bksl-nl """ Tests pour la fonction ajoutepy-unddebut """bksl-nl assert ajoutepy-unddebut(None, 3).valeur == 3bksl-nl assert ajoutepy-unddebut(None, 3).suivant == Nonebksl-nl print("Tests de ajoutepy-unddebut passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import ajoutepy-unddebutbksl-nltestpy-undajoutepy-unddebut()bksl-nlbksl-nl 5/5

def ajoutepy-unddebut(m, e):bksl-nl """ Maillon, int -> Maillonbksl-nl Renvoie le maillon dont l'attribut valeur est e et l'attribut suivant est m """bksl-nl passbksl-nlbksl-nl

Parcours d'une liste chaînée¶

Affichage d'une liste chaînée¶

Pour afficher une liste chaînée, il faut parcourir tous les maillons la composant. Pour cela, deux approches sont possibles : une méthode récursive et méthode itérative.

Méthode récursive¶

Si le maillon est vide alors on affiche un symbole indiquant qu'il s'agit du maillon vide. Sinon, on affiche la valeur contenue dans le maillon, puis on affiche les maillons suivants de la chaîne.

###

def affichepy-undrec(m):bksl-nl """ Maillon -> Nonebksl-nl Affiche les valeurs de la chaîne dont le premier maillon est m. """bksl-nl if estpy-undvide(m):bksl-nl print("x")bksl-nl else:bksl-nl print(tete(m), end = " - ")bksl-nl affichepy-undrec(queue(m))bksl-nlbksl-nlaffichepy-undrec(m3)bksl-nlbksl-nldef affichepy-undi(m):bksl-nl """ Affiche les valeurs de la chaîne dont le premier maillon est m """bksl-nl maillonpy-undcourant = mbksl-nl while not estpy-undvide(maillonpy-undcourant):bksl-nl print(tete(maillonpy-undcourant), end=' - ')bksl-nl maillonpy-undcourant = queue(maillonpy-undcourant)bksl-nl print("x")bksl-nlbksl-nlaffichepy-undi(m3)bksl-nlaffiche = affichepy-undibksl-nlbksl-nl

Que se passe-t-il si on échange les lignes 7 et 8 du code de la fonction affiche_rec ?
À quoi sert l'argument nommé end de la fonction print ? Modifier le code de la fonction précédente afin que l'affichage effectué par l'instruction affiche_rec(m3) soit :
```
5 | 6 | 9 | -1 | x
```

Méthode itérative¶

On initialise une variable maillon_courant qui stocke le maillon courant du parcours de la liste. Tant que le maillon courant n'est pas vide (ce qui veut dire que l'on n'est pas encore au bout de la chaîne), on affiche la valeur du maillon courant puis le maillon courant devient le maillon suivant dans la chaîne. Lorsque l'on atteint la fin de la chaîne, on affiche un symbole indiquant qu'il s'agit du maillon vide.

###

def affichepy-undrec(m):bksl-nl """ Maillon -> Nonebksl-nl Affiche les valeurs de la chaîne dont le premier maillon est m. """bksl-nl if estpy-undvide(m):bksl-nl print("x")bksl-nl else:bksl-nl print(tete(m), end = " - ")bksl-nl affichepy-undrec(queue(m))bksl-nlbksl-nlaffichepy-undrec(m3)bksl-nlbksl-nldef affichepy-undi(m):bksl-nl """ Affiche les valeurs de la chaîne dont le premier maillon est m """bksl-nl maillonpy-undcourant = mbksl-nl while not estpy-undvide(maillonpy-undcourant):bksl-nl print(tete(maillonpy-undcourant), end=' - ')bksl-nl maillonpy-undcourant = queue(maillonpy-undcourant)bksl-nl print("x")bksl-nlbksl-nlaffichepy-undi(m3)bksl-nlaffiche = affichepy-undibksl-nlbksl-nl

On utilisera dans la suite simplement l'instruction affiche pour afficher une chaîne de maillons.

Longueur d'une chaîne¶

On appelle longueur d'une chaîne de maillons le nombres de maillons la composant. Écrire une fonction longueur qui étant donné un maillon m, détermine la longueur de la chaîne de maillons dont le premier maillon est m.

On écrira une version récursive et une version itérative de cette fonction.

###

def message(input, output, expected):bksl-nl return f"Erreur :\n Entrée : {input}\n Sortie : {output}\n Attendu : {expected}"bksl-nlbksl-nldef tab2maillon(tab):bksl-nl maillon = Nonebksl-nl for i in range(len(tab) - 1, -1, -1):bksl-nl maillon = Maillon(tab[i], maillon)bksl-nl return maillonbksl-nlbksl-nldef égaux(m1, m2):bksl-nl if estpy-undvide(m1) and estpy-undvide(m2):bksl-nl return Truebksl-nl elif estpy-undvide(m1) ^ estpy-undvide(m2):bksl-nl return Falsebksl-nl return tete(m1) == tete(m2) and égaux(queue(m1), queue(m2))bksl-nlbksl-nldef testpy-undlongueur():bksl-nl """ Tests pour la fonction longueur """bksl-nl inputs = [tab2maillon([i for i in range(n)]) for n in range(10)]bksl-nl outputspy-undi = [longueurpy-undi(m) for m in inputs]bksl-nl outputspy-undr = [longueurpy-undr(m) for m in inputs]bksl-nl expecteds = [n for n in range(10)]bksl-nl for i in range(10):bksl-nl assert outputspy-undi[i] == expecteds[i], message(inputs[i], outputs[i], expecteds[i])bksl-nl assert outputspy-undr[i] == expecteds[i], message(inputs[i], outputs[i], expecteds[i])bksl-nl print("Tests de longueur passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import longueurbksl-nltestpy-undlongueur()bksl-nlbksl-nl 5/5

def longueurpy-undr(m):bksl-nl """ Maillon -> intbksl-nl Compte le nombre de maillons présents dans la chaîne dont le premier maillon est m """bksl-nl # version récursivebksl-nl passbksl-nlbksl-nldef longueurpy-undi(m):bksl-nl """ Maillon -> intbksl-nl Compte le nombre de maillons présents dans la chaîne dont le premier maillon est m """bksl-nl # version itérativebksl-nl passbksl-nlbksl-nl

Élément d'indice i¶

Écrire le code d'une fonction element qui étant donné un maillon m, et un entier i, supposé compatible avec la longueur de la chaîne, renvoie la valeur stockée dans le maillon d'indice \(i\) de la chaine dont le premier maillon est m.

On écrira une version récursive et une version itérative de cette fonction.

###

def testpy-undelement():bksl-nl """ Tests pour la fonction element """bksl-nl inputs = tab2maillon([i for i in range(10)])bksl-nl outputspy-undi = [elementpy-undi(inputs, i) for i in range(10)]bksl-nl outputspy-undr = [elementpy-undr(inputs, i) for i in range(10)]bksl-nl expecteds = [i for i in range(10)]bksl-nl for i in range(10):bksl-nl assert outputspy-undi[i] == expecteds[i], message(inputs, outputs[i], expecteds[i])bksl-nl assert outputspy-undr[i] == expecteds[i], message(inputs, outputs[i], expecteds[i])bksl-nl print("Tests de element passés avec succès.")bksl-nl return Truebksl-nl# from tp import elementbksl-nltestpy-undelement()bksl-nlbksl-nl 5/5

def elementpy-undr(m, i):bksl-nl """ Maillon, int -> intbksl-nl m est non vide, 0 <= i < longueur(m)bksl-nl Renvoie l'élément d'indice i de la chaîne de maillons dont le premier est m """bksl-nl # version récursivebksl-nl passbksl-nlbksl-nldef elementpy-undr(m, i):bksl-nl """ Maillon, int -> intbksl-nl m est non vide, 0 <= i < longueur(m)bksl-nl Renvoie l'élément d'indice i de la chaîne de maillons dont le premier est m """bksl-nl # version itérativebksl-nl passbksl-nlbksl-nl

Remplacer l'élément d'indice i¶

Écrire le code d'une fonction remplace qui étant donné un maillon m non vide, un entier i, supposé compatible avec la longueur de la chaîne, et un élément e, renvoie la chaîne où la valeur du maillon d'indice i a été remplacée par e. Ainsi, après l'exécution de remplace(m) :

le premier maillon de la chaîne est toujours le maillon m ;
l'attribut valeur du maillon d'indice i de la chaine est e.
les autres maillons de la chaîne sont inchangés.

On pourra utiliser au choix un algorithme de parcours récursif ou itératif.

###

def testpy-undremplace():bksl-nl """ Tests pour la fonction remplace """bksl-nl print("Tests de remplace passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import remplacebksl-nl# testpy-undremplace()bksl-nlbksl-nl 5/5

def remplacepy-undr(m, i, e):bksl-nl """ Maillon, int, int -> NoneTypebksl-nl m est non vide, 0 <= i < longueur(m)bksl-nl Remplace par e la valeur du i-ème maillon de la chaine commençant par m """bksl-nl # version récursivebksl-nl passbksl-nlbksl-nldef remplacepy-undi(m, i, e):bksl-nl """ Maillon, int, int -> NoneTypebksl-nl m est non vide, 0 <= i < longueur(m)bksl-nl Remplace par e la valeur du i-ème maillon de la chaine commençant par m """bksl-nl # version itérativebksl-nlbksl-nl

Ajouter un élément à l'indice i¶

Écrire une fonction ajoute_position qui étant donné un maillon m, un entier i, supposé compatible avec la longueur de la chaîne, et un élément e, ajoute un maillon à la chaine de telle sorte que :

le premier maillon de la chaîne soit toujours le maillon m ;
le maillon d'indice i de la chaîne ait pour valeur e ;
l'ordre d'apparition des valeurs des autres maillons de la chaîne est inchangé.

On pourra utiliser au choix un algorithme de parcours récursif ou itératif.

###

def testpy-undajoutepy-undposition():bksl-nl """ Tests pour la fonction ajoutepy-undposition """bksl-nl print("Tests de ajoutepy-undposition passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import ajoutepy-undpositionbksl-nl# testpy-undajoutepy-undposition()bksl-nlbksl-nl 5/5

def ajoutepy-undposition(m, e, i):bksl-nl """ Maillon, int, int -> NoneTypebksl-nl Ajoute l'élément e en i-ième position de la chaine dont le premier maillon est m """bksl-nl passbksl-nlbksl-nl

Suppression d'un élément¶

Écrire une fonction supprime qui étant donné un maillon m, un entier i, supposé compatible avec la longueur de la chaîne, supprime la valeur i de la chaine dont le premier maillon est m de telle sorte que le premier maillon de la chaîne soit toujours le maillon m.

On pourra utiliser au choix un algorithme de parcours récursif ou itératif. On traitera le cas où la liste est constitué d'un seul élément et le cas i = 0 à part.

###

def testpy-undsupprime():bksl-nl """ Tests pour la fonction supprime """bksl-nl print("Tests de supprime passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import supprimebksl-nl# testpy-undsupprime()bksl-nlbksl-nl 5/5

def supprime(m, i):bksl-nl """ Maillon, int -> NoneTypebksl-nl Supprime la valeur i de la chaine dont le premier maillon est m """bksl-nl passbksl-nlbksl-nl

Documents¶

Implémentation par des listes chaînées (sujet)
Fichiers python :
- templates
- tests