Le principe de la liste chaînée

Le schéma ci-dessous illustre le principe d'une liste chaînée : chaque cellule est constitué d'une valeur et d'une adresse mémoire. Cette adresse réfère à la valeur suivante.

La liste chainée est une façon parmi d'autres d'implémenter les listes.

La liste ci-dessus peut être notée :

(1, address->) (4 , address->) (7, address->) (2 , address->) (0, None)

implémentation

On organise l'implémentation avec 2 classes :

class Cellule :
    
    def __init__(self,valeur=None,fille=None) :
        self.valeur = valeur
        self.fille = fille
        
    def __str__(self):
        return str(self.valeur)



class Liste :
    def __init__(self):
        self.debut = None
        
    # liste vide
    def est_vide(self):
        return self.debut == None
    
    # affichage de la liste
    def __str__(self):
        if self.est_vide():
            return "liste vide"
        else:
            tmp = self.debut
            res = "["
            while tmp.fille is not None:
                res = res + str(tmp.valeur) + "]->[" # ou mettre ',' pour un affichage classique
                tmp = tmp.fille
            res = res + str(tmp.valeur) + "]"
        return res
            
# pour essais      
    
print('---création liste vide----')
lst=Liste()
print(lst)
print('----remplissage à la main---------')
lst.debut=Cellule(1,Cellule(4,Cellule(7,Cellule(2,Cellule(0)))))
print(lst)

Ajouter un élément en fin de liste

Le principe est simple :

• Si la liste est vide on la crée avec la valeur à ajouter.
• Sinon on ajoute l'élément en fin de liste.

class Cellule :
    
    def __init__(self,valeur=None,fille=None) :
        self.valeur = valeur
        self.fille = fille
        
    def __str__(self):
        return str(self.valeur)



class Liste :
    def __init__(self):
        self.debut = None
        
    # liste vide
    def est_vide(self):
        return self.debut == None
    
    # ajouter un élément en fin de liste
    def ajouter(self,el):
        if self.est_vide():
            self.debut = Cellule(el)
        else:
            tmp = self.debut
            while tmp.fille is not None:
                tmp = tmp.fille
            tmp.fille = Cellule(el)

    # affichage de la liste
    def __str__(self):
        if self.est_vide():
            return "liste vide"
        else:
            tmp = self.debut
            res = "["
            while tmp.fille is not None:
                res = res + str(tmp.valeur) + "]->[" # ou mettre ',' pour un affichage classique
                tmp = tmp.fille
            res = res + str(tmp.valeur) + "]"
        return res
            
# pour essais      
    
print('---création liste vide----')
lst2=Liste()
print(lst2)
print('----remplissage---------')
t=(1,4,7,2,0,12)
for el in t:
    lst2.ajouter(el)
print(lst2)

Déterminer la longueur de la liste

Lorsque l'on utilise les listes Python, la fonction len(liste) renvoie la longueur de la liste.

Il s'agit ici de redéfinir pour nos listes la méthode len..

En voici le principe:

def __len__(self):
    si la liste est vide:
        on renvoie 0
    sinon:
        compteur <--1
        tmp <-- le début de la liste (la liste)
        tant que tmp.fille est pas vide:
            compteur <-- compteur+1
            tmp <-- tmp.fille
        on renvoie le compteur

À faire :

Réaliser la méthode len

class Cellule :
    
    def __init__(self,valeur=None,fille=None) :
        self.valeur = valeur
        self.fille = fille
        
    def __str__(self):
        return str(self.valeur)



class Liste :
    def __init__(self):
        self.debut = None
        
    # liste vide
    def est_vide(self):
        return self.debut == None
    
    # ajouter un élément en fin de liste
    def ajouter(self,el):
        if self.est_vide():
            self.debut = Cellule(el)
        else:
            tmp = self.debut
            while tmp.fille is not None:
                tmp = tmp.fille
            tmp.fille = Cellule(el)

            
    #calcul de la longueur de la liste   
    def __len__(self):
        # à faire
        
        
    # affichage de la liste
    def __str__(self):
        if self.est_vide():
            return "liste vide"
        else:
            tmp = self.debut
            res = "["
            while tmp.fille is not None:
                res = res + str(tmp.valeur) + "]->[" # ou mettre ',' pour un affichage classique
                tmp = tmp.fille
            res = res + str(tmp.valeur) + "]"
        return res
            
# pour essais      
    
print('---création liste vide----')
lst2=Liste()
print(lst2)
print("longueur :",len(lst2))
print('----remplissage---------')
t=(1,4,7,2,0,12)
for el in t:
    lst2.ajouter(el)
print(lst2)
print("longueur :",len(lst2))

Accéder à un élément de la liste

