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.
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)
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)
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.
...
É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
...
É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
...
É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
...
On travaille dans cet exercice uniquement sur des listes triées.
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
...