Structures de données : les listes, les piles et les files

Tiré du cours de David Roche : Structures de données : les listes, les piles et les files

1. Introduction

De nombreux algorithmes "classiques" manipulent des structures de données plus complexes que des simples nombres (nous aurons l’occasion d’en voir plusieurs cette année).Nous allons ici voir quelques-unes de ces structures de données. Nous allons commencer par des types de structures relativement simples : les listes, les piles et les files.

Ces trois types de structures sont qualifiés de linéaires.

2. Les listes

Une liste est une structure de données permettant de regrouper des données.

Une liste L est composée de 2 parties :

sa tête (souvent noté car), qui correspond au dernier élément ajouté à la liste,
sa queue (souvent noté cdr) qui correspond au reste de la liste.

Le langage de programmation Lisp (inventé par John McCarthy en 1958) a été un des premiers langages de programmation à introduire cette notion de liste (Lisp signifie list processing).

Voici les opérations qui peuvent être effectuées sur une liste :

vide() : créer une liste vide L= vide()
estVide(L) : tester si une liste est vide, renvoie vrai si la liste est vide
ajouteEnTete (x,L) : ajouter un élément en tête de liste avec L une liste et x l’élément à ajouter
supprEnTete(L) : supprimer la tête x d’une liste L et renvoyer cette tête x
compte(L) : Compter le nombre d’éléments présents dans une liste, renvoie le nombre d’éléments présents dans la liste L

La fonction cons() permet d’obtenir une nouvelle liste à partir d’une liste et d’un élément :

L1 = cons(x,L))

Il est possible "d’enchaîner" les cons() et d’obtenir ce genre de structure :

cons(x, cons(y, cons(z,L)))

Exemples :

# créer une liste vide
L=vide()

print(estVide(L))
# renvoie vrai

# La liste L contient maintenant l'élément 3
ajoutEnTete(3,L)

print(estVide(L))
# renvoie faux

ajoutEnTete(5,L)
# la tête de la liste L correspond à 5, la queue contient l'élément 3

ajoutEnTete(8,L)
# la tête de la liste L correspond à 8, la queue contient les éléments 3 et 5

t = supprEnTete(L)
print(t)
# la variable t vaut 8, la tête de L correspond à 5 et la queue contient l'élément 3

L1 = vide()
L2 = cons(8, cons(5, cons(3, L1)))
# La tête de L2 correspond à 8 et la queue contient les éléments 3 et 5

2.1. Travail à faire : Analyse

Voici une série d’instructions (les instructions ci-dessous s’enchaînent),

Analysez le programme ci-dessous et anticipez les affichages :

L = vide()
ajoutEnTete(10,L)
print(L)
ajoutEnTete(9,L)
print(L)
ajoutEnTete(7,L)
print(L)
L1 = vide()
L2 = cons(5, cons(4, cons(3, cons (2, cons(1, cons(0,L1))))))
print(L2)

Documentation officielle de Python sur les structures de données (5.1.1 et 5.1.2) .

Implémentez les fonctions nécessaires et testez le programme :
- Exercice sur les listes
Aviez-vous correctement anticipez les affichages ?

3. Les piles

On retrouve dans les piles une partie des propriétés vues sur les listes.

Dans les piles, il est uniquement possible de manipuler le dernier élément introduit dans la pile. On prend souvent l’analogie avec une pile d’assiettes : dans une pile d’assiettes la seule assiettedirectement accessible et la dernière assiette qui a été déposée sur la pile.

Les piles sont basées sur le principe LIFO (Last In First Out : le dernier rentré sera le premier à sortir). On retrouve souvent ce principe LIFO en informatique.

Voici les opérations que l’on peut réaliser sur une pile :

on peut savoir si une pile est vide : pile_vide(P)
on peut empiler un nouvel élément sur la pile : push(P,x)
on peut récupérer l’élément au sommet de la pile tout en le supprimant. On dit que l’on dépile : pop()
on peut accéder à l’élément situé au sommet de la pile sans le supprimer de la pile : sommet(P)
on peut connaitre le nombre d’éléments présents dans la pile : taille(P)

Exemples :

