- matplotlib - numpy

Structures de données linéaires

Liste

1. Définitions

En algorithmique, une liste est une structure de données abstraite qui représente une collection ordonnée d'éléments. Chaque élément est identifié par sa position (son index) dans la liste.
Une liste peut être vide (ne contenant aucun élément) ou contenir un nombre quelconque d'éléments.
On appelle « tête » ou « head » le premier élément de la liste et « queue » la liste privée de son premier élément.

2. Opérations de listes (primitives de listes)

Les listes sont généralement des structures de données mutables, ce qui signifie que l'on peut modifier leurs éléments après leur création. Il est seulement possible d’ajouter et de lire une donnée en tête de la liste.
Ainsi, une liste est définie par les primitives suivantes :

  • cree_liste() : Crée une liste vide
  • is_empty(L) (est_vide(L)) : Renvoie True si la liste, L est vide, False sinon.
  • head(L) (est_la_tete(L)) : Renvoie la valeur de l'élément en tête de liste sans le supprimer.
  • queue(L) : Renvoie la liste L privé de son premier élément.
  • push(L, elt) (ajoute(L)) : Ajoute l'élément elt en tête de liste de la liste, L.

Attention : Ne pas confondre avec les listes Python !

3. Implantation d'une liste simple à l'aide d'une liste Python

La définition décrit comment une liste devrait fonctionner et quelles opérations elle devrait permettre, mais elle ne précise pas comment ces opérations doivent être réalisées en pratique. Les implémentations concrètes de listes peuvent varier en fonction des besoins et des contraintes de programmation, mais elles doivent respecter les principes fondamentaux de la structure de données abstraite de la liste.
Plusieurs implantations possibles : Implantation avec l'objet liste de Python.

#Créer une liste def cree_liste(): """Crée une liste vide.""" return [] def est_vide(L): """Renvoie True si la liste L est vide, False sinon.""" return len(L) == 0 def est_vide2(L): """Renvoie True si la liste L est vide, False sinon.""" return L == [] def est_vide3(L): """Renvoie True si L est vide, False sinon.""" if not L: return True return False def tete_liste(L): """ Renvoie la valeur de l'élément en tête de liste sans le supprimer. Si L est vide lève une exception. """ if est_vide(L): raise ValueError("La liste est vide : \ il y a un débordement négatif.") else: return L[0] def queue(L): """Renvoie la liste L privée de son premier élément. Lève une exception si la liste est vide. """ if est_vide(L): raise ValueError("La liste est vide !") return L[1:] #Entête : élément situé à l'extrémité gauche def insere_tete(L, elt): """ajoute elt à la tête de la liste L.""" L.insert(0, elt) return None

Application :

  1. Créer un objet liste, que l'on identifie par la variable ma_liste.
  2. À l'aide d'une boucle for insérer dans cet objet les nombres de 5 à 10.
  3. Avec ma_liste, tester les différentes primitives du type liste.
  4. Compléter la fonction ci-dessous.
def insere_avant(elt, i, L): """"Insère elt dans L avant l'élément situé à l'index i."""

Pile

1. Définition

Une pile (stack en anglais) est un type de données abstrait qui suit le principe du dernier entré, premier sorti (LIFO, Last-In-First-Out). Cela signifie que l'élément le plus récemment ajouté à la pile est le premier à être retiré. Il est nommé pile car il se comporte comme une pile d'objets du monde réel, où l'on ajoute un objet sur le dessus de la pile et retire toujours l'objet du dessus. Autrement dit, les insertions et suppressions se font toutes du même côté. À un moment donné, on ne peut accéder qu'à l'élément supérieur d'une pile.

2. Opérations de piles

  • cree_pile() : Crée une pile vide.
  • est_vide_pile(P) : Vérifie si la pile P est vide.
  • empile(P, elt) ou push(P, elt) : Insère l'élément elt au sommet de la pile P, lève une exception si la pile est pleine.
  • depile(P) ou pop(P) : Supprime et renvoie l’élément le plus haut de la pile P, lève une exception si la pile est vide.

