L2 MIASHS, Algorithme et Programmation 2, année 2021
Liste chainée simple
Une liste chaînée d’entiers est une structure de donnée représentant des suites d’entiers en faisant pointer chaque élément vers le suivant. On va utiliser la structure de pointeurs des listes pour les définir.
Récursivement, on a la définition suivante:
- La liste vide est une liste chaînée
- Pour
L
une liste chaînée etv
un entier, alors[v, L]
est une liste chaînée.
Par exemple, L = [42, [20, [3, [10, []]]]]
est la liste représentant la suite 42, 20, 3, 10
.
Pour toutes les fonctions suivantes, indiquez la complexité.
Length
Écrire une fonction length
qui prend en argument une liste chaînée et qui retourne sa longueur.
Par exemple, length(L)
retourne 4.
Get
Écrire une fonction get
qui prend une liste chaînée et un entier \(i\) et qui retourne le \(i^\text{ème}\) élément de la liste.
Par exemple, get(L, 2)
retourne 3.
Extract
Écrire une fonction extract
qui prend une liste chaînée \(L\) et un entier \(i\) et qui retourne la liste chaînée qui débute à l’indice \(i\).
Par exemple extract(L, 1)
retourne la liste chaînée [20, [3, [10, []]]]
.
Attention, vous devez avoir id(L[1]) == extract(L, 1)
Prepend
Écrire une fonction prepend
qui prend une liste chaînée et qui ajoute à sa gauche une valeur, sans recopier la liste initiale.
Par exemple, prepend(L, 220)
à L
on obtient la liste suivante: [220, [42, [20, [3, [10, []]]]]
.
Votre fonction doit aussi vérifier que id(L) == id(prepend(L, 220)[1])
, pour pas qu’il y ait de copie.
Append
Écrire une fonction append
qui prend une liste chaînée et qui ajoute à sa droite une valeur, sans recopier la liste initiale. Attention, c’est une fonction en place, elle ne retourne rien.
Par exemple, append(L, 220)
à L
on obtient la liste suivante: [42, [20, [3, [10, [220, []]]]]
.
Votre fonction doit aussi vérifier que
= id(L)
i 220)
append(L, print(i == id(L))
Traceback (most recent call last):
File "/home/cha/conf_files/utils/check_py_md", line 75, in repl
exec(code, env)
File "<string>", line 1, in <module>
NameError: name 'L' is not defined
Pop
Écrire une fonction pop
qui prend une liste chaînée et un entier \(i\) et qui: - supprime de la liste l’élément à l’indice \(i\) de la liste - retourne sa valeur
Extend
Écrire une fonction extend
qui prend deux listes chaînées \(L\) et \(K\) et ajoute \(K\) à la fin de \(L\). Attention, c’est une fonction en place, elle ne retourne rien.
Par exemple extend(L, [12, [13, []]])
retourne [42, [20, [3, [10, [12, [13, []]]]]]]
.
Sort
Implémenter un tri en place de votre choix pour les listes chaînées.
Une liste doublement chaînée circulaire (Difficile)
Dans une liste doublement chaînée circulaire, on a les propriétés suivantes:
- Chaque élément pointe vers l’élément suivant et l’élément précédent.
- L’élément précédant le premier élément de la liste est le dernier élément de la liste.
- L’élément suivant le dernier élément de la liste est le premier élément de la liste.
On définit les listes doublement chaînées en Python de la manière suivante:
Chaque élément de la liste est une list
Python de taille 3 où: - Le premier élément est la valeur de la liste. - Le deuxième élément est la liste correspondant à l’élément suivant - Le troisième élément est la liste correspondant à l’élément précédent
Par exemple, la liste de taille 1
contenant la valeur 42 peut être définie ainsi:
= [42]
L
L.append(L) L.append(L)
La liste de taille 2
contenant 42
et 43
peut être définie ainsi:
= [42]
L = [43]
K
L.append(K)
L.append(K)
K.append(L) K.append(L)
La liste de taille 3
contenant 42
, 43
et 44
:
= [42]
L = [43]
K = [44]
T
L.append(K)
K.append(T)
T.append(L)
L.append(T)
T.append(K) K.append(L)
Refaire toutes les fonctions précédentes pour les listes doublement chaînées circulaires.