Les tableaux

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 :



t : tableau entier[0..9]




Un tel tableau peut par exemple contenir les éléments suivants :



0

1

2

3

4

5

6

7

8

9

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 :



x <- t[0]




L'élément désigné du tableau peut être utilisé comme n'importe quelle variable :



t[6] <- 43




Cette instruction a modifié le tableau t :



0

1

2

3

4

5

6

7

8

9

45

54

1

-56

22

134

43

12

90

-27

 

 

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.




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]




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

 

 

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.




Exemple

On cherche ici à savoir si un tableau saisi au clavier n'est constitué que d'entiers positifs :



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[O..n-1]

- positif : booléen, vrai si aucun entier négatif n'a été détecté

 

 

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.




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)

 

 

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, ...]




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.



x <- t[0,0]




L'élément désigné du tableau peut alors être utilisé comme n'importe quelle variable :



t[2,1] <- 43




Cette instruction a modifié le tableau :



45	54	1	-56	22
64	8	54	34	2
56	43	-47	0	12





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

 

 

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] :



5 13 18 23 46 53 89 97

3 4 5 6 7 8 9 10




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é !




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é

© Aflo Informatique , 2003-2004