Les listes doublement chaînée

a marqué ce sujet comme résolu.

Bonjour à tous,

Je doit implémenter dans python les listes doublement chaînée avec une programmation fonctionnelle. Voilà ce que j’ai commencé à faire 

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):

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 ?

Merci d’avances. Lesnox

+0 -0

Bonjour à tous,

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 
o val (entier) : la valeur contenue dans le noeud
o   precedent (NoeudLDC) : le nœud précédent. Vaut None pour un nœud en début de liste
o   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 :
o   n est une liste de 3 éléments (la fonction native isinstance sera utile)
o   n[0] est un entier
o   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
o   GetValLDC(n : NoeudLDC) : entier
o   GetPrecedentLDC(n : NoeudLDC) : NoeudLDC
o   GetSuivantLDC(n : NoeudLDC) : NoeudLDC

•   Créez les fonctions suivantes :
o   LongueurLDC(l) : entier (renvoie la longueur de la liste)
o   InsererDebutLDC(l,val) : NoeudLDC (insère un nœud au début de la liste)
o   InsererFinLDC(l,val) : NoeudLDC (insère un nœud à la fin de la liste)
o   SupprimerDebutLDC(l) : NoeudLDC (supprime le premier nœud de la liste)
o   SupprimerFinLDC(l) : NoeudLDC (supprime le dernier nœud de la liste)
o   AccesLDC(l,p) : NoeudLDC (renvoie le nœud d’indice p dans la liste. Le premier nœud a pour indice 0)
o   InsererPlaceLDC(l,val,p) : NoeudLDC (insère le nœud contenant val
juste après le nœud d’indice p ; le premier nœud a pour indice 0)
o   SupprimerPlaceLDC(l,p) : NoeudLDC (supprime de l le nœud d’indice p ; le premier nœud a pour indice 0)
o   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)
o   LDC2List(l) : tableau (renvoie la liste Python (tableau) contenant les éléments de l ; renvoie [] si l vaut None)
o   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 si l 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.

+0 -0

J’aimerais savoir si une personne a déjà fait ceci car je trouve uniquement des exemples avec de la POO.

Je souhaiterais comprendre comment faire en ayant un exemple ;)

lesnox

Oui à titre d’exercice, mais je comprends pas trop quelles sont tes questions.

+1 -0

Comment faire quoi plus précisément ? Les fonctions manquantes ?

Je pense que tu pourrais déjà retravailler et simplifier ton code existant :

  • les == True dans les conditions sont inutiles, une expression booléenne s’évalue déjà à True ou False
  • pour comparer un objet avec None on utilisera l’opérateur is (test d’identité) plutôt que == (test d’égalité)
  • ta fonction creerNoeudLDC peut être grandement simplifiée puisque tout ce qu’elle fait se résumé en return [val, precedent, suivant]. Par contre ne devrait-elle pas s’occuper aussi de créer les liaisons avec les nœuds voisins ?
+1 -0

Dans ton 1er message tu parles de programmation fonctionnelle tu ne confondrais pas pas avec programmation à l’aide de fonctions ?

Ton code actuellement n’utlise pas vraiment les principes de la programmation fonctionelle, et si python donne accès a certains element de programmation fonctionnelle, ce n’est pas un language prévu pour cet usage.

Dans le 2eme message avec la liste des fonctions à creer :

La description de ce qui est retouné par CreerNoeudLDC, correspond déja la definition d’un objet.

• Créer la fonction CreerNoeudLDC(val,precedent,suivant) : NoeudLDC o val (entier) : la valeur contenue dans le noeud o precedent (NoeudLDC) : le nœud précédent. Vaut None pour un nœud en début de liste o suivant (NoeudLDC) : le nœud suivant. Vaut None pour un nœud en fin de liste

