Chapitre 3 : Structures de données.

Introduction :

Pour ranger ses affaires, on choisit le bon contenant : une pile d'assiettes, une file d'attente, un agenda.

En informatique, c'est pareil : selon ce que l'on veut faire des données, une organisation sera bien plus commode qu'une autre.

1. Activité : une mystérieuse classe Truc.

À faire dans le cahier.

L'éditeur contient une classe Truc et quelques lignes qui l'utilisent.

Tu n'as pas besoin de comprendre le code de la classe : on va seulement observer comment se comporte un objet Truc quand on l'utilise.

  1. Exécute le programme : il ajoute cinq prénoms dans t. Dans la console sous l'éditeur, tape ensuite plusieurs fois t.enleve(). Quel prénom sort à chaque appel ? Ajoute d'autres prénoms avec t.ajout(…), enlève-en encore, puis énonce la règle.
  2. Schématise dans ton cahier le comportement d'un objet de classe Truc. Où rencontre-t-on ce fonctionnement dans la vie courante ?
  3. En anglais, on résume cette règle par l'acronyme FIFO : First In, First Out. Traduis-le et explique pourquoi il décrit bien la classe Truc.
class Truc: class Maillon: def __init__(self, valeur): self.valeur = valeur self.suivant = None def __init__(self): self.sortie_file = None self.entree_file = None def ajout(self, objet): nouveau = self.Maillon(objet) if self.est_vide(): self.sortie_file = nouveau else: self.entree_file.suivant = nouveau self.entree_file = nouveau def enleve(self): objet = self.sortie_file.valeur self.sortie_file = self.sortie_file.suivant if self.sortie_file is None: self.entree_file = None return objet def est_vide(self): return self.sortie_file is None t = Truc() t.ajout("Alice") t.ajout("Bob") t.ajout("Chloé") t.ajout("David") t.ajout("Emma")


    
>>>

2. Structures de données

En informatique, que cela soit pour les ordinateurs personnels, les smartphones, les serveurs ou tout autre matériel numérique, nos programmes manipulent un ordre considérable de données

Les programmes actuels structurent leurs données dans les algorithmes.

Il y a plusieurs façons de structurer les données au niveau logiciel.

3. Les structures statiques et dynamiques

Avant de ranger des données, il faut se poser une question : leur nombre peut-il changer en cours de route ?

  • Une structure de données statique est un ensemble de données dont la taille est fixée lors de la création de la structure. Ensuite, le nombre de cases ne change plus : on peut seulement changer ce qu'elles contiennent. Une case inoccupée contient une valeur spéciale, par exemple None en Python.
  • Une structure de données dynamique est un ensemble de données dont la taille peut varier après la création de la structure : elle grandit quand on ajoute, elle rétrécit quand on retire.

Pense au parking du lycée : il a 5 places, ni plus ni moins, qu'elles soient libres ou occupées : c'est une structure statique. Une file d'attente à la cantine, elle, s'allonge et se raccourcit sans cesse : c'est une structure dynamique.

Pourquoi ne pas tout faire en dynamique ? Parce que la souplesse a un prix : une structure statique réserve sa place en mémoire une fois pour toutes, c'est simple et rapide. Une structure dynamique oblige la machine à trouver de la place à chaque fois qu'elle grandit (on le verra avec les tableaux).

Dans l'animation, le tableau statique t naît avec 4 cases vides (None), la liste l naît vide. On range les mêmes valeurs dans les deux, puis on en retire : observe leur taille.

Tableau statique de 4 cases
Liste (structure dynamique)
élément rangé élément retiré opération refusée

4. Exemples :

5. Structures linéaires et non linéaires.

Pour savoir si une structure est linéaire, place-toi sur un élément et demande-toi : quel est l'élément juste avant ? Et celui juste après ?

  • Une structure de données linéaire est une structure où les données sont placées les unes à la suite des autres. Chaque élément a un seul prédécesseur hormis la première donnée et chaque élément a un seul successeur hormis la dernière donnée. On peut donc toujours les aligner sur une seule ligne : il y a un premier, un dernier, et un seul chemin pour aller de l'un à l'autre.
  • Une structure de données non linéaire est une structure de données qui n'est pas linéaire ! Il suffit qu'un élément ait plusieurs successeurs (un dossier contient plusieurs fichiers : c'est un arbre) ou que les éléments soient reliés dans tous les sens, au point de pouvoir tourner en rond (un réseau de routes entre des villes : c'est un graphe).

