Chapitre 5 : Les tableaux

Chapitre 5 : Les Tableaux

I. Problématique

On considère le problème suivant :

Supposons que nous avons à déterminer à partir de 30 notes fournies en entrée, le nombre
d’étudiants qui ont une note supérieure à la moyenne de la classe.
Pour parvenir à un tel résultat, nous devons :
 Lire les 30 notes
 Déterminer la moyenne de la classe : m
Il faut donc conserver toutes les notes en mémoire afin qu’elles soient accessibles durant
l’exécution du programme.

Solution 1 :

Utiliser 30 variables réelles nommées x1, x2,…, x30

 Cette façon de faire présente deux inconvénients :

- Il faut trouver un nom de variable par note ;

- Il n’existe aucun lien entre ces différentes valeurs. Or, dans plusieurs cas, on est
appelé à appliquer le même traitement à l’ensemble ou à une partie de ces valeurs.

Solution 2 :

Définir un espace mémoire qu’on appelle MOY qui sera divisé en 30 parties équitables,
indicées de 1 à 30.

MOY

Contenu 15 12 5 10 4 50 ……
Indice 1 2 3 4 5 6 27 28 29 30
On définit un tableau de 30 cases à une seule dimension qu’on appelle Tableau.

1
Chapitre 5 : Les tableaux

II. Définition

Un tableau est une structure de donnée formé d’élément de même type, que nous pouvons
accéder avec un indice.
En effet, un tableau n’est qu’une succession de case mémoire assurant un arrangement
contigu de plusieurs valeurs du même type.
 Caractéristiques:

Un tableau est caractérisé par:

 Un nom : un identificateur du tableau

 Le type de ses éléments qui peut être un entier, un réel, un caractère, une chaine de
caractère, un autre tableau ou un type composé.
 L'indice qui est l'indicateur assurant le parcours des cases du tableau une à une.L'indice
peut être tout type dont les éléments possèdent un successeur (les types scalaires).En
général, un indice est in type entier.

III. Les tableaux à une dimension

L’exemple ci-dessus est un tableau à une seule dimension ou unidimensionnel. Un
tableau unidimensionnel est composé d'une seule ligne et de plusieurs colonnes. Le
nombre de colonne indique la taille ou la longueur du tableau.
1. Déclaration d'un tableau

Type
Nom_tableau : tableau [borne_inf .. borne_sup] de type de élément
Variable
tab : Nom_tableau
I : entier

Ou
Variable
Nomvar : Tableau [borne_inf .. borne_sup] de type_élément

2
Chapitre 5 : Les tableaux

Exemple :

On veut déclarer un tableau T de moyennes

Type
Tab_Moy = Tableau [1..20] de réel
Variable
T : Tab_Moy
I : entier (* indice du tableau T *)

Dans un tableau :
 Tous les composants sont de même type.
 Le type des indices est entier.
 Le nombre des composants est défini à la déclaration du tableau. Il est donc statique.
2. Accès à un élément du tableau
La syntaxe générale pour accéder à un élément d'un tableau est:

<Nom_Tableau> [<Indice_De_L_Element>]

L'indice de l'élément est une valeur comprise entre Borne_Inf et Borne_Sup

Exemple : Moyenne[13]13.40

3. Opérations élémentaires sur un tableau

Pour représenter ces différentes opérations, on va utiliser un tableau T d’entiers.
a. Initialiser un Tableau

Algorithme Ini_Tab
Constante N = 100
Type TabEnt = Tableau [1..N] de Entier
Variable T : TabEnt
I : entier
Début
Pour I de 1 à N Faire
T(I)0
FinPour
Fin

3
Chapitre 5 : Les tableaux

b. Remplir un Tableau

