Retour à l'index
Avec les éléments de programmation que nous connaissons, nous sommes capables de programmer tout ce qui est programmable. Cependant l'expérience des programmeurs a conduit à introduire d'autres notions, théoriquement non indispensables mais facilitant nettement la pratique de la programmation. Ceci est le cas des sous-programmes ; c'est le cas également des structures de données que nous allons étudier maintenant.
Jusqu'à maintenant on attribuait une variable simple par donnée à un instant précis. Il arrive que les données soient nombreuses et aient un certain lien entre elles, ce concept de lien étant considéré de façon intuitive et suffisamment vague pour l'instant. Ce phénomène conduit à considérer ce que l'on appelle une structure de données en informatique.
Lorsque les données sont nombreuses et de même nature, au lieu de manipuler un grand nombre de variables, il est plus pratique de ranger ces variables dans un tableau.
La notion de tableau est une notion courante très utilisée, pas seulement en informatique. Il s'agit la plupart du temps de tableaux à deux dimensions avec des lignes et des colonnes. Mais on peut aussi considérer des tableaux à une seule dimension (ce sont plutôt des listes dans le langage courant) ou à plusieurs dimensions (plus difficilement représentables de façon graphique à partir de la quatrième dimension).
Voyons, d'une part, comment mettre en oeuvre les tableaux en programmation et, d'autre part, leur intérêt pour les problèmes de programmation. Nous allons étudier les tableaux à une dimension, les tableaux à deux dimensions puis les tableaux à plusieurs dimensions.
| Notion intuitive. | Un tableau à une dimension est formé d'éléments tous de même nature et repérés par un index. |
| Représentation graphique. | Un tableau à une dimension est souvent représenté comme une suite de cases avec un index pointant sur une case. N.B. : tab = tab[0] |
Un tableau (à une dimension) porte un nom qui est, comme d'habitude, un identicateur non déjà utilisé pour autre chose, par exemple TAB. Il s'agit plus exactement d'une variable de tableaux.
| Syntaxe. | La déclaration d'un tableau suit la syntaxe suivante : <type> <Nom> [Entier]; où Type est un type, Nom est un identicateur et Entier une expression constante entière positive. |
| Sémantique. | Type est le type des éléments du tableau, Nom est le nom du tableau et Entier est le nombre (maximum) d'éléments du tableau. |
| Exemple. | On déclare un tableau TAB de cinq réels de la façon suivante : float TAB [5]; |
| Syntaxe. | L'accès à un élément du tableau de nom Nom se fait en désignant cet élément de la façon suivante : Nom[index] où index est une expression entière positive. |
| Sémantique. | Ceci permet de désigner l'élément du tableau dont l'index est celui désigné. En langage C, comme en général en informatique et contrairement à ce qui se passe en mathématiques, l'indexation commence à 0 (et non à 1). La
valeur de l'index doit donc être comprise entre 0 et Entier-1. |
| Exemple. | Si on veut accèder au troisième élément du tableau déclaré ci-dessus, donc celui d'index 2, il sufft d'écrire TAB[2]. Ceci conduit à des instructions du genre : TAB[3] = 4.5; X = 3*TAB[I] + 2*TAB[I+5]; à condition, bien sûr, que la variable X soit déclarée d'un type convenable et que I et I+5 prennent leurs valeurs parmi les index possibles. |
| Remarque. | En langage C, comme dans la plupart des langages informatiques, il n'y a pas de vérication pour savoir si la valeur de l'index est bien comprise entre 0 et Entier-1. Si on sort de l'intervalle d'indexation, on risque de récupérer des valeurs sans signication (en cas de lecture) ou, pire, de détruire une partie du contenu de la mémoire vive (en cas d'écriture). Il faut donc être extrêmement vigilant à l'égard de ce problème. Lorsque l'exectution d'un programme contenant un tel contenu tente d'accéder à une partie mémoire non autorisée, le programme retourne une erreur. Cette erreur est la 'SegmentationFault' qui est la pire erreur du langage C. En effet, cette erreur ne peut ê détécté à la compilation et nous savons que l'erreur existe mais sans savoir à quelle ligne. |
| Introduction. | Nous allons traiter un premier exemple montrant l'intérêt de la notion de tableau pour des problèmes de programmation. Le problème suivant est suffisamment courant et exemplaire pour qu'on s'y intéresse. |
| Problème. | Les élèves d'une classe ont obtenu chacun une note à un certain examen. Nous voulons déterminer combien d'entre eux ont une note supérieure à la moyenne de la classe. |
| Un premier algorithme. | Le premier algorithme auquel on peut penser est le suivant :
|
| Inconvénient de cet algorithme. | Cet algorithme possède un inconvénient majeur pour l'utilisateur : il faut saisir l'ensemble des notes deux fois. On comprend que l'ordinateur ne peut pas deviner les notes et qu'il faut donc les saisir une fois, mais l'ordinateur ne pourrait-il pas retenir les notes ? |
| Un meilleur algorithme. | Soit N le nombre d'élèves. On peut :
|
| Programme. | Ceci nous conduit au programme suivant en supposant qu'il y ait 59 élèves :
#include <stdio.h>
int main(void)
{
int i, s;
float m; /* m pour moyenne */
float note[59];
/* Saisie des notes */
for (i=0 ; i < 59 ; i++)
{
printf("\nQuelle est la note numero %d : ",i+1);
scanf("%f", ¬e[i]);
}
/* Calcul de la moyenne */
m = 0; /* initialisation de la moyenne */
for (i = 0 ; i < 59 ; i++) /* la moyenne : somme des note ... */
m = m + note[i];
m = m/59; /* ... puis division par le nombre de note. */
printf("\nLa moyenne est de : %4.2f", m);
/* Calcul du nombre de notes superieures a la moyenne */
s = 0;
for (i = 0 ; i < 59 ; i++)
if (note[i] >= m) /* si la note est supperieur à la moyenne ... */
s = s+1; /* ... on augmente le nombre d'élève ayant une note supperieur a la moyenne, de 1*/
printf("\nLe nombre de notes superieures a la moyenne de la classe est de : %d \n", s);
}
|
| Avantage et inconvénient de cet algorithme. | On voit tout de suite l'avantage de cet algorithme par rapport au précédent pour l'utilisateur. Cependant il présente également un inconvénient : le nombre d'élèves doit être connu au moment de la programmation alors, que pour le premier algorithme, il était demandé à l'utilisateur. |
| Introduction. | On peut contourner en général l'inconvénient que nous venons de constater pour l'utilisation des tableaux. On déclare une dimension maximum du tableau puis on demande une dimension effective à l'utilisateur, ce qui détermine la partie du tableau réellement utilisée. |
| Exemple. | Ceci nous conduit, par exemple, au programme suivant, en supposant qu'il y a au plus 150 élèves par classe :
#include <stdio.h>
int main(void)
{
const int max = 150;
int n, i, s;
float m;
float note [max];
/* Determination du nombre effectif d'eleves */
printf("Quel est le nombre d\'eleves ? : ");
scanf("%d", &n);
/* Saisie des notes */
for (i=0 ; i < n ; i++)
{
printf("\nQuelle est la note numero %d : ",i+1);
scanf("%f", ¬e[i]);
}
/* Calcul de la moyenne */
m = 0;
for (i = 0 ; i < n ; i++)
m = m + note[i];
m = m/n;
printf("\nLa moyenne est de : %4.2f", m);
/* Calcul du nombre de notes superieures a la moyenne */
s = 0;
for (i = 0 ; i < n ; i++)
if (note[i] >= m)
s = s+1;
printf("\nLe nombre de notes superieures a la moyenne de la classe est de : %d\n", s);
}
|
| Remarque. | On notera la déclaration de la constante max pour la dimension maximum du tableau. Si celle-ci se révèle un jour insuffisante il suffit de changer cette ligne. Tout inconvénient a-t-il complètement disparu ?. Bien sûr que non puisque, comme nous venons de le faire remarquer, la dimension maximum peut se révéler insuffisante. L'expérience montre cependant que pour certains problèmes de programmation, tel que celui que nous venons de considérer, il existe des dimensions maximum naturelles. Remarquons aussi que nous avons remplacé un inconvénient par un autre. En effet le tableau avec sa dimension maximum occupe plus de place que nécessaire en mémoire centrale. On dit que la structure de données tableau est une structure de données statique, par opposition aux structures de données dynamiques pour lesquelles l'utilisateur peut saisir la taille au moment de l'exécution (et non avant la compilation). |
| Introduction. | On peut initialiser un tableau de façon individuelle, élément par élément, par exemple grâce à une boucle. Mais, en langage C, on peut aussi initialiser le tableau lors de sa déclaration. |
| Syntaxe. | On fait suivre la déclaration du tableau du signe d'égalité puis des valeurs (qui sont des expressions constantes), séparées par des virgules et placées entre accolades :
type Nom [Entier] = { k1, k2, ... , kEntier-1}; |
| Sémantique. | Si le nombre de valeurs est inférieur au nombre d'éléments du tableau, les éléments en trop sont remplis avec des 0 (tout au moins dans le cas de tableaux de nombres). |
| Exemple. | On peut écrire : int TAB [5] = {1, 34, 10, 24};et on a alors, par exemple, TAB[2] = 10 |
Cours, éxercices ou graphismes libre de droit. Un mail est souhaitable | Webmestre : Aublet Bastien (bastien.aublet@hotmail.fr)