Listes chaînées¶

Dans ce TP on reprend les exercices du TD 8 sur les listes chaînées.

Dans tous ces exercices, sauf indication contraire, toutes les méthodes sont à écrire dans la classe ListeChainee, dans la cellule ci-dessous. Après avoir implémenté chaque méthode, vous ajouterez les tests correspondants sous le texte de l'exercice, sans oublier de recharger à chaque fois la nouvelle version de vos classes.

Listes chaînées simples¶

class Maillon:
    
    def __init__(self, elem, suivant=None): ## Complexité : 
        self.elem = elem
        self.suivant = suivant

class ListeChainee:
    
    def __init__(self):
        self.premier = None
        self.dernier = None

    def __len__(self):
        courant = self.premier
        cpt = 0
        while courant is not None:
            courant = courant.suivant
            cpt += 1
        return cpt
    
    def __str__(self):
        res = "["
        courant = self.premier
        if courant is not None:
            res += str(courant.elem)
            courant = courant.suivant
        while courant is not None:
            res += ", " + str(courant.elem)
            courant = courant.suivant
        res += "]"
        return res
    
    def compte(self, elem):       
        courant = self.premier
        cpt = 0
        while courant is not None:
            if courant.elem == elem :
                cpt += 1
            courant = courant.suivant
        return cpt
    
    def cherche(self,elem):
        courant = self.premier
        cpt = 0
        while courant is not None :
            if courant.elem == elem :
                return cpt
            cpt += 1
            courant = courant.suivant
        return None
            
    def inserePremier(self, elem):
        self.premier = Maillon(elem, self.premier)
        
    def insereFin(self, elem):
        if self.premier is None:
            self.premier = Maillon(elem)
        else:
            courant = self.premier
            while courant.suivant is not None:
                courant = courant.suivant
            courant.suivant = Maillon(elem)
        
    def extraitPremier(self):
        res = self.premier.elem
        self.premier = self.premier.suivant
        return res

    def extraitFin(self):
        if self.premier.suivant is None:
            res = self.premier.elem
            self.premier = None
            return res
        else:
            courant = self.premier
            while courant.suivant.suivant is not None:
                courant = courant.suivant
            res = courant.suivant.elem
            courant.suivant = None
            return res
    
    def valeurNieme(self, n):
        courant = self.premier
        if courant is None :
            return None
        else :
            cpt = 0
            while cpt < n :
                cpt += 1
                courant = courant.suivant
            courant.elem = elem
        
    def fixeNieme(self,n,elem):
        if self.premier is None :
            self.premier = Maillon(elem)
        else :
            courant = self.premier
            cpt = 0
            while cpt < n :
                cpt += 1
                courant = courant.suivant
            courant.elem = elem
                
    def insereNieme(self,n,elem):
        if self.premier is None :
            self.premier = Maillon(elem)
        else :
            courant = self.premier
            cpt = 0
            while cpt < n :
                cpt += 1
                courant = courant.suivant
    
    def extraitNieme(self,n):
        if self.premier.suivant is None:
            res = self.premier.elem
            self.premier = None
            return res
        else:
            courant = self.premier
            cpt = 0
            while courant is not None:
                cpt += 1
    
    def etend(self,autre):
        pass
        
    def supprimeRepetitions(self):
        courant = self.premier
        while courant is not None :
            if courant == courant.suivant :
                courant = None
            courant = courant.suivant
    
    def estTriee(self):
        courant = self.premier
    
    def renverseIter(self):
        pass
    
    def renverseRec(self):
        pass

lst.inserePremier(2)

str(lst)

None

'[2]'

Pour chacune des questions suivantes, indiquez la complexité (au pire et au mieux, en temps et en espace) des méthodes que vous écrirez.

