Structures de Données
1 Les Listes / Les tableaux
2 Exemple introductif
Supposons qu'on veut conserver les notes d'une classe de 30 étudiants
pour extraire quelques informations. Par exemple : calcul du nombre
d'étudiants ayant une note supérieure à 10
Le seul moyen dont nous disposons actuellement consiste à déclarer 30
variables, par exemple N1, …, N30. Après 30 instructions lire, on doit
écrire 30 instructions Si pour faire le calcul
nbre ← 0
Si (N1 >10) alors nbre ←nbre+1 FinSi
….
Si (N30>10) alors nbre ←nbre+1 FinSi
c'est lourd à écrire
Heureusement, les langages de programmation offrent la possibilité de
rassembler toutes ces variables dans une seule structure de donnée
appelée tableau /Liste
Tableaux
3
Un tableau / Liste est un ensemble d'éléments de même type désignés
par un identificateur unique
Une variable entière nommée indice permet d'indiquer la position d'un
élément donné au sein du tableau et de déterminer sa valeur
La déclaration d'un tableau s'effectue en précisant le type de ses
éléments et sa dimension (le nombre de ses éléments)
En pseudo code :
variable tableau identificateur[dimension] : type
Exemple :
variable tableau notes[30] : réel
On peut définir des tableaux de tous types : tableaux d'entiers, de réels,
de caractères, de booléens, de chaînes de caractères, …
Tableaux
4
: remarques
L'accès à un élément du tableau se fait au moyen de l'indice. Par
exemple, notes[i] donne la valeur de l'élément i du tableau notes
Selon les langages, le premier indice du tableau est soit 0, soit 1. Le
plus souvent c'est 0 (c'est ce qu'on va adopter en pseudo-code).
Dans ce cas, notes[i] désigne l'élément i+1 du tableau notes
Un grand avantage des tableaux est qu'on peut traiter les données
qui y sont stockées de façon simple en utilisant des boucles
Tableaux
5 : saisie et affichage
Algorhitme Saisie_Aff8Tab
variable i: entier
tableau T[10] : réel
Debut
Pour i allant de 0 à 9
Lire (T[i] )
FinPour
Pour i allant de 0 à 9
T[i] T[i] + 2
FinPour
Fin
6
Algorithmes qui permettent d'afficher les éléments d'un tableau :
Debut
Nb 0
Pour i allant de 0 à 9
si T[i] > 10 alors
Nb Nb + 1
Ecrire (‘’ les positions ‘’ , i)
FinSi
FinPour
Ecrire (‘’ les nombres de notes > a 1O‘’ , Nb)
Fin
7 Ecrire un algorithme qui permet de Saisir 10 Notes ,
puis augmentent ces notes de 2 points et affiche le
résultat Final
8 Tableaux : exemples (1)
Algorhitme MoyTab
Variables i ,nbre : entier
tableau T[10] : réel
Début
Pour i allant de 0 à 9
Ecrire T[i]
FinSi
FinPour
Fin
Quelques algorithmes sur les
tableaux
Ecrire un algorithme qui calcule la moyenne des notes
existantes ( déjà saisi) dans un tableau notes[10]
Quelques algorithmes sur les
tableaux
Ecrire un algorithme qui recherche une note x dans
un tableau notes[10].
Afficher si elle existe ou non
Quelques algorithmes sur les
tableaux
Ecrire un algorithme qui
permet de saisir un tableau de 10 Notes
Affiche la Note maximale dans ce tableau
Algorithme1
Principe
Lecture du tableau
Recherche de la valeur maximale
On utilise une variable Max dans laquelle on met la valeur
maximale
D’abord, on initialise Max avec la valeur de la première case du
tableau
Max T[0]
Algorithme 1
Ensuite, on parcourt les cases de la 2ème
jusqu’à la dernière. A chaque étape, on teste si
la valeur de la case courante est supérieure à la
valeur de Max. Si c’est le cas, on change la
valeur de Max
Algorithme 1
Squelette de l’algorithme
1. Déclaration des variables
• T, i, Max
2. Lecture du tableau
3. Recherche de la valeur maximale
4. Affichage de la valeur maximale
Algorithme 1
Algorithme Exemple1
Variable i, Max : entier
Variable Tableau T : [10] Reel
Début
Pour i allant de 0 à 9
Lecture du tableau
Lire( T[i] )
FinPour
…
Algorithme 1
…
Max T[0]
Pour i allant de 1 à 9
Si T[i] > Max Alors
Max T[i] Recherche de
FinSij la valeur
FinPour maximale
Ecrire(Max )
Fin Affichage de la
valeur
maximale
Algorithme 1
Algorithme Exemple2
Variable i, Max : entier
tableau T [10] : entier
Début
Max T[0]
Pour i allant de 1 à 9
Si T[i] > Max Alors
Max T[i]
FinSi
FinPour
Ecrire(Max)
Fin
Algorithme 2
Ecrire un algorithme qui
Permet de lire un tableau de 10 entiers
Puis affiche l’indice de la valeur maximale
Algorithme 2
Algorithme Ex2
Variable i, iMax : entier
Variable T : tableau[10] d’entiers
Début Noter que iMax
Lire(T(1)) ne représente
iMax T(1) 1 plus la valeur
Pour i = 2 à 10 maximale mais
Lire( T(i) )
l’indice de la
Si T(i) > Max Alors
valeur maximale
Max T(i) i
FinSi
FinPour
Ecrire(Max)
Fin
20 Tri d'un tableau
Le tri consiste à ordonner les éléments du tableau dans l’ordre
croissant ou décroissant
Il existe plusieurs algorithmes connus pour trier les éléments
d’un tableau :
Le tri par sélection
Le tri par insertion
Le tri rapide
…
21 Le tri par sélection
Le principe du tri par sélection/échange
(ou tri par extraction) est d'aller chercher
le plus petit élément du vecteur pour le
mettre en premier, puis de repartir du
second élément et d'aller chercher le plus
petit élément du vecteur pour le mettre en
second, etc..
Algorithme de tri par échange
22
Algorithme Tri_echange
Variables i, j, echange : entier
Tableau [10] : entier
Début
Pour i Allant de 0 à 8 Faire
Pour J Allant de 1à 9 Faire
Si T[i] > T[j] Alors
echange ← T[i]
T[i] ← T[j]
T[j] ← echange
FinSi
FinPour
FinPour
Fin
Tableaux à deux dimensions
23
Les langages de programmation permettent de déclarer des
tableaux dans lesquels les valeurs sont repérées par deux indices.
Ceci est utile par exemple pour représenter des matrices
En pseudo code, un tableau à deux dimensions se déclare ainsi :
variable tableau identificateur[dimension1] [dimension2] : type
Exemple : une matrice A de 3 lignes et 4 colonnes dont les éléments
sont réels
variable tableau A[3][4] : réel
A[i][j] permet d'accéder à l’élément de la matrice qui se trouve
à l’intersection de la ligne i et de la colonne j
Exemples : lecture et écriture d'une matrice
Algorithme
24 Lec_Aff_Matrice
variables i,j : entier
tableau M [3][4]: réel
Début
Pour i allant de 0 à 2
Pour j allant de 0 à 3
lire (M[i][j])
FinPour
FinPour
Pour i allant de 0 à 2
Pour j allant de 0 à 3
écrire ( M[i][j])
FinPour
FinPour
Fin
25 Exemples : affichage d'une matrice
Algorithme qui permet d'afficher les éléments d'une matrice :
Algorithme AffichMatrice
tableau M [3][4]: réel
variables i,j : entier
Pour i allant de 0 à 2
Pour j allant de 0 à 3
écrire (" M[",i, "] [",j,"]=", M[i][j])
FinPour
FinPour
Fin
26
Algorithme SomMatrice
tableau M1[3][4],M2 [3][4],M3 [3][4] : réel
variables i,j : entier
Début
****Initialisation de la Matrice****
Pour i allant de 0 à 2
Pour j allant de 0 à 3
M3[i][j] ← 0
FinPour
FinPour
Pour i allant de 0 à 2
Pour j allant de 0 à 3
M3[i][j] ← M1[i][j]+M2[i][j]
Ecrire(M3[i][j] )
FinPour