CM #6 : Vecteurs et Tableaux
Objectifs
  • Déclarer un tableau d'entiers, initialiser toutes ses cases et utiliser le tableau
  • Connaître les différentes manières de parcourir un tableau
  • Déclarer, initialiser et utiliser des matrices
  • Connaître l'encodage de texte sous forme d'un tableau de caractères et savoir utiliser les fonctions de gestion de chaînes de caractères contenus dans string.h
  • Savoir concevoir des algorithmes utilisant des tableaux et savoir évaluer leur complexité
  • Connaître la spécificité des tableaux en terme de paramètres

Menu

Lorsque l’on veut utiliser un grand nombre de variables dans un programme, il devient fastidieux d’avoir un identifiant pour chacune des variables. De même certaines données ne sont pas adaptées aux types de base et nécessitent un certain espace mémoire pour être stockées. Pour résoudre ces deux problèmes, on utilise une suite de cases adjacentes en mémoire qui sont indiquées par un seul identificateur. Ainsi les données sont représentées sous forme d’un vecteur (ou tableau en C). L’objectif de ce chapitre est d’aborder la déclaration et l’utilisation de tableaux statiques à une dimension (vecteur) et deux dimensions (matrices). Des exemples classiques de tableaux d’entiers et de caractères sont donnés.

Principe et utilisation

Définition d'un vecteur
Un vecteur ou tableau est une suite de cases dont le contenu est de même type et dont les cases sont numérotées (ou indexées) de 0 à N-1 (pour un tableau de taille N).

En C, la syntaxe de déclaration d’un tableau est la suivante:

#define N 50

int t[N];           // tableau de 50 cases où chaque case est un entier
char tab[512];      // tableau de 512 cases où chaque case est un caractère
float ftab[465789]; // tableau de ...... chaque case est un réel

Ainsi que l’utilisation:

int w = t[10];                  // accès à la case d'indice 10 (11ieme case) du tableau t
int x = 10[t];                  // idem
char y = tab[1024];             // voir remarque ci-dessous
float z = ftab[56 * 3 - 84];    // OK
int t2[N] = {0};                // déclaration et initialisation de toutes les cases à 0
Remarque
Bien qu'illégale d'un point de vue algorithmique (accès à la case d'indice 1024 d'un tableau de 512 cases), la deuxième ligne ne génère pas systématiquement d'erreur à l'exécution. Si l'espace mémoire qui suit le tableau tab n'est pas utilisé (par un autre programme par exemple), alors aucune erreur ne sera générée. Dans le cas contraire, votre programme engendre une erreur du type segmentation fault à l'exécution. Par conséquent, vérifier que vous ne faites pas d'accès en dehors du tableau.

Les tableaux que nous utilisons dans ce cours ont une taille fixée à l’avance (à la déclaration) et ne peuvent pas être redimensionnés. On parle de tableaux statiques. Ceci dit, un certain nombre de fonctions doivent être effectives pour des tableaux de taille quelconque. Pour cela, on peut utiliser des constantes qui définissent la taille des tableaux utilisés ou alors définir des fonctions pour lesquelles la taille des tableaux utilisés sont un paramètre (cette seconde approche est préférable). Le programme suivant illustre ces deux approches:

#include <stdio.h>

const int N = 10;

void affiche_tab (int t[N])
{
    for (int i = 0; i < N; ++i)
    {
        printf ("%d ", t[i]);
    }
    printf ("\n");
}

void affiche_tab2 (int t[], int m)
{
    for (int i = 0; i < m; ++i)
    {
        printf ("%d ", t[i]);
    }
    printf ("\n");
}

int main ()
{
    int tab[N] = { 0 };

    affiche_tab (tab);
    affiche_tab2 (tab, N);

    return 0;
}
Remarque
Dans la déclaration de affiche_tab2, vous pouvez constater que la taille du tableau t n'est pas renseignée. D'une part car m n'est pas connue par le compilateur et donc il n'est pas possible d'écrire int t[m] et d'autre part car la taille est optionnelle dans la déclaration. Ainsi, dans la déclaration de affiche_tab, il est tout à fait possible de ne pas spécifier la taille.
Important: Passage de tableaux en paramètres
Lorsque l'on passe un tableau en paramètre d'une fonction, on ne passe que l'identificateur et pas les crochets et la taille puisqu'en dehors de la déclaration d'un tableau, l'opérateur crochet [] indique qu'on accède à une case et non au tableau en entier.

