Chapitre 5 Structure de données : les Tableaux
5.1. Définition
Un tableau T est une variable structurée formée d’un nombre entier N de variables simples de
même type, qui sont appelées les composantes du tableau.
Le nombre de composantes N est alors la dimension du tableau.
On dit encore que T est un vecteur de dimension N.
5.2. Utilité
Un tableau est une structure de données constituée d’un nombre fini d’éléments de
même type.
Lorsque plusieurs données de même type, généralement destinées au même traitement
doivent être accessibles le long d’un programme, on propose d’utiliser la structure d’un
tableau.
5.3. Composantes
Nom : identificateur d’un tableau.
Type-élément : Les éléments d’un tableau sont caractérisés par leur type (entier, réel, caractère,
chaine de caractères, booléen, etc.).
Indice : Tout type dont les éléments possèdent un successeur (les types scalaires), généralement
de type entier.
5.4. Les tableaux à une dimension
Le type défini par un tableau est fonction :
Du nombre d’éléments maximal que peut contenir le tableau
Du type des éléments que peut contenir le tableau
Par exemple un tableau d’entiers de taille 10 et un tableau d’entiers de taille 20 sont deux types
différents.
On peut utiliser directement des variables de type tableau, ou définir de nouveau type à partir
du type tableau.
On utilise un type tableau via la syntaxe suivante :
Type
nom_type = Tableau[intervalle] de <type> ;
Var <nom de la variable> : nom_type ;
ou
27
Algorithmique –ENSP - Humanité numérique & Art numérique ingénieur – Mme NINKO Lidwine
Type
nom_type = Tableau[taille] de <type> ;
Var <nom de la variable> : <nom_type> ;
<type> est le type des éléments stockés par le tableau.
Intervalle est un intervalle sur un type simple dénombrable avec des bornes constantes. Taille
représente la taille du tableau.
Exemple 1 :
Type
Tab = Tableau[1..100] de entier ;
Var notes : Tab ;
Type
Tab = Tableau[100] de entier ;
Var notes : Tab ; //Ici l’intervalle est de 0 à 99
Exemple 2 :
Type
Notes = Tableau [1..26] de réel ; //défini un nouveau type appelé Notes, qui est un tableau
de 26 réels.
Var a : Notes ; //déclare une variable de type Notes
b : Notes ; /* Déclare une variable de type Notes, a et b sont de même type */
Exemple 3 :
Type
Tabl = Tableau["a".."z"] de entier ; //déclare une variable de type tableau de 26 entiers.
Var c1 : Tabl ;
5.4.1. Accès aux composantes d’un tableau
Considérons un tableau T de taille N
L’accès au premier élément du tableau se fait par T[0]
L’accès au dernier élément du tableau se fait par T[N-1]
Exemple :
5.4.2. Chargement d’un tableau
Ecrire un algorithme qui permet de remplir un tableau de 5 entiers.
Algorithme Chargement ;
28
Algorithmique –ENSP - Humanité numérique & Art numérique ingénieur – Mme NINKO Lidwine
Type
vecteur = Tableau[1..5] de entier ;
Var T : vecteur ;
i : entier ;
Début
Ecrire ("Entrer les éléments du tableau") ;
Pour i de 1 à 5 Faire
Lire(T[i]) ;
FinPour ;
Fin
5.4.3. Affichage du contenu d’un tableau
Algorithme Affiche ;
Type
vecteur = Tableau[1..5] de entier ;
Var T : vecteur ;
i : entier ;
Début
Ecrire ("Affichages des éléments du tableau") ;
Pour i de 1 à 5 Faire
Ecrire (T[i]) ;
FinPour ;
Fin
5.4.4. Méthode de recherche dans un tableau
[Link]. La recherche séquentielle
Problème : Déterminer la première position d’une valeur donnée dans un tableau de N élément.
Résoudre ce problème en utilisant la notion de procédures/Fonctions
Algorithme Recherche ;
Const Nmax = 50 ;
Type
tab = Tableau [1..Nmax] de entier ;
Var T : tab ;
N, val : entier ;
//Procédure Chargement
Procédure Chargement (Var T : tab ; N : entier)
Var i : entier ;
Début
Pour i de 1 à N Faire
Lire(T[i]) ;
FinPour ;
FinProcédure ;
//Procédure Affiche
Procédure Affiche (T : tab ; N : entier) ;
Var i : entier ;
29
Algorithmique –ENSP - Humanité numérique & Art numérique ingénieur – Mme NINKO Lidwine
Début
Pour i de 1 à N Faire
Ecrire (T[i]) ;
FinPour ;
FinProcédure ;
//Procédure Indice
Fonction Indice (T : tab ; N, val : entier) : entier ;
Var i, pos : entier ;
Début
pos 52 ;
i1 ;
Tant que (i ≤ N et pos = = 52) Faire
Si (T[i] == val) Alors
Pos i ;
Sinon
i i+1 ;
FinSi ;
FinTantque ;
Indice pos ;
Retourner (Indice) ;
FinFonction ;
//Programme Principal
Début
Répéter
Ecrire ("Donner la taille de T :") ;
Lire(N) ;
Jusqu’à (N>1 et N<=Nmax) ;
Ecrire (" Chargement de T ") ;
Chargement (T, N) ;
Ecrire (" Affichage de T ") ;
Affiche (T, N) ;
Ecrire ("Donner la valeur à chercher dans T :") ;
Lire(val) ;
Si (Indice (T, N, val) == 52) alors
Ecrire (val, "n’existe pas dans T ") ;
sinon
Ecrire (val, "existe à la position", Indice (T, N, val), "dans T ") ;
FinSi ;
Fin
[Link]. La recherche dichotomique
Problème : Déterminer la première position d’une valeur donnée dans un tableau de N élément
triés dans le sens croissant. Résoudre ce problème en utilisant la notion de
procédures/Fonctions.
Principe :
30
Algorithmique –ENSP - Humanité numérique & Art numérique ingénieur – Mme NINKO Lidwine
Le principe est de décomposer le tableau T en deux sous tableaux. Trois cas peuvent se
produire :
Si val == T[milieu] alors val est trouvé et la recherche est terminée.
Si val < T[milieu] alors on va chercher val dans la partie gauche du tableau T.
Si val > T[milieu] alors on va chercher val dans la partie droite du tableau T.
On poursuit la recherche tant que T[milieu] est différent de val et tant que la taille de sous
tableau reste valide.
Fonction Dichotomique (T : tab ; N, val : entier) : entier ;
Var i, pos, mil, inf, sup : entier ;
Début
Pos -1 ;
Inf 1 ;
Sup N ;
Tant que (inf <= sup et pos == -1) faire
mil (inf + sup) div 2 ;
Si (T[mil] == val) Alors
pos mil ;
Sinon
Si (val<T[mil]) Alors
Sup mil – 1 ;
sinon
inf mil + 1 ;
FinSi ;
FinSi ;
FinTantque ;
Dichotomique pos ;
Retourner (Dichotomique) ;
FinFonction
5.4.5. Méthode de tri dans un tableau
[Link]. Tri par sélection (par minimum)
Principe : Le principe de cette méthode est simple. Elle consiste à :
Chercher l’indice du plus petit élément du tableau T[1..N] et permuter l’élément
correspondant avec l’élément d’indice 1;
Chercher l’indice du plus petit élément du tableau T[2..N] et permuter l’élément
correspondant avec l’élément d’indice 2 ;
……..
Chercher l’indice du plus petit élément du tableau T[N-1..N] et permuter l’élément
correspondant avec l’élément d’indice N-1;
Procédure Triselection (Var T : tab ; N : entier) ;
Var i, j, aux, indmin : entier ;
Début
Pour i de 1 à N-1 faire
indmin i ;
Pour j de i+1 à N faire
31
Algorithmique –ENSP - Humanité numérique & Art numérique ingénieur – Mme NINKO Lidwine
Si (T[j] < T[indmin]) Alors
indmin j ;
Finsi ;
FinPour ;
Si (i != indmin) Alors
aux T[i] ;
T[i] T[indmin] ;
T[indmin] aux ;
Finsi ;
FinPour ;
FinProcédure
[Link]. Tri par insertion
C’est un tri en général plus coûteux en particulier en nombre de transfert à effectuer qu’un tri
par sélection.
Principe :
Son principe est de parcourir un tableau non trié en le décomposant en deux parties une partie
déjà triée et une partie non triée. La méthode est identique à celle que l'on utilise pour ranger
des cartes que l'on tient dans sa main : on insère dans le paquet de cartes déjà rangées une
nouvelle carte au bon endroit. L'opération de base consiste à prendre l'élément frontière dans la
partie non triée, puis à l'insérer à sa place dans la partie triée (place que l'on recherchera
séquentiellement), puis à déplacer la frontière d'une position vers la droite. Ces insertions
s'effectuent tant qu'il reste un élément à ranger dans la partie non triée. L'insertion de l'élément
frontière est effectuée par décalages successifs d'une cellule.
Algorithme tri_insertion ;
Const N = 100 ;
Type
Tab = Tableau[1..N] de entier ;
Var T : Tab ;
i,j,aux : entier ;
Début
j 2 ;
Tant que j<=N faire
ij-1 ;
auxT[j] ;
Tant que (i>0 et T[i]>aux) faire
T[i+1] T[i] ;
i i-1 ;
Fintantque ;
T[i+1]aux ;
i j+1 ;
Fintantque ;
Fin
5.5. Les tableaux à deux dimensions
32
Algorithmique –ENSP - Humanité numérique & Art numérique ingénieur – Mme NINKO Lidwine
5.5.1. Définition
Un tableau à deux dimensions M est à interpréter comme un tableau (unidimensionnel) de taille
L dont chaque composante est un tableau (unidimensionnel) de taille C.
On appelle L le nombre de lignes du tableau et C le nombre de colonnes du tableau. Un tableau
à deux dimensions contient L*C composantes.
5.5.2. Déclaration
Type
<nom_type> =Tableau[PremierIntervalle, DeuxièmeIntervalle] de <type> ; //type
représente le type des éléments du tableau.
Var <nom de la variable> : <nom_type> ;
Ou
Type
<nom_type> =Tableau[Taille1, Taille2] de <type> ; //type représente le type des
éléments du tableau.
Var <nom de la variable> : <nom_type> ;
Exemple1 :
Type
Mat =Tableau[0..50, 0..30] de entier ;
Var M1 : Mat ;
Exemple2 :
Type
Mat =Tableau[1..20, 1..100] de chaine de caractère ;
Var M2 : Mat ;
Exemple3 :
Type
Mat =Tableau[100, 200] de réel ;
Var M3 : Mat ;
Remarque :
Il est également possible de définir une matrice comme dans l’exemple suivant :
33
Algorithmique –ENSP - Humanité numérique & Art numérique ingénieur – Mme NINKO Lidwine
Const NL = 100 ;
NC = 50 ;
Type
Matrice = Tableau [0..NL, 0..NC] de caractère ;
Var M : Matrice ;
5.5.3. Accès aux composantes d’une matrice
Considérons un tableau A de L lignes et C colonnes.
Les indices du tableau varient de 1 à L, respectivement de 1 à C.
La composante de la Nième ligne et Mième colonne est notée : A[N, M].
Syntaxe :
<Nom du tableau>[<ligne>, <colonne>]
Exemple : Considérons une matrice de 3 lignes et 4 colonnes
0 1 2 3
0 A[0,0] A[0,1] A[0,2] A[0,3]
1 A[1,0] A[1,1] A[1,2] A[1,3]
2 A[2,0] A[2,1] A[2,2] A[2,3]
5.5.4. Chargement d’une matrice
Algorithme Chargement ;
Const NL=30 ;
NC=40 ;
Type
Mat = Tableau [1..NL, 1..NC] de entier ;
Var M : Mat ;
i, j : entier ;
Début
Ecrire ("Entrer les éléments de la matrice") ;
Pour i de 1 à NL Faire
Pour j de 1 à NC Faire
Lire (M [i, j]) ;
FinPour ;
FinPour ;
Fin
5.5.5. Affichage du contenu d’une matrice
Algorithme Affichage ;
Const NL=30 ;
NC=40 ;
Type
Mat = Tableau [1..NL, 1..NC] de entier ;
Var M : Mat ;
i, j : entier ;
34
Algorithmique –ENSP - Humanité numérique & Art numérique ingénieur – Mme NINKO Lidwine
Début
Ecrire ("Affichage des éléments de la matrice") ;
Pour i de 1 à NL Faire
Pour j de 1 à NC Faire
Ecrire (M[i, j]) ;
FinPour ;
FinPour ;
Fin
5.6. Les tableaux à n dimensions
Par extension, on peut aussi utiliser des tableaux à plus grande dimension
Leur déclaration est la suivante :
Type
nom_type = tableau [intervalle1][intervalle2]. . . [intervallen] de <type> ;
Var <nom de la variable> : nom_type ;
Ou
Type
nom_type = tableau [taille1][taille2]. . . [taillen] de <type> ;
Var <nom de la variable> : nom_type ;
Exemple 1 :
Type
tab = tableau[0..100][0..50][0..200] [0..50] de réel ;
Var S : tab ;
Exemple 2 :
Type
tab = tableau[1..10][0..9][ "a".."z"] de entier ;
Var T : tab ;
5.6.1. Accès aux composantes d’un tableau à n dimensions
Pour le tableau de l’exemple 2, pour accéder au premier élément du tableau on a tab [1, 0, "a"],
dernier élément du tableau on a tab [10, 9, "z"]
Affectation
tab[2, 1, "b"] 100 ;
a tab[2, 1, "b"] ;
5.6.2. Chargement d’un tableau à n dimensions
Type
table = tableau[1..N][1..M][1..S] de entier ;
Procédure Chargement (Var A : table ; N1, M1, S1 : entier) ;
35
Algorithmique –ENSP - Humanité numérique & Art numérique ingénieur – Mme NINKO Lidwine
Var i , j, k : entier ;
Début
Pour i de 1 à N1 Faire
Pour j de 1 à M1 Faire
Pour k de 1 à S1 Faire
Lire (A [i, j, k]) ;
FinPour ;
FinPour ;
FinPour ;
FinProcédure ;
5.6.3. Affichage d’un tableau à n dimensions
Procédure Chargement (Var A : table ; N1, M1, S1 : entier) ;
Var i , j, k : entier ;
Début
Pour i de 1 à N1 Faire
Pour j de 1 à M1 Faire
Pour k de 1 à S1 Faire
Ecrire (A [i, j, k]) ;
FinPour ;
FinPour ;
FinPour ;
FinProcédure ;
36
Algorithmique –ENSP - Humanité numérique & Art numérique ingénieur – Mme NINKO Lidwine
