Réalisation d'une classe Liste Chainee

 Publié le November 20, 2023  |  3 minutes  |  611 mots  |  

Par transformation des fonctions du document 1 dans ce chapitre en méthodes, écrire le code de la classe Liste qui définit le type abstrait « Liste chaînée ».

Réponse 
  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

from __future__ import annotations


class Maillon:
    """
    Un maillon de la liste.
    """

    def __init__(self: Maillon, valeur: int, suivant: Maillon = None) -> None:
        self.valeur = valeur
        self.suivant = suivant


class Liste:
    """
    Implémentation de la classe liste.
    """

    def __init__(self: Liste, valeur: int = None) -> None:
        """
        Initialisation de l'objet. Il est possible de créer une liste
        vide ou une liste contenant un élément.

        Il est possible de créer directemnt une liste contenant plusieurs
        éléments il faut utiliser une fonctionnalité de Python que vous
        ne connaissez pas forcément et qui n'est pas au programme.
        """
        if valeur is None:
            self.maillons = None
        else:
            self.maillons = Maillon(valeur)

    def est_vide(self: Liste) -> bool:
        """ Détermine si la liste est vide. """
        return self.maillons is None

    def __len__(self: Liste) -> int:
        """ Retourne le nombre d'éléments dans la liste. """
        if self.est_vide():
            return 0
        else:
            nbre = 0
            maillon = self.maillons
            while maillon is not None:
                nbre += 1
                maillon = maillon.suivant
            return nbre

    def append(self: Liste, valeur: int) -> None:
        """
        Ajoute valeur à la fin de la liste.
        """
        if self.est_vide():
            self.maillons = Maillon(valeur)
        else:
            maillon = self.maillons
            while maillon.suivant is not None:
                maillon = maillon.suivant

            maillon.suivant = Maillon(valeur)

    def append_first(self: Liste, valeur: int) -> None:
        """
        Ajoute valeur au début de la liste.
        """
        maillon = Maillon(valeur)
        maillon.suivant = self.maillons
        self.maillons = maillon

    def pop(self: Liste) -> int:
        """
        Retire le dernier élément de la liste et le retourne.

        Lève une erreur si la liste est vide.
        """
        if self.est_vide():  # Liste vide
            raise Exception("La liste est vide !")

        maillon = self.maillons
        if maillon.suivant is None:  # Cas d'une liste à un élément
            valeur = maillon.valeur
            self.maillons = None
            return valeur
        else:
            while maillon.suivant.suivant is not None:  # Cas général
                maillon = maillon.suivant
            valeur = maillon.suivant.valeur
            maillon.suivant = None
            return valeur

    def pop_first(self: Liste) -> int:
        """
        Retire le premier élément de la liste et le retourne.

        Lève une erreur si la liste est vide.
        """
        if self.est_vide():  # Liste vide
            raise Exception("La liste est vide !")

        valeur = self.maillons.valeur
        self.maillons = self.maillons.suivant
        return valeur

    def __getitem__(self: Liste, i: int) -> int:
        """
        Redéfinition de la fonction d'accès à l'élément d'indice i.
        """
        if self.est_vide():
            raise Exception("La liste est vide !")

        maillon = self.maillons
        j = 0
        while j < i:
            if maillon is None:
                raise IndexError("Indice hors des limites !")
            maillon = maillon.suivant
            j += 1
        return maillon.valeur

    def __str__(self: Liste) -> str:
        """
        Représentation de la liste sous-forme d'une chaîne de caractères.
        """
        rep = "["

        maillon = self.maillons
        while maillon is not None:
            rep += str(maillon.valeur)
            if maillon.suivant is not None:
                rep += ", "
            maillon = maillon.suivant

        rep += "]"
        return rep
Liste  Liste chaînée 

Implémentation du type abstrait Liste Chaînée à l'aide de listes Python

 Publié le November 20, 2023  |  3 minutes  |  555 mots  |  

Reprendre toutes les fonctions des sections 2 et 3 du document 1 de ce chapitre, en implémentant cette fois le type abstrait « Liste chaînée » à l’aide de tuples (à la place de la classe).

Réponse 
  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

