Données Linéaires

Identification

Infoforall

21 - Types linéaires


Il ne s'agit pas d'une vrai activité. Juste d'un gros rappel très rapide.

Résumons ce que vous avez appris sur les données séquentielles et linéaires et les trois types abstraits que vous avez découvert :

  • Type LISTE :
    • Idée générale : séquence ordonnée dans laquelle on peut lire, insérer ou supprimer les données à n'importe quelle position de la séquence.
    • Interface : on doit pouvoir créer une nouvelle liste, lire un élément, insérer un élément, supprimer un élément et tester si la liste est vide.
    • Implémentation tuple (tete, queue) : simple mais efficace uniquement si on ne désire agir que sur la tête
    • Implémentation tableau : coût CONSTANT en lecture et modification d'un élément mais coût LINEAIRE en insertion ou suppression d'un élément.
    • Implémentation liste chaînée : coût LINEAIRE en lecture ou modification d'un élément (sauf exception) mais le coût à l'insertion ou à la suppression est CONSTANT. Possibilité de concaténer deux listes en stockant assez d'informations dans la liste. La LISTE CHAINEE peut être vue comme un type abstrait également. On peut l'implémenter :
      • Dans une structure basée sur des objets LISTE et CELLULE
      • Dans une structure où les informations sont dans un TABLEAU et les CELLULES sont d'autres tableaux.
  • Type PILE :
    • Idée générale : séquence ordonnée dans laquelle on peut lire, insérer ou supprimer les données uniquement sur l'une des extrémités qu'on nomme le SOMMET.
    • Concept LIFO
    • Interface : on doit pouvoir créer une nouvelle pile, lire le sommet, insérer un élément au sommet (empiler), supprimer le sommet actuel (dépiler) et tester si la pile est vide.
    • Implémentation tuple (sommet, queue) : coût CONSTANT à l'empilement et au dépilement
    • Implémentation tableau : coût CONSTANT également à l'empilement et au dépilement.
    • Implémentation liste chaînée : coût CONSTANT également à l'empilement et au dépilement
  • Type FILE :
    • Idée générale : séquence ordonnée dans laquelle on peut lire et supprimer qu'à une extrémité qu'on nomme AVANT, et insérer à l'autre extrémité qu'on nomme ARRIERE.
    • Concept FIFO
    • Interface : on doit pouvoir créer une nouvelle file, lire l'avant, insérer à l'arrière (enfiler), supprimer l'avant (défiler) et tester si la file est vide.
    • Implémentation tableau contenant juste les données : coût LINEAIRE au défilement donc peu efficace.
    • Implémentation deux piles : coût LINEAIRE au défilement lorsque la pile de sortie est vide. Le coût est sinon CONSTANT à l'enfilement et au défilement.
    • Implémentation liste chaînée : le coût est CONSTANT à l'enfilement et au défilement. Version Objet et version Tableaux.
    • Implémentation tableau contenant les informations et un tableau de données ou dictionnaire contenant les informations et un tableau de données : le coût est CONSTANT à l'enfilement et au défilement.
    • Implémentation tableau unique contenant informations et données : coût CONSTANT à l'enfilement et au défilement mais code plus complexe au final que les versions efficaces précédentes.

Activité publiée le 25 10 2020
Dernière modification : 25 10 2020
Auteur : ows. h.