Algorithme sur les tableaux d’entiers

Voici quelques exemples classiques d’algorithmes pour tableaux d’entiers.

Echange de deux cases d’un tableau

L’algorithme d’échange de cases en C est:

void echange (int i, int j, int t[])
{
    int tmp;
    tmp  = t[i];
    t[i] = t[j];
    t[j] = tmp;
}

int main ()
{
    const int TAILLE = 32;
    int       t[TAILLE];

    // ... init du tableau ...

    echange (2, 3, t);

    return 0;
}
C et paramètres de type tableaux
Les tableaux sont des paramètres modifiables en C contrairement aux types de base (plus de détails seront donnés dans le chapitre sur les pointeurs). Dans le code précédent, le tableau t aura ses cases d'indice 2 et 3 permutées.

Parcours d’un tableau

Ci-dessous se trouve un algorithme qui affiche tous les éléments d’un tableau:

#include <stdio.h>

void print_tab (int tab[], int size_tab)
{
    for (int i = 0; i < size_tab; i++)
    {
        printf ("%d\n", tab[i]);
    }
}

Copie d’un tableau

Ci-dessous se trouve un algorithme qui permet de copier le contenu d’un tableau dans un autre tableau:

void copy_tab (int source_tab[], int dest_tab[], int size_tab)
{
    for (int i = 0; i < size_tab; i++)
    {
        dest_tab[i] = source_tab[i];
    }
}

Recherche dans un tableau

Ci-dessous se trouve un algorithme qui permet de déterminer le plus grand élément d’un tableau:

int max_tab (int tab[], int size_tab)
{
    // hypothèse que size_tab > 0
    int maximum = tab[0];

    for (int i = 1; i < size_tab; i++)
    {
        if (tab[i] > maximum) maximum = tab[i];
    }

    return maximum;
}

Ci-dessous se trouvent deux algorithmes qui permettent de déterminer si un élément est présent dans un tableau. La première version présente une rupture prématurée de flot (la sortie de fonction est dans une boucle), la seconde non. Les deux versions sont effectives mais de manière générale, la seconde version est conseillée car elle offre un code plus lisible et de meilleur qualité (plus facilement maintenable).

#include <stdbool.h>

bool find_in_tab_return (int tab[], int size_tab, int value)
{
    for (int i = 0; i < size_tab; i++)
    {
        if (tab[i] == value) return true;
    }
    return false;
}
#include <stdbool.h>

bool find_in_tab_ (int tab[], int size_tab, int value)
{
    bool found = false;
    int  i     = 0;

    while ((false == found) && (i < size_tab))
    {
        if (tab[i] == value) found = true;
        i++;
    }

    return found;
}

Algorithme sur les mots / textes

En C n’importe quel texte de plus d’un caractère est représenté par un tableaux de caractères. On parle également de chaînes de caractères puisqu’il s’agit d’un type de base dans certains langages de programmation (type string). En C, les chaînes de caractères se terminent par un caractère spécial qui est \0 (code ASCII 0). Ainsi pour stocker le mot toto, il faut un tableau de 5 caractères (4 + 1 pour \0). La déclaration et initialisation de chaînes de caractères se fait de plusieurs manières:

char chaine1[10] = {'t', 'o', 't', 'o'};
char chaine2[100] = "toto";
char chaine3[] = "toto"; // taille calculée automatiquement, ici 5

char c = chaine1[2]; // c vaut `t`

Les algorithmes sur les caractères reprennent les mêmes principes que ceux sur les tableaux d’entiers. Ci-dessous un algorithme qui compte le nombre d’occurrences de la lettre a dans une chaîne de caractères:

#include <string.h>

int count_occurences (char char_tab[])
{
    int occurences = 0;

    for (unsigned long i = 0; i < strlen (char_tab); i++)
    {
        if ('a' == char_tab[i]) occurences++;
    }

    return occurences;
}

Tableaux à deux dimensions / Matrices