Dans l'animation, cinq structures se présentent l'une après l'autre. Pour chacune, on observe un élément à la fois (en jaune), avec son prédécesseur (en vert) et ses successeurs (en bleu), puis on la range dans la bonne colonne.

élément observé prédécesseur successeur / voisin
Linéaire
Non linéaire

6. Exemples :

7. Structures indexées et non indexées.

Ici, la question est : pour atteindre un élément précis, faut-il passer par les autres ?

  • Une structure de données indexée (ou à accès par clef) est une structure où les données sont accessibles immédiatement sans forcément avoir à parcourir d'autres données. Chaque élément a un numéro (son indice) ou une clef qui permet d'aller directement à lui, comme un casier numéroté au vestiaire. En Python, l[4] donne tout de suite l'élément d'indice 4 d'une liste, même si elle en contient un million.
  • Une structure de données non indexée est une structure où l'accès à certaines données se fait en parcourant d'autres données. Comme dans un train dont on ne peut pas sortir : pour aller au 4e wagon, il faut traverser les trois premiers.

La classe Truc de l'activité est non indexée : on ne peut obtenir que le premier prénom entré. Pour atteindre le 4e, il faut d'abord passer par les trois premiers.

Dans l'animation, une structure indexée et une structure non indexée contiennent les mêmes valeurs. On leur demande le même élément : compte les étapes de chacune.

Structure indexée
Structure non indexée
élément examiné (cerclé : déjà parcouru) élément cherché, trouvé

8. Exemples :

9. Les tableaux.

Un tableau est une suite finie d'éléments, repérés par un indice entier allant de 0 à n − 1, auxquels on accède directement grâce à cet indice. C'est donc une structure linéaire (les indices ordonnent les éléments) et indexée (accès immédiat).

Il faut faire attention au contexte pour savoir si c'est une structure statique ou dynamique :

  • dans certains langages (comme le C), un tableau est statique : sa taille est choisie à la création et ne change plus (c'est le TableauStatique de l'exercice suivant) ;
  • en Python, une list est un tableau dynamique : on peut lui ajouter des éléments avec append ou en retirer avec pop.

Dans l'animation, on demande plusieurs éléments du tableau t par leur indice : observe comment chacun est trouvé, puis ce qui se passe quand l'indice dépasse n − 1.

Tableau t de 8 éléments (indices sous les cases)
élément de t élément demandé indice inexistant

10. Exercice : classe TableauStatique.

Le parking du lycée compte exactement 5 places numérotées de 0 à 4. Ce nombre ne changera jamais : on ne peut ni ajouter ni retirer de place. Pour chaque place, on veut savoir quelle voiture l’occupe (sa plaque d’immatriculation) ou si elle est libre (None). On accède directement à une place par son numéro, sans parcourir les autres.

Une liste Python, qui peut grandir avec append, ne convient donc pas tout à fait : il nous faut un tableau statique, dont la taille est fixée une fois pour toutes à sa création.

On souhaite créer une classe TableauStatique qui permet de créer un objet de type statique, indexé et linéaire.

Le squelette de la classe est déjà écrit : complète chaque ... dans l’éditeur.

Le tableau doit avoir les caractéristiques suivantes :

  • La taille est fixée à la création avec __init__(self, taille).
  • À l’initialisation, le tableau est rempli avec des None (attribut privé).
  • L'attribut privé __tab est une liste qui contiendra les données du tableau.
  • L’attribut __taille est privé et correspond à la taille du tableau
  • La méthode taille_tableau(self) retourne la taille du tableau.
  • La méthode est_vide(self) renvoie True si le tableau est composé uniquement de None, False sinon.
  • La méthode change(self, i, data) change l’élément d’indice i en data.
  • La méthode effacer(self, i) remplace l’élément d’indice i par None.
  • La méthode connaitre(self, i) renvoie le contenu de l’élément à l’indice i.
  • La méthode affiche_tout(self) affiche le contenu complet du tableau.