Écrivez une méthode compte(self, elem) qui renvoie le nombre d'occurrences de elem dans la liste.
Écrivez une méthode cherche(self, elem) qui renvoie la position de la première occurrence de elem dans la liste (en comptant à partir de 0), ou None s'il n'est pas dans la liste.
Écrivez les méthodes inserePremier(self, elem) qui ajoute l'élément elem en tête de la liste self, et extraitPremier(self) qui supprime l'élément de tête de la liste et renvoie sa valeur.
Écrivez deux méthodes valeurNieme(self, n), qui renvoie la valeur du n-ème élément de la liste (en commençant à compter à 0), sans la retirer de la liste, et fixeNieme(self, n, elem) qui modifie sa valeur. Dans les deux cas, la fonction peut provoquer une erreur si n n'est pas un indice correct.
Écrivez les méthodes insereFin(self, elem) et extraitFin(self) analogues aux méthodes d'insertion et d'extraction en tête de liste.
Écrivez une méthode insereNieme(self, n, elem) qui insère l'élément elem en nème position dans la liste et extraitNieme(self, n) qui supprime l'élément en n-ème position dans la liste et renvoie sa valeur (en commençant à compter à 0). Dans les deux cas, la fonction peut provoquer une erreur si n n'est pas un indice correct.
Écrivez une méthode etend(self, autre) qui étend la liste self par la liste autre, à la manière de la méthode Python extend (c'est à dire en rajoutant une copie entière de la liste autre à la fin de self).
Écrivez une méthode supprimeRepetitions(self) qui supprime les éléments en double consécutifs d'une liste.
Écrivez une méthode estTriee(self) qui renvoie True si la liste est triée dans l'ordre croissant, False sinon.
Écrivez une méthode itérative renverseIter(self) qui renverse la liste self.
$\bigstar$ Écrivez une méthode récursive renverseRec(self) qui renverse la liste self. Cette méthode devrait être de complexité linéaire.

# Écrivez les méthodes demandées dans la classe ListeChainee 
# en haut de cette feuille, et vos tests dans cette cellule
# 
def egaliteListeChaineeListe(lstChainee, lst):
    # test l'égalité des éléments d'une liste chainée et d'une liste
    pass



ma_chaine = ListeChainee()  
for i in range(5):
    ma_chaine.inserePremier(i)  
    ma_chaine.insereFin(i)  

assert(ma_chaine.compte(2)==2)
assert(ma_chaine.cherche(1)==3)
assert(ma_chaine.valeurNieme(1)==3)

ma_chaine.fixeNieme(3,6)
assert(ma_chaine.valeurNieme(3)==6)

ma_chaine.insereNieme(4,11)
assert(ma_chaine.valeurNieme(3)==6)
assert(ma_chaine.valeurNieme(4)==11)
assert(ma_chaine.valeurNieme(5)==0)

ma_chaine.extraitNieme(2)
assert(ma_chaine.valeurNieme(1)==3)
assert(ma_chaine.valeurNieme(2)==6)
assert(ma_chaine.valeurNieme(3)==11)

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-9-652aaeffa122> in <module>()
     11 for i in range(5):
     12     ma_chaine.inserePremier(i)
---> 13     ma_chaine.insereFin(i)
     14 
     15 assert(ma_chaine.compte(2)==2)

AttributeError: 'ListeChainee' object has no attribute 'insereFin'

Ajout d'attributs¶

Dans cet exercice, nous allons étudier des variantes de la classe ListeChainee et leurs conséquences sur la complexité de certaines opérations. Pour chaque question, décrivez les méthodes qu'il est souhaitable de modifier et comment les modifier, et quel impact cela aura sur la complexité (en temps et en espace) de ces méthodes.

Ajoutez aux instances de la classe ListeChainee un attribut self.longueur.
Ajoutez un attribut dernier désignant le dernier Maillon d'une liste chaînée.
Ajoutez à chaque Maillon un attribut precedent désignant le maillon précédent dans la liste, s'il existe.

# Pour cet exercice, vous pouvez soit faire les modifications
# directement dans la classe ListeChainee ci-dessus, soit créer 
# des variantes distinctes.
...

Tri par insertion de listes chaînées¶

Écrivez la méthode insereTrie(self, elem) qui insère l'élément elem à la première position respectant l'ordre croissant des éléments de la liste (c'est-à-dire juste après un élément strictement inférieur et juste avant un élément supérieur ou égal).
Écrivez la méthode triInsertion(self) qui trie la liste par insertions successives, à l'aide de la méthode insereTrie précédente, et renvoie une ListeTriee. Précisez sa complexité.
Précisez la complexité de ce tri (en comptant séparément le nombre de comparaisons et le nombre d'affectations) et comparez au cas des listes Python.

# Écrivez les méthodes demandées dans la classe ListeChainee 
# en haut de cette feuille, et vos tests dans cette cellule
...

Tri par fusion de listes chaînées¶

Écrivez la méthode separePairsImpairs(self) qui renvoie deux instances de ListeChainee contenant respectivement les éléments de rang pair et de rang impair de self. Autrement dit, cette méthode renverra deux listes, l'une contenant les éléments de rang 0, 2, 4 etc. de self, et l'autre les éléments de rang 1, 3, 5, etc. Précisez sa complexité.
Écrivez la méthode fusionTriee(self, other) qui renvoie une liste triée contenant les éléments des deux listes triées self et other.
Écrivez la méthode triFusion(self) qui trie la liste self par l'algorithme de tri par fusion à l'aide des deux méthodes précédentes (on peut choisir d'utiliser la méthode separeDebutFin(self) à la place de la méthode separePairsImpairs(self)).
Précisez la complexité de ce tri (en comptant séparément nombre de comparaisons et nombre d'affectations) et comparez au cas des listes Python.

# Écrivez les méthodes demandées dans la classe ListeChainee 
# en haut de cette feuille, et vos tests dans cette cellule
...

Mélange de cartes¶

Écrivez la méthode separeDebutFin(self) qui renvoie deux instances de ListeChainee contenant respectivement la première et la seconde moitié des éléments de self (à un élément près).
Écrivez la méthode fusionAlternee(self, other) qui rassemble deux listes en une seule, en alternant les cartes de la liste self et de la liste other. Si l'une des deux listes est épuisée, on peut simplement rajouter en fin de résultat les cartes restantes de l'autre.
Écrivez la méthode battre(self, n) qui "bat" la liste comme un paquet de cartes, en utilisant les deux méthodes précédentes n fois.

# Écrivez les méthodes demandées dans la classe ListeChainee 
# en haut de cette feuille, et vos tests dans cette cellule
...

Opérations ensemblistes¶

On travaille dans cet exercice uniquement sur des listes triées.

Écrivez les méthodes union(self, other), intersection(self, other) et difference(self, other), qui renvoient respectivement la liste des éléments apparaissant dans l'une ou l'autre des listes self et other, ou dans les deux listes, ou dans self mais pas dans other. Ces méthodes peuvent servir de base à la manipulation d'ensembles.

Note : ce n'est pas implémenté comme ça en Python !

# Écrivez les méthodes demandées dans la classe ListeChainee 
# en haut de cette feuille, et vos tests dans cette cellule
...