Définition
Tableau:
Les tableaux sont une structure de données de type liste contenant une collection d'éléments stockés en mémoire de façon contigue et accessibles via un indice.
Sur la figure ci-dessus, chaque case représente un élément de tableau. Il est ainsi clairement visible qu'un élément possède trois propriétés distincts:
- indice : Représente la position de l'élément dans le tableau
- valeur : Valeur de l'élément, utilisable au même titre qu'une variable
- adresse : Emplacement mémoire où est concrètement stocké l'élément du tableau
Avantages et inconvénients
Contrairement aux listes chaînées, les éléments d'un tableau sont représentés contiguement en mémoire et le tableau possède une taille fixe. Redimensionner dynamiquement un tableau est une opération complexe: le système d'exploitation va en réalité créer un nouveau tableau, c'est à dire réserver un nouvel emplacement en mémoire suffisament grand pour y acceuillir les données. Ensuite, il doit y copier l'ancien tableau puis libérer l'espace qu'il occupait.
Si vous utilisez une collection d'objets dont le nombre total est inconnu ou imprédictible à la création du programme, peut-être vaut-il mieux utiliser une liste chainée. En revanche, si vous connaissez le nombre maximal d'objet qu'aura à gérer votre programme, un tableau offre de meilleures performances à l'emploi. En outre, l'indice permet d'accéder directement à n'importe quel élément du tableau. L'usage des tableaux est donc préféré lorsque le programme nécessite de nombreuses opérations de tri ou de recherche.
Primitives et fonctions utiles
Les tableaux n'ont pas de primitives officiellement décrites. Par l'accès direct aux éléments du tableau, la plupart des primitives usuelles sont grandement simplifiées. Nous ne présenterons donc ici que quatres fonctions utiles :insertion : ajoute un élément dans le tableau (en redimensionnant le tableau).suppression : supprime un élément du tableau (en redimensionnant le tableau).minimum : renvoie le plus petit élément du tableau
- maximum : renvoie le plus grand élément du tableau
- recherche : renvoie l'index de l'élément cherché dans le tableau
Insertion d'éléments avec redimensionnement
Insérer un nouvel élément dans un tableau déjà plein nécessite de le redimensionner. En règle générale, l'usage de cette fonction est à éviter. Dans le cas d'un programme nécessitant de multiples redimensionnements, la structure de liste chaînée est à privilégier.
Primitive 'Insertion d'élément avec redimensionnement du tableau' en Pseudo-Code :
Tableau: InsertionTableau (Tableau: tab, Element: nouvElement):
ajouter une case au tableau
Si (espace mémoire alloué)
tab[nbElements+1]=nouvElement
renvoyer tab
sinon
ECHEC: impossible de redimensionner le tableau
FinFonction
Implémentation en C de la primitive 'Insertion avec redimensionnement' (cliquer pour ouvrir)
#include "stdlib.h"
Element* InsertionTableau ( Element* pTab, Element nouvElement)
{
// Détermination de la taille du tableau
int iNbElements = sizeof ( pTab) / sizeof ( pTab[ 0 ] ) ;
// Redimensionnement dynamique du tableau
pTab
= realloc ( pTab
, ( iNbElements
+ 1 ) * sizeof ( Element
) ) ; if ( pTab!= NULL) // Si le redimensionnement est valide:
{
pTab[ iNbElements] = nouvElement; // Ajouter l'élément au tableau
return pTab; // SUCCES
} // Sinon:
return NULL; // ECHEC (cause: redimensionnement impossible)
}
Suppression d'un élément avec redimensionnement
Supprimer un élément dans un tableau nécessite de déplacer tous les éléments suivants dans le tableau puis de le redimensionner pour supprimer l'espace vacant. En règle générale, l'usage de cette fonction est à éviter. Dans le cas d'un programme nécessitant de multiples redimensionnements, la structure de liste chaînée est à privilégier.
Primitive 'Suppression d'élément avec redimensionnement du tableau ' en Pseudo-Code :
Tableau: SuppressionTableau (Tableau: tab, Entier: indice):
Pour i=indice à nbreElement(tab) Faire
tab[i]=tab[i+1]
FinFaire
Supprimer dernière case
Si (redimensionnement OK)
Renvoyer tab
sinon
ECHEC: impossible de redimensionner le tableau
FinFonction
Implémentation en C de la primitive 'Suppression avec redimensionnement' (cliquer pour ouvrir)
#include "stdlib.h"
Element* SuppressionTableau ( Element* pTab, int iIndice)
{
int i;
// Détermination de la taille du tableau
int iNbElements = sizeof ( pTab) / sizeof ( pTab[ 0 ] ) ;
// A partir de l'indice de l'élément à supprimer:
for ( i= iIndice; i
Minimum et Maximum
Ces deux fonctions sont identiques à un détail près: nous aurons besoin de fonctions permettant de déterminer ce qu'est 'être plus petit' ou 'être plus grand' pour comparer deux éléments. Dans les algorithmes présentés dans la suite, nous utiliserons donc les fonctions de propotype suivant:
boolean IsPlusPetit(element1, element2);
boolean IsPlusGrand(element1, element2);
Chacune de ces fonctions renvoie TRUE si l'élément1 est respectivement 'plus petit' ou 'plus grand' que l'élément2. Pourquoi ne pas utiliser element1element1 ? Tout simplement parce que nos éléments ne sont pas nécessairement des nombres! Par exemple: dans une application gérant des hôtels, nous pourrons définir que IsPlusPetit(hotel1, hotel2) indiquera l'hôtel le moins cher, l'hôtel avec le moins d'étoile ou encore celui ayant les plus mauvaises appréciations.
D'un point de vue performance, l'algorithme de recherche d'un extrema dans un tableau (maximum ou minimum) est dit en log(n). Cela signifie que cette recherche nécessite un nombre d'opérations proportionel au nombre d'éléments dans le tableau. Ceci s'explique tout simplement par le fait qu'il faille passer en revue tous les éléments du tableau pour en trouver l'extremum.
L'algorithme procède de la manière suivante:
- Le premier élément est considéré comme étant l'extremum actuel.
- En passant sur le second élément, si celui est plus petit (ou plus grand) que l'élément actuel, le minimum (ou maximum) devient le second élément. Sinon, le premier est toujours considéré comme l'extremum.
- Ainsi de suite jusqu'au dernier élément du tableau.
Primitive 'Minimum' en Pseudo-Code :
Entier: Fonction MinimumTableau (Tableau: tab):
min=tab[0]
Pour i allant de 0 à nbElements:
Si min>tab[i]:
min=tab[i]
FinSi
FinPour
FinFonction
Implémentation en C de la primitive 'Minimum' (cliquer pour ouvrir)
int MinimumTableau ( Element* pTab)
{
int i;
int iMin = pTab[ 0 ] ; // Initialisation du min
// Détermination de la taille du tableau
int iNbElements = sizeof ( pTab) / sizeof ( pTab[ 0 ] ) ;
/* parcours du tableu à la recherche du minimum */
for ( i= 0 ; i
Recherche
Le principe de cet algorithme est tout simple : parcourir le tableau et vérifier élément par élément s'il s'agit de celui que l'on cherche. Dès que l'élément est trouvé, l'algorithme s'arrête et l'indice de l'élément est renvoyé. De fait, cet algorithme recherche en fait la première occurence d'un élément .
Notons que de la même façon que pour la fonction de recherche d'un extrema, nous aurons ici besoin d'une fonction pour définir ce qu'est 'être égal' pour deux éléments. Dans le cas d'hôtels par exemple, il faudra certainement vérifier qu'à la fois le nom et l'adresse des hôtels concordent pour qu'ils soient considérés comme identiques. Nous utiliserons la fonction de prototype suivant :
boolean IsEgal(element1, element2)
La fonction de recherche d'un élément dans le tableau est dite de complexité O(log(n)). Cela signifie qu'il faudra au maximum un nombre d'opération proportionel au nombre d'éléments du tableau pour trouver celui recherché. Ceci s'explique tout simplement par le fait qu'au pire des cas -si l'élément recherché n'est pas dans le tableau ou si c'est le dernier- il faudra parcourir l'intégralité du tableau avant de le trouver.
Primitive 'Recherche' en Pseudo-Code :
entier: Fonction RechercherTableau(Tableau: tableau, Element: valElement):
Pour i allant de 0 à taille du tableau:
Si tab[i] vaut valElement:
Renvoyer i
FinSi
FinPour
Retourner -1
FinFonction
Implémentation en C de la primitive 'Recherche' (cliquer pour ouvrir)
int RechercherTableau( Element* pTab, Element valElem)
{
int i;
// Détermination de la taille du tableau
int iNbElements = sizeof ( pTab) / sizeof ( pTab[ 0 ] ) ;
/* parcours du tableau */
for ( i= 0 ; i
Imprimer
Envoyer
Bug ou erreur ?