Skip to content

Réorganisation listes chaînées

Énoncé

Dans cet exercice, on reprend les listes chaînées basiques qu'on a déjà utilisées dans les exercices de la séance précédente : une liste chaînée sera tout simplement une référence vers la première cellule (ou None si la liste chaînée est vide).

Complétez le programme ci-dessous, en implantant les fonctions suivantes :

  • une fonction inverse(lsc) qui inverse les éléments de la liste chaînée ; par exemple, si la liste chaînée initiale est 1 -> 2 -> 3 -> 4 -> FIN, la liste chaînée inversée sera 4 -> 3 -> 2 -> 1 -> FIN ; vous devez implanter cette fonction sans aucune allocation de cellule (ce qui interdit notamment d'utiliser la fonction d'insertion en tête) ; la fonction renvoie la liste chaînée inversée en résultat ;

  • une fonction insere_triee(lsc, val)qui insère la valeur à sa place dans une liste chaînée supposée triée par ordre croissant ; par exemple, si la liste chaînée initiale est 1 -> 2 -> 4 -> 5 -> FIN et qu'on appelle insere_triee(lsc, 3), la liste chaînée sera 1 -> 2 -> 3 -> 4 -> 5 - > FIN à la fin de la fonction ; la fonction renvoie la liste chaînée complétée en résultat ;

  • une fonction trie_max(lsc) qui trie la liste chaînée par ordre croissant en utilisant l'algorithme du tri par sélection du maximum ; là-encore, on ne doit pas allouer de nouvelles cellules, à part un élément fictif si nécessaire ; la fonction renvoie la liste chaînée triée en résultat.

On rappelle le principe de l'algorithme du tri par sélection du maximum :

  1. on parcours la liste initiale pour rechercher l'élément maximum ;

  2. on insère la cellule correspondante en tête de la liste résultat et on la retire de la liste initiale.

  3. le tri est terminé lorsque la liste initiale est vide.

  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
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#!/usr/bin/env python3
"""
  Programme pour manipuler des listes simplement chaînées basiques.
"""

from random import randint

# TODO implantez les fonctions suivantes :
#   - inverse
#   - insere_triee
#   - trie_max


class Cellule:
    """
    Une cellule est composée d'une valeur et d'une référence vers la
      cellule suivante (ou None s'il n'y a pas de suivant)
    """

    # pylint: disable=too-few-public-methods

    def __init__(self, val, suiv):
        """
        Constructeur
        """
        self.val = val
        self.suiv = suiv

    def __str__(self):
        """
        Afficheur
        """
        return f"{self.val} -> "


def est_vide(lsc):
    """
    Teste si la liste chaînée est vide
    """
    return lsc is None


def insere_tete(lsc, val):
    """
    Insère une cellule de valeur val en tête de la liste chaînée
    """
    return Cellule(val, lsc)


def affiche(lsc):
    """
    Affiche la liste chaînée
    """
    cour = lsc
    while cour is not None:
        print(cour, end="")
        cour = cour.suiv
    print("FIN")


def init_liste_chainee(vals=None):
    """
    Initialise une liste chaînée pour tester.
    Renvoie la liste chaînée
    """
    lsc = None
    if vals is None:  # on insère 10 chiffres aléatoires
        for _ in range(10):
            lsc = insere_tete(lsc, randint(0, 9))
    else:  # on insère les valeurs passées en argument en ordre inverse
        for val in vals:
            lsc = insere_tete(lsc, val)
    return lsc




def main():
    """
    Fonction principale
    """
    print("Liste chaînée initiale  : ", end="")
    lsc = init_liste_chainee((2, 2, 4, 6, 6, 8))
    affiche(lsc)
    print("Liste chaînée inversée  : ", end="")
    lsc = inverse(lsc)
    affiche(lsc)
    print("Insertion triée : ", end="")
    for val in (1, 3, 3, 5, 7, 9, 9):
        lsc = insere_triee(lsc, val)
    affiche(lsc)
    print("Liste chaînée aléatoire : ", end="")
    lsc = init_liste_chainee()
    affiche(lsc)
    print("Tri (maximum)   : ", end="")
    lsc = trie_max(lsc)
    affiche(lsc)


