structure de données abstraites linéaires I

Objectifs :

• Distinguer des structures par le jeu des méthodes qui les caractérisent.
• Choisir une structure de données adaptée à la situation à modéliser.
• Spécifier une structure de données par son interface.
• Distinguer interface et implémentation.
• Écrire plusieurs implémentations d’une même structure de données.

1. Définitions

1.1. Structures de données

Dans un programme, une fois les données définies, on a besoin d’un mécanisme pour les stocker et les manipuler efficacement.
Une structure de données est donc une manière particulière d’organiser et de traiter des données dans un ordinateur.
Exemples : les tableaux, les fichiers, les listes, les piles, les arbres, etc.
En fonction de l'organisation des éléments, les structures de données sont classées en deux types :

• structures de données linéaires :
  
• Structures de données non linéaires :
  

1.2. Structures de données linéaires

On dit qu’une structure de données est linéaire lorsque :

• Les éléments sont accessibles dans un ordre séquentiel (un élément après l’autre)
  
• Les données suivent un ordre logique (ils sont numérotés).
  

Exemples : listes, piles (Stack), files (Queue)...

2. Structures de données Python

Le langage Python met à disposition plusieurs types de structures de données déjà prêts à l’emploi. On peut ainsi manipuler des séquences d’éléments avec des méthodes spécifiques.

2.1. Exemple avec une liste

# Création d’une liste
lst = [5, 3, 10, -7]

# Ajout d’un élément
lst.append(50)

# Accès par indice
print(lst[2])

# Suppression du dernier élément
lst.pop()

2.2. Exemple avec un dictionnaire

# Création d’un dictionnaire
dico_notes = {"Alice": 15, "Bob": 12, "eve": 18}

# Ajout d’une entrée
dico_notes["Dupond"] = 20

# Accès à la note de Bob
dico_notes["Bob"]

12

# Récupérer, dans une liste, toutes les clés
prenoms = list(dico_notes.keys())

2. Structures de données linéaires

2.1. Listes

2.2.1. Définitions

En algorithmique, une liste est une collection ordonnée d'éléments.

• Chaque élément est accessible par sa position (indice).
• On peut ajouter, supprimer ou modifier un élément.
• La longueur de la liste peut varier.

Une liste peut être vide ou contenir un nombre quelconque d'éléments.

2.2.2. Interface : Fonctions de listes

• obtenir(lst, i) : Renvoie l'élément de lst à la position i.
• est_vide(lst) (is_empty(lst)) : Renvoie True si lst est vide, False sinon.
• inserer(lst, x, i) : Insère x dans lst à la position i.
• supprimer(lst, i) : efface de lst l'élément à la position i.

Attention : Ne pas confondre avec les listes Python !

2.2.3. Implantation d'une liste avec l'objet liste de Python

#Créer une liste
def cree_liste():
    """Crée une liste vide."""
    return []

#Tester si une liste est vide
une_liste = cree_liste()

def est_vide(l):
    """Renvoie True si la liste L est vide, False sinon."""
    return L == []

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

une_liste = list(range(5, 10))

une_liste

is_empty(une_liste)

push(une_liste, 20)

est_la_tete(une_liste)

Application :

1. Créer une liste, ma_liste
2. À l'aide d'une boucle for insérer les nombres de 5 à 10.
3. Tester les différentes fonctions créées auparavant.
4. Compléter la primitive ci-dessous.

def insere_avant(elt, i, L):
    """"Insère après l'élément situé à l'index i."""
    
    return 

2.2. Pile

2.2.1. Définition

Une pile (stack en anglais) est une structure de données linéaire dans laquelle les insertions et suppressions se font au même bout de la séquence, qu’on appelle le sommet (top).
Elle suit le principe du dernier entré, premier sorti (LIFO, Last In First Out).

2.2.2. Interface : Fonctions de piles

• empiler(p, elt) ou push(p, elt) : Ajoute l'élément, elt, au sommet de la pile p. Lève une exception si la pile est pleine.
• depiler(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).

Quelques fonctions additionnelles

