# listes chaîné
+++ sommaire
Le but de ce document est de s'entraîner sur la manipulation de listes chaînées ainsi que la récursivité.
## Structures utilisées
### Liste chaînée simple
widget python
class CelluleSimple():
def __init__(self, valeur, suivante):
self.v = valeur
self.s = suivante
widget
### Liste chaînée double
widget python
class CelluleDouble():
def __init__(self, valeur, precedente, suivante):
self.v = valeur
self.s = suivante
self.p = precedente
widget
## Initialisation de liste
### Création d'une liste avec valeurs croissantes
widget python
def initListeSimple(n):
[bloc afficher la reponse
lst = None
for i in range(n,-1,-1):
lst = CelluleSimple(i, lst)
return lst
bloc]
def initListeDouble(n):
[bloc afficher la reponse
lst = None
for i in range(n,-1,-1):
celluleCourante = lst
lst = CelluleSimple(i, lst)
lst.suivante = celluleCourante
return lst
bloc]
widget
### Création d'une liste avec valeurs aléatoires
widget python
import random
def initListeAleaSimple(n):
[bloc afficher la reponse
lst = None
for i in range(n,0,-1):
lst = CelluleSimple(random.randint(0,10), lst)
return lst
bloc]
def initListeAleaDouble(n):
[bloc afficher la reponse
lst = None
for i in range(n,0,-1):
celluleCourante = lst
lst = CelluleSimple(random.randint(0,10), lst)
lst.s = celluleCourante
return lst
bloc]
widget
## Afficher le contenu d'une liste
widget python
def afficherListe(lst):
[bloc afficher la reponse
if(lst.s == None):
print(lst.v)
else:
print(lst.v, end=" ")
afficherListe(lst.s)
bloc]
widget
## Manipulations générales
### Afficher l'élément numéro n
widget python (fonction d'affichage du contenu d'une liste:4) (fonctions de création de liste aléa:3) (Classe CelluleSimple:0)
def elementNumeroN(n, lst):
[bloc afficher la reponse
if( lst == None):
raise IndexError(f"numéro {n} invalide")
if(n==1):
return lst.v
else:
return elementNumeroN(n - 1, lst.s)
bloc]
lst = initListeAleaSimple(10)
afficherListe(lst)
print(f"le septième élément de la liste chaînée est : {elementNumeroN(7, lst)}")
widget
### Compter le nombre d'occurrences d'une valeur
widget python (fonction d'affichage du contenu d'une liste:4) (fonctions de création de liste aléa:3) (Classe CelluleSimple:0)
def occurences(v, lst):
[bloc afficher la reponse
if(lst == None):
return 0
c = 1 if lst.v == v else 0
return c + occurences(v, lst.s)
bloc]
lst = initListeAleaSimple(10)
afficherListe(lst)
for v in range(11):
print(f"valeur {v} : {occurences(v, lst)} cellule(s)")
widget
### Trouver la première cellule de valeur X
widget python (fonction d'affichage du contenu d'une liste:4) (fonctions de création de liste aléa:3) (Classe CelluleSimple:0)
def trouve(x, lst):
[bloc afficher la reponse
if(lst == None):
return None
elif(lst.v == x):
return 0
else:
r = trouve(x, lst.s)
if(r != None):
return 1 + r
else:
return None
bloc]
lst = initListeAleaSimple(10)
afficherListe(lst)
for v in range(11):
print(f"valeur {v}, position de la cellule : {trouve(v, lst)}")
widget
On se rends compte que la version récursive de la fonction "trouve" n'est pas terrible. La version itérative est plus lisible.
widget python (fonction d'affichage du contenu d'une liste:4) (fonctions de création de liste aléa:3) (Classe CelluleSimple:0)
def trouve(x, lst):
[bloc afficher la reponse
compteur = 0
while(lst != None):
if(lst.v == x):
return compteur
compteur += 1
lst = lst.s
return None
bloc]
lst = initListeAleaSimple(10)
afficherListe(lst)
for v in range(11):
print(f"valeur {v}, position de la cellule : {trouve(v, lst)}")
widget
### Concaténer deux listes chaînées
+++bulle matthieu
On se fixe comme contrainte de créer une troisième liste sans modifier les deux listes à concaténer
+++
widget python (fonction d'affichage du contenu d'une liste:4) (fonctions de création de liste aléa:3) (Classe CelluleSimple:0)
def concatener(lst1, lst2):
[bloc afficher la reponse
if(lst1 == None):
return lst2
else:
return CelluleSimple(lst1.v, concatener(lst1.s, lst2))
bloc]
[bloc afficher la complexité
# La complexité est en O(|lst1|) où |lts1| est le nbr de cellules dans la liste lst1
bloc]
lst1 = initListeAleaSimple(5)
lst2 = initListeAleaSimple(10)
print('Voici la liste générée : ')
afficherListe(concatener(lst1,lst2))
print('composée des deux listes : ')
afficherListe(lst1)
afficherListe(lst2)
widget
## Manipulations avancées : en fonction du type de liste chaînée
### Renverser une liste
+++bulle matthieu
On se fixe comme contrainte de créer une nouvelle liste renversée à partir d'une liste initiale. Donc pas de modification de cette liste initiale.
+++
#### Liste chaînée Simple
widget python (fonction de concaténation:9:41:47) (fonction d'affichage du contenu d'une liste:4) (fonctions de création de liste aléa:3) (Classe CelluleSimple:0)
def renverser(lst):
[bloc afficher la reponse
if(lst == None):
return None
return concatener(renverser(lst.s), CelluleSimple(lst.v,None))
bloc]
[bloc afficher la complexité
"""
La complexité est en O(|lst|²) où |lts| est le nbr de cellules dans la liste lst
Ceci car la fonction 'concaterner' effectue 1 + 2 + 3 + ... + |lst| appels récursifs, ce qui revient à O(|lst|²)
"""
bloc]
lst = initListeAleaSimple(10)
afficherListe(lst)
print('Inversion : ')
afficherListe(renverser(lst))
widget
#### Liste chaînée Double
#### Quelle différence ?