Soit une pile P composée des éléments suivants : 12, 14, 8, 7, 19 et 22 (le sommet de la pile est 22)

Pour chaque exemple ci-dessous on repart de la pile d’origine :

pop(P) : renvoie 22 `et la pile `P est maintenant composée des éléments suivants : 12, 14, 8, 7 et 19 (le sommet de la pile est 19)
push(P,42) : la pile P est maintenant composée des éléments suivants : 12, 14, 8, 7, 19, 22 et 42
sommet(P) : renvoie 22, la pile P n’est pas modifiée
pile_vide(P) : renvoie vrai si P est vide, ce qui se produirait si on applique 6 fois pop(P)
taille(P) : renvoie le nombre d’élément que contient P. Après avoir appliqué une fois pop(P), taille(P) renvoie 5

3.1. Travail à faire : Analyse

Soit une pile P composée des éléments suivants : 15, 11, 32, 45 et 67 (le sommet de la pile est 67).

Quel est l’effet de l’instruction pop(P) ?
Quel l’effet de l’instruction push(P,2) ?
Que retourne l’instruction taille(P) ?
On exécute 3 fois l’instruction pop(P), que retourne sommet(P) ?
Coder les fonctions nécessaires et testez le programme :
- Exercice sur les piles
Aviez-vous vu juste ?

4. Les files

Comme les piles, les files ont des points communs avec les listes.

Différences majeures : dans une file on ajoute des éléments à une extrémité de la file et on supprime des éléments à l’autre extrémité. On prend souvent l’analogie de la file d’attente devant un magasin pour décrire une file de données.

