Structures de données linéaires

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 :

CREER_LISTE_VIDE() crée et retourne une liste vide.
INSERER(L,e,i) : insére l'élément e à la position i de la liste L.
SUPPRIMER(L,i) : supprime l'élément à la position i de la liste L.
RECHERCHER(L,e) : recherche l'élément e de la liste L et on retourne son index.
LIRE(L,i) : retourne l'élément de la liste L en position i.
MODIFIER(L,i,e) : L'élément à la position i de la liste L est remplacée par l'élement e.
LONGUEUR(L) : retourne le nombre d'éléments de la liste L.

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 :
		

			 La première case du tableau (d'indice 0) contient le nombre d'éléments présents dans la liste.
			 Les cases suivantes du tableau (d'indices 1 à n) contiennent les éléments de la liste ou bien sont vides.
		
		
		
			
				
			
			
				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)
		
			
		
		
			
Fonction SUPPRIMER(L,i)
	Si (L[0] == 0 ou i > L[0])
		retourner Faux
	Pour k allant de i à L[0] - 1 par pas de 1
		L[k] = L[k+1]
	L[0] = L[0] - 1
	Retourner Vrai

		
		
		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.
		
		
			
		
		
			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 :
		
		
			
				
					CREER_PILE_VIDE() crée et retourne une pile vide.
				
			
			
				
					EMPILER(P,e) : insére l'élément e au sommet de la pile P.
				
			
			
				
					DEPILER(P) : enlève et retourne l'élément au sommet de la pile P.
				
			
			
				
					EST_VIDE(P) : retourne Vrai si la pile P est vide et Faux sinon.
				
			
			
				
					EST_PLEINE(P) : retourne Vrai si la pile P est pleine et Faux sinon.
				
			
		
		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 :
		

			 La première case du tableau (d'indice 0) contient l'indice de la prochaine case vide.
			 Les cases suivantes du tableau (d'indices 1 à n) contiennent les éléments de la pile ou bien sont vides.
				La dernière case non vide du tableau est le sommet de la pile.
		
		
			
				
			
			
				Représentation d'une liste de taille maximale 5 éléments.
			
		
		 Proposez le pseudo-code de la fonction EMPILER(P,x)
		
			
		
		
			
	Fonction EMPILER(P,x)
		Si (P[0] == n + 1)
			retourner Faux
		i = P[0]
		P[i] = x
		P[0] = i + 1
		retourner Vrai
	
		
		 Proposez le pseudo-code de la fonction DEPILER(P)
		
			
		
		
			
Fonction DEPILER(P)
	Si (P[0] <= 1)
		retourner None
	P[0] = P[0] - 1
	retourner P[P[0]]

		
		
		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 :
		
		
			
				
					CREER_FILE_VIDE() crée et retourne une file vide.
				
			
			
				
					ENFILER(F,e) : insére l'élément e à la queue de la file F.
				
			
			
				
					DEFILER(F) : enlève et retourne l'élément situé en tête de la file F.
				
			
			
				
					EST_VIDE(F) : retourne Vrai si la file F est vide et Faux sinon.
				
			
			
				
					EST_PLEINE(F) : retourne Vrai si la file F est pleine et Faux sinon.
				
			
		
		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)
		
			
		
		
			
Fonction ENFILER(F,x)
	Queue= F[1]
	Taille = F[2]
	Si taille = n
		retourner Faux
	F[Queue] = x
	Si Queue = n + 3
		Queue = 3
	sinon
		Queue = Queue + 1
	Taille = Taille + 1
	F[2] = Taille
	F[1] = queue
	Retourner Vrai
		
		
		 Proposez le pseudo-code de la fonction DEFILER(F)
		
			
		
		
			
Fonction DEFILER(F)
	Tete = F[0]
	Taille = F[2]
	Si taille != 0
		x = F[Tete]
		Si Tete = n + 3
			Tete = 3
		sinon
			Tete = Tete + 1
		Taille = Taille - 1
		F[2] = Taille
		F[0] = Tete
		Retourner x
	Retourner None
		
		
		
		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"}

Les listes

Définition

Exemple

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

Représentation d'une liste avec un tableau

Pseudo-code pour les fonctions `INSERER` et `SUPPRIMER`

Proposez le pseudo-code de la fonction `SUPPRIMER(L,i)`

Les piles

Exemple :

Représentation d'une pile avec un tableau

Proposez le pseudo-code de la fonction `EMPILER(P,x)`

Proposez le pseudo-code de la fonction `DEPILER(P)`

Les files

Exemple :

Représentation d'une file avec un tableau

Proposez le pseudo-code de la fonction `ENFILER(F)`

Proposez le pseudo-code de la fonction `DEFILER(F)`

Les dictionnaires

Exemple :

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

Les listes

Définition

Exemple

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

Représentation d'une liste avec un tableau

Pseudo-code pour les fonctions INSERER et SUPPRIMER

Proposez le pseudo-code de la fonction SUPPRIMER(L,i)

Les piles

Exemple :

Représentation d'une pile avec un tableau

Proposez le pseudo-code de la fonction EMPILER(P,x)

Proposez le pseudo-code de la fonction DEPILER(P)

Les files

Exemple :

Représentation d'une file avec un tableau

Proposez le pseudo-code de la fonction ENFILER(F)

Proposez le pseudo-code de la fonction DEFILER(F)

Les dictionnaires

Exemple :

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

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

Pseudo-code pour les fonctions `INSERER` et `SUPPRIMER`

Proposez le pseudo-code de la fonction `SUPPRIMER(L,i)`

Proposez le pseudo-code de la fonction `EMPILER(P,x)`

Proposez le pseudo-code de la fonction `DEPILER(P)`

Proposez le pseudo-code de la fonction `ENFILER(F)`

Proposez le pseudo-code de la fonction `DEFILER(F)`