Structures de données linéaires

Les structures de données linéaires sont des suites d'éléments $e_1 , e_2 , \dots , e_n$. Dans une structure linéaire, on traite les données séquentiellement, c'est-à-dire les unes après les autres. De plus on doit pouvoir ajouter et supprimer des éléments.
On va s'intéresser à trois types de structures linéaires : les listes, les piles et les files.

Compléter ce cours/TD au fur et à mesure que vous le faites. Pour écrire dans une cellule, double-cliquez dedans. Une fois le TD fait, imprimez-le : pour réviser, la mémorisation se fait mieux avec un cours papier que sur écran.

Les listes

Une première remarque fondamentale : on ne parle pas du type listvu en Python en première. Le type listde Python est en fait un tableau dynamique.

Une liste en informatique est une suite d'éléments. Cette suite est finie, et peut être vide. Chaque élément de la suite est repérée par son indice : la liste est ordonnée par l'indice (et non par la valeur de l'élément).

Deuxième remarque : une liste informatique n'est pas non plus ce qu'on appelle une liste dans le langage courant. Quand on a une liste de courses, on ne suit pas l'ordre de la liste pour faire ses courses. Et on ne met pas deux fois le même ingrédient (sauf étourderie). Dans un style plus littéraire, vous pouvez lire les notes de chevet (枕草子, Makura no sōshi) de Sei Shōnagon, écrites vers 990. Ce sont des listes poétiques : "Choses dont on néglige souvent la fin", "Choses que l'on méprise", "Choses qui font battre le cœur", "Fleurs des arbres", "Cascades"...

Une liste est généralement définie comme une liste chaînée, avec un élément de tête, avec ensuite une autre liste, qui contient les éléments suivants. On a ici une définition récursive de la structure de données liste. Chaque élément de la liste est une cellule (cell).

Exemple à compléter : On donne la liste L1des jours de la semaine :
L1 = [lundi , mardi, mercredi , jeudi , vendredi , samedi , dimanche] L1a pour tête à compléter et est suivie de la liste L2 = à compléter
L2a pour tête à compléter et est suivie de la liste L3 = à compléter
Donner la dernière étape de cette décomposition:

Appeler le professeur pour vérification

Les opérations de base, dites fonctions primitives, sur les listes sont :

  • construction d'une liste. La liste peut être vide, ou bien on peut la construire à partir d'un élément de tête et d'une autre liste. On appelle cette fonction : creerListe(e = Aucun , liste = Aucun)
  • test de vacuité d'une liste : estVide(liste)
  • Obtention de la longueur de la liste : longueur(liste)
  • Accéder au k-ième élément de la liste : lire(liste , k)
  • Supprimer le k-ième élément de la liste : supprimer(liste , k)
  • Insérer un élément en k-ième position dans la liste : inserer(liste , k)

Exercices (sur papier ou à compléter dans la cellule) :

On utilisera uniquement les fonctions primitives définies ci-dessus

  1. Créer la liste de vos quatre films préférés. les films doivent être dans l'ordre de vos préférences. Essayez d'écrire une seule ligne.
  2. On donne une liste L1. Ecrire un algorithme en langage naturel renvoyant la liste L2, qui est dans l'ordre inverse de L1.

Une première implémentation

Compléter le code suivant pour implémenter toutes les primitives du type liste. Les attributs de cette classe sont :

  • __cell : la liste proprement dite
  • __tete : l'élément de tête de la liste (éventuellement None)
  • __queue: la liste composant la deuxième partie de __cell(éventuellement None)
In [5]:
class Liste(object) :

    def __init__(self, *args):
        if len(args) == 0:
            # Pas de paramètres : on construit une liste vide
            self.__cell = None
        elif len(args) == 2:
            # Deux paramètres : un élément et une liste
            if isinstance(args[1], Liste):
                self.__cell = (args[0], args[1])
            else:
                print("le deuxième argument du constructeur doit être une liste")
        else:
            print("le constructeur de liste prend soit 0 soit 2 arguments")

    def estVide(self) :
        return self.__cell == None
    
    def longueur(self) :
        return
    
    def lire(self , i) :
        return
    
    def supprimer(self , i) :
        return
    
    def inserer(self , i) :
        return
    
    def getTete(self) :
        if not self.estVide() :
            return self.__cell[0]
        
    def getQueue(self) :
        if not self.estVide() :
            return self.__cell[1]
    
    def __repr__(self) :
        if self.estVide() :
            return '()'
        else:
            return '(' + repr(self.getTete()) + ',' + repr(self.getQueue()) + ')'

truc = Liste()
bidule = Liste("film1" , truc)
maliste = Liste("film2" , bidule)
print(maliste)
zaff = Liste()
print(zaff, zaff.estVide())

('film2',('film1',()))
() True

Tester votre code avec les réponses aux exercices précédents. Pour l'exercice 1, on rédigera le test sous forme d'un assert(). Pour l'exercice 2, on pourra rajouter une méthode inverser(liste).

Exercices

  1. Donner la complexité dans le pire des cas des méthodes estVide(), longueur(),inserer()
  2. Ecrire une méthode estEgale(liste2)qui teste si la liste2 est égale à la liste appelant la méthode.
  3. Ecrire une méthode appartient(element) qui renvoie Nonesi l'élément n'appartient pas à la liste, et son indice sinon. En déduire une méthode supprElement(element) qui supprime la première occurence d'un élément donné dans une liste
  4. Ecrire une méthodederniere(liste) qui renvoie la dernière cellule de la liste. En déduire une méthode concatener(liste2)qui concatène la liste2 en fin de la liste appelant la méthode.

Autres versions des listes

On peut créer d'autres versions des listes:

  • Listes basées sur des tableaux. On perd l'intérêt des listes, qui est d'insérer facilement un élément
  • Listes circulaires. Permet de boucler en fin de liste sur le premier élément
  • Listes doublement chaînées. Permet de connaîter non seulement l'élément suivant dans la liste, mais aussi le précédent
  • Listes doublement chaînées circulaires

Rappel sur une remarque importante : le type abstrait Listen'est pas le type list de Python. Les listes de Python sont basées sur des tableaux, et mélangent des accès de type fonctions (del(ma_liste[3]), des accès de type objet (ma_liste.append('truc')), et des accès plus étranges (machin in ma_liste , ma_liste[3:6])

Une deuxième implémentation

Changer la programmation des méthodes longueur et lire() (vous pouvez par exemple passer de l'itératif au récursif, et vice-versa).
Le changement de programmation change-t-il l'usage de la classe ?

In [ ]:

Des primitives différentes pour le type liste

Le type Liste n'est pas fixé dans le marbre. On peut proposer des primitives moins nombreuses, et plus simple :

  • construction d'une liste vide : creerListe()
  • test de vacuité d'une liste : estVide(liste)
  • Ajouter un élément en tête de la liste : cons(élément). C'est en fait le constructeur "historique" du type liste.
  • Renvoyer le premier élément de la liste sans le supprimer : car(liste). Renvoie la "tête" de liste
  • Renvoyer la liste, éventuellement vide, obtenue à partir de la liste initiale en supprimant son premier élément. : cdr(liste , k). Renvoie la "queue" de la liste.

Une liste L peut s'écrire L = cons(car(L) , cdr(L))

Une implémentation est donnée ci-dessous, basée sur des cellules (tête , queue). Construire des fonctions ou des méthodes permettant de renvoyer un tableau dynamique Python (type list, entre []) et de donner la longueur de la liste (sans passer par le tableau dynamique de Python).

In [ ]:
class Cellule :
    def __init__(self, tete, queue) :
        self.car = tete
        self.cdr = queue
        
class Liste :
    def __init__(self, c) :
        self.cellule = c
        
    def estVide(self):
        return self.cellule is None
        
    def car(self):
        assert not(self.cellule is None) , 'Listevide'
        return self.cellule.car
    
    def cdr(self):
        assert not(self.cellule is None) , 'Listevide'
        return self.cellule.cdr
    
    def __repr__(self):
        if self.estVide() :
            return '()'
        else:
            return '(' + repr(self.car( )) + ',' + repr(self.cdr()) + ')'

    #Correction
    def longueurListe(self):
        L = self
        n = 0
        while not (L.estVide()) : 
            n = n + 1
            L = L.cdr()
        return n

    def listeElements(self) :
        L = self
        t = []
        while not (L.estVide()) :
            t.append(L.car())
            L = L.cdr()
        return t
    #Fin correction


def cons(tete, queue) : 
        return Liste(Cellule(tete, queue))


    
nil = Liste(None)       # notation "nil" historique 
liste = Liste(Cellule(0,nil))
for i in range(1,5):
    liste = Liste(Cellule(i,liste))

print(liste)
print(liste.cdr())
print(liste.cdr().car())
print(liste ,liste.longueurListe() , liste.listeElements())

Types abstraits

Comme vous venez de le voir juste ci-dessus, la manière dont est programmée la classe n'influe pas sur son usage. Plus précisément, l'implémnetation de la classe ne joue pas sur sa signature. Le type de données Liste peut être définit de manière abstraite. Par exemple, pour utiliser des flottants en Python, vous n'av(i)ez pas besoin de connaître la représentation sous la forme mantisse-exposant, forme que l'on a vue dans le cours sur le codage.
On définit un type abstrait par sa signature : nom des opérations, type des arguments, type du retour des opérations.
Autant l'implémentation d'un type abstrait ne jioue pas sur sa signature, par définition même, autant elle peut jouer sur la complexité des opérations du type.

Piles

Une pile est une structure linéaire où les insertions et les suppressions se font toutes du même côté, à l'image d'une pile d'assiettes : on rajoute les nouvelles assiettes au sommet de la plie, on prend des assiettes sur le sommet de la pile également. Les piles sont appelées stack ou LIFO en anglais (last in, first out).

Une interface (un peu plus détaillée que la signature) d'une pile peut être :

Fonction Description
creerPile() $\rightarrow$ Pile Créer une pile vide
estPileVide(p) $\rightarrow$ Booléen Teste si la pile p est vide
empliler(p , élément) Insère élément en tête de p
depiler(p) $\rightarrow$ élément Enlève l'élément au sommet de la pile p et le renvoie
sommet(p) $\rightarrow$ élément Renvoie l'élément au sommet de la pile p

Exercices Piles 1

  1. Dans quel état se trouve une pile vide après les opérations suivantes
    • empiler(1)
    • empiler(2)
    • dépiler
    • empiler(3)
    • empiler(4)
    • empiler(5)
    • dépiler
    • dépiler
  2. Créer le type Pile, le tester. Si vous avez implémenté ce type d'une manière différente de votre voisin, vous pouvez tester et comparer l'efficacité de vos implémentations avec %timeit (mon_test(...))
In [ ]:
class Pile :
    

# un test parmi d'autres
    a = creerPile()
for i in range(6):
    empiler(randint(1, 6), a)
for i in range(6):
    depiler(a)
    print(a)

il est légitime de se demander à quoi sert une pile en informatique. On en trouve dans la gestion des modifications de documents dans les traitements de texte. Dans LibreOffice, ctrl-z permet d'annuler la dernière modification du texte, en "dépilant". On peut itérer cette opération. De même dans les navigateurs, le bouton "page précédente" cache une pile conservant les adresses visitées. Plus généralement, on a précédemment mentionné les "piles d'appel", notamment en programmation récursive. C'est bien une structure du type abstrait pile qui est utilisée.

Exercice Piles 2

3 . Ecrire une deuxième implémentation de la structure Pile. Si vous ne l'avez pas fait, utilisez la classe précédente Liste pour cela : on peut réaliser Pile très économiquement à partir de cette dernière. Et si vous avez déjà utilisé Liste, implémentez par exemple à partir de tableaux (type list) Python.

In [ ]:

Encore un exercice (plus amusant)

La notation polonaise inverse (notation postfixe) est une manière de noter les calculs sans utiliser de parenthèses. Cette notation a été utilisée ar certaines calculatrices, notamment de Hewlett-Packard.
Exemple : calcul de 7 8 * 2 +

  • On lit les deux premiers nombres et l'opérateur, on calcule 7*8 = 56
  • On garde le 56 en tête, on lit le nombre et l'opérateur suivant : 56 + 2 = 58 qui est le résultat du calcul

Pour cet exercice, on n'utilisera que des nombre positifs et pas de division (pour éviter la division par 0) . L'évaluation d'une expression est simple et utilise une pile :

  • Initialement la pile est vide
  • Si on trouve un nombre, on l'empile
  • Si on trouve un opérateur, on dépile deux fois pour trouver les deux opérandes (attention à l'ordre pour la soustraction, non symétrique). On effectue l'opération, et on empile le résultat
  • Le résultat de l'opération se lit en sommet de pile.
  1. Sur papier, donner le résultat de 1 2 3 4 + 5 - 7 + . Ecrire ce calcul sous forme infixe (c'est-à-dire de la manière usuelle avec les parenthèses).
  2. Ecrire une fonction Python qui, étant donnée une chaîne de caractères exprimant un calcul sous forme postfixe, donne le résultat du calcul, sous les préconditions : nombres positifs, pas de division, expression "bien formée". La tester. Rappel : la méthode split permet d'obtenir une liste comportant les différents "mots" d'une chaîne de caractères. Utilisée sans arguments, le séparatuer est l'espace : 'un deux trois'.split() renvoie ['un', 'deux', 'trois'].
In [ ]:

Files

Une file est une structure linéaire où les insertions et les suppressions se font à l'opposé l'une de l'autre, à l'image d'une file d'attente : le premier arrivé est le premier servi. Les piles sont appelées FIFO ou queue en anglais (first in, first out).

Une interface possible d'une file est :

Fonction Description
creerFile() $\rightarrow$ Pile Créer une file vide
estFileVide(f) $\rightarrow$ Booléen Teste si la file f est vide
enfiler(f , élément) Insère élément en queue de f
defiler(f) $\rightarrow$ élément Enlève l'élément aen tête de la file f et le renvoie
tete(f) $\rightarrow$ élément Renvoie l'élément en tête de la file f

Exercices Files 1

  1. Dans quel état se trouve une pile vide après les opérations suivantes
    • enfiler(1)
    • enfiler(2)
    • défiler
    • enfiler(3)
    • enfiler(4)
    • enfiler(5)
    • défiler
    • défiler
      Comparer avec l'exercice correspondant sur les piles
  2. Créer le type File, le tester. Si vous avez implémenté ce type d'une manière différente de votre voisin, vous pouvez tester et comparer l'efficacité de vos implémentations avec %timeit (mon_test(...))
In [ ]:

Exercices Files 2

3 . Ecrire un programme qui permet de retourner une pile, en utilisant uniquement une file.

Exercices complémentaires

Dans ces exercices, la structure de données à utiliser parmi liste, pile et file n'est pas précisée : c'est à vous de la déterminer.

  1. Bon parenthésage. On donne une chaîne de caractères dans laquelle figurent des parenthèes ouvrantes (, fermantes ), et de même pour les crochets [et ]. Ecrire une fonction qui vérifie le bon parenthésage de l'expression. ([()])est bien parenthésée, ([()] et ([(])) ne le sont pas (il manque une )dans le premier cas, et dans le deuxième )et ]sont inversés)
  2. Problème de Flavius Josèphe. Flavius Josèphe est un historiographe romain juif du 1er siècle, dont l'oeuvre historique est sujette à caution. Il a donné la première version du problème suivant : "41 soldats juifs, cernés par des soldats romains, décident de former un cercle. Un premier soldat est choisi au hasard et est exécuté, le troisième à partir de sa gauche (ou droite) est ensuite exécuté. Tant qu'il y a des soldats, la sélection continue. Le but est de trouver à quel endroit doit se tenir un soldat pour être le dernier. Josèphe, peu enthousiaste à l'idée de mourir, parvint à trouver l'endroit où se tenir. Quel est-il ?"
    Variante : 42 soldats juifs, deux survivants, et les romains en tuent un sur trois.
In [ ]:

Sources :

  • cours de Clémentine Nebut, Université de Montpellier II
  • Wikipedia
  • Types de Données et Algorithmes, C. Froidevaux, MC Gaudel, M Soria
  • Eléments d'Algorithmique, D. Beauquier, J. Berstel, Ph. Chrétienne
  • Document d'accompagnement éduscol Terminale NSI

[![Licence CC BY NC SA](https://licensebuttons.net/l/by-nc-sa/3.0/88x31.png "licence Creative Commons CC BY SA")](http://creativecommons.org/licenses/by-nc-sa/3.0/fr/)
Frederic Mandon, Lycée Jean Jaurès - Saint Clément de Rivière - France (2015-2019)