Les tableaux

Définition

Logo 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. 
Représentation en mémoire d'un tableau
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 :

  1. Tableau: InsertionTableau (Tableau: tab, Element: nouvElement):
  2. ajouter une case au tableau
  3. Si (espace mémoire alloué)
  4. tab[nbElements+1]=nouvElement
  5. renvoyer tab
  6. sinon
  7. ECHEC: impossible de redimensionner le tableau
  8. FinFonction

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 :

  1. Tableau: SuppressionTableau (Tableau: tab, Entier: indice):
  2. Pour i=indice à nbreElement(tab) Faire
  3. tab[i]=tab[i+1]
  4. FinFaire
  5. Supprimer dernière case
  6. Si (redimensionnement OK)
  7. Renvoyer tab
  8. sinon
  9. ECHEC: impossible de redimensionner le tableau
  10. FinFonction

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:

  1. boolean IsPlusPetit(element1, element2);
  2. 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 :

  1. Entier: Fonction MinimumTableau (Tableau: tab):
  2. min=tab[0]
  3. Pour i allant de 0 à nbElements:
  4. Si min>tab[i]:
  5. min=tab[i]
  6. FinSi
  7. FinPour
  8. FinFonction

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 :

  1. 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 :

  1. entier: Fonction RechercherTableau(Tableau: tableau, Element: valElement):
  2. Pour i allant de 0 à taille du tableau:
  3. Si tab[i] vaut valElement:
  4. Renvoyer i
  5. FinSi
  6. FinPour
  7. Retourner -1
  8. FinFonction

Votre note : Aucun(e) Moyenne : 2.5 (23 votes)

Commentaires

Utilisateur non enregistré

acheter viagra securise

[url=http://buyviagraonlinezrx.com/]buy viagra online[/url]

viagra online

average age men viagra