Chapitre 4 :

Les tableaux
Sommaire

Mise en situation
I- Les tableaux
1- Les tableaux unidimensionnels
2- Les tableaux multidimensionnels
II- Les tableaux et les pointeurs
III- Opérations sur les tableaux
1- Tri par sélection du minimum
2- Tri par insertion
3- Tri à bulles
4- Tri rapide (quicksort)

Mise en situation :
Les variables ( int float char) ne permettent de stocker qu'une seule
donnée à la fois. Ces variables distinctes seraient beaucoup trop lourdes à
gérer. Le langage C propose les tableaux, permettant de stocker plusieurs
données de même type.

I‐ Les tableaux

Un tableau est une structure de données linéaire qui regroupe de manière contiguë
en mémoire (les unes à la suite des autres) des variables de même type.

Un tableau est donc une suite contigüe de cases (espace mémoire) de même taille. La taille
de chacune des cases est déterminée par le type de donnée que le tableau contient.

donnée donnée donnée ... donnée donnée donnée

Représentation d’un tableau

Les éléments du tableau peuvent être :

- des données de type simple : int, char, float, long, double...

31
 (la taille d'une case du tableau est alors le nombre d'octets sur lequel la donnée
est codée) ;
- des structures ;
- des tableaux.
- des pointeurs (variables contenant des adresses mémoires) ;

Attention :
Etant donné qu'un tableau est composé d'un nombre fixé d'éléments d'un
type donné, la taille d'un tableau est déterminée dès sa déclaration.

 Classification des tableaux :

- Lorsque le tableau est composé de données de type simple, on parle de tableau

monodimensionnel (ou vecteur).
- Lorsque celui-ci contient lui-même d'autres tableaux on parle alors de tableaux
multidimensionnels (ou matrice )

1‐ Les tableaux unidimensionnels

Un tableau unidimensionnel est un tableau qui contient des éléments qui ne sont pas
des tableaux.

Syntaxe :
La déclaration d'un tableau unidimensionnel est la suivante :