def est_dans(tab: list[int], val: int) -> bool:
    """
    Recherche la présence de val dans tab.
    """
    trouve = False

    i = 0
    while i < len(tab) and not trouve:
        if val == tab[i]:
            trouve = True
        i += 1

    return trouve


def est_dans_rec(tab: list[int], n: int, i: int = 0) -> bool:
    """
    Recherche si la valeur n est présente au moins une fois
    dans le tableau tab.
    Algorithme récursif, i est l'indice de recherche.
    """
    if i == len(tab):
        return False
    elif tab[i] == n:
        return True
    else:
        return est_dans_rec(tab, n, i + 1)


def insere(tab: list[int], n: int, i: int) -> None:
    """
    Insère la valeur n à l'indice i du tableau tab.
    Algorithm itératif et en place.
    
    Lève une exception si le tableau est déjà plein.
    
    HYPOTHÈSE : la gestion des "trous" n'est pas assurée,
    l'algorithme se contente de décaler les valeurs vers 
    la droite.
    """
    dernier_indice = len(tab) - 1

    if tab[dernier_indice] != None:
        raise Exception("Tableau plein !")

    k = dernier_indice
    while k > i:
        tab[k] = tab[k - 1]
        k -= 1

    #for k in range(dernier_indice, i, -1):
    #    tab[k] = tab[k - 1]

    tab[i] = n


def insere_rec(tab: list[int], n: int, i: int, k: int) -> None:
    """
    Insère la valeur n à l'indice i du tableau tab.
    Algorithm récursif et en place. k est l'indice de
    recherche. 
    Sa première valeur doit être len(tab) - 1.
    
    Lève une exception si le tableau est déjà plein.
    
    HYPOTHÈSE : la gestion des "trous" n'est pas 
    assurée, l'algorithme se contente de décaler 
    les valeurs vers la droite.
    """
    dernier_indice = len(tab) - 1

    if tab[dernier_indice] != None and k == dernier_indice:
        raise Exception("Tableau plein !")
    elif k == i:
        tab[i] = n
        return None
    else:
        tab[k] = tab[k - 1]
        return insere_rec(tab, n, i, k - 1)


if __name__ == "__main__":
    tab = [i for i in range(20)]

    assert est_dans(tab, 12) == True
    assert est_dans(tab, 0) == True
    assert est_dans(tab, 20) == False

    assert est_dans_rec(tab, 12) == True
    assert est_dans_rec(tab, 0) == True
    assert est_dans_rec(tab, 20) == False

    print("Insertion itérative")
    tab = [1, 1, 2, 3, 4, 5, None, None, None]
    print(tab)
    insere(tab, 7, 0)
    print(tab)
    insere(tab, 7, 0)
    print(tab)
    insere(tab, 7, 0)
    print(tab)
    #insere(tab, 7, 0)
    #print(tab)
    print()
    print("Insertion récursive")
    tab = [1, 1, 2, 3, 4, 5, None, None, None]
    print(tab)
    insere_rec(tab, 7, 0, len(tab) - 1)
    print(tab)
    insere_rec(tab, 7, 0, len(tab) - 1)
    print(tab)
    insere_rec(tab, 7, 0, len(tab))
    print(tab)
Liste  Liste chaînée 

Les Files

 Publié le October 31, 2020  |  6 minutes  |  1164 mots  |  

Rappel : Type de Données Abstrait (TDA)

Une structure de données ou type de données abstrait est un moyen d’organiser et de manipuler les données en mémoire. Un TDA est donc définit par :

  • Son nom ;
  • Sa spécification, c’est à dire la liste des manipulations/opérations que l’on peut ou pas effectuer. La spécification indique généralement la complexité de chacune des opérations prévues par le TDA.
Un type de données abstrait ne dépend pas de la manière dont la structure de données est implémentée dans le langage de programmation utilisé.
Un TDA peut être implémenté de plusieurs façons différentes.

Qu’est-ce qu’une file ?

Une file est une structure de données abstraite dans laquelle les données sont organisées comme le seraient des personnes dans une file d’attente (au guichet de la poste par exemple) :

[Lire]
File  Pile  Liste chaînée  Liste  Tableau dynamique  Complexité 

