Aller au contenu

Algorithmes récursifs et listes chaînées

Liste chaînée

On rappelle le code de la classe Maillon :

1
2
3
4
5
6
class Maillon:
    """ Un maillon d'une liste chainée. """
    def __init__(self, v, s):
        """ int, Maillon -> None """
        self.valeur = v
        self.suivant = s

  1. On suppose que les deux objets m1 et m2 de type Maillon ont été définis, soit avec premier code, soit avec le second code.

    Premier code.

    1
2
3
    m1 = Maillon(1, None)       
m2 = Maillon(2, m1)
m1 = Maillon(1, m2)

    Deuxième code.

    1
2
3
    m1 = Maillon(1, None)       
m2 = Maillon(2, m1)
m1.suivant = m2

    On donne l'affichage réalisé par les instructions suivantes. 

    1
2
3
4
    print(id(m1)) 
print(id(m1.suivant)) 
print(id(m2)) 
print(id(m2.suivant)) 

    140655316784640
140655306819856
140655306819856
140655316784640

    En déduire quel code a été utilisé pour définir les maillons m1 et m2. Appuyer votre réponse sur un schéma explicatif.

    Il s'agit d'une question de cours.

  2. Écrire une fonction supprime_fin qui étant donné un maillon m d'une liste chaînée supprime le dernier maillon de cette chaîne, en en renvoyant la valeur. On parcourera toute la chaîne à l'aide d'une boucle en s'arrêtant à l'avant-avant dernier maillon. On supposera pour cela que m est le premier maillon d'une chaîne constituée d'au moins deux éléments. Les maillons de la chaîne pourront être modifiés.

    1
2
3
4
5
6
7
8
9
       def supprime_fin(m):
       """ Maillon -> int
       Supprime le dernier maillon de la chaine, en renvoie la valeur """
       maillon_courant = m
       while maillon_courant.suivant.suivant != None:
           maillon_courant = maillon_courant.suivant
       v = maillon_courant.suivant.valeur
       maillon_courant.suivant = None
       return v

    1
2
3
4
5
    m = Maillon(1, Maillon(2, Maillon(3, None))) 
v = supprime_fin(m)
print(v)
print(m.suivant.valeur)
print(m.suivant.suivant)

    3
2
None

Algorithme récursif

Cet exercice porte sur le type Liste définit en tp. Vous répondrez aux questions suivantes en n’utilisant que les fonctions est_vide, creer_vide, ajoute, tete, queue.

  1. On souhaite écrire une fonction identiques qui prend comme arguments deux listes l1 et l2 et qui renvoie True si les deux listes sont constituées des mêmes éléments, dans le même ordre, False sinon.

    1. Compléter le tableau ci-dessous. On représentera une liste par la liste de ses éléments entre parenthèses, sans se soucier de l’implémentation du type Liste. Ainsi la liste dont le premier élément est 1 et le second élément est 2 sera représentée par (1, 2).

      l1 l2 identiques(l1, l2)
      () () True
      (1) () False
      () (3) False
      (2, 7, 8) (2, 8, 7) False
      (2, 7, 8) (2, 7, 8) True
      (3, 7, 8) (5, 7, 8) False

    2. Compléter le code de la fonction identiques ci-dessous afin qu'elle réponde aux conditions de l'énoncé.

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
            def identiques(l1, l2):
          """ Liste, Liste -> bool
          Détermine si les deux listes sont constituées des mêmes éléments, dans le même ordre """
          if est_vide(l1) and est_vide(l2):
              return True
          elif est_vide(l1):
              return False
          elif est_vide(l2):
              return False
          else:
              avant = est_vide(queue(l1), queue(l2))
              return avant and tete(l1) == tete(l2)
      2. Si l est une liste, alors la liste l "renversée" est la liste constituée des éléments de l rangés dans le sens inverse. Ainsi, si l est la liste (2, 4, 6) la liste l "renversée" est la liste (6, 4, 2).

    On souhaite écrire une fonction concatener_inverse qui étant donné deux listes l1 et l2 concatène la liste l1 "renversée" avec la liste l2.

    1. Compléter le tableau ci-dessous.

      l1 l2 concatener_inverse(l1, l2)
      (2, 4, 6) (3, 5, 7) (6, 4, 2, 3, 5, 7)
      () () ()
      () (1) (1)
      () (1, 2) (1, 2)
      (1, 2) (3, 4) (2, 1, 3, 4)
      (1, 5, 9, 13) (7, 4, 3) (13, 9, 5, 1, 7, 4, 3)

    2. Écrire le code d'une fonction python concatener_inverse, récursive, qui réponde aux conditions de l'énoncé.

      On remarquera que lorsque l1 = (2, 4, 6) et l2 = (3, 5, 7), on peut obtenir la liste (6, 4, 2, 3, 5, 7) en concaténant la liste l1prime = (4, 6) "renversée" avec la liste l2prime = (2, 3, 5, 7).

      1
2
3
4
5
6
7
8
            def concatener_inverse(l1, l2):
          """ Liste, Liste -> Liste
          Concatène la liste l1 "renversée" avec la liste l2 """
          if est_vide(l1):
              return l2
          else:
              l2prime = ajoute(l2, tete(l1))
              return concatener_inverse(queue(l1), l2prime)