La structure de tableau permet de stocker des séquences d'éléments mais n'est pas adaptée à toutes les opérations que l'on pourrait vouloir effectuer
sur des séquences. Les tableaux de Python permettent par exemple d'insérer ou de supprimer efficacement des éléments à la fin d'un tableau, avec les opérations append et pop, mais se prêtent mal à l'insertion ou la suppression d'un élément à une autre position.
En effet, les éléments d'un tableau étant contigus et ordonnés en mémoire, insérer un élément dans une séquence demande de déplacer tous les éléments qui le suivent pour lui laisser une
place.
Si par exemple on veut insérer une valeur v à la première position d'un tableau
| 1 | 1 | 2 | 3 | 5 | 8 | 13 |
il faut d'une façon où d'une autre construire le nouveau tableau
| v | 1 | 1 | 2 | 3 | 5 | 8 | 13 |
dans lequel la case d'indice 0 contient maintenant la valeur v.
On peut le faire en utilisant l'opération insert des tableaux de Python.
t = [1,1,2,3,5,8,13]
v = 4
print(\"t =\",t)
t.insert(v,0)
print(\"t =\",t)
Cette opération est cependant très coûteuse, car elle déplace tous les éléments du tableau d'une case vers la droite après avoir agrandi le tableau.
C'est exactement comme si nous avions écrit les lignes suivantes :
t = [1,1,2,3,5,8,13]
v = 4
print(\"t =\",t)
t.append(None)
for i in range(len(t) - 1, 0, -1):
t[i] = t[i - 1]
t[0] = v
print(\"t =\",t)
Avec une telle opération on commence donc par agrandir le tableau, en ajoutant un nouvel élément à la fin avec append.
| 1 | 1 | 2 | 3 | 5 | 8 | 13 | None |
Puis on décale tous les éléments d'une case vers la droite, en prenant soin de commencer par le dernier et de terminer par le premier.
| 1 | 1 | 1 | 2 | 3 | 5 | 8 | 13 |
Enfin, on écrit la valeur v dans la première case du tableau.
| v | 1 | 1 | 2 | 3 | 5 | 8 | 13 |
Au total, on a réalisé un nombre d'opérations proportionnel à la taille du tableau. Si par exemple le tableau contient un million d'éléments, on fera un
million d'opérations pour ajouter un premier élément.
En outre, supprimer le premier élément serait tout aussi coûteux, pour les mêmes raisons.
Dans cette séquence nous étudions une structure de données, la liste chaînée, qui d'une part apporte une meilleure solution au problème de l'insertion et de la suppression au début d'une séquence d'éléments, et d'autre part servira de brique de base à plusieurs autres structures dans les prochaines séquences.
Comme le nom le suggère sa structure est en outre caractérisée par le fait que les éléments sont chaînés entre eux, permettant le passage d'un élément à l'élément suivant.
Ainsi, chaque élément est stocké dans un petit bloc alloué quelque part dans la mémoire, que l'on pourra appeler maillon ou cellule, et y est accompagné d'une deuxième information : l'adresse mémoire où se trouve la cellule contenant l'élément suivant de la liste.
Ici, on illustré une liste contenant trois éléments, respectivement 1, 2 et 3.
Chaque élément de la liste est matérialisée par l'emplacement en mémoire
contenant d'une part sa valeur (dans la case de gauche} et d'autre part l'adresse mémoire de la valeur suivante (dans la case de droite).
Programme — Cellule d'une liste chaînée
class Cellule:
\"\"\"une cellule d'une Liste chaînée\"\"\"
def __init__(self, v, s):
self.valeur = v
self.suivante = s
Dans le cas
du dernier élément, qui ne possède pas de valeur suivante, on utilise une valeur spéciale désignée ici par le symbole ⊥ et marquant la fin de la liste.
Une façon traditionnelle de représenter une liste chaînée en Python consiste à utiliser une classe décrivant les cellules de la liste, de sorte que chaque élément de la liste est matérialisé par un objet de cette classe.
Cette classe est appelée ici Cellule et est donnée dans le programme ci-dessus.
Tout objet de cette classe contient deux attributs : :
- un attribut valeur pour la valeur
de l'élément (l'entier, dans notre exemple)
- et un attribut suivante pour la cellule suivante de la liste.
Lorsqu'il n'y à pas de cellule suivante, c'est-à-dire lorsque l'on considère la dernière cellule de la liste, on donne à l'attribut suivante la valeur None.
Dit autrement, None est notre représentation du symbole ⊥.
Pour construire une liste, il suffit d'appliquer le constructeur de la classe Cellule autant de fois qu'il y a d'éléments dans la liste.
lst = Cellule(1, Cellule(2, Cellule(3, None)))
Ainsi, l'instruction construit la liste 1,2,3 donnée en exemple plus haut et la stocke dans une variable lst.
Plus précisément, on a ici créé trois objets de la classe Cellule, que l'on peut visualiser comme suit
#affiche le contenu de lst
print(lst)
c = lst
espace = \" \"
while c is not None :
print(espace,\"|-->\",c.valeur,\" , \",c.suivante)
c = c.suivante
espace += \" \"
Tester le code ci-dessous et conclure.
![\"liste11.png](\"https://sciencesappliquees.com/images/nsi/liste12.png\")
La valeur contenue dans la variable lst est l'adresse mémoire de l'objet contenant la valeur 1, qui lui-même contient dans son attribut suivante l'adresse mémoire de l'objet contenant la valeur 2, qui enfin contient dans son attribut suivante l'adresse mémoire de l'objet contenant la valeur 3.
Ce dernier contient la valeur None dans son attribut suivante, marquant ainsi la fin de la liste.
Par la suite, on s'autorisera un dessin simplifié, de la manière suivante.
![](\"https://sciencesappliquees.com/images/nsi/liste1.png\")
Dans ce dessin, il faut interpréter chaque élément de la liste comme un objet de la classe Cellule.
","title":"Structure de liste chaînée"},{"edit":"Mettre ici les résultats.
Comme on le voit, une liste est soit la
valeur None, soit un objet de la classe Cellule dout l'attribut suivante contient une liste. C'est là une définition récursive de la notion de liste.
Mettre le résultat ici.
Représentations alternatives. D'autres représentations des listes chaînées sont possibles. Plutôt qu'un objet de la classe Cellule, on pourrait
utiliser un couple, et dans ce cas écrire (1, (2, (3,None))), ou encore un tableau à deux éléments, et dans ce cas écrire [1, [2, [3,None]]]. Cependant, l'utilisation d'une valeur structurée avec des champs nominés
(ici les attributs valeur et suivante) est idiomatique, y compris dans un langage comme Python.
Variantes des listes chaînées. Il existe de nombreuses variantes de la structure de liste chaînée, dont la liste cyclique, où le dernier élément est lié au premier,
![](\"https://sciencesappliquees.com/images/nsi/liste3.png\")
ou la liste doublement chaînée, où chaque élément est lié à l'élément suivant et à l'élément précédent dans la liste,
![](\"https://sciencesappliquees.com/images/nsi/liste4.png\")
ou encore la liste cyclique doublement chaînée qui combine ces deux variantes.
Dans tout cette séquence, on ne manipule que des listes simplement chaînées et ne contenant pas de cycles.
Homogénéité. Bien que nous illustrions cette séquence avec des listes d'entiers, les listes chaînées, au même titre que les tableaux Python, peuvent
contenir des valeurs de n'importe quel type.
Ainsi, on peut imaginer des listes de chaînes de caractères, de couples, etc. Comme pour les tableaux, nous recommandons une utilisation homogène des listes chaînées, où tous les éléments de la liste sont du même type.
","title":""},{"edit":"Dans cette section, nous allons programmer quelques opérations fondamentales sur les listes.
D'autres opérations sont proposées en exercices.
La première opération que nous allons programmer consiste à calculer la longueur d'une liste chaînée, c'est-à-dire le nombre de cellules qu'elle contient.
Il s'agit donc de parcourir la liste, de la première cellule jusqu'à la dernière, en suivant les liens qui relient les cellules entre elles.
On peut réaliser ce parcours, au choix, avec une fonction récursive ou avec une boucle.
Nous allons faire les deux. Dans les deux cas, on écrit une fonction longueur qui reçoit une liste lst en argument et renvoie sa longueur.
def longueur (lst):
\"\"\"renvoie La longueur de la Liste lst\"\"\"
Commençons par la version récursive. Elle consiste à distinguer le cas de base, c'est-à-dire une liste vide ne contenant aucune cellule, du cas général, c'est-à-dire une liste contenant au moins une cellule.
Dans le premier cas, il suffit de renvoyer 0 :
if lst is None:
return 0
Ici, on a testé si la liste lst est égale à None avec l'opération is de Python mais on aurait tout aussi bien pu utiliser ==, c'est-à-dire écrire lst == None.
Dans le second cas, il faut renvoyer 1, pour la première cellule, plus la longueur du reste de la liste, c'est-à-dire la longueur de la liste lst suivante, que l'on peut calculer récursivement :
else:
return 1 + longueur (lst.suivante)
On se persuade facilement que cette fonction termine, car le nombre de cellules de Ia liste passée en argument à la fonction longueur décroît strictement à chaque appel.
Écrivons maintenant la fonction longueur différemment, cette fois avec une boucle. On commence par se donner deux variables : une variable n contenant la longueur que l'on calcule et une variable c contenant la cellule courante du parcours de la liste.
def longueur (lst) :
\"\"\"renvoie la longueur de la liste lst\"\"\"
n = 0
c = lst
Initialement, n vaut 0 et c prend la valeur de lst, c'est-à-dire None si la liste est vide et la première cellule sinon.
Le parcours est ensuite réalisé avec une boucle while, qui exécute autant d'itérations qu'il y a de cellules dans
la liste.
while c is not None:
L'opération is not est, comme on le devine, la négation de l'opération is.
On exécuter donc cette boucic tant que c n'est pas égale à None.
À chaque étape, c'est-à-dire pour chaque cellule de la liste, on incrémente le compteur n et on passe à la cellule suivante en donnant à c la valeur de c.suivante.
n += 1
c = c.suivante
Une fois que l'on sort de la boucle, il suffit de renvoyer la valeur de n.
return n
Il est important de comprendre que, dans cette version itérative, seule la variable c est modifiée, pour désigner successivement les différentes cellules de la liste :
![](\"https://sciencesappliquees.com/images/nsi/liste5.png\")
L'affectation c = c.suivante ne modifie pas le contenu ou la structure de la liste, seulement le contenu de la variable c, qui est l'adresse d'une cellule de ta liste.
Le code complet de ces deux fonctions Longueur est donné ci-dessous.
Programme — Calcul de la longueur d'une liste
class Cellule:
\"\"\"une cellule d'une Liste chaînée\"\"\"
def __init__(self, v, s):
self.valeur = v
self.suivante = s
lst = Cellule(1, Cellule(2, Cellule(3, None)))
# avec une fonction récursive
def longueurR(lst):
\"\"\"renvoie la Longueur de La liste lst\"\"\"
if lst is None :
return 0
else:
return 1 + longueurR(lst.suivante)
# avec une boucle
def longueurB(lst):
\"\"\"renvoie la longueur de la Liste lst\"\"\"
n = 0
c = lst
while c is not None:
n += 1
c = c.suivante
return n
print(longueurB(lst))
print(longueurR(lst))
Complexité. Il est clair que la complexité du calcul de la longueur est directement proportionnelle à la longueur elle-même, puisqu'on réalise un nombreux constant d'opération pour chaque cellule de la liste. Ainsi, pour une liste lst de mille cellules, longueur(lst) va effectuer mille tests, mille appels récursifs et mille additions dans sa version récursive, et mille tests, mille additions et deux mille affectations dans sa version itérative.
Mettre le résultat ici (code et figure).
Comparaison avec None.
c.suivante == None ou c.suivante is None?
À priori, il n'y à pas de différence entre écrire lst is None et lst == None.
Les deux opérations ne sont pas exactement les mêmes : l'opération is est une égalité physique {être identiquement le même objet, au même endroit dans la mémoire) et l'opération == est une égalité structurelle (être la même valeur, après une comparaison
en profondeur).
Mais dans le cas particulier de la valeur None, ces deux
égalités coïncident, car l'objet qui représente None est unique.
On teste donc bien si la valeur de lst est None dans les deux cas.
Cependant, une classe peut redéfinir l'égalité représentée par l'opération == et, dans ce cas, potentiellement modifier le résultat d'une comparaison avec None. Pour cette raison, il est d'usage de tester l'égalité à None avec is plutôt qu'avec ==. Bien évidemment, dans le cas précis de notre propre classe Cellule, nous savons qu'elle ne redéfinit pas l'opération ==, Néanmoins, nous choisissons de nous conformer à cette bonne pratique.
Comme deuxième opération sur les listes, écrivons une fonction qui renvoie le n-ième élément d'une liste chaînée.
On prend la convention que le premier élément est désigné par n = 0, comme pour les tableaux.
On cherche donc à écrire une fonction de la forme suivante.
def nieme_element(n, lst):
\"\"\"renvoie Le n-ième élément de la liste lst
Les éléments sont numérotés à partir de 9\"\"\"
Comme pour la fonction Longueur, nous avons le choix entre écrire la fonction nieme_element comme une fonction récursive ou avec une boucle.
Nous faisons ici le choix d'une fonction récursive.
Comme pour le calcul de la longueur, nous commençons par traiter le cas d'une liste qui ne contient aucun élément. Dans ce cas, on choisit de lever une exception, en l'occurrence la même exception IndexError que celle levée par Python lorsque l'on tente d'accéder à un indice invalide d'un tableau.
if lst is None:
raise IndexError (\"indice invalide\")
La chaîne de caractères passée en argument de l'exception est arbitraire.
Si en revanche la liste lst n'est pas vide, il y à deux cas de figure à considérer. Si n = 0, c'est que l'on demande le premier élément de la liste et il est alors renvoyé.
if n == 0:
return Ist.vaieur
Sinon, il faut continuer la recherche dans le reste de la liste. Pour cela, on fait un appel récursif à nieme_element en diminuant de un la valeur de n.
else:
return nieme_element(n - 1, lst.suivante)
Attention à ne pas oublier ici l'instruction return, car il faut renvoyer le résultat de l'appel récursif et non pas se contenter de faire un appel récursif.
Ceci achève le code de la fonction nieme_element. Le code complet est
Programme — N-ième élément d'une liste
lst = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))
def nieme_element(n, lst):
\"\"\"renvote le n-ième élément de La liste lst
les éléments sont numérotés à partir de O\"\"\"
if lst is None:
raise IndexError(\"indice invalide\")
if n == 0 :
return lst.valeur
else:
return nieme_element(n - 1, lst.suivante)
print(nieme_element(2,lst))
Complexité. La complexité de la fonction nieme_element est un peu plus subtile que celle de la fonction longueur. Dans certains cas, on effectue exactement n appels récursifs pour trouver le n-ième élément, et donc un nombre d'opérations proportionnel à n.
Dans d'autres cas, en revanche, on parcourt toute la liste. Cela se produit clairement lorsque n > longueur (lst). Il pourrait être tentant de commencer par comparer n avec la longueur de la liste, pour ne pas parcourir la liste inutilement, mais c'est inutile car le calcul de la longueur parcourt déjà toute la liste. Pire encore, calculer la longueur de la liste à chaque appel récursif résulterait en un programme de complexité quadratique (proportionnelle au carré de la longueur de la liste).
On peut remarquer que la liste est également intégralement parcourue lorsque n < 0. En effet, la valeur de n va rester strictement négative, puisqu'on la décrémente à chaque appel, et on finira par atteindre la liste vide.
Pour y remédier, ii suffit de modifier légèrement le premier test de la fonction, de la manière suivante :
if n < 0 or lst is None:
raise IndexError(\"indice invalide\")
On obtient exactement le même comportement qu'auparavant (la levée de l'exception IndexError) mais cela se fait maintenant en temps constant, car la liste n'est plus parcourue.
","title":"N-ième élément d'une liste"},{"edit":"Mettre le résultat ici (code et figure).
Considérons maintenant l'opération consistant à mettre bout à bout les éléments de deux listes données.
On appelle cela la concaténation de deux
listes.
Ainsi, si la première liste contient 1,2,3 et la seconde 4,5 alors le résultat de la concaténation est 1,2,3,4,5. Nous choisissons d'écrire la concaténation sous la forme d'une fonction concatener qui reçoit deux listes en arguments et renvoie une troisième liste contenant la concaténation.
def concatener{(l1, l2):
\"\"\"concatène les listes l1 et l2, sous la forme d'une nouvelle liste\"\"\"
Il est ici aisé de procéder récursivement sur la structure de la liste 11. Si elle est vide, la concaténation est identique à la liste l2, qu'on se contente donc de renvoyer.
if l1 is None:
return l2
Sinon, le premier élément de la concaténation est le premier élément de l1 et le reste de la concaténation est obtenu récursivement en concaténant le reste de 11 avec l2.
else:
return Cellule(l1.valeur, concatener(l1.suivante,l2))
Le programme ci-dessus contient l'intégralité du code.
Il est important de comprendre ici que les listes passées en argument à la fonction concatener ne sont pas modifiées.
Plus précisément, les éléments de la liste l1 sont copiés et ceux de l2 sont partagés.
Illustrons-le avec la concaténation des listes 1,2,3 et 4,5.
Après les trois instructions
l1 = Cellule(1, Cellule(2, Cellule(3, None)))
l2 = Cellule(4, Cellule(5, None))
l3 = concatener(l1, l2)
on à la situation suivante, avec huit cellules au total :
![](\"https://sciencesappliquees.com/images/nsi/liste6.png\")
On voit que les trois cellules de l1 ont été dupliquées, pour former le début de la liste 1,2, 3 ,4, 5, et que les deux cellules de l2 sont partagées pour former à la fois la liste l2 et la fin de la liste l3.
Il n'y a pas de danger à réaliser ainsi un tel partage de cellules, tant qu'on ne cherche pas à modifier les listes, Une alternative consisterait à copier également tous les éléments de l2, ce qui pourrait se faire en écrivant une fonction copie et en remplaçant return l2 par
return copie(l2).
Mais c'est inutile dès lors qu'on choisit de ne jamais modifier les listes une fois construites.
Dans la section suivante, nous discuterons d'une autre façon de réaliser la concaténation de deux listes l1 et l2, consistant à modifier la dernière cellule de la liste 11 pour la faire pointer vers la première cellule de la liste l2.
Mais nous mettrons également en garde contre les dangers que comporte une telle modification.
Programme - Concaténation de deux listes
def concatener(l1, l2):
\"\"\"concatène les listes l1 et l2, sous La forme d'une nouvelle liste\"\"\"
if l1 is None:
return l2
else:
return Cellule(l1.valeur, concatener(l1.suivante,l2))
l1 = Cellule(1, Cellule(2, Cellule(3, None)))
l2 = Cellule(4, Cellule(5, None))
l3 = concatener(l1, l2)
print(\"lg l3=\", longueurB(l3))
Complexité. Il est clair que le coût de la fonction concatener est directement proportionnel à la longueur de la liste 11. En revanche, il ne dépend
pas de la longueur de la liste l2.
Mettre le résultat ici (code et figure).
Comme quatrième et dernière opération sur les listes, considérons le renversement d'une liste, c'est-à-dire une fonction renverser qui, recevant en argument une liste comme 1,2, 3, renvoie la liste renversée 3, 2,1.
Vu que la récursivité a été utilisée avec succès pour écrire les trois opérations précédentes, il semble naturel de chercher une écriture récursive de la fonction renverser.
Le cas de base est celui d'une liste vide, pour laquelle
il suffit de renvoyer la liste vide. Pour le cas récursif, en revanche, c'est plus délicat, car le premier élément doit devenir le dernier élément de la liste renversée. Aussi, il faut renverser la queue de la liste puis concaténer à la fin le tout premier élément.
Vu que nous venons justement d'écrire une fonction
concatener, il n'y a qu'à s'en servir. Cela nous donne un code relativement simple pour la fonction renverser.
def renverser1(lst):
if lst is None:
return None
else:
return concatener(renverser(lst.suivante), Cellule(lst.valeur, None))
l1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, None)))))
r1 = renverser1(l1)
Un tel code, cependant, est particulièrement inefficace. Si on en mesure le temps d'exécution, on s'aperçoit qu'il est proportionnel au carré du nombre d'éléments.
Pour renverser une liste de 1000 éléments, il faut près d'un demimillion d'opérations.
En effet, il faut commencer par renverser une liste de 999 éléments, puis concaténer le résultat avec une liste d'un élément. Comme on l'a vu, cette concaténation coûte 999 opérations. Et pour renverser la liste de 999 éléments, il faut renverser une liste de 998 éléments puis concaténer le résultat avec une liste d'un élément. Et ainsi de suite.
Au total, on a donc au moins 999 + 998 + .. + 1 = 499500 opérations.
Une fois n'est pas coutume, la récursivité nous à mis sur la piste d'une mauvaise solution, du moins en termes de performance.
Il se trouve que dans le cas de la fonction renverser, une boucle while est plus adaptée.
En effet, il suffit de parcourir les éléments de la liste lst avec une simple boucle, et d'ajouter ses éléments au fur et à mesure en tête d'une seconde liste, appelons-la r.
Ainsi, le premier élément de la liste lst se retrouve en dernière position dans la liste r, le deuxième élément de lst en avant-dernière position dans r, etc., jusqu'au dernier élément de lst qui se retrouve en première position dans r.
Une bonne image est celle d'une pile de feuilles de papier sur notre bureau : si on prend successivement chaque feuille au sommet de la pile pour former à côté une seconde pile, alors on aura inversé l'ordre des feuilles au final.
Ici, la liste lst joue le rôle de la première pile et la liste r celle de la seconde.
Pour mettre en œuvre le code, on commence par se donner deux variables : une variable r pour le résultat et une variable c pour parcourir la liste lst.
def renverser(lst):
r = None
c = lst
On parcourt ensuite la liste avec une boucle while, en ajoutant à chaque étape le premier élément de c en tête de la liste r, avant de passer à l'élément suivant.
while c is not None:
Cellule(c.valeur, r)
c = c.suivante
Enfin, il ne reste plus qu'à renvoyer la liste r une fois sorti de la boucle.
return r
Le programme ci-dessous contient l'intégralité du code.
def renverser(lst):
\"\"\"renvoie une liste contenant les éléments de lst dans l'ordre inverse\"\"\"
r = None
c = lst
while c is not None:
r = Cellule(c.valeur, r)
c = c.suivante
return r
def afficher(lst) :
\"\"\"affiche les éléments d'une liste\"\"\"
c = lst
while c is not None:
print(c.valeur,c.suivante)
c = c.suivante
print(\"l1 = \")
l1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, None)))))
afficher(l1)
print(\"r1 = \")
r1 = renverser(l1)
afficher(r1)
Complexité. Il est clair que cette nouvelle fonction
directement proportionnel à la longueur de la liste lst, car le code fait un simple parcours de la liste, avec deux opérations élémentaires à chaque étape.
Ainsi, renverser une liste de 1000 éléments devient presque instantané, avec un millier d'opérations, là où notre fonction basée sur la concaténation utilisait un demi-million d'opérations.
","title":"Renverser une liste"},{"edit":"Mettre le résultat ici (code et figure).
Jusqu'à présent, nous avons délibérément choisi de ne jamais modifier les deux attributs valeur et suivante d'un objet de la classe Cellule. Une fois qu'un tel objet est construit, il n'est plus jamais modifié.
Cependant, rien ne nous empêcherait de le faire, intentionnellement ou accidentellement, car il reste toujours possible de modifier la valeur de ces attributs a posteriori avec des affectations.
Reprenons l'exemple de la liste 1,2,3 du début de cette séquence, construite avec
lst = Cellule(1, Cellule(2, Cellule(3, None)))
et que nous représentons ainsi :
Nous pouvons modifier la valeur du deuxième élément de la liste avec l'affectation suivante
lst.suivante.valeu = 4
On n alors la situation suivante :
![](\"https://sciencesappliquees.com/images/nsi/liste7.png\")
C'est-à-dire avec la liste 1,3,8.
Ici, on vient de modifie le contenu de la liste,
en modifiant un attribut valeur.
Mais on peut également modifier la structure de la liste, en modifiant un attribut suivante.
Si par exemple on réalise maintenant l'affectation
lst.suivante.suivante =Cellule(5,None)
alors on se retrouve avec la situation suivante :
![](\"https://sciencesappliquees.com/images/nsi/liste8.png\")
Ici, on a représenté que l'attribut suivante du deuxième élément pointait anciennement vers l'élément 3 (en pointillés) et qu'il pointe désormais vers un nouvel élément 5. La variable lst contient maintenant la liste 1,4,3.
Mettre le résultat ici (code et figure).
Puisque les listes peuvent être modifiées à posteriori, comme nous venons de l'expliquer, il peut être tentant d'en tirer profit pour écrire autrement certaines de nos opérations sur les listes.
Ainsi, pour réaliser la concaténation de deux listes, par exemple, il suffit de modifier l'attribut suivante du
dernier élément de la première liste pour lui donner la valeur de la seconde liste.
Cela semble une bonne idée. Mais il y a un risque.
Supposons que l'on construise deux listes 1,2,3
et 4,5 de la manière suivante :
l2 = Cellule(2, Cellule(3, None))
l1 = Cellule(1, l2)
l3 = Cellule(4, Cellule(5, None))
On note en particulier que la variable l2 contient toujours la liste 2,3, même si elle a servi depuis à construire la liste 1,2,3 stockée dans la variable l1.
![](\"https://sciencesappliquees.com/images/nsi/liste9.png\")
S'il nous prend maintenant l'envie de concaténer les listes l1 et l3 en reliant le dernier élément de l1 au premier élément de l3, par exemple en appelant
une fonction concatener_en_place(l1, l3) qui ferait cela, alors on se retrouverait dans cette situation :
![](\"https://sciencesappliquees.com/images/nsi/liste10.png\")
La variable l1 contient maintenant la liste 1,2,3,4,5, ce qui était recherché, mais la variable l2 ne contient plus la liste 2,3 mais la liste 2,3,4,5.
C'est là un effet de bord qui n'était peut-être pas du tout souhaité.
D'une manière générale, pouvoir accéder à une même donnée par deux chemins différents n'est pas un problème en soi, mais modifier ensuite la donnée par l'intermédiaire de l'un de ces chemins (ici l1) peut résulter en une modification non souhaitée de la valeur accessible par un autre chemin (ici l2).
Par ailleurs, que feraient deux appels supplémentaires à concatener_en_place(l1, l3)?
C'est pourquoi nous avons privilégié une approche où la concaténation, et plus généralement les opérations qui construisent des listes, renvoient de nouvelles listes plutôt que de modifier leurs arguments.
On peut remarquer que c'est là une approche également suivie par certaines constructions de Python. L'opération + de Python, par exemple, ne modifie pas ses arguments mais renvoie une nouvelle valeur, qu'il s'agisse d'entiers, de chaînes de caractères ou encore de tableaux.
Ainsi, si t est le tableau [1, 2], alors t + [3]
construit un nouveau tableau [1, 2, 3].
En ce sens, l'opération + se distingue d'autres opérations, comme .append, qui modifient leur argument.
Comme nous allons le voir dans la section suivante, cela ne nous empêche pas pour autant d'utiliser nos listes dans un style de programmation impératif.
Mettre le résultat ici (code et figure).
Pour terminer cette séquence sur les listes chaînées, nous allons maintenant montrer comment encapsuler une liste chaînée dans un objet.
L'idée consiste à définir une nouvelle classe, Liste, qui possède un unique attribut, tete, qui contient une liste chaînée. On l'appelle tete car il désigne la tête de la liste, lorsque celle-ci n'est pas vide (et None sinon).
Le constructeur initialise l\"attribut tete avec la valeur None.
class Liste:
\"\"\"une Liste chaînée\"\"\"
def __init__(self):
self.tete = None
Autrement dit, un objet construit avec Liste() représente une liste vide.
On peut également introduire une méthode est_vide qui renvoie un booléen indiquant si la liste est vide.
def est_vide(self):
return self.tete is None
En effet, notre intention est d'encapsuler, c'est-à-dire de cacher, la représentation de la liste derrière cet objet. Pour cette raison, on ne souhaite pas que l'utilisateur de la classe Liste teste explicitement si l'attribut tete vaut None, mais qu'il utilise cette méthode est_vide.
On poursuit la construction de la classe Liste avec une méthode pour ajouter un élément en tête de la liste.
def ajoute(self, x):
self.tete = Cellule(x, self.tete)
Cette méthode modifie l'attribut tete et ne renvoie rien. Si par exemple on exécute les quatre instructions ci-dessous :
lst = Liste()
lst.ajoute(3)
lst.ajoute(2)
lst.ajoute(1)
on obtient la situation suivante :
![](\"https://sciencesappliquees.com/images/nsi/liste11.png\")
On a donc construit ainsi la liste 1,2,3, dans cet ordre.
On peut maintenant reformuler nos opérations, à savoir longueur, nieme_element, concatener ou encore renverser, comme autant de méthodes de la classe Liste.
Ainsi, on peut écrire par exemple
def longueur(self):
return longueur(self.tete)
qui ajoute à la classe Liste une méthode longueur, qui nous permet d'écrire lst.longueur(} pour obtenir la longueur de la liste lst.
Il est important de noter qu'il n'y a pas confusion ici entre la fonction longueur définie précédemment et la méthode longueur.
En particulier, la seconde est définie en appelant la première. Le langage Python est ainsi fait que, lorsqu'on écrit longueur (self.tete), il ne s'agit pas d'un appel récursif à la méthode longueur. (Un appel récursif s'écrirait self. longueur().) Si l'on trouve que donner le même nom à la fonction et à la méthode est source de confusion, on peut tout à fait choisir un nom différent pour la méthode, comme par exemple
def taille(self):
return longueur(self.tete)
Mieux encore, on peut donner à cette méthode le nom __len__ et Python nous permet alors d'écrire len(lst} comme pour un tableau.
En eflet, lorsque l'on écrit len en Python, ce n'est qu'un synonyme pour l'appel de méthode __len__().
De même, on peut ajouter à la classe Liste une méthode pour accéder au n-ième élément de la liste, c'est-à-dire une méthode qui va appeler notre fonction nieme_element sur self.tete.
Le nom de la méthode est arbitraire et nous pourrions choisir de conserver le nom nieme_element. Mais
là encore nous pouvons faire le choix d'un nom idiomatique en Python, à savoir __getitem__
def __getitem_ _(self, n):
return nieme_element(n, self.tete)
Ceci nous permet alors d'écrire lst{[i] pour accéder au i-ème élément de notre liste, exactement comme pour les tableaux.
Pour la fonction renverser, on fait le choix de nommer la méthode reverse car là encore OuiCar là encore c'est un nom qui existe déjà pour les tableaux de Python.
Programme - Encapsulation d'une liste dans un objet
class Liste:
\"\"\"une Liste chaînée\"\"\"
def __init__(self):
self.tete = None
def est_vide(self):
return self.tete is None
def ajoute(self, x):
self.tete = Cellule(x, self.tete)
def __len__(self):
return longueurB(self.tete)
def __getitem__(self, n):
return nieme_element(n, self.tete)
def reverse(self) :
self.tete = renverser(self.tete)
def __add__(self, lst):
r = Liste()
r.tete = concatener(self.tete, lst.tete)
return r
lst = Liste()
print(lst.est_vide())
lst.ajoute(3)
print(lst.est_vide())
lst.ajoute(2)
lst.ajoute(1)
print(len(lst))
print(lst[1])
Enfin, le cas de la concaténation est plus subtil, car il s'agit de renvoyer une nouvelle liste, c'est-à-dire un nouvel objet. On choisit d'appeler la méthode __add__ qui correspond à la syntaxe + de Python.
def __add__(self, lst):
r = Liste()
r.tete = concatener(self.tete, lst.tete)
return r
Ainsi, on peut écrire lst+lst pour obtenir la liste 1,2,3,1,2,3.
Mettre le résultat ici (code et figure).
Intérêt d'une telle encapsulation. Il est multiple. D'une part, il cache la représentation de la structure à l'utilisateur.
Ainsi, celui qui utilise notre classe Liste n'a plus à manipuler explicitement la classe Cellule.
Mieux encore, il peut complètement ignorer l'existence de la classe Cellule.
De même, il ignore que la liste vide est représentée par la valeur None. En particulier, la réalisation de la classe Liste pourrait être modifiée sans pour autant que le
code qui l'utilise n'ait besoin d'être modifié à son tour.
D'autre part, l'utilisation de classes et de méthodes nous permet de donner le même nom à toutes les méthodes qui sont de même nature.
Ainsi, on peut avoir plusieurs classes avec des méthodes est_vide, ajoute, etc. Si nous avions utilisé de simples fonctions, il faudrait distinguer
liste _est_vide, pile est vide, ensemble _est_vide, etc.
Écrire une fonction listeN(n) qui reçoit en argument un entier n, supposé positif ou nul, et renvoie la liste des entiers 1,2,...,n, dans cet ordre. Si n = 0, la liste renvoyée est vide.
Tester avec :
l2 = listeN(5)
afficher(l2)
Résultat :
1 <__main__.Cellule object at 0x103540a20>
2 <__main__.Cellule object at 0x103540a58>
3 <__main__.Cellule object at 0x103540da0>
4 <__main__.Cellule object at 0x103540a90>
5 None
Attention les adresses mémoires ne seront pas les mêmes.
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
def listeN(n):
lst = None
while n > 0:
lst = Cellule(n, lst)
n -= 1
return lst
l2 = listeN(5)
afficher(l2)
Écrire une fonction affiche liste(lst) qui affiche, en utilisant la fonction print, tous les éléments de la liste lst, séparés par des espaces, suivis d'un retour chariot.
L'écrire comme une fonction récursive, puis avec une boucle while.
Tester avec :
l2 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))
affiche_liste(l2)
Le résultat est :
a b c d
Mettre le résultat ici (code et figure).
Pour éviter que print n’insère un retour chariot après chaque élément, on utilise print(..., end= \" \"), puis un unique print() à la fin de la liste.
Avec une récursivité :
l2 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))
def affiche_liste(lst):
if lst is None:
print()
else :
print(lst.valeur, end=\" \")
affiche_liste(lst.suivante)
affiche_liste(l2)
Avec une itération :
l2 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))
def affiche_liste(lst):
c = lst
while c is not None:
print(c.valeur, end=\" \")
c = c.suivante
print()
affiche_liste(l2)
Ecrire une procédure insertion_en_tete(lst,x) qui prend comme paramètres une liste lst et une valeur x et qui insère un nouvel élément en tête de la liste chaînée lst.
Tester avec :
lst1 = Cellule(1, Cellule(2, Cellule(3, None)))
affiche_liste(lst1)
insertion_en_tete(lst1,0)
affiche_liste(lst1)
Résultat :
1 2 3
0 1 2 3
Mettre le résultat ici (code et figure).
def insertion_en_tete(lst,x):
lst.suivante = Cellule(lst.valeur,lst.suivante)
lst.valeur = x
Ecrire une procédure insertion_en_queue(lst,x) qui prend comme paramètres une liste lst et une valeur x et qui insère un nouvel élément en queue de la liste chaînée lst.
Tester avec :
lst1 = Cellule(1, Cellule(2, Cellule(3, None)))
affiche_liste(lst1)
insertion_en_queue(lst1,4)
affiche_liste(lst1)
Résultat :
1 2 3
1 2 3 4
Mettre le résultat ici (code et figure).
def insertion_en_queue(lst,x):
if lst.suivante is None :
lst.suivante = Cellule(x,None)
else :
insertion_en_queue(lst.suivante,x)
Ecrire une procédure inserer_dans_liste(lst,x,posi) qui a comme paramètres :
- la liste lst;
- la valeur de l'élément;
- la position posi
et qui insère un nouvel élément de sorte qu'il se trouve à une position donnée dans la liste. La position est un entier et correspond au numéro du futur élément dans la liste. Le
premier élément porte le numéro 0.
Tester avec :
lst1 = Cellule(1, Cellule(2, Cellule(3, None)))
affiche_liste(lst1)
inserer_dans_liste(lst1,4,0)#posi en tete
affiche_liste(lst1)
inserer_dans_liste(lst1,8,2)#posi au milieu
affiche_liste(lst1)
inserer_dans_liste(lst1,7,4)#posi en queue
affiche_liste(lst1)
inserer_dans_liste(lst1,10,6)# indice trop grand
Résultat :
1 2 3
4 1 2 3
4 1 8 2 3
4 1 8 2 3 7
Traceback (most
Mettre le résultat ici (code et figure).
def inserer_dans_liste(lst,x,posi):
if posi == 0 :
if lst.suivante is not None:
lst.suivante = Cellule(lst.valeur,lst.suivante)
lst.valeur = x
else :
lst.suivante = Cellule(x,None)
elif lst.suivante is None :
raise IndexError(\"Problème d'indice\")
else :
inserer_dans_liste(lst.suivante,x,posi-1)
Ecrire une procédure sup_tete(lst) qui prend comme paramètres une liste lst et qui supprime le premier élément de la liste chaînée lst.
Tester avec :
lst1 = Cellule(1, Cellule(2, Cellule(3, None)))
affiche_liste(lst1)
sup_tete(lst1)
affiche_liste(lst1)
Résultat :
1 2 3
2 3
Mettre le résultat ici (code et figure).
def sup_tete(lst) :
lst.valeur = lst.suivante.valeur
lst.suivante = lst.suivante.suivante
Ecrire une procédure sup_queue(lst) qui prend comme paramètres une liste lst et qui supprime le dernier élément de la liste chaînée lst.
Tester avec :
lst1 = Cellule(1, Cellule(2, Cellule(3, None)))
affiche_liste(lst1)
sup_queue(lst1)
affiche_liste(lst1)
Résultat :
1 2 3
1 2
Mettre le résultat ici (code et figure).
def sup_queue(lst) :
if lst.suivante.suivante is None :
lst.suivante = None
else :
sup_queue(lst.suivante)
Ecrire une procédure sup_element(lst,posi) qui prend comme paramètres une liste lst, un entier pour la position et qui supprime l'élément en position posi dans la liste chaînée lst.
Attention, la numérotation dans la liste commence à 0.
Tester avec :
lst1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, None))))
affiche_liste(lst1)
sup_element(lst1,1)
affiche_liste(lst1)
Résultat :
1 2 3 4
1 3 4
Mettre le résultat ici (code et figure).
def sup_element(lst,posi) :
if posi == 0 :
lst.valeur = lst.suivante.valeur
lst.suivante = lst.suivante.suivante
else :
sup_element(lst.suivante,posi-1)
Réécrire la fonction nieme_element
lst = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))
def nieme_element(n, lst):
\"\"\"renvote le n-ième élément de La liste lst
les éléments sont numérotés à partir de O\"\"\"
if lst is None:
raise IndexError(\"indice invalide\")
if n == 0 :
return lst.valeur
else:
return nieme_element(n - 1, lst.suivante)
print(nieme_element(2,lst))
avec une boucle while.
Tester avec :
l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))
print(nieme_element(2,l1))
Résultat :
c
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
Comme pour la fonction longueur, on se sert d’une
variable c pour parcourir la liste. On se sert également d’une variable i pour
mesurer notre avancement dans la liste. Il y a donc une double condition
d’arrêt à la boucle.
def nieme_element(n, lst):
i = 0
c = lst
while i < n and c is not None:
i += 1
c = c.suivante
if n < 0 or c is None:
raise IndexError(\"indice invalide\")
return c.valeur
l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", None))))
print(nieme_element(2,l1))
Note : la condition n < 0 nous préserve d’une valeur négative qui aurait été passée à la fonction nieme_element. Bien entendu, on aurait pu effectuer ce
test dès l’entrée de la fonction, avant même de parcourir la liste, ou encore supposer que n est positif ou nul.
Écrire une fonction occurrences(x, lst) qui renvoie le nombre d'occurrences de la valeur x dans la liste lst.
L'écrire comme une fonction récursive, puis avec une boucle while.
Tester avec :
l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))
print(\"nb b :\",occurrences(\"b\",l1))
print(\"nb a :\",occurrences(\"a\",l1))
Résultat :
nb b : 3
nb a : 1
Mettre le résultat ici (code et figure).
Avec une fonction récursive :
def occurrences(x, lst):
if lst is None:
return 0
elif x == lst.valeur:
return 1 + occurrences(x, lst.suivante)
else:
return occurrences(x, lst.suivante)
l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))
print(\"nb b :\",occurrences(\"b\",l1))
print(\"nb a :\",occurrences(\"a\",l1))
Avec une itération (boucle) :
def occurrences(x, lst):
n=0
c = lst
while c.suivante is not None :
if x == c.valeur:
n += 1
c = c.suivante
if x == c.valeur:
n += 1
return n
l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))
print(\"nb b :\",occurrences(\"b\",l1))
print(\"nb a :\",occurrences(\"a\",l1))
Écrire une fonction trouve(x, lst} qui renvoie le rang de la première occurrence de x dans lst, le cas échéant, et None sinon.
L'écrire comme une fonction récursive, puis avec une boucle while.
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
Tester avec ;
l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))
print(\"posi c :\",trouve(\"c\",l1))
print(\"posi a :\",trouve(\"a\",l1))
print(\"posi e :\",trouve(\"e\",l1))
Résultat :
posi c : 2
posi a : 0
posi e : None
Ici la version récursive est assez pénible à écrire, car
il faut tester si l’appel récursif a renvoyé None :
ef trouve(x, lst):
if lst is None:
return None
elif lst.valeur == x :
return 0
else:
r = trouve(x, lst.suivante)
if r == None:
return None
else:
return 1 + r
l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))
print(\"posi c :\",trouve(\"c\",l1))
print(\"posi a :\",trouve(\"a\",l1))
print(\"posi e :\",trouve(\"e\",l1))
La boucle, en revanche, est plus simple à écrire :
def trouve(x, lst):
i=0
c = lst
while c is not None:
if c.valeur == x:
return i
c = c.suivante
i += 1
return None
l1 = Cellule(\"a\", Cellule(\"b\", Cellule(\"c\", Cellule(\"d\", Cellule(\"b\", Cellule(\"c\", Cellule(\"b\", None)))))))
print(\"posi c :\",trouve(\"c\",l1))
print(\"posi a :\",trouve(\"a\",l1))
print(\"posi e :\",trouve(\"e\",l1))
Écrire une fonction récursive concatener_inverse(l1, l2)
qui renvoie le même résultat que concatener(renverser(l1), l2), mais sans appeler ces deux fonctions.
En déduire une fonction renverser qui a la même complexité que le programme renverser de la séquence.
Tester avec :
lst1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))
lst = concatener_inverse(lst1,lst1)
affiche_liste(lst)
Résultat :
6 5 4 3 2 1 1 2 3 4 5 6
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
On procède récursivement sur la structure de la
liste l1 :
def concatener_inverse(l1, l2):
if l1 is None:
return l2
else:
return concatener_inverse(l1.suivante, \\
Cellule(l1.valeur, l2))
lst1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))
lst = concatener_inverse(lst1,lst1)
affiche_liste(lst)
La fonction renverser s’en déduit trivialement, en prenant une liste videdef renverser (1st):
return concatener_inverse(lst, None)
Écrire une fonction identiques(l1, l2) qui renvoie un booléen indiquant si les listes l1 et l2 sont identiques, c'est-à-dire contiennent exactement les mêmes éléments, dans le même ordre.
On suppose que l'on peut comparer les éléments de l1 et l2 avec l'égalité == de Python.
Tester avec :
lst1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))
lst2 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))
lst3 = Cellule(1, Cellule(2, Cellule(3, Cellule(7, Cellule(5, Cellule(6, None))))))
print(identiques(lst1,lst2))
print(identiques(lst1,lst3))
Résultat :
True
False
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
On le fait ici avec une fonction récursive. Il faut
prendre soin de bien traiter le cas où l’une ou l’autre des listes est vide :
def identiques(l1, l2):
if l1 is None:
return l2 is None
if l2 is None:
return l1 is None
return l1.valeur == l2.valeur \\
and identiques(l1.suivante, l2.suivante)
lst1 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))
lst2 = Cellule(1, Cellule(2, Cellule(3, Cellule(4, Cellule(5, Cellule(6, None))))))
lst3 = Cellule(1, Cellule(2, Cellule(3, Cellule(7, Cellule(5, Cellule(6, None))))))
print(identiques(lst1,lst2))
print(identiques(lst1,lst3))
Écrire une fonction inserer(x, lst) qui prend en arguments un entier x et une liste d'entiers lst, supposée triée par ordre croissant, et qui renvoie une nouvelle liste dans laquelle x a été inséré à sa place
Ainsi, insérer la valeur 3 dans la liste 1,2, 5,8 renvoie la liste 1,2,3,5,8.
On suggère d'écrire inserer comme une fonction récursive.
Tester avec :
lst = Cellule(2, Cellule(4, Cellule(7, Cellule(8, Cellule(9, Cellule(12, None))))))
affiche_liste(lst)
lst = inserer(4,lst)
lst = inserer(1,lst)
lst = inserer(14,lst)
affiche_liste(lst)
Résultat :
2 4 7 8 9 12
1 2 4 4 7 8 9 12 14
Mettre le résultat ici (code et figure).
Le cas d'arrêt est double : soit la liste est vide,
soit x n’est pas plus grand que la valeur en tête de liste. Dans les deux cas, on ajoute x au début de lst. Sinon, on conserve le premier élément et on
insère x récursivement dans la liste lst.suivante.
def inserer(x, lst):
if lst is None or x <= lst.valeur:
return Cellule(x, lst)
else:
return Cellule(lst.valeur, inserer(x, lst.suivante))
lst = Cellule(2, Cellule(4, Cellule(7, Cellule(8, Cellule(9, Cellule(12, None))))))
affiche_liste(lst)
lst = inserer(4,lst)
lst = inserer(1,lst)
lst = inserer(14,lst)
affiche_liste(lst)
En se servant de l'exercice précédent, écrire une fonction tri_par_insertion(lst) qui prend en argument une liste d'entiers lst et renvoie une nouvelle liste, contenant les mêmes éléments et triée par ordre croissant.
On suggère de l'écrire comme une fonction récursive.
Tester avec :
lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))
affiche_liste(lst1)
lst2 = tri_par_insertion(lst1)
affiche_liste(lst2)
Résultat :
5 8 7 1 3 6
1 3 5 6 7 8
Mettre le résultat ici (code et figure).
Le cas de base correspond à une liste de longueur
au plus 1, pour laquelle il suffit de la renvoyer.
def tri_par_insertion(lst):
if lst is None or lst.suivante is None:
return lst
else:
return inserer(lst.valeur, \\
tri_par_insertion(lst.suivante))
lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))
affiche_liste(lst1)
lst2 = tri_par_insertion(lst1)
affiche_liste(lst2)
Note : on pourrait également écrire if longueur(ist) <= 1 mais ce serait calculer inutilement la longueur de la liste (calculer la longueur oblige à parcourir toute la liste), ce qui dégraderait les performances de ce programme.
Écrire une fonction liste_de_tableau(t} qui renvoie une liste qui contient les éléments du tableau t, dans le même ordre.
On suggère de l'écrire avec une boucle for.
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
Tester avec :
t1 = [2,4,5,7,9,10,12]
print(t1)
lst1 = liste_de_tableau(t1)
affiche_liste(lst1)
Résultat ;
[2, 4, 5, 7, 9, 10, 12]
2 4 5 7 9 10 12
Pour préserver l’ordre des éléments, il faut prendre
soin de parcourir le tableau de la droite vers la gauche :
def liste_de_tableau(t):
lst = None
for i in range(len(t) - 1, -1, -1):
lst = Cellule(t[i], lst)
return lst
t1 = [2,4,5,7,9,10,12]
print(t1)
lst1 = liste_de_tableau(t1)
affiche_liste(lst1)
Écrire une fonction derniere_cellule(lst) qui renvoie l'adresse mémoire de la dernière cellule de la liste lst. On suppose la liste lst non vide.
Tester avec :
lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))
print(derniere_cellule(lst1))
lst2 = Cellule(1, Cellule(5, Cellule(4, Cellule(6, Cellule(8, None)))))
print(derniere_cellule(lst2))
Résultat :
<__main__.Cellule object at 0x10405f898>
<__main__.Cellule object at 0x10405fe48>
Mettre le résultat ici (code et figure).
def derniere_cellule(lst):
c = lst
while c.suivante is not None:
c = c.suivante
return c
lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))
print(derniere_cellule(lst1))
En utilisant la fonction de l'exercice précédent, écrire une seconde fonction, concatener_en_place(l1, l2), qui réalise une concaténation en place des listes l1 et l2, c'est-à-dire qui relie la dernière cellule de l1 à la première cellule de l2. Cette fonction doit renvoyer la toute première cellule de la concaténation.
Tester avec :
lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))
lst2 = Cellule(1, Cellule(5, Cellule(4, Cellule(6, Cellule(8, None)))))
affiche_liste(lst1)
affiche_liste(lst2)
lst3 = concatener_en_place(lst1, lst2)
affiche_liste(lst1)
affiche_liste(lst2)
affiche_liste(lst3)
Résultat :
5 8 7 1 3 6
1 5 4 6 8
5 8 7 1 3 6 1 5 4 6 8
1 5 4 6 8
5 8 7 1 3 6 1 5 4 6 8
Mettre le résultat ici (code et figure).
def concatener_en_place(l1, l2):
if l1 is None:
return l2
c = derniere_cellule(l1)
c.suivante = l2
return l1
lst1 = Cellule(5, Cellule(8, Cellule(7, Cellule(1, Cellule(3, Cellule(6, None))))))
lst2 = Cellule(1, Cellule(5, Cellule(4, Cellule(6, Cellule(8, None)))))
affiche_liste(lst1)
affiche_liste(lst2)
lst3 = concatener_en_place(lst1, lst2)
affiche_liste(lst1)
affiche_liste(lst2)
affiche_liste(lst3)
Fonction de vérification d’une liste chaînée triée
Ecrire une fonction qui vérifie si une liste chaînée est triée par valeurs croissantes du champ Info.
04-**-Procédure d’insertion en tête de liste chaînée
Ecrire une procédure qui insère un nouvel élément en tête d’une liste chaînée.
05-**-Procédure d’insertion en queue de liste chaînée
Ecrire une procédure qui insère un nouvel élément en queue d’une liste chaînée.
06-**- Procédure d’insertion à une position donnée
Ecrire une procédure qui insère un nouvel élément de sorte qu'il se trouve à une position donnée
dans la liste. La position est un entier et correspond au numéro du futur élément dans la liste. Le
premier élément porte le numéro 1.
07-**- Procédure de suppression d’un élément d’une liste chaînée à
une position donnée
Ecrire une procédure qui supprime un élément d’une liste chaînée à une position donnée.
DVD-MIAGE Exercices Algorithmique
Exercices ch. 9, 10 et 11 Page 3/20
08-**- Fonction de calcul de moyenne des étudiants
Le département dans lequel vous êtes inscrit souhaite gérer les notes de ses étudiants. Les étudiants
ont pour identifiant leur numéro d’étudiant. Ils ont un nom et un prénom. Ces informations sont
stockées dans une liste chaînée dont chaque élément comporte aussi un champ moy pour la
moyenne de l'étudiant et un champ eval qui est un pointeur sur sa liste de notes. La liste de notes de
chaque étudiant est aussi une liste chaînée dont la tête est le champ eval de la cellule de l'étudiant.
On dispose des déclarations suivantes :
Types :
Ch10 = Chaine de 10 caractères
Ch30 = Chaine de 30 caractères
Ent
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).