Skip to content

Listes doubles

Énoncé

On va travailler sur des listes doublement chaînées. Chaque cellule d'une liste doublement chaînée contient non seulement une valeur et un champ suivant comme pour les listes classiques, mais aussi un champ pointant sur la cellule précédente dans la liste.

Commencer par écrire une classe Cellule respectant cette définition.

Écrire ensuite le constructeur de la classe ListeDouble qui va allouer deux éléments fictifs en tête (sentinelles) et les chaîner correctement l'un à l'autre. Une liste vide sera donc composée des deux éléments fictifs chaînés l'un à l'autre : Tete <-> Queue et les éléments significatifs seront ensuite insérés entre les deux éléments fictifs : Tete <-> 1 <-> 2 <-> 3 <-> Queue.

Remplissage de la liste

Implanter une méthode remplir(self, tab) qui remplit la liste avec les valeurs du tableau passé en argument, dans le même ordre. Cette fonction ne renvoie rien car les sentinelles de tête et de queue ne sont pas modifiées.

Affichage de la liste

Implanter une méthode afficher(self, inv=False) qui affiche le contenu de la liste (i.e. les cellules contenant des valeurs significatives séparées par des <->). L'affichage se fera en partant de la fin ssi inv == True et en partant du début sinon.

Échange de deux éléments

Implanter une fonction echanger(cell) qui échange les cellules cell et cell.suiv dans la liste, et renvoie un pointeur vers l'ancienne cellule cell.suiv. On procédera par réorganisation des chaînages, sans toucher aux valeurs (i.e. vous n'avez pas le droit de simplement échanger les valeurs des deux cellules). On prendra comme hypothèse que la cellule cell n'est pas la dernière de la liste (i.e. il y a bien une cellule contenant une valeur significative après cell).

Tri de la liste

Implanter enfin une méthode trier(self) qui trie la liste par ordre croissant selon l'algorithme du nain de jardin, dont on rappelle le principe :

  • un nain de jardin cherche à trier des pots de fleurs par taille croissante ;
  • il regarde le pot devant lui : s'il est plus petit que le pot à sa droite, le nain avance d'un pas vers la droite (s'il n'est pas arrivé à la fin de la file de pots) ;
  • si le pot devant lui est plus grand que le pot à sa droite, le nain échange les deux pots, et recule d'un pas vers la gauche (s'il n'est pas revenu au début de la file de pots).

On pourra prendre comme hypothèse que la liste n'est pas vide.

On pourra tester les fonctions avec le programme principal suivant :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#!/usr/bin/env python3
"""
  Listes doublement chainees
"""

from random import randint


def main():
    """
      Fonction principale
    """
    liste = ListeDouble()
    liste.remplir([randint(0, 9) for _ in range(5)])
    print("Liste initiale  : ", end="")
    liste.afficher()
    print("en sens inverse : ", end="")
    liste.afficher(True)
    cell = liste.tete.suiv
    while cell is not liste.queue.prec:
        echanger(cell)
        print("Test echanger   : ", end="")
        liste.afficher()
    liste.trier()
    print("Liste triee     : ", end="")
    liste.afficher()
    print("en sens inverse : ", end="")
    liste.afficher(True)

main()

Correction

Cliquez ici pour révéler la correction.

liste_double.py :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#!/usr/bin/env python3
"""
  Listes doublement chainees
"""

from random import randint

from cellule_double import Cellule

class ListeDouble:

    def __init__(self):
        """
          Cree une liste doublement chainee
        """
        self.tete = Cellule('T', None, None)
        self.queue = Cellule('Q', None, None)
        self.tete.suiv = self.queue
        self.queue.prec = self.tete

    def remplir(self, tab):
        """
          Remplit la liste a partir des valeurs d'un tableau
        """
        for val in tab:
            nouv = Cellule(val, self.queue.prec, self.queue)
            self.queue.prec.suiv = nouv
            self.queue.prec = nouv

    def afficher(self, inv=False):
        """
          Affichage
        """
        cour, fin = ((self.queue.prec, self.tete) if inv else (self.tete.suiv, self.queue))
        while cour is not fin:
            print(cour, end="")
            cour = cour.prec if inv else cour.suiv
        print("FIN")

    def trier(self):
        """
          Trie la liste selon l'algorithme du nain de jardin
        """
        cour = self.tete.suiv
        while cour.suiv is not self.queue:
            if cour.val > cour.suiv.val:
                cour = echanger(cour)
                if cour.prec is not self.tete:
                    cour = cour.prec
            else:
                cour = cour.suiv

def echanger(cell):
    """
      Echange cell avec cell.suiv, renvoie le pointeur mis a jour
    """
    prec = cell.prec
    cour = cell
    suiv = cell.suiv
    suiv_suiv = suiv.suiv
    prec.suiv = suiv
    cour.prec = suiv
    cour.suiv = suiv_suiv
    suiv.prec = prec
    suiv.suiv = cour
    suiv_suiv.prec = cour
    return suiv

def main():
    """
      Fonction principale
    """
    liste = ListeDouble()
    liste.remplir([randint(0, 9) for _ in range(5)])
    print("Liste initiale  : ", end="")
    liste.afficher()
    print("en sens inverse : ", end="")
    liste.afficher(True)
    cell = liste.tete.suiv
    while cell is not liste.queue.prec:
        echanger(cell)
        print("Test echanger   : ", end="")
        liste.afficher()
    liste.trier()
    print("Liste triee     : ", end="")
    liste.afficher()
    print("en sens inverse : ", end="")
    liste.afficher(True)

main()