Essayer d'insérer un élément dans une pile pleine provoque une erreur d'overflow (débordement positif).
Essayer de supprimer un élément d'une pile vide provoque une erreur d'underflow (débordement négatif).

image pile

Quelques primitives additionnelles

  • sommet_pile(P) ou top(P) ou peek(P) : Renvoie l’élément supérieur de la pile P sans le supprimer. On lève une exception si la pile est vide.
  • est_pleine(P) ou is_full(P) : Renvoie True si la pile P est pleine, False sinon.

3. Implantation d'une pile à l'aide d'une liste Python

pile def cree_pile(): """Crée une pile vide.""" pile = [] return pile def est_vide_pile(p): """ Renvoie True si la pile p est vide, False sinon. """ return len(p) == 0 def sommet(p): """ Renvoie (sans supprimer) l'élément au sommet (l'élément à l'extrême droite dans la liste Python). Lève une exception Vide si la pile p est vide. """ if est_vide_pile(p): raise ValueError("La pile est vide !") else: return p[-1] def empile(p, elt): """ Insère elt au sommet de la pile p (à l'extrême droite dans la liste Python). """ p.append(elt) return None # Dépiler def depile(p): """ Renvoie et supprime le sommet de la pile p (à l'extrême droite dans la liste Python). Lève une exception si la pile P est vide. """ if est_vide_pile(p): raise ValueError("La pile est vide !") else: return p.pop()

Application :

  1. Créer un objet pile que l'on référence par la variable ma_pile
  2. À l'aide d'une boucle for insérer dans cet objet les nombres de 5 à 10.

  3. 10
    9
    8
    7
    6
    5

    Tester les différentes primitives de listes.
  4. Compléter la primitive ci-dessous.
  5. Afficher les éléments de ma_pile, comme donné ci-contre :
  6. Écrire une fonction, inverse_pile qui prend en entrée une pile et renvoie une pile avec les mêmes éléments mais inversés.
def inverse_pile(p): """Inverse la pile p dans une autre pile."""

File

1. Définition

Contrairement aux piles, une file (queue en anglais) est ouverte à ses deux extrémités : une file est une structure de données linéaire où les insertions se font toutes d'un même côté (l'entrée de file) et les suppressions toutes de l'autre côté (la sortie de file). Elle suit donc le principe du « premier entré, premier sorti » en abrégé FIFO (First-In-First-Out).
Ainsi, une file comporte une tête, head, (le tout premier élément ajouté) et une queue (le dernier élément ajouté). Lorsqu’un élément est ajouté, il prend place à la queue de la file. L’élément retiré est toujours le premier en tête de la file.
Cette structure est nommée « file d’attente » car elle ressemble à une file d’attente réelle, c’est-à-dire des personnes qui attendent quelque chose dans une file d’attente. La première personne à rejoindre la file est également la première à être servie. Les noms spécifiques pour ces opérations sont enfile pour insérer et defile pour supprimer.

2. Opérations de files

  • enfile(F, elt) ou enqueue(F, elt) : Insère un élément à la fin de la file F.
  • defile(F) ou dequeue(F) : Renvoie et supprime l'élément en tête de la file F. Lève une exception si la file F est vide
la file

Quelques fonctions additionnelles

  • premier(F) : Renvoie (sans le supprimer) l’élément en tête de la file F. Lève une exception si la file F est vide.
  • est_vide(F) : Renvoie True si la file F est vide, False sinon.
  • taille_file(F) : Renvoie le nombre d'élément de la file F.

3. Applications des files

  • Utilisé pour mettre en œuvre des systèmes de mise en file d’attente (p. ex. files d’attente prioritaires).
  • Les serveurs d'impression, qui doivent traiter les requêtes dans l'ordre dans lequel elles arrivent, et les insèrent dans une file d'attente.
  • Certains moteurs multitâches, dans un système d'exploitation, qui doivent accorder du temps-machine à chaque tâche, sans en privilégier aucune.
  • Un algorithme de parcours en largeur d'un graphe utilise une file pour mémoriser les nœuds visités