Les files sont basées sur le principe FIFO (First In First Out : le premier qui est rentré sera le premier à sortir. Ici aussi, on retrouve souvent ce principe FIFO en informatique.

Voici les opérations que l’on peut réaliser sur une file :

on peut savoir si une file est vide : file_vide(F)
on peut ajouter un nouvel élément à la file : ajout(F,x)
on peut récupérer l’élément situé en bout de file tout en le supprimant : retire(F)
on peut accéder à l’élément situé en bout de file sans le supprimer de la file : premier(F)
on peut connaitre le nombre d’éléments présents dans la file : taille(F)

Exemples :

Soit une file F composée des éléments suivants : 12, 14, 8, 7, 19 et 22 (le premier élément rentré dans la file est 22 ; le dernier élément rentré dans la file est 12).

ajout(F,42) : la file F est maintenant composée des éléments suivants : 42, 12, 14, 8, 7, 19 et 22 (le premier élément rentré dans la file est 22 ; le dernier élément rentré dans la file est 42)
retire(F) : la file F est maintenant composée des éléments suivants : 42, 12, 14, 8, 7, et 19 (le premier élément rentré dans la file est 19 ; le dernier élément rentré dans la file est 12)
taille(F) : renvoie 6
premier(F) renvoie 19, la file F n’est pas modifiée
on applique retire(F) 6 fois de suite : file_vide(F) renvoie vrai

4.1. Travail à faire : Analyse

Soit une file F composée des éléments suivants : 1, 12, 24, 17, 21 et 72 (le premier élément rentré dans la file est 72 ; le dernier élément rentré dans la file est 1).

Quel est l’effet de l’instruction ajout(F,25) ?

Correction

F = [1, 12, 24, 17, 21, 72]

ajout(F,25)
print(F)

Sortie du programme :

[25, 1, 12, 24, 17, 21, 72]

Quel est l’effet de l’instruction retire(F) ?
Quel l’effet de l’instruction ajout(F,2) ?
Que retourne l’instruction taille(PF) ?
On exécute 3 fois l’instruction retire(F), que retourne premier(F) ?
On retire et on affiche l’affiche l’élément retiré ainsi que le nouveau contenu de la file tant qu’elle n’est pas vide.
Coder les fonctions nécessaires et testez le programme :
- Exercice sur les files
Aviez-vous vu juste ?

5. Types abstraits et représentation concrète des données

Nous avons évoqué ci-dessus la manipulation des types de données (liste, pile et file) par des algorithmes, mais, au-delà de la beauté intellectuelle de réfléchir sur ces algorithmes, le but de l’opération est souvent, à un moment ou un autre, de "traduire" ces algorithmes dans un langage compréhensible pour un ordinateur (Python, Java, C,…).

On dit alors que l’on implémente un algorithme.

Il est donc aussi nécessaire d’implémenter les types de données comme les listes, les piles ou les files afin qu’ils soient utilisables par les ordinateurs.

Les listes, les piles ou les files sont des "vues de l’esprit" présent uniquement dans la tête des informaticiens, on dit que ce sont des types abstraits de données (ou plus simplement des types abstraits). L’implémentation de ces types abstrait, afin qu’ils soient utilisables par une machine, est loin d’être une chose triviale. L’implémentation d’un type de données dépend du langage de programmation. Il faut, quel que soit le langage utilisé, que le programmeur retrouve les fonctions qui ont été définies pour le type abstrait (pour les listes, les piles et les files cela correspond aux fonctions définies ci-dessus).

Certains types abstraits ne sont pas forcément implémentés dans un langage donné, si le programmeur veut utiliser ce type abstrait, il faudra qu’il le programme par lui-même en utilisant les "outils" fournis par son langage de programmation.

Pour implémenter les listes (ou les piles et les files), beaucoup de langages de programmation utilisent 2 structures : les tableaux et les listes chaînées.

5.1. Les tableaux

Un tableau est une suite contiguë de cases mémoires (les adresses des cases mémoire se suivent) :

Figure 1. Mémoire vide

Le système réserve une plage d’adresse mémoire afin de stocker des éléments.

Figure 2. Tableau en mémoire

La taille d’un tableau est fixe : une fois que l’on a défini le nombre d’éléments que le tableau peut accueillir, il n’est pas possible modifier sa taille. Si l’on veut insérer une donnée, on doit créer un nouveau tableau plus grand et déplacer les éléments du premier tableau vers le second tout en ajoutant la donnée au bon endroit !
Dans certains langages de programmation, on trouve une version "évoluée" des tableaux : les tableaux dynamiques. Les tableaux dynamiques ont une taille qui peut varier. Il est donc relativement simple d’insérer des éléments dans le tableau. Ce type de tableaux permet d’implémenter facilement le type abstrait liste (de même pour les piles et les files)
À noter : les "listes Python" (listes Python) sont des tableaux dynamiques. Attention de ne pas confondre avec le type abstrait liste défini ci-dessus, ce sont de "faux amis".

Figure 3. Tableau dynamique

5.2. Les listes chainées

Autre type de structure que l’on rencontre souvent et qui permet d’implémenter les listes, les piles et les files : les listes chaînées.
- Dans une liste chaînée, à chaque élément de la liste on associe 2 cases mémoire : la première case contient l’élément et la deuxième contient l’adresse mémoire de l’élément suivant.

Il est relativement facile d’insérer un élément dans une liste chaînée :

5.3. Les tuples

Il est aussi possible d’implémenter les types abstraits en utilisant des structures plus complexes que les tableaux et les listes chaînées.

Par exemple, en Python, il est possible d’utiliser les tuples pour implémenter le type abstrait liste :

5.4. Travail à faire : Implémentation des listes avec des tuples

Saisir les fonctions suivantes :

def vide():
    return None
def cons(x,L):
    return(x,L)
def ajouteEnTete(L,x):
    return cons(x,L)
def supprEnTete(L):
    return (L[0],L[1])
def estVide(L):
    return L is None
def compte(L):
    if estVide(L):
        return 0
    return 1 + compte(L[1])

Saisir successivement les commandes suivantes dans une console Python :

>>> L = vide()
>>> estVide(L)
>>> L = cons(5, cons(4, cons(3, cons(2, cons(1, cons(0,L))))))
>>> estVide(L)
>>> compte(L)
>>> L = ajouteEnTete(L,6)
>>> compte(L)
>>> x, L=supprEnTete(L)
>>> x
>>> compte(L)
>>> x, L=supprEnTete(L)
>>> x
>>> compte(L)

Observer la construction de la iste et les effets de chaque action.

6. Travail à faire : Problèmes

Résoudre les problèmes suivants : Utilisation des piles