Une matrice est ici un tableau à deux dimensions et impose les mêmes contraintes que les vecteurs à savoir que tous les éléments doivent être de même type et que la taille (nombre de lignes et de colonnes) doit être fixée. Pour une matrice de taille $N \times M$, les lignes sont indexées de 0 à N-1 et les colonnes de 0 à M-1.

Déclaration et utilisation

En C, la syntaxe se déduit facilement de la syntaxe des vecteurs et bien entendu les mêmes restrictions existent que pour les vecteurs(débordement mémoire):

int m[456][946];
char n[456][223];

int x = m[10][20]; // accès à la case (10, 20)
int y = n[456 / 10][50];

Exemples classiques

Ci-dessous se trouve un algorithme qui permet d’afficher le contenu d’une matrice (affichage en ligne):

const int M = 128;
const int N = 64;

void print_matrix (int mat[M][N])
{
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            printf ("%d ", mat[i][j]);
        }
        printf ("\n"); // retour a la ligne apres chaque ligne de mat
    }
}

Erreurs classiques sur les tableaux

Pas d’initialisation

Ce principe est le même que pour les variables de type de base (int, float, char…): toutes les variables doivent être initialisées avant d’être utilisées, comme le montre l’exemple ci dessous:

#include <stdio.h>

void affiche_tab(int t[], int n)
{
    for (int i = 0; i < n; ++i)
    {
        printf("%d ", t[i]);
    }
    printf("\n");
}

int main()
{
    const int N = 10;
    int tab[N];

    affiche_tab(tab, N);

    return 0;
}
jdequidt@weppes:~$ clang tab_non_init.c -Wall
jdequidt@weppes:~$ ./a.out
1583286184 32767 0 0 0 0 0 0 0 0
jdequidt@weppes:~$ ./a.out
1565579176 32767 0 0 0 0 0 0 0 0
jdequidt@weppes:~$

Débordement mémoire

Il faut toujours s’assurer que dans les parcours de tableaux ou de matrices, on inspecte des cases valides. Dans le cas contraire, les conséquences peuvent être importantes et particulièrement complexes à corriger comme le montre l’exemple suivant:

#include <stdio.h>

void affiche_tab(int t[], int n)
{
    for (int i = 0; i < n; ++i)
    {
        printf("%d ", t[i]);
    }
    printf("\n");
}

void debordement(int t[], int n)
{
    for (int i = 0; i < 2 * n; ++i)
    {
        t[i] = i * i;
    }
}

int main()
{
    const int N = 10;
    int tab[N] = {0};
    int tab2[N] = {0};

    debordement(tab2, N);

    printf("tab = ");
    affiche_tab(tab, N);
    printf("tab2 = ");
    affiche_tab(tab2, N);

    return 0;
}
jdequidt@weppes:~$ clang tab_non_init.c -Wall
jdequidt@weppes:~$ ./a.out
tab = 144 169 196 225 256 289 324 361 0 0
tab2 = 0 1 4 9 16 25 36 49 64 81
jdequidt@weppes:~$

On constate que le contenu de tab est modifié après son initialisation alors qu’aucune instruction ne le modifie directement. La fonction qui modifie tab2 déborde sur tab et modifie donc indirectement les valeurs de tab. Les conséquences peuvent être plus graves si on appelle la fonction debordement avec tab en paramètre. Dans ce cas, le résultat est le suivant:

jdequidt@weppes:~$ clang tab_non_init.c -Wall
jdequidt@weppes:~$ ./a.out
Segmentation Fault
jdequidt@weppes:~$ echo $?
134
jdequidt@weppes:~$

Le débordement mémoire provoque une erreur de segmentation qui provoque l’arrêt du programme. La commande echo $? affiche le code de retour du main, il est différent de 0 preuve que le programme ne s’est pas exécuté correctement.

Copie de tableaux

Il n’est pas possible de copier un tableau autrement qu’en copiant son contenu case par case. Ainsi l’expression a = b ou a et b sont deux tableaux ne fonctionne pas, cf:

int main()
{
    const int N = 10;
    int tab[N] = {0};
    int tab2[N] = {0};

    init(tab, N);

    tab2 = tab;

    return 0;
}
jdequidt@weppes:~$ clang affect_tab.c -Wall
jdequidt@weppes:~$ ./a.out
temp.c:7:7: error: array type 'int [10]' is not assignable
        tab2 = tab;
        ~~~~ ^
1 error generated.