Cours structures de données linéaires

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.


Les listes

Définition

Une liste est une structure de données permettant de regrouper des données et dont l'accès est séquentiel.

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 :

Exemple

:

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

		
L= CREER_LISTE_VIDE()
INSERER(L,'A',1)
INSERER(L,'O',2)
INSERER(L,'B',1)
INSERER(L,'V',3)
INSERER(L,'R',2)

Quel est le contenu de la variable L à la fin ?

A la fin : L = ('B','R','A','V','O')

Représentation d'une liste avec un tableau

Une manière simple de représenter une liste est d'utiliser un tableau de taille fixe dont chaque élément est identifié par son indice.

Tous les langages de programmation permettent d'implémenter des tableaux. En Python, le type de données le plus simple pour représenter un tableau est le type list.

On peut représenter une liste contenant n éléments avec un tableau L[0..n] comme suit :

Représentation d'une liste de taille maximale 5 éléments.

Parmi les listes, 2 structures particulières sont optimisées pour leur accès en mémoire.

Ce sont les piles et les files.

Pseudo-code pour les fonctions INSERER et SUPPRIMER


Fonction INSERER(L,x,i)
	Si (L[0] = n + 1 ou i - 1 > L[0])
		Retourner Faux
	Pour k allant de L[0] + 1 à (i + 1) par pas de -1
		L[k] = L[k-1]
	L[i] = x
	L[0] = L[0] + 1
	Retourner Vrai
		
	
Proposez le pseudo-code de la fonction SUPPRIMER(L,i)

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 assiette directement accessible et la dernière assiette qui a été déposée sur la pile.

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 :

Exemple :

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

		
P= CREER_PILE_VIDE()
EMPILER(P,3)
EMPILER(P,2)
N = DEPILER(P)
EMPILER(P,5)
EMPILER(P,7)
EMPILER(P,9)

A la fin : P = (3, 5, 7, 9) et N = 2

Représentation d'une pile avec un tableau

On peut représenter une pile contenant n éléments avec un tableau P[0..n] comme suit :

Représentation d'une liste de taille maximale 5 éléments.
Proposez le pseudo-code de la fonction EMPILER(P,x)
Proposez le pseudo-code de la fonction DEPILER(P)

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.

File

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 :

Exemple :

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

		
		F= CREER_FILE_VIDE()
		ENFILER(F,14)
		ENFILER(F,11)
		ENFILER(F,64)
		N = DEFILER(F)
		ENFILER(F,27)
		ENFILER(F,9)
		N = DEFILER(F)
		
		

Donner les valeurs de F et de N à la fin.

A la fin : F = (64, 27, 9) et N = 11

Représentation d'une file avec un tableau

On peut représenter une file contenant n éléments avec un tableau F[0..n+2] comme suit :

  • La première case du tableau (d'indice 0) contient l'indice de la tête de la file.
  • La deuxième case du tableau (d'indice 1) contient l'indice de la queue de la file,c'est-à-dire la prochaine case disponible pour la queue.
  • La troisième case du tableau (d'indice 2) contient le nombre d'éléments de la file.
  • Les cases suivantes du tableau (d'indices 3 à n+2) contiennent les éléments de la file ou sont vides.

Remarques :

  • A chaque fois qu'on enfile un élément, on augmente la taille de la file d'une unité ainsi que l'indice de la queue.
  • A chaque fois qu'on défile un élément, on diminue la taille de la file d'une unité et on augmente l'indice de la tête d'une unité.
  • Quand les indices de tête ou de queue dépasse la longueur du tableau, ils repartent au début du tableau (indice 3). Il s'agit d'une gestion circulaire d'un tableau.
Proposez le pseudo-code de la fonction ENFILER(F)
Proposez le pseudo-code de la fonction DEFILER(F)

Les dictionnaires

Un dictionnaire est une structure de données qui associe une valeur à une clé.

Exemple :

On peut représenter les informations sur une personne (Prénom, Nom, date de naissance) par un dictionnaire à l'aide de paires (clé,valeur) :

  • cle1 = "Prenom" valeur1 = "Alan"
  • cle2 = "Nom" valeur2 = "Turing"
  • cle3 = "Date_naissance" valeur2 = "23/05/1912"

Les dictionnaires ne sont pas une structure ordonnée. Contrairement aux listes, on ne peut pas retrouver un élément via sa position. On y accède via sa clé.

Voici les opérations que l'on peut réaliser sur un dictionnaire :

  • CREER_DICTIONNAIRE_VIDE() crée et retourne un dictionnaire vide.

  • INSERER(D,cle,valeur) : insére l'entrée cle-valeur dans le dictionnaire D.

  • SUPPRIMER(D,cle) : supprime l'entrée dont la clé est cle du dictionnaire D.

  • LIRE(D,cle) : retourne la valeur correspondant à la cle cle du dictionnaire D.

  • RECHERCHER(D,cle) : retourne Vrai si le dictionnaire D contient la clé cle et Faux sinon.

Exemple d'implémentation d'un dictionnaire en Python

un_illustre_informaticien = {"prenom":"Alan","nom":"Turing","date_naissance":"23-05-1912"}