class TableauStatique: def __init__(self, taille): self.__taille = ... # la taille reçue en paramètre self.__tab = [...] * taille # une liste remplie de None def taille_tableau(self): return self.__... def est_vide(self): for element in self.__tab: if element != ...: return ... return ... def change(self, i, data): self.__tab[...] = ... def effacer(self, i): self.__tab[i] = ... def connaitre(self, i): return self.__tab[...] def affiche_tout(self): print(self.__...) # Exemple d'utilisation # Le matin, le parking du lycée est vide. parking = TableauStatique(5) print(parking.taille_tableau()) # 5 places print(parking.est_vide()) # True # Deux voitures arrivent et se garent aux places 0 et 3. parking.change(0, "AB-123-CD") parking.change(3, "EF-456-GH") print(parking.est_vide()) # False # Qui est garé à la place 3 ? La place 1 est-elle libre ? print(parking.connaitre(3)) # EF-456-GH print(parking.connaitre(1)) # None # La voiture de la place 0 repart. parking.effacer(0) parking.affiche_tout() # [None, None, None, 'EF-456-GH', None]


    
>>>

11. La file.

Une file est une structure de données linéaire, non indexée, qui peut être dynamique et où l'élément que l'on peut sortir est le premier à être rentré (FIFO : First In, First Out).

C'est le principe d'une file d'attente à une caisse : le premier client arrivé est le premier servi. Observe l'animation ci-dessous : les éléments entrent par l'arrière (à gauche) et sortent par l'avant (à droite).

Entrée (enfiler) →Sortie (défiler) →
élément qui entre élément qui attend élément qui sort

Regarde bien : le premier entré est toujours le premier sorti.

12. La pile.

Une pile est une structure de données linéaire, non indexée, qui peut être dynamique et où l'élément que l'on peut sortir est le dernier à être rentré (LIFO : Last In, First Out).

C'est le principe d'une pile d'assiettes : on pose une assiette au sommet, et on reprend toujours celle du sommet. Observe l'animation ci-dessous : les éléments entrent et sortent par le haut.

Ce sont exactement les mêmes valeurs que dans la file plus haut, qui entrent au même moment : compare ce qui sort de chaque structure !

Entrée (empiler) et sortie (dépiler) par le sommet ↓↑
élément qui entre élément empilé élément qui sort

Regarde bien : le dernier entré est toujours le premier sorti.

13. Exemple: La pile dans Python

Par exemple, les piles et les files ne sont pas présentes dans Python.

On peut toutefois créer cet objet avec par exemple la classe Pile ci-dessous :

class Pile:
    def __init__(self):
        self.tablo = []

    def empiler(self, data):
        self.tablo.append(data)

    def depiler(self):
        return self.tablo.pop()

    def est_vide(self):
        return self.tablo == []


p = Pile()
p.empiler(2)
print(p.depiler())   # 2
print(p.est_vide())  # True

14. Exercice : utilisation de la classe Pile.

Ci-dessous :

  1. Créer une fonction caracteres_dans_pile qui prend comme paramètre un string et renvoie une pile contenant les caractères (un par un) de ce string.
  2. Créer une fonction nb_espaces qui prend comme paramètre une pile contenant des caractères et renvoie le nombre de fois où le caractère espace apparait sous la forme d'un integer.

    La pile peut être détruite dans le processus.

class Pile: def __init__(self): self.tablo = [] def empiler(self, data): self.tablo.append(data) def depiler(self): return self.tablo.pop() def est_vide(self): return self.tablo==[] def caracteres_dans_pile(texte): pass def nb_espaces(pile): pass


    
>>>

15. Exercice : utilisation de la classe File.

L’éditeur contient la classe Truc de l’activité 1, renommée cette fois File avec le vocabulaire habituel des files (lis sa documentation) : enfiler(objet) ajoute un élément à la fin, defiler() retire et renvoie le premier élément entré et est_vide() teste si la file est vide.

En utilisant cette classe File :

  1. Créer une fonction extraire(un_texte) qui prend un string et met chaque caractère dans une file.
  2. Créer une fonction voyelle(une_file) qui prend une file qui contient des caractères et renvoie un integer correspondant au nombre de voyelles présentes dans la file.

    La file pourra être détruite dans le processus.

  3. Créer une fonction plus_grande(une_file) qui prend une file composée uniquement d’entiers et renvoie le plus grand nombre de la file.
