Une structure de données est dite linéaire si on peut la représenter sous forme linéaire ( en ligne ).

Les files et les piles vues dans le cours sd1 sont des structures linéaires

Un exemple de file :

un exemple de pile :

  1. Nous verrons par la suite des structures non linéaires :

    Arbre :

    Graphe :

  2. Dans ce cours, nous allons voir deux autres structures linéaires les listes et les dictionnaires.

Le type abstrait : liste

Liste

Une liste est une structure de données d'éléments indicés à partir de 0. Dans cette structure de données, il est possible d'ajouter et supprimer des éléments à une liste.

$L=\{Bob;x;A7;1011;f\}$

Dans cette liste, l'élément indicé 2 est A7

Cette liste dispose de 5 éléments

Interface d'une liste

$L=\{Bob;x;A7;1011;f\}$

On donne $L=\{NSI;plaisir; jeux;livres; \pi; E0F1\}$

Expliciter ce que font chacune des commandes suivantes :

  1. $ajouteEnFin(33,L)$ .
  2. $dernier(L)$.
  3. $debut(L)$ .
  4. $supprDernier(L)$.
  5. $taille(L)$.
  6. $get(2,L)$.

Les piles et les files sont des listes particulières, elle répondent à des problèmes où des structures de type LIFO FIFO sont adaptées.

Implémentation des listes avec des tableaux dynamiques

Tableaux dynamiques.

Les tableaux ont des tailles fixes alors que les listes non. C'est pour ça qu'il nous faut des tableaux dynamiques.

Tableaux dynamiques

Un tableau dynamique est un tableau dont la taille peut varier. Ainsi, si on a besoin d'ajouter un élément à un tableau, on crée un nouveau tableau plus grand, on copie les éléments de l'ancien tableau dans le nouveau, on ajoute le nouvel élément à la fin, on remplace l'ancien tableau par le nouveau, et enfin on supprime l'ancien tableau.

Les opérations possibles avec le tableaux dynamiques :

Implémentation des listes.

C'est l'implémentation choisie par le langage Python pour intégrer les listes.

Cette implémentation est efficace pour accéder à des éléments de la liste mais l'est beaucoup moins pour insérer des éléments. En effet insérer un élément oblige à décaler tous les éléments un par un. C'est pourquoi une autre implémentation est possible celle avec les listes chaînées.

Implémentation de listes avec des listes simplement chaînées.

Listes simplement chainées.

liste simplement chaînée

Une liste simplement chaînée est une structure de données dans laquelle les objets sont arrangés linéairement. Toutefois, contrairement au tableau, pour lequel l’ordre linéaire est déterminé par les indices, l’ordre d’une liste chaînée est déterminé par un pointeur dans chaque objet.

A partir d'un élément $x$ d'une liste simplement chainées, on peut accéder à l'élément suivant, noté $succ[x]$.

Chaque élément $x$ d’une liste simplement chaînée L est un objet comportant 2 champs : un champ clé (le nom de la variable qui contient la donnée) noté $clé[x]$ et un deuxième champ pointeur noté $pointeVers[succ[x]]$ qui pointe vers le prochain élément de la liste.

On peut ainsi noté un élément $x$ d'une liste L ainsi : $(cle[x],pointeVers[succ[x]])$.

A chaque liste $L$, on peut disposer de sa tête : on notera $tete[L]$ le premier élément d'une liste.

On notera NIL la valeur du pointeur qui ne pointe sur rien. Ce sera le marqueur de fin de la liste.

Ainsi les données : $\{\alpha; \gamma; \phi; \beta\}$ peut être représentées avec une liste simplement chaînée ainsi :

liste_image

Il faut avoir en tête que la modification d'un pointeur a un coût très inférieur à la réaffectation d'un élément.

Interface des listes

L'interface des listes se compose des opérateurs suivants :

La liste vide est composée d'un premier champ clé vide et d'un second champ NIL.

On propose la fonction $mystere(L,i)$ où $L$ est une liste et $i$ une clé de cette liste suivante écrit en pseudo code :

1. mystere(L,i)
2. x=tete[L]
3. si cle[x]==i 
4.     tete[L]=succ[x]
5. sinon 
6.     tant que cle[x]!=i et pointeVers[succ[x]]!=NIL
7.         y=x 
8.         x=succ[x]
9.     fin tant que
10.     pointeVers[succ[y]]=pointeVers[succ[x]]

  1. appliquer $mystere(L,cle[\alpha])$ et $mystere(L,cle[a])$ sur la liste représenter ici
  2. Proposer un nom pour la fonction $mystere$.

