Les structures linéaires

Les structures linéaires sont des structures de données dont les éléments sont placés les uns derrière les autres.
On distingue 3 nouvelles structures en Terminale NSI :

• Les listes chaînées ;
• Les piles ;
• Les files.

Chacune de ces structures va pouvoir être modélisée par une classe, et vont avoir un ensemble de méthodes similaires.

Point histoire

Les listes chaînées sont à la base du langage LISP (List Processing) datant de 1958, utilisant des listes pour représenter des expressions arithmétiques (appelée S-expressions).
L'expression : 5 * (7 + 3) donnerait en LISP : (* 5 (+ 7 3 ) )

Les listes, piles et files vont avoir la même structure de données :

• Une tête représentée par une valeur ;
• Un reste représentant le reste de la structure.

Le reste de la structure va également posséder une tête et un reste, qui lui-même possédera une tête et un reste ... Jusqu'à atteindre le bout de la structure, représenté par un reste vide (None en python).

Notion de Primitives

Les primitives sont les fonctions de base qui permettent de manipuler une structure de données. Elles sont essentielles car elles définissent les opérations fondamentales que l'on peut effectuer sur cette structure.
Les opérations élémentaires sur les structures sont :

• Créer une structure vide ;
• Créer une structure avec des éléments ;
• Tester si une structure est vide ;
• Ajouter un élément à la structure ;
• Supprimer un élément de la structure ;
• Calculer la taille de la structure.

Liste chaînée

Les listes chaînées sont des cellules contenant pour chacune d'elle la valeur qu'elle est censée contenir, et un pointeur menant à la cellule suivante :

Primitives de la structure :

vide()

Crée et retourne une liste vide :

L = vide()

estVide(liste)

Retourne True si la liste en paramètre est vide, False sinon :

print(estVide(L)) #Affiche True

cons(valeur,liste)

Ajoute le paramètre valeur en tête de la liste en paramètre, et retourne la liste construite :

L1 = cons(1,L) #L1 est une liste avec la valeur 1 en tête

car(liste)

Retourne la tête de la liste en paramètre :

print(car(L1)) #Affiche 1

cdr(liste)

Retourne le reste de la liste en paramètre :

L2 = cons(2, L1)
r = cdr(L2) #r contient concrètement L1

Pile

C'est une structure dont on ne peut manipuler que le premier élément. Pour manipuler le second, il faut sortir le premier.

LIFO

La structure se base sur le concept du LIFO (Last In First Out), c'est-à-dire Dernier Entré Premier Sorti.

On reprend le concept d'une pile d'assiettes pour schématiser la structure :

• On ne manipule que l'assiette au sommet de la pile.
• Si l'on souhaite prendre la dernière assiette, il faut retirer une par une les précédentes.
• Si l'on doit rajouter une assiette à la pile, elle se place au sommet.

Primitives de la structure :

vide()

Crée et retourne une pile vide :

P = vide()

estVide(pile)

Retourne True si la pile en paramètre est vide, False sinon :

print(estVide(P)) #Affiche True

empiler(valeur,pile)

Ajoute le paramètre valeur au sommet de la pile en paramètre :

empiler(1,P) #L1 est une liste avec la valeur 1 en tête

depiler(pile)

Retourne et supprime le sommet de la pile en paramètre :

print(depiler(P)) #Affiche 1

taille(pile)

Retourne la taille de la pile en paramètre :

print(taille(P)) #Affiche 0
empiler(3,P)
print(taille(P)) #Affiche 1

File

C'est une structure dont on ne peut manipuler que le plus vieil élément. Pour manipuler le second plus vieux, il faut sortir le plus vieux.

FIFO

La structure se base sur le concept du FIFO (First In First Out), c'est-à-dire Premier Entré Premier Sorti.

On reprend le concept d'une file d'attente (supermarché, etc...) pour schématiser la structure :

• La première personne à la caisse est la première à passer ;
• Si des personnes arrivent dans la file, elles sont placées les unes derrière les autres ;
• La dernière personne à rentrer dans la file est donc la dernière à passer.

Primitives de la structure :

vide()

Crée et retourne une file vide :

F = vide()

estVide(file)

Retourne True si la file en paramètre est vide, False sinon :

print(estVide(F)) #Affiche True

enfiler(valeur,file)

Ajoute le paramètre valeur à la fin de la file en paramètre :

enfiler(1,F) #L1 est une liste avec la valeur 1 en tête

defiler(file)

Retourne et supprime le premier élément de la file en paramètre :

print(defiler(F)) #Affiche 1

taille(file)

Retourne la taille de la file en paramètre :

print(taille(F)) #Affiche 0
enfiler(3,F)
print(taille(F)) #Affiche 1