Tableau (structure de donnees)

Tableau (structure de donnees)

Tableau (structure de données)

Page d'aide sur l'homonymie Pour les articles homonymes, voir Tableau.

En informatique, un tableau (array en anglais) est une structure de données de base qui est un ensemble d'éléments (des variables ou autres entités contenant des données), auquel on a accès à travers un numéro d'index (ou indice).

Dans les langages classiques, tous les éléments d'un tableau doivent être du même type. Dans les langages de plus haut niveau (comme Python, APL, etc.), cette restriction n'existe plus.

Sommaire

Performances et limites

Le temps d'accès à un élément par son index est constant, quel que soit l'élément désiré. Cela s'explique par le fait que les éléments d'un tableau sont contigus dans l'espace mémoire. Avec l'index, on sait donc à combien de cases mémoire se trouve l'élément en partant du début du tableau.

Les limites d'une telle structure viennent de son avantage. Un tableau étant représenté en mémoire sous la forme de cellules contiguës, les opérations d'insertion et de suppression d'élément sont impossibles, sauf si on crée un nouveau tableau, de taille plus grande ou plus petite (selon l'opération). Il est alors nécessaire de copier tous les éléments du tableau original dans le nouveau tableau, puis de libérer l'espace mémoire alloué à l'ancien tableau. Cela fait donc beaucoup d'opérations et oblige certains langages fournissant de telles possibilités à implémenter leurs tableaux, non pas sous la forme traditionnelle (cellules adjacentes), mais en utilisant une liste chaînée, ou une combinaison des deux structures pour améliorer les performances.

Tableau à une dimension

Un tableau à une dimension, composé de 7 éléments.

Avec un tableau à une dimension (aussi appelé un vecteur), un numéro d'index donne accès à un seul élément. L'image de droite géométrique est une représentation graphique d'une telle structure de données, composée de 7 éléments.

En algorithmique, un tableau se déclare comme suit :

nomdutableau [valdebut..valfin] : Tableau de type

En langage C par exemple, on accède au premier élément d'un tableau nommé tab de la manière suivante :

tab[0];

En prenant le tableau en exemple, cette instruction retournera 45. Il est important de savoir que la numérotation de l'index commence à 0.

Tableau à deux dimensions (ou plus)

Un tableau à deux dimensions, composé de 25 éléments

La création d'un tableau à deux dimensions (aussi appelé matrice) permet l'accès à plus d'une valeur à partir d'un indice. Autrement dit, un numéro d'index pointe sur un autre tableau. L'image d'un peigne représente une telle structure de données.

Comme on le voit, le premier tableau est composé de pointeurs vers des tableaux. L'accès à un élément se fait donc à travers deux indices.

En langage C, l'accès au troisième élément du quatrième tableau se fait de la manière suivante :

tab[3][2];

Cette instruction retournera 58.

Il n'y a pas de limite au nombre de dimensions (mises à part leur utilité et la taille de la mémoire disponible). Ainsi, l'accès à un élément dans un tableau à n dimensions (où n est un entier naturel non nul) se fait à l'aide de n indices (un indice pour chaque dimension).

La position (ou ordre) des indices est cruciale. Dans l'exemple précédent, l'élément désigné par tab[3][2] (de valeur 58) diffère de l'élément indexé par tab[2][3] (de valeur 89).

Tableau trié

Un Tableau trié est un tableau dont les éléments sont ordonnés selon une relation d'ordre total.

Tableau croisé dynamique

Article détaillé : Tableau croisé dynamique.

Tableaux connus

  • Autres sens dans le Wiktionnaire : voir la page consacrée à tableau.
  • Portail de la programmation informatique Portail de la programmation informatique
Ce document provient de « Tableau (structure de donn%C3%A9es) ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Tableau (structure de donnees) de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Tableau (structure de données) — Pour les articles homonymes, voir Tableau. En informatique, un tableau (array en anglais) est une structure de données de base qui est un ensemble d éléments (des variables ou autres entités contenant des données), auquel on a accès à travers un… …   Wikipédia en Français

  • Structure de donnees persistante — Structure de données persistante En informatique, une structure de données persistante est une structure de données qui préserve ses versions antérieures lorsqu elle est modifiée ; une telle structure est observationnellement immuable, car… …   Wikipédia en Français

  • Structure de données persistante — En informatique, une structure de données persistante est une structure de données qui préserve ses versions antérieures lorsqu elle est modifiée ; une telle structure est observationnellement immuable, car ses opérations ne la modifient pas …   Wikipédia en Français

  • Structure de données — En informatique, une structure de données est une structure logique destinée à contenir des données, afin de leur donner une organisation permettant de simplifier leur traitement. Une structure de données implémente concrètement un type abstrait …   Wikipédia en Français

  • VList (structure de données) — VList En algorithmique, une VList est une structure de données persistante (conçue par Phil Bagwell en 2002), qui combine l accès rapide aux éléments (comme dans les tableaux) avec la souplesse d extension des listes simplement chaînées. Sommaire …   Wikipédia en Français

  • File (Structure De Données) — Pour les articles homonymes, voir File.  Pour les articles homophones, voir Fil et Phil. En informatique, une file ( queue en anglais ) est une structure de données basée sur le principe PEPS (Premier entré, premier sorti), en an …   Wikipédia en Français

  • File (structure de donnees) — File (structure de données) Pour les articles homonymes, voir File.  Pour les articles homophones, voir Fil et Phil. En informatique, une file ( queue en anglais ) est une structure de données basée sur le principe PEPS (Premier entré,… …   Wikipédia en Français

  • File (structure de données) — Pour les articles homonymes, voir File.  Pour les articles homophones, voir Fil et Phil. En informatique, une file ( queue en anglais ) est une structure de données basée sur le principe du Premier entré, premier sorti, en anglais FIFO… …   Wikipédia en Français

  • Maillage (structure de données) — Un maillage en anglais : mesh est une structure de données géométriques permettant de représenter des subdivisions de surface à l aide d un ensemble de polygones. Les maillages sont particulièrement utilisés en infographie, pour représenter… …   Wikipédia en Français

  • structure — [ stryktyr ] n. f. • 1528; « construction » XIVe; lat. structura, de struere « construire » 1 ♦ Manière dont un édifice est construit; agencement des parties d un bâtiment. ⇒aussi superstructure. « L immobile structure des cathédrales »… …   Encyclopédie Universelle

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”