Algorithme Remp_Tab
Constante N = 100
Type TabEnt = Tableau [1..N] de Entier
Variable T : TabEnt
I : entier
Début
Pour I de 1 à N Faire
Ecrire(‘élément d"indice’,I)
Lire(T(I))
FinPour
Fin

Lire(T(I)) consiste à entrer une valeur à partir du clavier et la mémoriser dans la I ème case
du tableau T.

c. Affichage les éléments d’un tableau

On va afficher les éléments strictement positifs du tableau T

Algorithme Aff_Tab
Constante N = 100
Type TabEnt = Tableau [1..N] de Entier
Variable T : TabEnt
I : entier
Début
Pour I de 1 à N Faire
Si T(I) > 0 Alors
Ecrire(‘élément d"indice’,I)
Ecrire(T(I))
FinSi
FinPour
Fin

4
Chapitre 5 : Les tableaux

d. Additionner les éléments de deux tableaux

On dispose de deux tableaux T1 et T2 et on veut réaliser la somme. Ça consiste à additionner
les éléments de même indice et les mémoriser dans un tableau T3.
Condition nécessaire : T1 et T2 de même taille et leurs éléments de même type.

Algorithme Add_Tab
Constante N = 100
Type TabEnt = Tableau [1..N] de Entier
Variable
T1, T2, T3 : TabEnt
I : entier
Début
Pour I de 1 à N Faire
T3(I)  T1(I) + T2(I)
FinPour
Fin

e. Multiplier les éléments de deux tableaux

Algorithme Mult_Tab
Constante N = 100
Type
TabEnt = Tableau [1..N] de Entier
Variable T1, T2, T3 : TabEnt
I : entier
Début
Pour I de 1 à N Faire
T3(I) T1(I) * T2(I)
FinPour
Fin

5
Chapitre 5 : Les tableaux

4. Exercice d’application
On dispose d’un tableau d’entiers T et on veut afficher le nombre d’éléments positifs et le
nombre d’éléments négatifs contenus dans le tableau.
Solution
Algorithme Pos_Neg
Constante N = 20
Type
TabEnt = Tableau [1..N] de Entier
Variable
T : TabEnt
I, Nbp, Nbn : entier
Début
Nbp 0
Nbn 0
Pour I de 1 à N Faire
Si (T(I) >= 0) Alors
Nbp Nbp + 1
Sinon
Nbn Nbn + 1
FinSi
FinPour
Écrire(Nbp)
Écrire(Nbn)
Fin

5. Recherche dans un tableau

a. Définition
La recherche d'une information est une opération fréquemment rencontrée dans les
traitements des suites de valeurs. Il y a deux types de recherche dans un tableau:
- recherche séquentielle
- recherche dichotomique

6
Chapitre 5 : Les tableaux

b. recherche séquentielle

Algorithme Rech_Seq
Constante N = 20
Type
TabEnt = Tableau [1..N] de Entier
Variable
T : TabEnt
I , X: entier (* X est l’élément à chercher dans le tableau *)
Trouve : Booléen (*cette variable va nous permettre de sortir dès qu’on trouve X*)
Début
Lire(X)
I1
Trouve Faux
Tant que (I<=N) ET (Trouve = Faux) Faire
Si (T(I) <> X) Alors
I I + 1
Sinon
Trouve Vrai
FinSi
FinTantQue
Si (Trouve = Vrai) Alors
Ecrire(X, ‘appartient à T’)
Sinon
Ecrire (X,’ne se trouve pas dans T’)
FinSi
Fin

c. Recherche dichotomique

Ce type de recherche s'effectue dans un tableau ordonné.

Principe

1. On divise le tableau en deux parties sensiblement égales,

2. On compare la valeur à chercher avec l'élément du milieu,
3. Si elles ne sont pas égales, on s'intéresse uniquement à la partie contenant les éléments
voulus et on délaisse l'autre partie.
4. On recommence ces 3 étapes jusqu'à avoir un seul élément à comparer.

7
Chapitre 5 : Les tableaux

Exemple : On suppose qu'on dispose d'un tableau V de N éléments. On veut chercher la

valeur Val.

ALGORITHME Recherche_Dich
Variable
T: tableau [1..11] de entier
x, binf,bsup, mil: entier
DEBUT
écrire ("Donner la valeur à rechercher:")
lire (x)
binf  1
bsup  11
répéter
mil  (binf + bsup) / 2 // il s'agit d'une division entière
si T[mil] > x alors
bsup  mil 1
sinon
binf  mil + 1
fin si
jusqu' à T[mil] = x ou bsup < binf
si bsup < binf alors
écrire ("EXISTE PAS")
sinon si T[mil] = x alors
écrire ("EXISTE")
fin si
FIN

8
Chapitre 5 : Les tableaux

6. Algorithmes de tri
a. Définition
On désigne par tri, l'opération qui consiste à ordonner une suite de valeurs suivant
une relation d'ordre (ordre croissant et décroissant).
Il y a plusieurs façons ou techniques pour effectuer un tri. On va considérer 3 tris:
- tri par sélection
- tri par insertion
- tri à bulle

b. Tri par sélection

 Principe de tri
Le principe de ce tri est défini comme suit:
 On recherche le plus grand des n éléments du tableau (dans le cas d'un tri
décroissant ou le plus petit dans le cas d'un tri croissant)
 On échange cet élément avec le premier élément du tableau
 Le plus grand élément se trouve alors en première position. On peut appliquer entre
les deux opérations précédentes aux n1 éléments restants, puis aux n-2 éléments restants et
ceci jusqu'à ce qu'il ne reste plus qu'un élément(le dernier lequel le plus petit)

 Exemple
143 12 122 3 21
Premier passage : le plus petit élément est a la position 3, on permute la valeur
T[3] et la valeur T[1]. Le tableau devient :
3 12 122 143 21
Deuxième passage : le plus petit élément est a la position 2, on permute la valeur T[2] et la
valeur T[2]. Le tableau devient :

3 12 122 143 21
Troisième passage: le plus petit élément est à la position 5, on permute la
valeur T[5] et la valeur T[3]. Le tableau devient :
3 12 21 143 122
Quatrième passage : le plus petit élément est à la position 5, on permute la valeur T[5] et la
valeur T[4]. Le tableau devient :

3 12 21 121 143

9
Chapitre 5 : Les tableaux

 Algorithme

ALGORITHME Tri_Selection
Variable
T: tableau [1..10] de entier
i, min,ind, temp: entier
DEBUT
Pour ind de 1 à 4 faire
min  ind
pour i de ind + 1 à 5 faire
si T[i] < T[min] alors
min  i
fin si
fin pour
temp  T[ind]
T[ind]  T[min]
T[min]  temp
Fin pour
FIN

c. Le tri par insertion

 Principe de tri

Le principe du tri par insertion consiste à insérer un par un les éléments en les plaçant
correctement:
on insère le second élément du tableau dans sa place au niveau du sous tableau constitué du
premier élément, on insère ensuite le troisième élément du tableau dans sa place au niveau du
sous tableau constitué du premier et deuxième élément et ainsi de suite jusqu'au dernier
élément.

10
Chapitre 5 : Les tableaux

 Exemple
Si l’on part de :

143 12 122 3 21

Premier passage :
12 143 122 3 21

Deuxième passage :
12 122 143 3 21

Troisième passage :
3 12 122 143 21

Quatrième passage :
3 12 21 122 143

 Algorithme

ALGORITHME Tri_Insertion
Variable
T: tableau [1..14] de entier
temp, ind, j: entier
DEBUT
pour ind de 2 à 14 faire
temp T[ind]
j ind - 1
Tant que j > 0 et T[j] > temp faire
T[j + 1] T[j]
j j - 1
Fin tant que
T[j + 1] temp
Fin pour
FIN

d. Le tri à bulles
 Principe

Le principe du tri bulle est de comparer deux a deux les éléments e1 et e2 consécutifs d'un
tableau et d'effecteur une permutation si e1 > e2. On continue de trier les éléments du tableau
jusqu'a ce qu'il n'y ait plus de permutation.

11
Chapitre 5 : Les tableaux

 Exemple
143 12 122 3 21
Premier passage :
12 143 122 3 21

12 122 143 3 21

12 122 3 143 21

12 122 3 21 143
Deuxième passage :

12 122 3 21 143
12 3 122 21 143

12 3 21 122 143
12 3 21 122 143

Troisième passage:
12 3 21 122 143
3 123 21 122 143

12 3 21 122 143

12 3 21 122 143

Quatrième passage :

12 3 21 122 143
12 3 21 122 143
12 3 21 122 143

3 12 21 122 143

12
Chapitre 5 : Les tableaux

Algorithme

ALGORITHME Tri_Bulle
Variable
T: tableau [1..5] de entier
i, temp: entier
permute: booléen
DEBUT
répéter
permute faux
pour i de 5 à 2 faire
si T[i - 1] > T[i] alors
permute vrai
temp T[i - 1]
T[i - 1]T[i]
T[i]  temp
Fin si
Fin pour
jusqu'à non (permute)
FIN

7. Exercice d'application
Ecrire un algorithme qui permet d’afficher :
- le nombre d’apparition d’une valeur X donnée dans un tableau T,
- la position de la première apparition de X.

Solution

Algorithme StatX
Constante N=20
Type Tab_Ent = Tableau[1..N] de Entier
Variable I,X,NA,PP,DP : entier
Début
NA0
Lire(X)
Pour I de 1 à N Faire
Si (T(I) = X) Alors
NANA+1
FinSi
FinPour
Écrire(NA)
PP0
Pour I de 1 à N Faire
Si (T(I) = X) Alors
PPI
I999
FinSi
FinPour
Écrire(PP)
Fin

13
Chapitre 5 : Les tableaux

I. Les tableaux à deux dimensions

1. Définition

Si un traitement utilise plusieurs tableaux à une dimension, subissant le même traitement, on

utilise souvent un seul tableau à deux dimensions (ou matrice).
Chaque élément du tableau est alors identifié par deux indices : l’un désignant la ligne et
l’autre la colonne.
 Représentation Algorithmique
Représentation
Constante Algorithmique
Nbr_Lig = Val1 (* Nombre de Lignes *)
Nbr_Col = Val2 (* Nombre de Colonnes *)
Type
Matrice = Tableau [1..Nbr_Lig, 1..Nbr_Col] de Type_élément_Matrice
Variable
M : Matrice

Ou

Constante
Nbr_Lig = Val1 (* Nombre de Lignes *)
Nbr_Col = Val2 (* Nombre de Colonnes *)
Variable
M : Tableau [1..Nbr_Lig, 1..Nbr_Col] de Type_élément_Matrice

 Exemple
Une matrice de 4 colonnes 3 lignes :

1 2 3 4
1 k l m n
2 C v h f
3 q z t o

14
Chapitre 5 : Les tableaux

2. Opérations de base sur une Matrice

On va supposer que le Type_Elément_Matrice est Entier
a. Initialiser une matrice
Pour I de 1 à Nbr_Lig Faire
Pour J de 1 à Nbr_Col Faire
M(I,J) 0
FinPour
FinPour

b. Remplir une matrice

Pour I de 1 à Nbr_Lig Faire
Pour J de 1 à Nbr_Col Faire
Lire(M(I,J))
FinPour
FinPour

La primitive Lire(M(I,J)) consiste à lire à partir du clavier un élément et le placer à la Ième

Ligne et à la J ème Colonne.
c. Parcourir une matrice
Par exemple, on veut afficher tous les éléments de la matrice dont la valeur est supérieure à
10. Pour I de 1 à Nbr_Lig Faire
Pour J de 1 à Nbr_Col Faire
Si (M(I,J) >= 10) Alors
écrire(M(I,J))
FinSi
FinPour
FinPour

d. Additionner deux matrices

Condition nécessaire : les deux matrices doivent être de même type et de même taille.
Pour I de 1 à Nbr_Lig Faire
Pour J de 1 à Nbr_Col Faire
M(I,J) M1(I,J) + M2(I,J)
FinPour
FinPour

15
Chapitre 5 : Les tableaux

e. Recherche d’un élément dans une matrice

La recherche ne peut être que séquentielle. En pensant à la recherche dichotomique, elle ne
sera pas possible étant donné qu’une matrice triée n’existe pas !
Algorithme Rech_Matrice
Constante
Nbr_Lig = 10 (* Nombre de Lignes *)
Nbr_Col = 10 (* Nombre de Colonnes *)
Type
Matrice = Tableau [1..Nbr_Lig, 1..Nbr_Col] de Type_élément_Matrice
Variable
M : Matrice
I, J : Entier (* I étant l’indice des lignes et J celui des colonnes *)
X : Entier
Trouve : Booléen
Début
Lire(X)
I 1
Trouve Faux
Tant que (I<=Nbr_Lig) ET (Trouve =Faux) Faire
J 1
Tant que (J<= Nbr_Col) ET (Trouve=Faux) Faire
Si (M(I,J) = X) Alors
Trouve Vrai
Sinon
J J+1
FinSi
FinTantque
I I+1
FinTantque
Si (Trouve = Vrai) Alors
Ecrire(X, ‘se trouve dans la matrice’)
Sinon
Ecrire(X,’est inexistant dans la matrice’)
FinSi
Fin

16