type Nom_du_tableau [Nombre d'éléments] ;

Représentation
Un tableau unidimensionnel contenant n entiers est représenté de la façon suivante :

indice 0 1 2 ... n
int int int .. int int Int

Exemple :

La déclaration d'un tableau qui doit contenir 8 éléments de type char :

char Tableau [8] ={‘A’,’B’,’C’,’D’,’E’,’F’,’G’,’H’};

indice 0 1 2 3 4 5 6 7
A B C D E F G H

32
 Accéder aux éléments

Pour accéder à un élément du tableau : le nom du tableau, suivi de l'indice de l'élément

entre crochets :

Nom_du_tableau[indice] ;

Remarque :

- L'indice du premier élément du tableau est 0

- L'indice du dernier élément du tableau est égal au nombre d'éléments – 1

Initialiser les éléments

Lorsque l'on définit un tableau, les valeurs des éléments qu'il contient ne sont pas
définies, il faut donc les initialiser (leur affecter une valeur).

 - Initialisation de chaque élément :

Affecter des valeurs aux éléments un par un:

Nom_Tableau[0] = Valeur 1 ;
Nom_Tableau[1] = Valeur 2 ;
Nom_Tableau[2] = Valeur 3 ;

Initialisation avec des boucles :

Utiliser une boucle (for) qui va permettre d'initialiser successivement chacun des
éléments.

for (i=0 ;i<taille_du_tableau ;i++)

{
printf("Entrer la valeur %d:\n") ;
scanf("%d", & Nom_Tableau[i]) ; //%d %c %f selon le cas
}

Initialisation à la déclaration :
D’initialiser le tableau à la définition en plaçant entre accolades les valeurs, séparées par
des virgules :

int Tableau[10] = {1, 2, 6, 5, 2, 1, 9, 8, 1, 5};

33
 2‐ Les tableaux multidimensionnels

Mise en situation :
Lignes et colonnes

Solution :

Exercice :
Comment représenter une année ? (1 an =56 semaines).

Les tableaux multidimensionnels sont des tableaux qui contiennent des tableaux.
On les appelle également : Matrices

Syntaxe :
La déclaration d’un tableau multidimensionnel se définit de la manière suivante :

type Nom_du_tableau [a1][a2][a3] ... [aN]

Exemple :
Définira avec la syntaxe suivante :

int Tableau [3][4]

34
On peut représenter un tel tableau de la manière suivante :

Tableau[0][0] Tableau[0][1] Tableau[0][2] Tableau[0][3]

Tableau[1][0] Tableau[1][1] Tableau[1][2] Tableau[1][3]
Tableau[2][0] Tableau[2][1] Tableau[2][2] Tableau[2][3]

- C’est un tableau qui comporte 3 éléments, chaque élément est un tableau de 4

éléments.
- Les valeur-s sont attribuées aux éléments successifs en incrémentant d'abord les
indices de droite, c'est-à-dire pour un tableau à 2 dimensions : [0][0], [0][1], [0][2]
... puis [1][0] etc.

Représentation
Tableau bidimensionnel (3 lignes, 4 colonnes) est stocké en mémoire de la manière
suivante :

Ou bien

II‐ Les tableaux et les pointeurs

Les écritures suivantes sont équivalentes:

Déclaration int *tableau; int tableau[10];

tableau = malloc(sizeof(int)*10);
…….
free(tableau)
adresse du 1er élément tableau &tableau[0]
adresse d'un autre élément (tableau + i) &(tableau[i])
le 1er élément *tableau tableau[0]
un autre élément *(tableau+i) tableau[i]

35
Attention :
- La déclaration d'un tableau entraîne automatiquement la
réservation de places en mémoire.
- Ce n'est pas le cas lorsque l'on déclare un pointeur. Il faut alors
utiliser une fonction d'allocation dynamique comme malloc.

Exemple :

36
En résumé :

III‐ Opérations sur les tableaux

On peut effectuer sur les tableaux plusieurs opérations :

- Permuter deux éléments
- Supprimer un élément ? (+ décalage)
- Décaler un élément ? (+ sauvegarde)
- Ajouter un élément ?( chercher position + sauvegarde + décalage)
- Trier un tableau

Algorithmes du Tri

Trier un ensemble d’objets consiste à les ordonner en fonction d’une relation d’ordre
définie sur ces objets.

Il faut connaitre qu'il existe 6 algorithmes connus pour trier les éléments d’un tableau :

 tri par sélection

 tri par insertion
 tri a bulle
 tri rapide
 tri par permutation
 tri par fusion

Cependant on ne va détailler que les 2 premiers types

37
1. Tri par sélection du minimum

Exemple : Tri par sélection : Trier un jeu de carte à la main !

Principe : Le principe du tri par sélection du minimum est d'aller

• Rechercher le plus petit élément et le permuter avec le premier élément t[0].
• Rechercher le deuxième petit élément et le permuter avec le deuxième élément
t[1].
• Faire la même chose avec le reste des éléments jusqu'à ce que le tableau soit
trié.

38
Explication de l’exemple :

Exemple :

Exemple de tri par sélection

39
Programme : Travaux Pratique

40
2. Tri par insertion :
Le principe du tri par insertion est de trier les éléments du tableau comme avec des cartes
: prendre les éléments du tableau un à un, et de les insérer au bon endroit.

Tri par insertion : Exemple concret

41
Principe de l’algorithme
- Les éléments à trier étaient donnés un par un.
- Prendre le premier élément :
le premier élément constituant, à lui tout seul, un tableau trié de longueur 1.
- On classe ensuite le second élément pour constituer un tableau trié de longueur 2,
- puis on classe le troisième élément pour avoir une liste triée de longueur 3
…. et ainsi de suite...

Le principe est donc d’insérer à la nième itération le nième élément à la bonne place.

Exemple :

42
Explication de l’exemple :

43
Programme : Travaux Pratique

44
3. Tri à bulles :

Il consiste à parcourir la liste en échangeant les paires d'éléments consécutifs qui ne sont
pas dans l'ordre. On effectue autant de parcours que des échanges sont nécessaires.
Autrement dit, on arrête dès qu'un parcours n'a fait aucun échange. Voir la figure gauche
ci-dessous.

Exemple de tri à bulles

4. Tri rapide (quicksort) :

Cette méthode consiste à choisir une valeur pivot, et séparer les éléments de la liste en
deux parties : ceux inférieurs au pivot, et ceux supérieurs au pivot. Les deux parties sont
alors triées, puis concaténées (la partie inférieure avant la partie supérieure). Pour le
pivot, on peut prendre le premier élément de la liste à trier. Voir la figure droite ci-
dessous.

45
 Exemple de tri rapide

Conclusion : Tableaux

 Avantages :
 Stocke des éléments même types,
 Les éléments sont stockés dans des emplacements de mémoire contigus
 Peut accéder facilement aux éléments à tout moment en utilisant l'index
 Tri et itération faciles

 Inconvénients :
 La taille est fixe
 Difficile à insérer et à supprimer
 Nécessite de la mémoire contiguë pour être allouée
 Si la taille déclarée est supérieure à celle utilisée : espace mémoire gaspillé.
 Espace mémoire figé : Impossible de l’agrandir (à moins d'en créer de nouveaux,
plus grands).
 On ne peut pas agrandir un tableau après sa création
 Insérer/supprimer une case au milieu : décaler d’autres éléments.
Cas d’utilisation :
• Pour stocker des informations de manière linéaire
• Convient aux applications nécessitant des recherches fréquentes

46