De plsu , la spec de la fonction `EstNoeudLDC' est :

• 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 : o n est une liste de 3 éléments (la fonction native isinstance sera utile)

La définition de la fonction et l’utlisation de isinstance pour verifier que tu as un bien un noeud en argument laisse à penser que les noeuds sont des objets, je pense que tu devrais creer une classe NoeudLDC avec uniquement 3 proprietés : val, precedent et suivant, cette classe aura uniquement la méthode __init__.

Ensuite tu codes des fonctions "normales" qui travaillent sur des objet NoeudLDC

Nota: le code que tu as soumis ne fait rien d’autres que définir des fonctions, as tu essayé de créer une liste chainée ? quels ont les résultats ?

+1 -0

Bonjour @kayou,

voici le code que j’ai mis en place pour les listes chaînée : 

def creerNoeud(val,suivant):
  ## un noeud est une liste Python de deux cases [valeur,noueud suivant] """
  return [val,suivant]

def creerListeVide():
  ## la liste vide vaut None 
  return None

def tete(l):
  assert(l != None) ## on ne peut pas obtenir la tete d'une liste videe
  return l[0]

def suivant(l):
  assert(l != None) ## on ne peut pas obtenir la noeud suivant sur une liste vide
  return l[1]
  
def setSuivant(n,ns):
    n[1] = ns
  
def ajouterDebut(l,val):
  if l == None:
    return creerNoeud(val,None)
  else:
    return creerNoeud(val,l)


def ajouterFin(l,val):
  if l == None:
    return creerNoeud(val,None)
  else:
    ## on parcoure la liste jusqu'à atteindre le dernier noeud
    n = l
    while suivant(n) != None:
      n = suivant(n)
    ## on met à jour le noeud suivant
    n[1] = creerNoeud(val,None)
    return l
 
def longueur(l):
    lg = 0
    n = l
    while n != None:
        lg += 1
        n = suivant(n)
    return lg
    

def ajouterPlace(l,val,x):
    ## attention, il faut vérifier que x est cohérent par
    ## rapport à la liste
    assert(x>=0)
    assert(x<longueur(l) or (x==0 and longueur(l)==0 ))
    
    if l == None:
        ## normalement, suite au assert, x vaut 0
        return creerNoeud(val,None)
    else:
        xcourant = x
        n = l ## n pointeur sur la même adresse que l
        while xcourant != 0:
            setSuivant(n,suivant(n))
            xcourant = xcourant - 1
        nn = creerNoeud(val,suivant(n)) ## 1 (creation nn), #2 branchment de nn sur le suivant de n
        setSuivant(n,nn) ## 3
    return l   ## l'adresse de l n'a pas bougé

l = creerListeVide()

l = ajouterDebut(l,28)
l = ajouterDebut(l,16)
l = ajouterDebut(l,23)
l = ajouterFin(l,100)
l = ajouterPlace(l,67,2)

print(longueur(l))

print(l[1][1][0])
print(id(l[1]))

En effet ce que je rechercher c’est à programmer par à l’aide de fonction mais sans passer par le type class. (j’ai trouver pleins d’exemple sur internet mais je souhaiterais faire sans.

+0 -0

Comment faire quoi plus précisément ? Les fonctions manquantes ?

Je pense que tu pourrais déjà retravailler et simplifier ton code existant :

  • les == True dans les conditions sont inutiles, une expression booléenne s’évalue déjà à True ou False
  • pour comparer un objet avec None on utilisera l’opérateur is (test d’identité) plutôt que == (test d’égalité)
  • ta fonction creerNoeudLDC peut être grandement simplifiée puisque tout ce qu’elle fait se résumé en return [val, precedent, suivant]. Par contre ne devrait-elle pas s’occuper aussi de créer les liaisons avec les nœuds voisins ?
entwanne

Bonjour @entwanne,

En effet si mais c’est la que j’ai un soucis de compréhension sur comment faire cette liaisons ?

Merci. Lesnox Lesnox

+0 -0

Pour créer la liaison il faut identifier le nœud précédent : normalement tu le connais puisque tu as une liste double chaînée et que tu sais où tu insères ton maillon.

Donc tu peux faire pointer la liaison next du maillon précédent sur le nouveau maillon, et la liaison prev sur maillon suivant sur le nouveau maillon aussi. Puis bien sûr faire pointer les liaisons prev et next de ce nouveau maillon vers les deux autres.

Essaie de prendre un papier et de faire des schémas, ça peut beaucoup aider.

+1 -0

Bonjour à tous,

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)
+0 -0

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.

lesnox

Déjà je ne pense pas qu’il soit utile de calculer la taille de la liste, ça te fait parcourir entièrement al liste pour rien (la taille dans ton cas n’étant pas une donnée connue mais demandant à être calculée).

Ensuite, le principe de la suppression d’un élément, c’est de localiser l’élément qui le précède et celui qui le suit pour les lier entre-eux, faisant ainsi sauter ton maillon. Il faut donc faire la liaison dans les deux sens.

Aussi, là tu calcules un maillon n à chaque tour de boucle que tu n’utilises pas. Et qui correspond juste à la précédente valeur de m. C’est noms ne sont d’ailleurs pas très explicites et nuisent à la lisibilité de ton code.

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.

lesnox

C’est exactement le même principe que SupprimerPlaceLDC sauf que tu ne repères pas un élément par rapport à sa position mais par sa valeur. Il te faut donc parcourir tous les éléments de ta liste et t’arrêter quand tu trouves la bonne valeur.

Si tu as parcouru tous les éléments sans trouver la valeur, alors elle n’est pas dans la liste. Le problème est que la condition de fin de ta boucle n’est pas bonne puisqu’elle ne t’empêche pas d’aller au-delà de la liste.

+0 -0

Bonjour entwanne,

finalement j’ai bien réussit hier à corriger les soucis, voici le nouveau code : 

###################################
##### Implémentation des LDC#######
###################################


def creerListeVide():
  """
    Crée une liste vide
    :paramètre : None 
    :return : None
  """
  ## la liste vide vaut None 
  return None

def setPrecedent (n, ns):
  """
    Mets la liste doublement chainée précendente du noeud dans le noeuds n 
    :paramètre : n : un noeud 
                 ns : liste doucblement chainée 
    :return : None 
  """
  n[1] = ns

def setSuivant (n, ns):
  """
    Mets la liste doublement chainée suivante du noeud dans le noeuds n
    :paramètre : n : un noeud
                 ns : liste doucblement chainée suivante
    :return : None
  """
  n[2] = ns  

def creerNoeudLDC(val, precedent, suivant):
  """
    Crée un noeud (une liste Python de trois cases) [valeur, noeud présecéent, noeud suivant]
    :paramètre : val : valeur du noeud
                  precedent : contient les noeuds précédent le noeud courant, None si pas de noeud précédent
                  suivant : contient les noeuds suivant le noeud courant, None si pas de noeud suivant
    :return : noeud sous la forme [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_Precedent(n):
  """
  """
  pass
  assert (n == None) or (isinstance(n, list) and len(n) == 3  and EstNoeudLDC_Precedent(n[1])) ## Devrait être None ou une liste de 3 éléments [entier, noeudLDC ou None, noeudLDC ou None]
  return True

def EstNoeudLDC_Suivant(n):
  """
  """
  pass
  assert (n == None) or (isinstance(n,list) and len(n)==3  and EstNoeudLDC_Suivant(n[2])) ## Devrait être None ou une liste de 3 éléments [entier, noeudLDC ou None, noeudLDC ou None]
  return True

def EstNoeudLDC(n):
  """
  """
  pass
  assert (n == None) or (EstNoeudLDC_Precedent(n) and EstNoeudLDC_Suivant(n)) ## Devrait être None ou une liste de 3 éléments [entier, noeudLDC ou None, noeudLDC ou None]
  return True



def GetValLDC(n):
  """
     Permet d'obtenir la valeur du noeud
    :paramètre : n : un noeud
    :return : la valeur du noeud
  """
  assert(n != None) ## on ne peut pas obtenir la valeur d'une liste vide
  assert (EstNoeudLDC(n)) ## Doit être un noeud
  return n[0]

def GetSuivantLDC(n):
  """
     Permet d'obtenir la liste des noeuds suivant
    :paramètre : n : un noeud
    :return : la liste des noeuds suivant
  """
  assert(n != None) ## on ne peut pas obtenir la noeud suivant sur une liste vide
  assert (EstNoeudLDC(n)) ## Doit être un noeud
  return n[2]

def GetPrecedentLDC(n):
  """
     Permet d'obtenir la liste des noeuds précédent
    :paramètre : n : un noeud
    :return : la liste des noeuds précédent
  """
  assert(n != None) ## on ne peut pas obtenir la noeud précédent sur une liste vide
  assert (EstNoeudLDC(n)) ## Doit être un noeud
  return n[1]

def LongueurLDC(l):
  """
     Permet d'obtenir la longeur de la liste doublement chainée
    :paramètre : l : liste doublement chainée
    :return : int : la valeur de la longeur de la liste
  """
  lg = 0
  n = l
  if l is None :
    return lg
  else :
    lg = 1
    while n[2] != None:
      lg += 1
      n = GetSuivantLDC(n)
    return lg


def InsererDebutLDC(l,val):
  """
     Permet d'inserer une valeur en début de liste doublement chainée
    :paramètre : l : liste doublement chainée
                  val : valeur du noeud
    :return : nn : la nouvelle liste chainée
  """
  if l is 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):
  """
     Permet d'inserer une valeur en fin de liste doublement chainée
    :paramètre : l : liste doublement chainée
                  val : valeur du noeud
    :return : l : la nouvelle liste chainée
  """
  if l is 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):
  """
     Permet de supprimer le premier noeud de la liste doublement chainée
    :paramètre : l : liste doublement chainée
    :return : n : la nouvelle liste chainée
  """
  assert(l != None) ## on ne peut pas supprimer un noeud dans une liste vide
  n = l
  if LongueurLDC(l) == 1:
    return None
  else :
    n = GetSuivantLDC(n)
    n[1] = None
  return n
        
def SupprimerFinLDC(l):
  """
     Permet de supprimer le dernier noeud de la liste doublement chainée
    :paramètre : l : liste doublement chainée
    :return : l : la nouvelle liste chainée
  """
  assert(l != None) ## on ne peut pas supprimer un noeud dans une liste vide
  n = l
  if LongueurLDC(l) == 1:
    return None
  else :
    while GetSuivantLDC(n) != None:
      n = GetSuivantLDC(n)
    setSuivant (GetPrecedentLDC(n), None)
    setPrecedent (n, None)
  return l

def AccesLDC(l,p):
  """
     Permet d'accéder au noeud d'indice p dans la liste doublement chainée l
    :paramètre : l : liste doublement chainée
                  p : int : indice du noeud souhaiter
    :return : liste : une liste de 3 éléments avec [la valeur du noeud, noeuds précédents, noeuds suivants]
  """
  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):
  """
     Permet d'inserer une valeur à la postion p dans la liste doublement chainée l
    :paramètre : l : liste doublement chainée
                  val : valeur du noeud
                  p : int : indice du noeud souhaiter
    :return : l : la nouvelle liste chainée
  """
  assert p <= LongueurLDC(l) ##L'indice donnée pour placer la valeur est trop grand par rapport à la liste
  if l is 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):
  """
     Permet de supprimer le noeud d'indice p dans la liste doublement chainée l 
    :paramètre : l : liste doublement chainée
                  p : int : indice du noeud souhaiter
    :return : l : la nouvelle liste chainée
  """
  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)
    GetSuivantLDC(m)[1] = m[1]
    GetPrecedentLDC(m)[2] = m[2]
    m[1] = None
    m[2] = None
  return l

def SupprimerValLDC(l,val):
  """
     Permet de supprimer le premier noeud de valeur val dans la liste doublement chainée l 
    :paramètre : l : liste doublement chainée
                  val : valeur du noeud à supprimer
    :return : n : la nouvelle liste chainée
  """
  assert(l != None) ## on ne peut pas supprimer à un noeud dans une liste vide
  n = l
  j = 0
  while GetValLDC(n) != val:
    n = GetSuivantLDC(n)
    assert(n != None)## la valeur donnée ne ce trouve pas dans la liste
    j +=1
  n = SupprimerPlaceLDC(l,j)
  return n
  
def LDC2List(l):
  """
     Permet de convertir la liste doublement chainée en une liste qui contient toute les valeurs des noeuds
    :paramètre : l : liste doublement chainée
    :return : List : la liste qui contient toute les valeurs de LDC
  """
  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):
  """
     Permet de convertir la liste qui contient la valeurs des noeuds en une liste doublement chainée
    :paramètre : l : la liste qui contient toute les valeurs de LDC
    :return : list : liste doublement chainée
  """
  if l != None :
    list = None
    for i in range (len(l)) :
      list = InsererFinLDC(list, l[i])
  else :
    assert () ## Ce n'est pas une liste ! 
  return list

#################################
##### Fonction de Test des LDC###
#################################


def est_vide(l):
  """
    Permet de testé si une liste l et vide ou non
    :paramètre : l : une liste doublement chainée
    :return : bool : True si la liste est vide et False si la liste n'est pas vide.
  """
  if LongueurLDC(l) == 0:
    return True
  else :
    return False

def test_creation_liste():
  """
  Test du Cosntructeur de la liste doublement chainée
  :return : bool : True le test est correct
  """
  ma_liste = creerListeVide()

  assert est_vide(ma_liste)
  return True
  
def test_ajout_tete():
  """
  Test de l'ajout d'une valeur en tête de la liste
  :return : bool : True le test est correct
  """
  ma_liste = creerListeVide()
  ma_liste = InsererDebutLDC(ma_liste, 28)

  assert not est_vide(ma_liste)
  assert LongueurLDC(ma_liste) == 1
  return True


def test_ajout_tete_a_fin():
  """
  Test de l'ajout d'une valeur en fin de la liste
  :return : bool : True le test est correct
  """
  ma_liste = creerListeVide()
  ma_liste = InsererDebutLDC(ma_liste, 32)
  ma_liste = InsererDebutLDC(ma_liste, 14)
  ma_liste = InsererFinLDC(ma_liste, 12)

  assert LongueurLDC(ma_liste) == 3
  return True

##def test_acces_LDC():
##  ma_liste = creerListeVide()
##  ma_liste = InsererDebutLDC(ma_liste, 32)
##  ma_liste = InsererDebutLDC(ma_liste, 14)
##  ma_liste = InsererFinLDC(ma_liste, 12)
##  Noeud_1 = AccesLDC(ma_liste, 1)


def test_supression_debut():
  """
  Test de supression de la tête de la 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 = InsererFinLDC(ma_liste, 12)
  ma_liste = SupprimerDebutLDC(ma_liste)  # La LDC est 14, 32, 12

  assert LongueurLDC(ma_liste) == 2
  assert AccesLDC(ma_liste, 0)[0] == 32
  return True

def test_supression_fin():
  """
  Test de supression de la fin de la 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 = InsererFinLDC(ma_liste,12)
  ma_liste = SupprimerFinLDC(ma_liste)     # La LDC est 14, 32, 12

  assert LongueurLDC(ma_liste) == 2
  assert AccesLDC(ma_liste, 2)[0] == 32
  return True

  
def test_ajout_place(val,p):
  """
  Test d'ajout une valeur à la place p
  :return : bool : True le test est correct
  """
  ma_liste = creerListeVide()
  ma_liste = InsererDebutLDC(ma_liste, 32)
  ma_liste = InsererDebutLDC(ma_liste, 14)
  ma_liste = InsererFinLDC(ma_liste, 12)
  ma_liste = InsererPlaceLDC(ma_liste, val, p)      # La LDC est 14, 32, 12,42

  assert LongueurLDC(ma_liste) == 4
  assert AccesLDC(ma_liste, p)[0] == val
  return True

def test_supression_place():
  """
  Test de supression d'un noeud à une place définit
  :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 = SupprimerPlaceLDC(ma_liste, 2)    # La LDC est 33, 66, 14, 32  ici on souhiate supprimer 14 le

  assert LongueurLDC(ma_liste) == 3
  assert AccesLDC(ma_liste, 2)[0] == 32
  return True

def test_supression_valeur():
  """
  Test de supression d'une valeur dans la 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 = SupprimerValLDC(ma_liste, 14)       # La LDC est 33, 66, 14, 32  ici on souhiate supprimer 14

  assert LongueurLDC(ma_liste) == 3
  assert AccesLDC(ma_liste, 2)[0] == 32
  return True

def test_LDC_To_List():
  """
  Test de Conversion de la LDC en List
  :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 = LDC2List(ma_liste)         # La LDC est 33, 66, 14, 32  ici on souhaite la convertir le List [33, 66, 14, 32]

  assert ma_liste == [33, 66, 14, 32]
  return True

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

##############################################
##### Programme de test des fonction #########
##############################################


if __name__ == '__main__':
  print('Test liste vide :', test_creation_liste())
  print('Test ajout tête :', test_ajout_tete())
  print('Test ajout fin :', test_ajout_tete_a_fin())
  print('Test supression début :', test_supression_debut())
  print('Test supression fin :', test_supression_debut())
  print('Test ajouter à la place :', test_ajout_place(422,2))
  print('Test supression Place :', test_supression_place())
  print('Test supression Valeur :', test_supression_valeur())
  print('Test conversion en List :', test_LDC_To_List())
  print('Test conversion en LDC :', test_List_To_LDC())
##  print('Test liste acces :', test_acces_LDC())

J’en suis maintenant à essayer les jeux de test pour les fonctions. Pour test_acces_LDC() j’ai cette erreur : 

Traceback (most recent call last):
  File "C:\Users\Julie\Downloads\Projet david bloc 3\Fonction_LDC.py", line 511, in <module>
    print('Test conversion en LDC :', test_List_To_LDC())
  File "C:\Users\Julie\Downloads\Projet david bloc 3\Fonction_LDC.py", line 493, in test_List_To_LDC
    assert AccesLDC(ma_liste_test,i) == AccesLDC(ma_liste,i)
RecursionError: maximum recursion depth exceeded in comparison

Mais je ne voit pas comment faire autrement pour automatiser le test ? a moins de l’afficher à l’utilisateur ?

Bonne journée. Lesnox

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte