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. Exercice : encapsulation dans une classe pile.

À faire dans le cahier.

class Truc:
    def __init__(self):
        self.__liste=[]

    def ajout(self,objet):
        self.__liste.insert(0,objet)

    def enleve(self):
        return self.__liste.pop()

    def nombre_objets(self):
        return len(self.__liste)

En considérant la classe Truc ci-dessus :

Comment qualifier l'attribut .__liste ?

nouvel_objet=Truc()
nouvel_objet.ajout(3)
nouvel_objet.ajout(2)
nouvel_objet.ajout(10)
print(nouvel_objet.enleve())
print(nouvel_objet.nombre_objets())

Qu'affiche le code suivant ?

Schématisez sur votre cahier la façon dont se comporte un objet de classe Truc.

Comment appelle-t-on cela dans la vie courante ?

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

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.
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.

4. Exemples :

Une liste en Python est une structure dynamique car on peut ajouter des données même après sa création.
Un tuple en Python est une structure statique.

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

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.
Une structure de données non linéaire est une structure de données qui n'est pas linéaire !

6. Exemples :

Une liste en Python est une structure linéaire.
Un arbre hiérarchique n'est pas une structure linéaire (en dehors de la liste chainée).
Un graphe n'est pas une structure linéaire.
Les listes chainées sont des structures linéaires.

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

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.
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.

8. Exemples :

Une liste en Python est une structure indexée par des nombres entiers.
Un arbre hiérarchique basique est une structure qui se lit en parcourant l'arbre.
Un graphe n'est pas une structure indexée.

9. Les tableaux.

Un tableau est une structure de données linéaire indexée.

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

10. Exercice : classe TableauStatique.

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

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 = ... self.__tab = ... def est_vide(self): ... def taille_tableau(self): return ... def change(self, i, data): ... def effacer(self, i): ... def connaitre(self, i): ... def affiche_tout(self): ... # Exemple d'utilisation t = TableauStatique(5) print(t.est_vide()) # True t.change(2, 10) print(t.connaitre(2)) # 10 t.affiche_tout() # [None, None, 10, None, 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())
print(p.est_vide())

14. Exercice : utilisation de la classe Pile.

Ci-dessous :

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.
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 : création de la classe File.

Créer la classe File contenant les méthodes suivantes :

enfiler(self, data) qui insère un objet dans la file
defiler(self) qui extrait le premier élément de la file
est_vide(self) qui teste si la file est vide
non_vide(self) qui teste si la file est non vide

class File: def __init__(self): pass # à compléter def enfiler(self, data): pass # à compléter def defiler(self): pass # à compléter def est_vide(self): pass # à compléter def non_vide(self): pass # à compléter

>>>

16. Exercice : utilisation de la classe File.

En utilisant la classe File :

Créer une fonction extraire(un_texte) qui prend un string et met chaque caractère dans une file.
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.
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: pass #copier/coller la classe de l'exercice précédent def extraire(un_texte): pass # à compléter def voyelle(une_file): pass # à compléter def plus_grande(une_file): pass # à compléter

>>>

17. 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 ....

>>>

18. 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]))

>>>