- Définition
Définition 5.1. Un tableau est une table d'association à clé unique telle que
- le nombre d'éléments de la table (dimension ou taille) est constant,
- l'accès aux éléments s'effectue directement par la clé,
- les valeurs minimum et maximum des clés sont des constantes.
On écrit en EXALGO
nom_tableau=tableau[min_indice..max_indice] de type_predefini;
ce qui signifie que
- les éléments ont pour type le type_prédéfini
- les indices des éléments vont de min_indice à max_indice, avec min_indice<max_indice,
La taille du tableau est donc max_indice-min_indice+1.
Pour accéder à un élément d'un tableau T d'indice I, on écrit T[I]. La complexité de l'accès à un élément du tableau est O(1).
Notation Soit min_indice<i<j<max_indice, notera T[i..j] la séquence des éléments de T (T[i],T[i+1],...,T[j]).
Beaucoup d'algorithmes peuvent être décrits sans préciser un type particulier.
Dans ce cas, on écrira à la place de type_prédéfini le mot élément et on précisera les valeurs possibles pour élément.
Exemple 5.1.
Soit deux tableaux
- TC=tableau[1..10]de car;
- TE=tableau[1..10]d'entiers;
L'algorithme qui permet de trier TC et TE est le même. Seul différe le type de l'élément manipulé. On écrirera dans ce cas un algorithme sur un tableau
T=tableau[1..10]d'éléments;
et on précisera que élément est dans {car,entier}.
- Primitives
Les paramètres tableaux doivent, sauf raison majeure, être passés en paramètre par référence afin d'éviter la recopie.
Initialisation d'un tableau
fonction init(ref T:tableau[min_indice..max_indice] d'éléments;
val valeurInitiale:élément):vide;
var i:entier;
début
pour i allant de min_indice à max_indice faire
T[i]= valeurInitiale
finpour
fin
finfonction
Complexité: O(n).
Taille d'un tableau
fonction taille(ref T:tableau[min_indice..max_indice] d'élément):entier;
début
retourner(max_indice-min_indice+1)
fin
finfonction
Complexité: O(1).
Echange d'éléments
fonction echange(ref T:tableau[min_indice..max_indice] d'élément;
val indice1,indice2: entier):vide;
var e:élément;
début
e=T[indice1];
T[indice1]=T[indice2];
T[indice2]=e;
fin
finfonction
Complexité: O(1).
Copie de tableau
fonction copie(ref T1,T2:tableau[min_indice..max_indice] d'élément;
val indiceT1_1,indiceT1_2,indiceT2: entier):booleen;
var i:entier;
début
si indiceT2+indiceT1_2-indiceT1_1>max_indice alors
retourner(faux)
sinon
pour i allant de indiceT1_1 à indiceT1_2 faire
T2[indiceT2]=T1[i];
indiceT2=indiceT2+1;
finpour
retourner(vrai)
fin
finfonction
Complexité
- minimum : O(1)
- maximum : O(n)
Source Python
- Quelques exemples d'algorithmes
Somme des éléments d'un tableau d'entiers
fonction somme(ref T:tableau[min_indice..max_indice] d'entiers):entier;
var s,i:entier;
début
s=0;
pour i allant de min_indice à max_indice faire
s=s+T[i]
finpour
retourner(s)
fin
Complexité: O(n)
Recherche d'un élément
Propriété 5.2. Soit i,j deux entiers, i<=j.
Soit T un tableau d'éléments d'indice variant entre i et j. Pour tout élément e, appartenant au tableau T, on a
T[i]=e ou e est dans T[i+1..j]
fonction cherche(ref T:tableau[min_indice..max_indice] d'élément;val e:élément):entier;
var i:entier;
début
pour i allant de min_indice à max_indice faire
si T[i]==e alors
retourner(i)
finpour
retourner()
fin
finfonction
Complexité
- minimum : O(1)
- maximum : O(n)
Source Python
Recherche de l'indice du premier élément minimum
On suppose que le tableau contient des éléments comparables (l'ensemble des éléments est muni d'une relation d'ordre). Choisissons ici, pour simplifier les notations, des entiers.
Propriété 5.3.. Soit i,j deux entiers, i<=j.
Soit T un tableau d'entiers d'indice variant entre i et j. Soit m l'élément minimum du tableau, on a
T[i]=m ou m est dans T[i+1..j]
fonction minimum(ref T:tableau[min_indice..max_indice] d'entier):entier;
var i,sauv:entier;
début
sauv=min_indice;
pour i allant de min_indice+1 à max_indice faire
si T[i]<T[sauv] alors
sauv=i
finsi
finpour
retourner(sauv)
finfonction
Complexité : O(n)
- Matrices
Déclaration
Une matrice M de dimension nxm est un tableau de dimension n dont chaque élément est un tableau de dimension m. On peut donc déclarer la matrice sous la forme suivante
var M:tableau[1..n]de tableau [1..m] d'éléments;
Initialisation
fonction initMatrice(ref M:tableau[1..n] de tableau [1..m] d'éléments;
val valeurInitiale:élément):vide;
var i,j:entier;
début
pour i allant de 1 à n faire
pour j allant de 1 à m faire
M[i][j]=valeurInitiale
finpour
finpour
retourner()
finfonction
Complexité : O(nm)
Somme de deux matrices réélles
fonction sommeMatrice(ref M1,M2:tableau[1..n] de tableau [1..m] de réels):
tableau[1..n] de tableau [1..m] de réels;
var i,j:entier;
var M:tableau[1..n] de tableau [1..m] de réels;
début
pour i allant de 1 à n faire
pour j allant de 1 à m faire
M[i][j]=M1[i][j]+M2[i][j];
finpour
finpour
retourner(M)
finfonction
Complexité : O(nm)