main()

Correction

Cliquez ici pour révéler la correction.

reorga_listes_chainees.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
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#!/usr/bin/env python3
"""
  Programme pour manipuler des listes simplement chaînées basiques.
"""

from random import randint

# TODO implantez les fonctions suivantes :
#   - inverse
#   - insere_triee
#   - trie_max


class Cellule:
    """
    Une cellule est composée d'une valeur et d'une référence vers la
      cellule suivante (ou None s'il n'y a pas de suivant)
    """

    # pylint: disable=too-few-public-methods

    def __init__(self, val, suiv):
        """
        Constructeur
        """
        self.val = val
        self.suiv = suiv

    def __str__(self):
        """
        Afficheur
        """
        return f"{self.val} -> "


def est_vide(lsc):
    """
    Teste si la liste chaînée est vide
    """
    return lsc is None


def insere_tete(lsc, val):
    """
    Insère une cellule de valeur val en tête de la liste chaînée
    """
    return Cellule(val, lsc)


def affiche(lsc):
    """
    Affiche la liste chaînée
    """
    cour = lsc
    while cour is not None:
        print(cour, end="")
        cour = cour.suiv
    print("FIN")


def init_liste_chainee(vals=None):
    """
    Initialise une liste chaînée pour tester.
    Renvoie la liste chaînée
    """
    lsc = None
    if vals is None:  # on insère 10 chiffres aléatoires
        for _ in range(10):
            lsc = insere_tete(lsc, randint(0, 9))
    else:  # on insère les valeurs passées en argument en ordre inverse
        for val in vals:
            lsc = insere_tete(lsc, val)
    return lsc


def inverse(lsc):
    """
    Inverse les elements de la liste chaînée
    """
    res = None
    while lsc is not None:
        suiv = lsc.suiv
        lsc.suiv = res
        res = lsc
        lsc = suiv
    return res


def insere_triee(lsc, val):
    """
    Insère une valeur à sa place dans une liste chaînée triée
    """
    fictif = Cellule("?", lsc)
    prec = fictif
    while prec.suiv is not None and prec.suiv.val <= val:
        prec = prec.suiv
    prec.suiv = Cellule(val, prec.suiv)
    return fictif.suiv


def trie_max(lsc):
    """
    Trie la liste chaînée en utilisant l'algorithme du tri par recherche du maximum.
    La liste chaînée résultat est triée par ordre croissant.
    Renvoie lsc
    """
    fictif = Cellule("?", lsc)
    lsc = None
    while fictif.suiv is not None:
        prec_max = fictif
        prec = fictif.suiv
        while prec.suiv is not None:
            if prec.suiv.val > prec_max.suiv.val:
                prec_max = prec
            prec = prec.suiv
        suiv = prec_max.suiv.suiv
        prec_max.suiv.suiv = lsc
        lsc = prec_max.suiv
        prec_max.suiv = suiv
    return lsc




def main():
    """
    Fonction principale
    """
    print("Liste chaînée initiale  : ", end="")
    lsc = init_liste_chainee((2, 2, 4, 6, 6, 8))
    affiche(lsc)
    print("Liste chaînée inversée  : ", end="")
    lsc = inverse(lsc)
    affiche(lsc)
    print("Insertion triée : ", end="")
    for val in (1, 3, 3, 5, 7, 9, 9):
        lsc = insere_triee(lsc, val)
    affiche(lsc)
    print("Liste chaînée aléatoire : ", end="")
    lsc = init_liste_chainee()
    affiche(lsc)
    print("Tri (maximum)   : ", end="")
    lsc = trie_max(lsc)
    affiche(lsc)


main()