class File: """ Classe File : structure linéaire FIFO (First In, First Out). Le premier élément entré est le premier élément sorti, comme dans une file d'attente. Utilisation : f = File() crée une file vide f.enfiler(x) ajoute l'élément x à la fin de la file f.defiler() retire le premier élément de la file et le renvoie (la file ne doit pas être vide) f.est_vide() renvoie True si la file est vide, False sinon Exemple : >>> f = File() >>> f.enfiler("a") >>> f.enfiler("b") >>> f.defiler() 'a' >>> f.est_vide() False """ class Maillon: def __init__(self, valeur): self.valeur = valeur self.suivant = None def __init__(self): self.sortie_file = None self.entree_file = None def enfiler(self, objet): nouveau = self.Maillon(objet) if self.est_vide(): self.sortie_file = nouveau else: self.entree_file.suivant = nouveau self.entree_file = nouveau def defiler(self): objet = self.sortie_file.valeur self.sortie_file = self.sortie_file.suivant if self.sortie_file is None: self.entree_file = None return objet def est_vide(self): return self.sortie_file is None def extraire(un_texte): pass # à compléter def voyelle(une_file): pass # à compléter def plus_grande(une_file): pass # à compléter


    
>>>

16. Exercice : (sujet 08 - 2025) vérification du bon parenthésage avec une pile.

On considère des chaînes composées uniquement de parenthèses ouvrantes '(' et fermantes ')'.

Un parenthésage est correct si :

  • le nombre de parenthèses ouvrantes est égal au nombre de parenthèses fermantes ;
  • en parcourant la chaîne de gauche à droite, on n’a jamais plus de parenthèses fermées que ouvertes.

Cette fonction utilise une pile et suit le principe suivant : en parcourant la chaîne de gauche à droite, si on trouve une parenthèse ouvrante, on l’empile au sommet de la pile et si on trouve une parenthèse fermante, on dépile (si possible) la parenthèse ouvrante stockée au sommet de la pile.

La chaîne est alors bien parenthésée si, à la fin du parcours, la pile est vide.

Elle est, par contre, mal parenthésée :

  • si dans le parcours, on trouve une parenthèse fermante, alors que la pile est vide ;
  • ou si, à la fin du parcours, la pile n’est pas vide.

Compléter la fonction bon_parenthesage(ch) ci-dessous :

>>> bon_parenthesage("((()())(()))")
True
>>> bon_parenthesage("())(()")
False
>>> bon_parenthesage("(())(()")
False
class Pile: def __init__(self): self.contenu = [] def est_vide(self): return self.contenu == [] def empiler(self, v): self.contenu.append(v) def depiler(self): assert not self.est_vide() return self.contenu.pop() def bon_parenthesage(ch): """Renvoie True si la chaîne ch est bien parenthésée, False sinon.""" p = Pile() for c in ch: if c == ...: p.empiler(c) elif c == ...: if p.est_vide(): ... else: ... return ....


    
>>>

17. Exercice : (sujet 21 - 2025) Piles — renverse et positifs

Cet exercice utilise des piles qui seront représentées par des listes Python.

Si pile est une pile, alors pile == [] indique si la pile est vide, pile.pop() retire et renvoie le sommet de la pile et pile.append(v) ajoute la valeur v au sommet de la pile.

Si on considère qu’une fonction manipule une pile, elle ne peut pas utiliser d’autres opérations que celles décrites ci-dessus.

On cherche à écrire une fonction positifs qui prend une pile de nombres entiers en paramètre et qui renvoie une nouvelle pile contenant les entiers positifs de la pile initiale, dans le même ordre, quitte à modifier la pile initiale.

Pour cela, on va également écrire une fonction renverse qui prend une pile en paramètre et qui renvoie une nouvelle pile contenant les mêmes éléments que la pile initiale, mais dans l’ordre inverse. Cette fonction sera également amenée à modifier la pile passée en paramètre.

Compléter le code Python des fonctions renverse et positifs ci-après.

Exemples :

>>> renverse([1, 2, 3, 4, 5])
[5, 4, 3, 2, 1]
>>> positifs([-1, 0, 5, -3, 4, -6, 10, 9, -8])
[0, 5, 4, 10, 9]
>>> positifs([-2])
[]
def renverse(pile): '''renvoie une pile contenant les mêmes éléments que pile, mais dans l'ordre inverse. Cette fonction détruit pile.''' pile_inverse = ... while pile != []: ....append(...) return ... def positifs(pile): '''renvoie une pile contenant les éléments positifs de pile, dans le même ordre. Cette fonction détruit pile.''' pile_positifs = ... while pile != []: ... = pile.pop() if ... >= 0: ... return ... #print(renverse([1, 2, 3, 4, 5])) #print(positifs([-3, 4, 7, 9, -5, -8, 3]))

    
>>>