• est_vide(p) ou is_empty(p) : Renvoie True si la pile, p, est vide, False sinon.
• sommet(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.

Contrairement à la liste, on n’accède pas directement à un élément par son indice.
On est obligé de passer par le sommet.

2.3.3. Applications des piles

• Vérification de parenthèses bien formées
• Historique des pages visitées dans un navigateur
• Annuler une opération dans un éditeur de texte

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

def creer_pile():
    """Crée une pile vide."""
    return []

def empiler(p, elt):
    """Insère elt au sommet de la pile (à l'exrême droite dans la liste Python)."""
    p.append(elt)
    #return 

def est_vide_pile(p):
    """
        Renvoie True si la pile p est vide, False sinon.
    """
    return len(p) == 0

def est_vide_pile2(p):
    """
        Renvoie True si la pile p est vide, False sinon.
    """
    return p == []

def est_vide_pile3(P):
    """Renvoie True si L est vide, False sinon."""
    if not P:
        return True
    return False

# Dépiler
def depiler(p):
    """
        Renvoie et supprime le sommet de la pile p (à l'exrême droite dans la liste Python).
        Lève une exception si la pile est vide.
    """
    if est_vide_pile(p):
        raise ValueError("La pile est vide !")
    else:
        return p.pop()

def sommet_pile(p):
    """
        Renvoie (sans le supprimer) l'élément au sommet (l'élément à l'extême droite dans la liste Python).
        Lève une exception Vide si la pile est vide.
    """
    if est_vide_pile(p):
        raise ValueError("La pile est vide !")
    else:
        return p[-1]

une_pile = creer_pile()

for i in range(5, 10):
    empiler(une_pile, i)

depiler(une_pile)

9

Application :

1. Créer une pile, ma_pile.
2. À l'aide d'une boucle for insérer les nombres de 5 à 10.
3. Tester les différentes fonctions créées.
4. Compléter la primitive ci-dessous.
5. Afficher les éléments de ma_pile, comme suit : 4 - 3 - 2 - 1.
6. Écrire une fonction, inverser_pile qui prend en entrée une pile et renvoie une pile avec les mêmes éléments mais inversés.

2.3. File

2.3.1. Définition

Une file (queue en anglais) est une structure de données linéaire dans laquelle :

• Les insertions se font à une extrémité (l’arrière, rear),
• Les suppressions se font à l’autre extrémité (l’avant, front).

La file suit le principe Premier Entré, Premier Sorti (FIFO — First In, First Out).

2.3.2. Fonctions de files

• enfiler(f, elt) ou enqueue(f, elt) : Insère l'élément elt à l'arrière de la file, f. On lève une exception si la file est pleine.
• defiler(f) ou dequeue(f) : Supprime le premier élément de la file f et le renvoie. Lève une exception si la file est vide.

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

Quelques fonctions additionnelles

• tete(f) ou premier(f) : Renvoie l’élément à l'avant de la file f sans le supprimer. Lève une exception si la file est pas vide.
• est_vide(f) ou is_empty(f) : Renvoie True si la file f est vide, False sinon.
• est_pleine(f) ou is_full(F) : Renvoie True si la file f est pleine, False sinon.

Contrairement à la liste abstraite, on ne peut pas accéder directement à une position arbitraire.

2.3.3. Applications des files

• Utilisée pour mettre en œuvre des systèmes de mise en file d’attente.
• Gestion de processus par un système d’exploitation.

2.3.4. Implantation d'une file à l'aide d'une liste Python

# Créer une file vide
def creer_file():
    file = []
    return file

une_file = cree_file()

# Enfiler
def enfiler(f, elt):
    """
        ajoute elt à la file f.
        Ne renvoie rien
    """
    f.append(elt)

enfiler(une_file, 1)

enfiler(une_file, 'a')

enfiler(une_file, 'b')

print(une_file)

[1, 'a', 'b']

# Défiler
def defiler(f):
    """
        Supprime et renvoie le premier élément (élément à l'extrémité gauche) de la file
    """
    return f.pop(0)

defiler(une_file)

'b'

print(une_file)

[]

# Vérifier si une pile est vide
def est_vide(f):
    """
        Renvoie vrai si la pile p est vide, faux sinon
    """
    return len(f) == 0

est_vide(une_file)

False

for i in range(5, 10):
    enfile(une_file, i)

print(une_file)

[5, 6, 7, 8, 9]

def premier(f):
    """
    Renvoie le premier élément de f sans le supprimer
    """
    return f[0]