Lorsque l'on manipule des listes Python, l'instruction liste[i] donne accès à l'élément d'indice i.

À faire :

Compléter la méthode acces(self,pos) qui prend en paramètre un indice i et qui renvoie l'élément d'indice i de la liste

class Cellule :
    
    def __init__(self,valeur=None,fille=None) :
        self.valeur = valeur
        self.fille = fille
        
    def __str__(self):
        return str(self.valeur)



class Liste :
    def __init__(self):
        self.debut = None
        
    # liste vide
    def est_vide(self):
        return self.debut == None
    
    # ajouter un élément en fin de liste
    def ajouter(self,el):
        if self.est_vide():
            self.debut = Cellule(el)
        else:
            tmp = self.debut
            while tmp.fille is not None:
                tmp = tmp.fille
            tmp.fille = Cellule(el)

            
    #calcul de la longueur de la liste   
    def __len__(self):
        # à compléter avec la question précédente
        
    
    def acces(self,pos):
        if pos < 0 or pos > len(self)-1 :
            return "pas possible"
        else :
            tmp = self.debut
            c = ...
            while c < ... :
                tmp = ....
                c = ....
            return .....

    
    # affichage de la liste
    def __str__(self):
        if self.est_vide():
            return "liste vide"
        else:
            tmp = self.debut
            res = "["
            while tmp.fille is not None:
                res = res + str(tmp.valeur) + "]->[" # ou mettre ',' pour un affichage classique
                tmp = tmp.fille
            res = res + str(tmp.valeur) + "]"
        return res
            
# pour essais      
    
print('---création liste vide----')
lst2=Liste()
print(lst2)
print("longueur :",len(lst2))
print('----remplissage---------')
t=(1,4,7,2,0)
for el in t:
    lst2.ajouter(el)
print(lst2)
print("longueur :",len(lst2))
print("---la méthode acces----")

for i in range(len(lst2)):
    print(lst2.acces(i))
    
print(lst2.acces(7))
print(lst2.acces(-1))

Insérer un élément à l'indice n

Supposons qu'on souhaite dans notre liste insérer un élément après le 4 pour obtenir cette liste : 1,4,12,7,2,0

La méthode consiste à se positionner à l'endroit où l'on souhaite faire l'insertion (sur le 7 dans ce cas) et de la remplacer par une nouvelle cellule dont la valeur est l'élément à inserer et sa fille le reste de la liste.

À faire :

Compléter la méthode inserer(self,el,pos) ci dessous:

class Cellule :
    
    def __init__(self,valeur=None,fille=None) :
        self.valeur = valeur
        self.fille = fille
        
    def __str__(self):
        return str(self.valeur)



class Liste :
    def __init__(self):
        self.debut = None

    #calcul de la longueur de la liste   
    def __len__(self):
        pass
            
    # liste vide
    def est_vide(self):
        return self.debut == None
    
    # affichage de la liste
    def __str__(self):
        if self.est_vide():
            return "liste vide"
        else:
            tmp=self.debut
            res = "["
            while tmp.fille is not None:
                res = res + str(tmp.valeur) + "]->[" # ou mettre ',' pour un affichage classique
                tmp = tmp.fille
            res = res + str(tmp.valeur) + "]"
        return res
    
    # ajouter un élément en fin de liste
    def ajouter(self,el):
        if self.est_vide():
            self.debut = Cellule(el)
        else:
            tmp = self.debut
            while tmp.fille is not None:
                tmp = tmp.fille
            tmp.fille = Cellule(el)
            
    def acces(self,pos):
        pass
        
    # insérer un élément à l'indice n
    def inserer(self,el,pos):
        if pos < 0 or pos > len(self)-1 :
            return .......
        elif pos == 0: # début de liste
            tmp = self.debut
            self.debut = Cellule(...,...)
        else:
            tmp = self.debut
            c = ...
            while c < ....:
                c = ....
                tmp = .....
            tmp.fille = Cellule(...,.....)
# pour essais    
    
print('---création liste vide----')
lst2=Liste()
print(lst2)
print("longueur :",len(lst2))
print('----remplissage---------')
t=(1,4,7,2,0)
for el in t:
    lst2.ajouter(el)
print(lst2)
print("longueur :",len(lst2))
print("---la méthode acces----")

for i in range(len(lst2)):
    print(lst2.acces(i))
    
print(lst2.acces(7))
print(lst2.acces(-1))

print("---la méthode inserer----")
lst2.inserer(12,2)
print(lst2)
lst2.inserer(51,0)
print(lst2)
lst2.inserer(51,-2)
print(lst2)
lst2.inserer(25,6)
print(lst2)
lst2.inserer(8,8)
print(lst2)

D'autres méthodes...

À faire :