4. Implantation d'une file

4.1. À l'aide d'une liste Python

Compléter les fonctions ci-après :

def cree_file(): """Crée une file vide.""" def enfile(F, elt): """ Insère elt à l'arrière de la file F (à l'extrême droite dans la liste Python). """ def est_vide_file(F): """Renvoie True si la file F est vide, False sinon.""" def defile(F): """ Renvoie et supprime le premier élément de la file F (l'élément le plus à gauche de la liste Python). Lève une exception si la pile est vide. """ def premier(F): """ Renvoie (sans supprimer) l'élément à l'avant (c'est-à-dire l'élément à l'extrême gauche dans la liste Python). Lève une exception Vide si la pile est vide. """

Exercice :
Écrire une fonction, inverse_file, qui prend en entrée une file et l'inverse dans une autre file grâce à une pile.

def inverse_file(f): """À l'aide d'une pile, inverse la file f dans une autre file."""
4.2. À l'aide de deux piles

L'idée de base est qu'une pile inverse l'ordre (contrairement à une file d'attente).
Une séquence d'éléments empilés dans une pile revient dans l'ordre inverse lorsqu'elle est dépiler. Par conséquent, deux piles enchaînées renverront des éléments dans le même ordre, puisque l'ordre inversé à nouveau inversé est l'ordre d'origine.
Pour une question de lisibilité, nous l'implémentons à l'aide d'un n-uplet nommé.
Par souci de cohérence avec la file précédente, la sortie est à gauche.
Opérations de cette file

def cree_file_de_piles(): """ Crée une file vide sous la forme d’un namedtuple composé de deux piles. La première pile correspond à la pile de sortie, la seconde à celle d'entrée. """ from collections import namedtuple PE = cree_pile() PS = cree_pile() File = namedtuple("File", "PS PE") return File(PS, PE) def taille_file_de_piles(F): """Renvoie le nombre d’éléments contenus dans la file F""" return taille_pile(F.PE) + taille_pile(F.PS) def est_vide_file_de_piles(F): """ Renvoie True si F est vide, False sinon. """ return est_vide_pile(F.PE) and est_vide_pile(F.PS) def enfile_file_de_piles(F, elt): """Insère elt à l'arrière (à l'entrée) de la file F.""" empile(F.PE, elt) return None

Défiler un élément de cette file
L'algorithme :

  • Si la pile de sortie n'est pas vide, dépiler la pile de sortie.
  • Sinon (si la pile de sortie est vide), alors
    • transférer tous les éléments de la pile d'entrée dans la pile de sortie et dépiler la pile de sortie.
    • si la pile d'entrée est aussi vide, lever une exception.
def reorganise_file_de_piles(F): """ Transfère les éléments de la pile d'entrée vers la pile de sortie si la pile de sortie est vide. """ if est_vide_pile(F.PS):#est_vide est une opération de pile while not est_vide_pile(F.PE): e = depile(F.PE) empile(F.PS, e) return None def defile_file_de_piles(F): """ Renvoie et supprime le premier élément de la file F. Lève une exception si la file F est vide. """ if est_vide_file_de_piles(F): raise ValueError("La file F est vide !") else: # On réorganise la file F, si nécessaire reorganise_file(F) depile(F.PS)

Application :

  1. Compléter la fonction premier_file_de_piles, ci-après.
  2. Créer une file implémentée grâce à deux piles que l'on référencera par la variable file_test. 
  3. On donne :
VOYELLES = "aeiouy"
Écrire un code qui permet d'insérer chacune des lettres de VOYELLES dans file_test.
  4. Afficher l'objet identifié par la variable file_test puis ses piles d'entrée et de sortie.
  5. Tester les différentes fonctions créées.
def premier_file_de_piles(F): """ Renvoie (sans supprimer) le premier élément de la file F. Lève une exception si la file est vide. """