Les tableaux
Date de publication : 16/03/2002 , Date de mise à jour : 27/01/2007
Par
julp (Autres articles)
Les tableaux sont omniprésents en programmation de par leur praticité : une variable
regroupant en son sein plusieurs éléments.
Cet article vous apprendra à déclarer un tableau et à l'utiliser qu'il soit simple
(sur une dimension) ou non.
1. Notion de tableau
2. Parcours complet d'un tableau
2.1. Exemple 1
2.2. Exemple 2
3. Parcours partiel d'un tableau
3.1. Exemple
4. Parcours imbriqués
4.1. Exemple
5. Tableaux multidimensionnels
5.1. Tableaux à deux dimensions
5.2. Exemple : calcul de la somme
6. Recherche dichotomique
1. Notion de tableau
Les tableaux servent à désigner une suite finie d'éléments de même type au
moyen d'une unique variable. Ces éléments peuvent être des entiers, des
chaînes, ... Ils sont stockés dans les différentes cases du tableau,
habituellement numérotées de 0 à n-1, n représentant la taille du tableau
(le nombre de cases dans le tableau).
Le type d'un tableau précise l'intervalle de définition et le type (commun)
des éléments.
tableau type_des_éléments[borne_inférieure .. borne_supérieure]
|
En général, nous choisirons toujours la valeur 0 pour la borne inférieure
dans le but de faciliter la traduction de l'algorithme vers les autres
langages (C, Java, ...). Par exemple, pour un tableau de 10 entiers, on
pourra écrire :
Un tel tableau peut par exemple contenir les éléments suivants :
| Indices : |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| Valeurs : |
45 |
54 |
1 |
-56 |
22 |
134 |
49 |
12 |
90 |
-27 |
Pour accéder à un élément du tableau, il suffit de préciser entre
crochets l'indice de la case contenant cet élément. Par exemple,
pour accéder au septième élément (49) du tableau d'entiers ci-dessus,
on écrit : t[6]. L'instruction suivante affecte à la variable x la valeur
du premier élément du tableau, c'est à dire 45 :
L'élément désigné du tableau peut être utilisé comme n'importe quelle
variable :
Cette instruction a modifié le tableau t :
| Indices : |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| Valeurs : |
45 |
54 |
1 |
-56 |
22 |
134 |
43 |
12 |
90 |
-27 |
2. Parcours complet d'un tableau
La plupart des algorithmes basés sur les tableaux utilisent des itérations
permettant de faire un parcours complet ou partiel des différents éléments
du tableau. De tels algorithmes établissent le résultat recherché par
récurrence en fonction des éléments successivement rencontrés.
Les répétitions inconditionnelles sont le moyen le plus simple de
parcourir complètement un tableau.
2.1. Exemple 1
Dans l'exemple suivant, la fonction affiche un à un tous les éléments
d'un tableau de n éléments :
fonction écrireTableau(n : entier, tab : tableau entier[0..n-1])
début
pour i de 0 à n-1 faire
écrire(tab[i])
fpour
fin
Lexique :
- i : entier, indice d'itération
- n : entier, taille du tableau
- tab : tableau entier[0..n-1]
Algorithme
début
n <- lire()
Pour i de 0 à n-1 faire
tab[i] <- lire()
fpour
écrireTableau(n, tab)
fin
Lexique :
- n : entier, taille du tableau
- tab : tableau entier[0..n-1]
|
Schéma de l'évolution de l'état des variables instruction par instruction :
On suppose que le tableau saisi, de taille 3, contient : 7, 10 et 8.
| Instructions |
Algorithme principal |
Fonction écrireTableau |
| |
|
tab |
|
|
tab |
| |
n |
tab[0] |
tab[1] |
tab[2] |
n |
i |
tab[0] |
tab[1] |
tab[2] |
| 1 |
3 |
|
|
|
/ |
| 2 (3 exécutions) |
|
7 |
10 |
8 |
/ |
| 3 |
|
|
|
|
3 |
|
7 |
10 |
8 |
| f1 |
|
|
|
|
|
0 |
|
|
|
| f2 |
|
|
|
|
|
|
écrire() |
|
|
| f1 |
|
|
|
|
|
1 |
|
|
|
| f2 |
|
|
|
|
|
|
|
écrire() |
|
| f1 |
|
|
|
|
|
2 |
|
|
|
| f2 |
|
|
|
|
|
|
|
|
écrire() |
| f1 |
|
|
|
|
|
(fin) |
|
|
|
2.2. Exemple 2
La fonction suivante multiplie par 2 tous les éléments d'un tableau.
fonction doublerTableau(n : entier, t InOut : tableau entier[0..n-1])
début
Pour i de 0 à n-1 faire
t[i] <- t[i]*2
fpour
fin
Lexique :
- n : entier, taille du tableau
- t : tableau entier[0..n-1], tableau modifiable
|
Schéma de l'évolution de l'état des variables instruction par instruction :
On suppose que l'appel de fonction est doublerTableau(3, tab),
où tab est un tableau de taille 3 qui contient : 7, 10 et 8.
| Instructions |
Algorithme principal |
Fonction doublerTableau |
| |
|
tab |
|
|
t |
| |
nb |
tab[0] |
tab[1] |
tab[2] |
n |
i |
t[0] |
t[1] |
t[2] |
| avant appel de la fonction |
3 |
7 |
10 |
8 |
/ |
| appel |
|
|
|
|
3 |
|
Avec le mot clé InOut t[0] et tab[0] sont la même "variable" |
Avec le mot clé InOut t[1] et tab[1] sont la même "variable" |
Avec le mot clé InOut t[2] et tab[2] sont la même "variable" |
| 1 |
|
|
|
|
|
0 |
/ |
| 2 |
|
14 |
|
|
|
|
/ |
| 1 |
|
|
|
|
|
1 |
/ |
| 2 |
|
|
20 |
|
|
|
/ |
| 1 |
|
|
|
|
|
2 |
/ |
| 2 |
|
|
|
16 |
|
|
/ |
| 1 |
|
|
|
|
|
(fin) |
/ |
| retour à l'algorithme appelant |
|
|
|
|
|
|
/ |
3. Parcours partiel d'un tableau
Certains algorithmes sur les tableaux se contentent de parcourir
successivement les différents éléments du tableau jusqu'à rencontrer
un élément satisfaisant une certaine condition. Un tel parcours partiel
est le plus souvent basé sur une répétition conditionnelle.
3.1. Exemple
Algorithme
début
tab <- lire()
i <- 0
positif <- vrai
tant que positif et i < n faire
si tab[i] < 0
alors positif <- faux
fsi
i <- i+1
ftant
si positif
alors écrire("tableau d'entiers naturels")
sinon écrire("tableau d'entiers relatifs")
fsi
fin
Lexique :
- i : entier, indice d'itération
- n : entier, taille du tableau
- tab : tableau entier[0..n-1]
- positif : booléen, vrai si aucun entier négatif n'a été détecté
|
4. Parcours imbriqués
Certains algorithmes sur les tableaux font appel à des boucles imbriquées :
la boucle principale sert généralement à parcourir les cases une à une,
tandis que le traitement de chaque case dépend du parcours simple d'une
partie du tableau (par exemple toutes les cases restantes), ce qui
correspond à la boucle interne.
4.1. Exemple
La fonction suivante calcule, pour chaque case d'un tableau, le nombre
de cases suivantes qui contiennent un élément strictement supérieur.
Les résultats sont placés dans un tableau.
fonction calculerNbSuccesseurSup(n : entier, t : tableau entier[0..n-1]):tableau entier[0..n-1]
début
Pour i de 0 à n-2 faire
tres[i] <- 0
fpour
Pour i de 0 à n-2 faire
Pour j de i+1 à n-1 faire
si t[i] < tres[i]+1
alors tres[i] <- tres[i]+1
fsi
fpour
fpour
retourne tres
fin
Lexique :
- n : entier, taille du tableau
- t : tableau entier[0..n-1]
- tres : tableau entier[0..n-1], tableau résultat (case i contient le nombre de cases
de t indice strictement supérieur à i qui contiennent un élément supérieur à t[i]
- i : entier, indice d'itération de la boucle principale (parcours pour remplir tres)
- j : entier, indice d'itération de la boucle interne (parcours des cases restantes de t)
|
5. Tableaux multidimensionnels
Les cases d'un tableau à une dimension sont indicées de manière consécutive
(cases "alignées"). Il est possible de disposer ces cases selon des grilles
(tableaux à deux dimensions), des cubes (tableaux à trois dimensions), ...
Les algorithmes les plus simples sur ces tableaux utilisent néanmoins en
général des boucles imbriquées : chaque niveau de boucle correspond au
parcours selon une dimension.
Le type d'un tableau précise l'intervalle de définition selon chaque
dimension.
tableau type_des_éléments[borne_inf_dim1 .. borne_sup_dim1, borne_inf_dim2 .. borne_sup_dim2, ...]
|
5.1. Tableaux à deux dimensions
Ces tableaux sont faciles à se représenter comme une grille (ou matrice)
ayant un certain nombre de lignes (première dimension) et un certain
nombre de colonnes (seconde dimension).
tableau type_des_éléments[0..nb_lignes-1, 0..nb_colonnes-1]
|
Un tel tableau, avec 5 colonnes et 3 lignes, peut par exemple contenir
les éléments suivants :
| |
0 |
1 |
2 |
3 |
4 |
| 0 |
45 |
54 |
1 |
-56 |
22 |
| 1 |
64 |
8 |
54 |
34 |
2 |
| 2 |
56 |
23 |
-47 |
0 |
12 |
Pour accéder à un élément du tableau, il suffit de préciser entre
crochets l'indice de la case contenant cet élément, et ce pour chacune
des dimensions. Par exemple, pour accéder à l'élément 23 du tableau
d'entiers ci-dessus, on écrit : t[2,1]. L'instruction suivante affecte
à la variable x la valeur du premier élément du tableau, c'est à dire 45.
L'élément désigné du tableau peut alors être utilisé comme n'importe
quelle variable :
Cette instruction a modifié le tableau :
| |
0 |
1 |
2 |
3 |
4 |
| 0 |
45 |
54 |
1 |
-56 |
22 |
| 1 |
64 |
8 |
54 |
34 |
2 |
| 2 |
56 |
43 |
-47 |
0 |
12 |
5.2. Exemple : calcul de la somme
fonction somme(li : entier, co : entier, t : tableau entier[0..li-1, 0..co-1]):entier
début
s <- 0
Pour i de 0 à li-1 faire
Pour j de 0 à co-1 faire
s <- s + t[i,j]
fpour
fpour
retourne s
fin
Lexique :
- li : entier, nombre de lignes du tableau
- co : entier, nombre de colonnes du tableau
- t : tableau entier[0..li-1, 0..co-1], tableau dont on cherche l'élément maximal
- s : entier, somme des éléments déjà parcourus
- i : entier, indice d'itération sur les lignes
- j : entier, indice d'itération sur les colonnes
|
6. Recherche dichotomique
La fonction rechercheDicho recherche un élément dans un tableau
trié et retourne l'indice d'une occurrence de cet élément (ou -1 en cas
d'échec). Une telle recherche peut être réalisée de manière séquentielle
ou dichotomique. Nous développons ici la version dichotomique qui est la
plus efficace en temps d'exécution.
On compare l'élément cherché à celui qui se trouve au milieu du tableau.
Si l'élément cherché est plus petit, on continue la recherche dans la
première moitié du tableau sinon dans la seconde. On recommence ce
processus sur la moitié. On s'arrête lorsqu'on a trouvé ou lorsque
l'intervalle de recherche est nul.
Exemples :
Exemple de recherche dans le tableau d'entiers suivant défini sur l'intervalle [3..10] :
| Indices : |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| Valeurs : |
5 |
13 |
18 |
23 |
46 |
53 |
89 |
97 |
Recherche de 46 :
Etape 1 : comparaison de 46 avec t[6] (6=(10+3)÷2), t[6]<46 => recherche dans [7..10]
Etape 2 : comparaison de 46 avec t[8], t[8]>46 => recherche dans [7..7]
Etape 3 : comparaison de 46 avec t[7], t[7]=46 => élément cherché trouvé à l'indice 7
Recherche de 10 :
Etape 1 : comparaison de 10 avec t[6], t[6]>10 => recherche dans [3..5]
Etape 2 : comparaison de 10 avec t[4], t[4]>10 => recherche dans [3..3]
Etape 3 : comparaison de 10 avec t[3], t[3]<10 => recherche dans [4..3], Borne inférieure supérieure à la borne supérieure donc on met fin à l'algorithme et l'élément cherché n'a pas été trouvé !
Voyons l'implémentation de cette fonction :
fonction rechercheDicho(e : entier, n : entier, t : tableau entier[0..n-1]):entier
début
debut <- 0
fin <- n-1
trouve <- faux
tant que debut <= fin et non trouve faire
i <- (debut+fin)÷2
si t[i] = e
alors trouve <- vrai
sinon si t[i] > e
alors fin <- i-1
sinon debut <- i+1
fsi
fsi
ftant
si trouve
alors indice <- i
sinon indice <- -1
fsi
retourne indice
fin
Lexique :
- e : entier, élément recherché
- n : entier, taille du tableau
- t : tableau entier[0..n-1], tableau trié par ordre croissant
- debut : entier, début de la zone de recherche
- fin : entier, fin de la zone de recherche
- trouve : booléen, faux tant que l'élément cherché n'est pas trouvé
- i : entier, indice de la case du milieu de la zone de recherche
- indice : entier, indice de l'élément recherché ou -1 s'il n'est pas trouvé
|
Copyright © 2007 . Aucune reproduction, même partielle, ne peut être faite
de ce site et de l'ensemble de son contenu : textes, documents, images, etc
sans l'autorisation expresse de l'auteur.
Sinon vous encourez selon la loi jusqu'à 3 ans de prison et jusqu'à 300 000 E
de dommages et intérêts.
Cette page est déposée à la
SACD.