Il s'agit ici de réaliser les méthodes : (et de les tester)

• Supprimer et renvoyer le premier élément de la liste
• Supprimer et renvoyer le dernier élément de la liste
• Supprimer un élément d'indice i dans la liste et le renvoyer

# à faire
class Cellule :
    
    def __init__(self,valeur=None,fille=None) :
        self.valeur = valeur
        self.fille = fille
        
    def __str__(self):
        return str(self.valeur)



class Liste :
    def __init__(self):
        self.debut = None

    #calcul de la longueur de la liste   
    def __len__(self):
        pass
            
    # liste vide
    def est_vide(self):
        return self.debut == None
    
    # affichage de la liste
    def __str__(self):
        if self.est_vide():
            return "liste vide"
        else:
            tmp=self.debut
            res = "["
            while tmp.fille is not None:
                res = res + str(tmp.valeur) + "]->[" # ou mettre ',' pour un affichage classique
                tmp = tmp.fille
            res = res + str(tmp.valeur) + "]"
        return res
    
    # ajouter un élément en fin de liste
    def ajouter(self,el):
        if self.est_vide():
            self.debut = Cellule(el)
        else:
            tmp = self.debut
            while tmp.fille is not None:
                tmp = tmp.fille
            tmp.fille = Cellule(el)
           
    def acces(self,pos):
        pass
        
    # insérer un élément à l'indice n
    def inserer(self,el,pos):
        pass
            
    def supp_dernier(self):
        pass
        
    def supp_premier(self):
        pass
        
    def supp_indice(self,pos):
        pass
            
# pour essais      
    
print('---création liste vide----')
lst2=Liste()
print(lst2)
print("longueur :",len(lst2))
print('----remplissage---------')
t=(1,4,7,2,0)
for el in t:
    lst2.ajouter(el)
print(lst2)
print("longueur :",len(lst2))

print("----supprimer dernier----")
p=lst2.supp_dernier()
print(lst2)
print(p)

print("----supprimer premier----")
q=lst2.supp_premier()
print(lst2)
print(q)

print("----supprimer indice----")
lst3=Liste()
t=(1,4,7,2,0)
for el in t:
    lst3.ajouter(el)
print(lst3)
r=lst3.supp_indice(3)
print(lst3)
print(r)
lst3.supp_indice(0)
print(lst3)
lst3.supp_indice(2)
print(lst3)

Des fonctions

À faire:

Écrire des fonctions qui renvoie:

• Le maximum d'une liste passée en paramètre
• Le minimum d'une liste passée en paramètre
• La somme des éléments de la liste
• La moyenne des éléments de la liste

Concaténation de deux listes

Voici une méthode qui réalise la concaténation de deux listes par addition

def __add__(self,other):
        if self.est_vide():
            return other
        elif other.est_vide():
            return self
        else:
            lst_tmp=Liste()
            # ajout de la 1ère liste
            tmp = self.debut
            lst_tmp.ajouter(tmp.valeur)
            while tmp.fille is not None:
                tmp = tmp.fille
                lst_tmp.ajouter(tmp.valeur)
            # ajout de la 2ème liste
            tmp = other.debut
            lst_tmp.ajouter(tmp.valeur)
            while tmp.fille is not None:
                tmp = tmp.fille
                lst_tmp.ajouter(tmp.valeur)
            return lst_tmp

À faire:

Implémenter cette méthode et faire des essais

lst4=Liste()
lst5=Liste()
t4=(5,4,3,0,1,8)
t5=(12,0,54,78,9)

for el in t4:
    lst4.ajouter(el)
print(lst4)
for el in t5:
    lst5.ajouter(el)
print(lst5)
print(lst4+lst5)

lst6=Liste()
print(lst5+lst6)

résultats attendus

[5]->[4]->[3]->[0]->[1]->[8]
[12]->[0]->[54]->[78]->[9]
[5]->[4]->[3]->[0]->[1]->[8]->[12]->[0]->[54]->[78]->[9]
[12]->[0]->[54]->[78]->[9]

# à faire

Le tri rapide (Quick sort)

On considère une liste

Voici un algorithme récursif de tri rapide

fonction tri_rapide(liste):

• Si la liste est de longueur inférieure ou égale à 1
• Alors elle est déjà triée, donc on renvoie la liste
• Sinon
• On choisit comme pivot le premier élément de la liste (ou le dernier ou n'importe lequel), et on le supprime de la liste
• On construit deux listes linf et lsup contenant respectivement les éléments inférieurs ou égaux au pivot et les éléments supérieurs au pivot
• On renvoie : tri_rapide(linf) + [pivot] + tri_rapide(lsup)

À faire :

Réaliser la fonction tri_rapide et la tester

# à faire