On propose la fonction $mystere(L,k)$ où $L$ est une liste et $k$ une clé de cette liste suivante écrit en pseudo code :

mystere(L,k) 
x=tete[L]
tant que cle[x]!=k et pointeVers[succ[x]]!=NIL
   x=succ[x]
fin tant que
retourner x
                            

  1. appliquer $mystere(L,cle[\alpha])$ et $mystere(L,cle[a])$ sur la liste représenter ici
  2. Proposer un nom pour la fonction $mystere$.

Ecrire en pseudo code les fonctions suivantes :

  1. $longueur(L)$ : qui renvoie le nombre d'élément dans la liste.
  2. $insererEnDebut(L,x)$ : L'élément $x$ (de la forme ($clé[x]$,$succ[x]$)) est inséré à la tête de la liste.
  3. $inserer(L,a,e)$ : L'élément $e$ est inséré après l'élément de clé $a$ présent dans la liste L.

SOLUTION

  1. longueur(L) 
    longueur=1
    x=tete[L]
    tant que pointeVers[succ[x]]!=NIL
       x=succ[x]
       k=k+1
    fin tant que
    retourner k
                                
  2. insererDebutListe(L,x) 
    pointeVers[succ[x]]=pointeVers[tete[L]]
    tete[L]=x
                                
  3. inserer(L,a,e) 
    x=tete[L]
    tant que cle[x]!=a:
        x=succ[x]
    fin tant que
    pointeVers[succ[e]]=pointeVers[succ[x]]
    pointeVers[succ[x]]=pointeVers[e]
                                

Implémentation des listes avec des listes simplement chainées.

L'objectif de cette partie est d'écrire les éléments de l'inerface d'une liste :

à l'aide des éléments vus dans la partie précédente.

Ecrire chaque élément de l'interface à l'aide des fonctions écrites dans la partie suivante.

CORRECTION :

Implémentation de l'objet liste simplement chainée en Python à partir des listes de Python

Créer la classe ListeSimpleCh qui possède comme attribut un objet de type list et sa tête à partir des listes en Python. On donne Le constructeur __init__(self,l,tete) avec deux attributs une liste $l$ et une $tete$ :

class ListeSimpleCh():
    """définition de l’objet liste"""
    
    def __init__(self,l,tete):
        self.l = l
        self.t=tete
    

Créer une instanciation de la classe ListeSimpleCh avec la liste [1,'bos',4,"BG",0]. Afficher la tete de liste.

Vous devez ajouter à cette classe :

Ecrire les fonctions suivantes en Python à partir de la classe définie précédemment

  1. $supprimer(L,i)$ : L'élément de clé i est supprimé de la liste.
  2. $rechercheListe(L,k)$ : qui retourne l'index du premier objet de clé k.
  3. $longueur(L)$ : qui renvoie le nombre d'élément dans la liste.
  4. $insererEnDebut(L,x)$ : L'élément $x$ est inséré à la tête de la liste.

Faire une classe Liste qui s'approche plus des listes. Un constructeur qui créé une liste vide et une méthode qui ajoute un élément.

Les dictionnaires

Dictionnaires

Un dictionnaire est une structure de données qui permet d'associer une valeur à une clé. Cette clé peut être un mot ou un entier. l'ensemble clé-valeur est appelé entrée.

prendre une autre numération, désordre

On peut modéliser un individu d'un répertoire téléphonique avec un dictionnaire. On pourrait prendre comme clé : nom et téléphone.

Rendez vous sur le cours de première pour retravailler l'ensemble des notions concernant les dictionnaires en Python.

Exercices

Préciser quelle est la structure de donnée à privilégier pour chacune de ces taches :

  1. Représenter un répertoire téléphonique.
  2. Stocker l'historique des actions effectuées dans un logiciel et disposer d'une commande Annuler.
  3. Envoyer des fichiers au serveur impression.
  4. On souhaite stocker un texte très long que l'on souhaite pouvoir modifier

Correction :

  1. On choisit le dictionnaire. Les clés seraient par exemple : nom, prénom, téléphone
  2. On se retrouve à avoir une structure de donnée du type LIFO on prend donc une pile.
  3. On se retrouve à avoir une structure de donnée du type FIFO on prend donc une file.
  4. liste en implantation simplement chainée