Les Piles

 Publié le October 27, 2020  |  6 minutes  |  1260 mots  |  

Rappel : Type de Données Abstrait (TDA)

Une structure de données ou type de données abstrait est un moyen d’organiser et de manipuler les données en mémoire. Un TDA est donc définit par :

  • Son nom ;
  • Sa spécification, c’est à dire la liste des manipulations/opérations que l’on peut ou pas effectuer. La spécification indique généralement la complexité de chacune des opérations prévues par le TDA.
Un type de données abstrait ne dépend pas de la manière dont la structure de données est implémentée dans le langage de programmation utilisé.
Un TDA peut être implémenté de plusieurs façons différentes.

Qu’est-ce qu’une pile ?

Une pile est une structure de données abstraite dans laquelle les données sont organisées comme le seraient des assiettes dans une pile d’assiettes contenue dans une boite de profondeur quelconque mais étroite (ce qui empêche de manipuler les assiettes par le côté).
On peut donc seulement :

[Lire]
Pile  Liste  Liste chaînée  Complexité  Classe 

Listes Chaînées, présentation

... et implémentation à l'aide d'une classe

 Publié le October 14, 2020  |  13 minutes  |  2710 mots  |  

Tableaux

  • Un tableau est une structure de données dans laquelle les éléments, tous de même type, occupent des positions contiguës en mémoire.
  • Le nombre d’éléments qu’un tableau peut contenir est déterminé à la création d’un tableau.
Type Python Type Opération Exemple Complexité
N’existe pas Tableau Accès à un élément tab[i] $O(1)$
Modification d’un élément tab[i] = x $O(1)$
Effacement d’un élément retire(tab, i) $O(n)$
Insertion d’un élément insere(tab, x, i) $O(n)$
Recherche d’un élément est_dans(tab, x) $O(n)$
  • La structure de données appelée « liste » dans le langage Python est implémentée à l’aide de tableaux dynamiques.

Remarque : Dans la suite de ce document, on va considérer que la liste Python tab, créé par l’instruction tab = [i for i in range(20)] est de longueur fixe. Elle se comporte alors comme un tableau.

[Lire]
Tableau  Tableau dynamique  Liste  Liste chaînée  Complexité 

Structures de données fournies avec le langage Python

 Publié le October 13, 2020  |  8 minutes  |  1670 mots  |  

Python possède dans la bibliothèque standard un grand nombre de structures de données, programmées de manière efficace.

Rappels : modules, fonctions

Pour chaque module, on distingue :

  • sa réalisation (ou implémentation) : c’est le code lui-même.

  • son interface (API) : c’est l’énumération des fonctions définies dans le module qui sont utilisées depuis d’autres modules/programmes, les clients.

  • L’interface doit présenter une documentation dans laquelle tout ce que doit savoir le client doit être indiqué.

    [Lire]
Dictionnaire  Liste  Tableau dynamique  Structures de données  Ensemble  Complexité  Tableau associatif 

Itérer sur les éléments d'un dictionnaire

 Publié le October 13, 2020  |  3 minutes  |  600 mots  |  

Au zoo de Beauval, il y a 5 éléphants d’Asie, 17 écureuils d’Asie, 2 pandas d’Asie, etc. On représente cet inventaire à l’aide d’un dictionnaire, de façon suivante :

1
2
3
4
5
6
7

zoo_Beauval={
    'éléphant': ('Asie', 5),
    'écureuil': ('Asie', 17),
    'panda': ('Asie', 2),
    'hippopotame': ('Afrique', 7),
    'girafe': ('Afrique', 4)
    }

On représente de la même façon le zoo de La Flèche :

1
2
3
4
5
6

zoo_LaFleche = {
    'ours': ('Europe', 4),
    'tigre': ('Asie', 7),
    'girafe': ('Afrique', 11),
    'hippopotame': ('Afrique', 3)
    }

On souhaite se doter d’une fonction plus_grand_nombre() qui prend un zoo en paramètre et qui renvoie le nom de l’animal le plus représenté dans ce zoo.
Par exemple

[Lire]
Dictionnaire  Liste