Dans une première partie je voudrais créer ses fonctions pour les listes doublement chainée :
Créer la fonction CreerNoeudLDC (val, precedent, suivant) : NoeudLDC
val (entier) : la valeur contenue dans le noeud precedent (NoeudLDC) : le nœud précédent. Vaut None pour un nœud en début de liste. suivant (NoeudLDC) : le nœud suivant. Vaut None pour un nœud en fin de liste
Créer la fonction EstNoeudLDC(n : NoeudLDC) : booleen : qui vérifie que n est bien un nœud de liste doublement chainée, c’est-à-dire que n vaut None ou : n estune liste de 3 éléments n[0] est un entier n[1] et n[2] sont aussi des NoeudLDC (fonction récursive)
Créer les fonctions d’accès aux données,et de modifications de ces données
GetValLDC (n: NoeudLDC) : entier
GetPrecedentLDC (n: NoeudLDC) : NoeudLDC
GetSuivantLDC (n: NoeudLDC) : NoeudLDC
Créez les fonctions suivantes :
LongueurLDC(l) :entier (renvoie la longueur de la liste)
InsererDebutLDC(l,val) : NoeudLDC(insère un nœud au début de la liste)
InsererFinLDC(l,val):NoeudLDC(insèreun nœudàla finde laliste) SupprimerDebutLDC(l) :NoeudLDC(supprime lepremiernœuddela liste) SupprimerFinLDC(l) : NoeudLDC (supprime le dernier nœud de la liste)
AccesLDC(l,p) :NoeudLDC (renvoie le nœud d’indice p dans la liste. Le premier nœud a pour indice 0) InsererPlaceLDC(l,val,p) : NoeudLDC (insère le nœud contenant val justeaprès le nœud d’indice p; le premier nœud a pour indice 0)
SupprimerPlaceLDC(l,p) :NoeudLDC (supprime de l le nœud d’indice p; le premier nœud a pour indice 0)
SupprimerValLDC(l,val) : NoeudLDC (supprime de l le premier nœud contenant val; premier car en effet, rien n’interdit que la liste contienne des doublons)
LDC2List(l) : tableau( renvoie la liste Python (tableau) contenant les éléments de l; renvoie [] si l vaut None )
List2LDC(l):NoeudLDC (renvoie la liste doublement chainée contenant dans le même ordre les éléments de la liste Python (tableau) l; renvoie None s'il vaut [] )
Je souhaiterais ensuite faire un jeux de teste pour tout ça dans un if name == " main ".
Dans une seconde partie, je souhaite créer ses fonctions :
Créer la fonction EstOrdonneeLDC(l) : booleen, qui renvoie True si la liste est croissante (doublons possibles)
Créer la fonction TriLDC(l) : NoeudLDC qui renvoie la liste doublement chainée triée des entiers de la liste doublement chainée l. On utilisera LDC2List, puis la fonction sort de Python, puis List2LDC.
Créer la fonction InsereOrdreLDC(l,val) qui insère val à sa place dans la liste doublement chainée croissante l, de manière que l reste croissante.
et tester avec un jeux de test comme dans la 1er partie.
voici ce que j'ai commencer à faire : <pre class="brush: python;">
def estVide(l):
if
return premier == None
def creerNoeudLDC(val, precedent, suivant):
""" un noeud est une liste Python de trois cases [valeur,noeud présecéent, noeud suivant]
"""
if precedent == None:
return [val, None, None]
if suivant == None:
return [val, precedent, None]
else:
return [val, precedent, suivant]
def EstNoeudLDC(n):
if n == None:
return True
if (isinstance(n[0], int) == True and isinstance(EstNoeudLDC(n[1]), True) == True and isinstance(EstNoeudLDC(n[2]), True) == True):
return True
else :
return False
def GetValLDC(n):
assert(n != None) ## on ne peut pas obtenir la valeur d'une liste vide
return n[0]
def GetSuivantLDC(n):
"""
"""
assert(n != None) ## on ne peut pas obtenir la noeud suivant sur une liste vide
return n[1]
def GetPrecedentLDC(n):
"""
"""
assert(n != None) ## on ne peut pas obtenir la noeud précédent sur une liste vide
return n[2]
def LongueurLDC(l):
lg = 0
n = GetValLDC(0)
while n != None:
lg += 1
n = GetSuivantLDC(l)
return lg
def InsererDebutLDC(l,val):
if l == None:
return creerNoeudLDC(val, None, None)
else:
l[0] = creerNoeudLDC(val, GetSuivantLDC(l[0]), None)
def InsererFinLDC(l,val):
if l == None:
return creerNoeud(val, None, None)
else:
## on parcoure la liste jusqu'à atteindre le dernier noeud
n = l
while GetSuivantLDC(n) != None:
n = GetSuivantLDC(n)
## on met à jour le noeud suivant
GetPrecedentLDC(n)[1] = creerNoeud(val, None, GetPrecedentLDC(n))
n[1] = creerNoeud(val, None, None)
return l
def SupprimerDebutLDC(l):
def SupprimerFinLDC(l):
def AccesLDC(l,p):
def InsererPlaceLDC(l,val,p):
def SupprimerPlaceLDC(l,p):
def SupprimerValLDC(l,val):
def LDC2List(l):
def List2LDC(l):
##if __name__ == '__main__':
## print('Test liste vide :', test_creation_liste())
## print('Test lng vide :', test_longueur_liste_vide())
## print('Test ajout tête :', test_ajout_tete())
## print('Test ajout tête :', test_ajout_tete2())
## print('Test tableau :', test_depuis_tableau())
#### Part 2 #####
def EstOrdonneeLDC(l):
def TriLDC(l):
def InsereOrdreLDC(l,val):
</pre>
Je suis preneur si vous avez des ressources sur le sujet car j’ai trouver beaucoup de Programmation orienté objet mais pas de programmation fonctionnelle ?
Le message qui suit est une réponse automatique activée par un membre de l'équipe. Les réponses automatiques leur permettent d'éviter d'avoir à répéter de nombreuses fois la même chose, ce qui leur fait gagner du temps et leur permet de s'occuper des sujets qui méritent plus d'attention. Nous sommes néanmoins ouverts et si vous avez une question ou une remarque, n'hésitez pas à contacter la personne en question par Message Privé. Pour plus d'informations, nous vous invitons à lire les règles générales du forum
Merci de colorer votre code à l'aide du bouton Code
Les forums d'Openclassrooms disposent d'une fonctionnalité permettant de colorer et mettre en forme les codes source afin de les rendre plus lisibles et faciles à manipuler par les intervenants. Pour cela, il faut utiliser le bouton de l'éditeur, choisir un des langages proposés et coller votre code dans la zone prévue. Si vous utilisez l'éditeur de messages en mode Markdown, il faut utiliser les balises <pre class="brush: python;">Votre code ici</pre>.
Merci de modifier votre message d'origine en fonction.
tJ'ai hésité à te répondre. Ton projet est ambitieux et tes connaissances en Python semblent limitées. On peut l'implanter de plus d'une façon: + chaque instance est une liste de 3 éléments: précédent, suivant, valeur: [precedent, suivant, valeur] + un dictionnaire: {'precedent': None, 'suivant': None, 'valeur': 0} Commence par les fonctions les plus simples, sinon tu perdras trop de temps à vouloir tout faire en même temps. Trier une liste chaînée est compliquée dans n'importe quel langage.
Le Tout est souvent plus grand que la somme de ses parties.
Je me suis amusé à implémenter certaines fonctions. Il m'a semblé plus facile de faire deux classes, une pour les noeuds, une pour la liste proprement dite. Cette façon de faire est beaucoup plus facile que mon idée des listes ou des dictionnaires. Pour l'instant, toutes les méthodes sont dans la classe des listes. Mais il pourrait y en avoir dans la classe des noeuds. L'utilisateur pourra jouer plus facilement avec les concepts associés aux listses doublement chaînées. Il pourra accéder directement aux objets se trouvant dans ces classes, mais ce n'est pas forcément souhaitable. Je n'ai pas accès au bouton code </>. On peut retrouver l'indentation en faisant un copier-coller du code. - class nodeLDC: def __init__(self, valeur=0): self.precedent = None self.suivant = None self.valeur = valeur
def listerLDC(self, reverse=False): if not reverse: node = self.premier while node is not None: yield node.valeur node = node.suivant else: node = self.dernier while node is not None: yield node.valeur node = node.precedent
def supprimeDebutLDC(self): if self.premier is None: return node = self.premier if self.nombre == 1: self.premier = self.dernier = None else: node.suivant.precedent = None self.premier = node.suivant del(node) self.nombre -= 1
def supprimeFinLDC(self): if self.dernier is None: return node = self.dernier if self.nombre == 1: self.premier = self.dernier = None else: node.precedent.suivant = None self.dernier = node.precedent del(node) self.nombre -= 1
def reverseLDC(self): self.premier, self.dernier = self.dernier, self.premier node = self.dernier while node is not None: node.precedent, node.suivant = node.suivant, node.precedent node = node.precedent
liste=listLDC() liste.ajouteDebutLDC(1) liste.ajouteDebutLDC(0) liste.ajouteFinLDC(2) liste.supprimeDebutLDC() liste.supprimeFinLDC() for i in range(2,6): liste.ajouteFinLDC(i) liste.reverseLDC() for i in liste.listerLDC(reverse=True): print(i)
Le Tout est souvent plus grand que la somme de ses parties.
c'est en effet ce que je cherche à faire mais sans les classes, en effet passer par des classes est bien plus simple...
Mon plus gros problème de compréhension vient du fait que je ne sais pas récupérer d'adresse en case mémoire de la valeur pour la mettre dans suivant ou précédent...
Je vais continuer à chercher et je vous tiens au courant. Lesnox
Je reviens avec mon idée de dictionnaire. Ce qui te manque, c'est une "adresse". Puisqu'ici on ne joue pas avec de "vraies" adresses, je pense au truc suivant: Chaque noeud de la liste sera une entrée dans un dictionnaire. listeChainee = {adresse1: [lien_gauche1, valeur1, lien_droit1], adresse2: [lien_gauche2, valeur2, lien_droit2], ...} Quand on crée un noeud, les liens gauche et droit valent None. Après ils peuvent être modifiés selon le chaînage. Au départ, ton descripteur de liste est une liste: descripteurListe = [lien_premier, lien_dernier, nombre_d_elements, adresse_disponible] soit: descripteurListe = [None, None, 0, 0] Chaque fois que tu crées un nouveau noeud, tu vas chercher le nombre courant dans le champs "adresse_disponible" et tu l'incrémentes dans ce champs. Tu crées une entrée dans le dictionnaire avec l'adresse obtenue comme clé et les valeurs requises dans la liste associée. Les liens gauche ou droit seront les clés des noeuds adjacents. Le chaînage est moins évident: listeChainee[precedent][-1]=courant listeChainee[courant][0]=precedent À la rigueur, on pourrait remplacer la liste par un sous-dictionnaire ... listeChainee = {adresse1: {'precedent': None, 'suivant': None, 'valeur': 0}, adresse2: {...}, ...} listeChainee[precedent]['suivant']=courant listeChainee[courant]['precedent']=precedent Le descripteur de liste pourrait être un dictionnaire si tu ne veut pas t'encombrer avec des indices: descripteurListe = {'premier': None, 'dernier': None, 'nombre': 0, 'adresse': 0} adresse = descripteurListe['adresse'] descripteurListe['adresse'] += 1 Je ne sais pas si j'ai été assez clair.
Le Tout est souvent plus grand que la somme de ses parties.
voilà où j’en suis, j’ai un soucis avec deux fonction, la fonction SupprimerPlaceLDC(l,p), je ne n’arrive pas à comprendre comment supprimer le nœud quand il est au milieu de la liste.
De même pour la fonction SupprimerValLDC(l,val), si l’utilisateur rentre une valeur qui n’est pas dasn la liste je vais sortir avec un assert mais pas le bon et je voudrait d’abord vérifier que la valeur val est bien dans la liste doublement chainée.
Merci d’avance de votre aide. Lesnox
###################################
##### Implémentation des LDC#######
###################################
def creerListeVide():
"""
"""
## la liste vide vaut None
return None
def setPrecedent (n, ns):
"""
"""
n[1] = ns
def setSuivant (n, ns):
"""
"""
n[2] = ns
def creerNoeudLDC(val, precedent, suivant):
""" un noeud est une liste Python de trois cases [valeur,noeud présecéent, noeud suivant]
"""
if precedent == None and suivant != None:
return [val, None, suivant]
if precedent != None and suivant == None:
return [val, precedent, None]
if precedent != None and suivant != None:
return [val, precedent, suivant]
else :
return [val, None, None]
def EstNoeudLDC(n):
"""
"""
if n == None:
return True
if (isinstance(n[0], int) == True and isinstance(EstNoeudLDC(n[1]), True) == True and isinstance(EstNoeudLDC(n[2]), True) == True):
return True
else :
return False
def GetValLDC(n):
"""
"""
assert(n != None) ## on ne peut pas obtenir la valeur d'une liste vide
return n[0]
def GetSuivantLDC(n):
"""
"""
assert(n != None) ## on ne peut pas obtenir la noeud suivant sur une liste vide
return n[2]
def GetPrecedentLDC(n):
"""
"""
assert(n != None) ## on ne peut pas obtenir la noeud précédent sur une liste vide
return n[1]
def LongueurLDC(l):
"""
"""
lg = 0
n = l
if l == None :
return lg
else :
lg = 1
while n[2] != None:
lg += 1
n = GetSuivantLDC(n)
return lg
def InsererDebutLDC(l,val):
"""
"""
if l == None:
return creerNoeudLDC(val, None, None)
else:
n = l
while GetPrecedentLDC(n) != None :
n = GetPrecedentLDC(n)
nn = creerNoeudLDC(val, None, n) # l pointe vers le 1er et non vers la tête de la LDC ?
setPrecedent (n,nn)
return nn
def InsererFinLDC(l,val):
"""
"""
if l == None:
return creerNoeudLDC(val, None, None)
else:
## on parcoure la liste jusqu'à atteindre le dernier noeud
n = l
while GetSuivantLDC(n) != None:
n = GetSuivantLDC(n)
## on met à jour le noeud suivant
n[2] = creerNoeudLDC(val, n, None)
m = GetSuivantLDC(l)
p = GetPrecedentLDC(l)
if p != None :
setPrecedent (n, m)
return l
def SupprimerDebutLDC(l):
"""
"""
assert(l != None) ## on ne peut pas supprimer un noeud dans une liste vide
n = l
print ("la liste n est : ", n)
n = GetSuivantLDC(n)
n[1] = None
return n
def SupprimerFinLDC(l):
"""
"""
assert(l != None) ## on ne peut pas supprimer un noeud dans une liste vide
n = l
while GetSuivantLDC(n) != None:
n = GetSuivantLDC(n)
setSuivant (GetPrecedentLDC(n), None)
setPrecedent (n, None)
return l
def AccesLDC(l,p):
"""
"""
assert(l != None) ## on ne peut pas accéder à un noeud dans une liste vide
assert p <= LongueurLDC(l) ##L'indice auqu'elle vous souhaitez accéder est trop grand par rapport à la liste
j = 0
m = l
while j < p:
j +=1
m = GetSuivantLDC(m)
return [m[0],m[1],m[2]]
def InsererPlaceLDC(l,val,p):
"""
"""
assert p <= LongueurLDC(l) ##L'indice donnée pour placer la valeur est trop grand par rapport à la liste
if l == None:
return creerNoeudLDC(val, None, None)
elif p == 0 :
InsererDebutLDC(l,val)
elif p == LongueurLDC(l) :
InsererFinLDC(l,val)
else:
j = 0
m = l
while j < p:
j +=1
m = GetSuivantLDC(m)
n = GetPrecedentLDC(m)
nn = creerNoeudLDC(val, m[1], m)
m[1] = nn
n[2] = m[1]
return l
def SupprimerPlaceLDC(l,p):
"""
"""
assert(l != None) ## on ne peut pas supprimer à un noeud dans une liste vide
assert p <= (LongueurLDC(l)-1) ##L'indice auqu'elle vous souhaitez supprimer la valeur est trop grand par rapport à la liste
m = l
if p == 0 :
m = SupprimerDebutLDC(l)
elif p == LongueurLDC(l)-1 :
m = SupprimerFinLDC(l)
else:
j = 0
while j < p:
j +=1
m = GetSuivantLDC(m)
n = GetPrecedentLDC(m)
print ("j vaut : ", j)
print("n est : ",m)
print("m est : ",GetPrecedentLDC(m))
setPrecedent(GetPrecedentLDC(m),GetSuivantLDC(m))
print("m''' est : ",m)
m[1] = None
m[2] = None
print("l'' vaut : ",m)
return m
##
##def SupprimerValLDC(l,val):
## """
## """
## assert(l != None) ## on ne peut pas supprimer à un noeud dans une liste vide
## n = l
## j = 0
## print(n)
## for i in range (LongueurLDC(l)):
## print(n)
## GetValLDC(n) == val :
## SupprimerPlaceLDC(l,i)
## else :
## assert(i == LongueurLDC(l)) ## La valeur que l'on souhaite supprimer ne ce trouve pas dans la liste.
## return l
def SupprimerValLDC(l,val):
assert(l != None) ## on ne peut pas supprimer à un noeud dans une liste vide
n = l
j = 0
print("la longeur de la lsite est : ", LongueurLDC(l))
while GetValLDC(n) != val:
n = GetSuivantLDC(n)
j +=1
print ("j vaut : ",j)
print("j vaut : ",j)
n = SupprimerPlaceLDC(l,j)
print("n' est : ", n)
return n
def LDC2List(l):
long = LongueurLDC(l)
n = l
j = 0
List = []
while j <= long :
List.append(GetValLDC(n))
n = GetSuivantLDC(n)
j += 1
return List
def List2LDC(l):
if l != None :
list = None
for i in range (len(l)) :
list = InsererFinLDC(list,l[i])
elif l == None :
return None
return list
l = creerListeVide()
l = InsererDebutLDC(l,28)
l = InsererDebutLDC(l,16)
l = InsererDebutLDC(l,23)
l = InsererFinLDC(l,100)
l = InsererPlaceLDC(l,44,2)
print(l)
l = SupprimerValLDC(l,44)
print(l)
Dans la fonction supprimerPlaceLDC: Si j'ai bien compris ton code, m est le noeud courant à être supprimé et n est le noeud précédent. Tu dois faire dans l'ordre l'équivalent de: n.suivant = m.suivant m.suivant.precedent = n del(m) Dans la fonction supprimerValLDC: while GetValLDC(n) != val: n = GetSuivantLDC(n) C'est ici que tu dois faire un assert(n != None) # valeur pas trouvée dans la liste
Le Tout est souvent plus grand que la somme de ses parties.
alors les soucis d'hier sont résolue, je passe maintenant a des test sur les fonction, voici la ou je bloque :
def test_List_To_LDC():
"""
Test de la conversion de la List en LDC
:return : bool : True le test est correct
"""
ma_liste = creerListeVide()
ma_liste = InsererDebutLDC(ma_liste, 32)
ma_liste = InsererDebutLDC(ma_liste, 14)
ma_liste = InsererDebutLDC(ma_liste, 66)
ma_liste = InsererDebutLDC(ma_liste, 33)
ma_liste_test = [33, 66, 14, 32]
ma_liste_test = List2LDC(ma_liste_test)
print("Ma liste : ", ma_liste)
print("Ma liste test : ", ma_liste_test) # La liste est [33, 66, 14, 32] ici on souhiate supprimer 14
assert LongueurLDC(ma_liste_test) == LongueurLDC(ma_liste)
for i in range (LongueurLDC(ma_liste_test)):
assert AccesLDC(ma_liste_test,i) == AccesLDC(ma_liste,i)
return True
et voilà l’erreur que j'ai :
Traceback (most recent call last):
File "C:\Users\Julie\Downloads\Projet david bloc 3\Fonction_LDC.py", line 485, in <module>
print('Test conversion en LDC :', test_List_To_LDC())
File "C:\Users\Julie\Downloads\Projet david bloc 3\Fonction_LDC.py", line 467, in test_List_To_LDC
assert AccesLDC(ma_liste_test,i) == AccesLDC(ma_liste,i)
RecursionError: maximum recursion depth exceeded in comparison
Je bloque aussi le le test de cette fonction : AccesLDC(l,p).
Dans la fonction InsererDebutLDC, si la liste existe, tu ne retourne rien. Pour convertir une liste (ordinaire) en liste chaînée, je ferais comme suit: for val in listeOrdinaire: InsererDebutLDC(maListeLDc, val) Ta liste chaînée est à l'envers par rapport à la liste initiale. Sinon, il faudra utiliser InsererFinLDC
Le Tout est souvent plus grand que la somme de ses parties.
Liste doublement chainée
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.