Dans chacun des cas suivants, déterminez quelle structure de données est la plus adaptée :

  1. Gérer le flux des personnes arrivant à la caisse d'allocations familiales ;
  2. Mise en place d'un mécanisme annuler/refaire pour un traitement de texte ;
  3. Garder les nombres premiers parmi les nombres de 2 à 1000 en utilisant la méthode du crible d'Eraosthène.
  4. Lors d'une partie échec, on veut enregistrer l'ensemble des coups joués et pouvoir les consulter.

La pile et la poo

Voila une définition de la classe pile en Python :

class Pile:
    def __init__(self,haut,reste=None):
        self.h=haut
        self.r=reste
    def estVide(self):
        if self.h==None:
            return True
        else:
            return False
    def empiler(self,valeur):
        self.r=Pile(self.h,self.r)
        self.h=valeur
    
    def depiler(self):
        if self.r==None:
            haut=self.h
            self.h=None
            return haut
        else:
            haut=self.h
            self.h=self.r.h
            self.r=self.r.r
            return haut
    def affiche(self):
        if self.r==None:
            print(self.h)
        else:
            Pile.affiche(self.r)
            print(self.h)

On considère la pile : P=("bob",(3,("nsi",(5,("vacances",vide)))))

  1. Créer une pile vide est testée qu'elle est bien considérée comme vide.
  2. Implémenter P sur votre machine en utilisant les méthodes (constructeurs et modificateurs) de la classe Pile.
  3. Améliorer la méthode affiche pour quelle affiche la pile dans le bon sens.
  4. Ecrire une fonction hauteur(P) qui renvoie la hauteur de la pile.
  5. Ecrire une fonction depil2(P) qui enlève de la Pile P l'élément situé en deuxième position de la pile et renvoie cet élément.
  6. Ecrire une fonction insere(P,elt) qui insère dans P l'élément elt à la position 2. On considère la position 1 correspond au haut de la pile.
  7. Ecrire une fonction acces(P,pos) qui renvoie l'élément situé en position "pos".

L'objet file en Python

Voila une définition de l'objet file en Python ( implémenter avec une liste doublement chainées)

On commence par définir un élément d'une liste doublement chainées :

class Element:
    #chaque élément a pour attribut : le precedent , le suivant et la valeur de l'élément
    def __init__(self,x):
        self.val=x
        self.precedent=None
        self.suivant=None
    def __str__(self): #methode qui permet de lance un print sur un tel objet
        return str(self.val)+"-"+str(self.suivant)

on définit ensuite l'objet file :

class File:
    #ici une file est la donnée de deux attributs : la file complète de type Element et le dernier élément de la file de type Element 
    def __init__(self):
        self.tete=None
        self.queue=None
    def enfile(self,x):
        e=Element(x) #on transforme l'élément à ajouter en un objet Element de listes doublement Chainées
        if self.tete==None:
            self.tete=e #file vide la tete est remplacée par l'élément e
        else:
            e.precedent=self.queue #le précédent de l'élément pointe sur l'ancienne queue de la file
            self.queue.suivant=e #l'ancienne queue de la file pointe sur e avec suivant
        self.queue=e #on redéfinit self.queue par e.
        
    def file_vide(self):
        return self.tete is None #renvoie True si None et False sinon
    
    def defile(self):
        if not self.file_vide():
            e=self.tete #on stocke l'élément à defiler
            if e.suivant is None: #cas où il n'y a qu'un élément 
                self.tete=None
                self.queue=None
            else:
                self.tete=e.suivant
                self.tete.precedent=None
            return e.val
        
    def __str__(self):
        return str(self.tete)

On considère la file : F=(5,11115,("vacances","Bob",7,"nsi",12))

Revoir l'implémentation de la file vue au cours sd1 en cas de besoin

  1. Identifier, dans l'exemple, la tête, la queue et le cœur de F.
  2. Créer une file vide et tester qu'elle est bien considérée comme vide.
  3. Implémenter F sur votre machine en utilisant les méthodes (constructeurs et modificateurs) de la classe File.
  4. Ecrire une fonction longueur(F) qui renvoie la longueur de la file.
  5. Ecrire une fonction affiche_coeur(F) qui affiche le coeur de la file.
  6. Ecrire une fonction defil2(F) qui enlève de la file F l'élément situé en deuxième position de la file et renvoie cet élément.
  7. Ecrire une fonction insere(F,elt) qui insère dans F l'élément elt à la position 2. On considère la position 1 correspond au haut de la file.
  8. Ecrire une fonction acces(F,pos) qui renvoie l'élément situé en position "pos".

Une vidéo pour vous aider :

Licence Creative Commons
Les différents auteurs mettent l'ensemble du site à disposition selon les termes de la licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International