Structures de données - Tableau

Le tableau est l'une des structures de données les plus élémentaires et les plus couramment utilisées.

Un tableau est une collection d'éléments de même type stockés de manière contiguë en mémoire.


Définition d'un tableau et disposition en mémoire

En C, après la déclaration d'un tableau, un bloc de mémoire contigu est alloué, et chaque élément peut être accédé directement par son index.

数组内存布局示意图

La figure ci-dessus montre la disposition mémoire d'un tableau contenant 5 éléments int. En supposant que l'adresse de départ soit 0x1000 et que chaque int occupe 4 octets, alors :

  • arr[0]Situé à l'adresse 0x1000
  • arr[1]Situé à l'adresse 0x1004 (0x1000 + 4)
  • arr[i]Situé à l'adresse 0x1000 + i × 4

C'est précisément en raison de cette caractéristique de stockage contigu que les tableaux peuvent utiliseradresse de départ + décalagepour accéder à n'importe quel élément en temps O(1).

Tableau unidimensionnel

Exemple

#include <stdio.h>

int main() {
    /* Déclarer et initialiser un tableau unidimensionnel */
    int arr[5] = {10, 20, 30, 40, 50};

    /* Parcourir et accéder à chaque élément */
    printf("Éléments du tableau : ");
    for (int i = 0; i < 5; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");  /* Sortie : éléments du tableau : 10 20 30 40 50 */

    /* Accès direct par indice, complexité temporelle O(1) */
    printf("arr[2] = %d\n", arr[2]);  /* Sortie : 30 */

    return 0;
}

Tableau multidimensionnel

C prend en charge les tableaux multidimensionnels, les plus courants étant les tableaux à deux dimensions, souvent utilisés pour représenter des données tabulaires telles que des matrices.

Les tableaux à deux dimensions sont toujours stockés de manière contiguë en mémoire par lignes (ordre ligne-major), et sont associés à une vue bidimensionnelle en calculant les indices de ligne et de colonne.

Exemple

#include <stdio.h>

int main() {
    /* Déclarer un tableau à deux dimensions avec 3 lignes et 4 colonnes */
    int matrix[3][4] = {
        {1,  2,  3,  4},
        {5,  6,  7,  8},
        {9, 10, 11, 12}
    };

    /* Parcourir le tableau à deux dimensions : la boucle externe parcourt les lignes, la boucle interne parcourt les colonnes */
    printf("Tableau à deux dimensions (matrice 3×4) :\n");
    for (int i = 0; i < 3; i++) {        /* i est l'indice de ligne */
        for (int j = 0; j < 4; j++) {    /* j est l'indice de colonne */
            printf("%2d ", matrix[i][j]);
        }
        printf("\n");
    }

    /* Accéder à un élément spécifique : matrix[row][column] */
    printf("matrix[1][2] = %d\n", matrix[1][2]);  /* Sortie : 7 */
    return 0;
}

La formule de calcul d'adresse mémoire pour un tableau à deux dimensions :元素地址 = 起始地址 + (i × 列数 + j) × sizeof(元素类型). Où i est l'indice de ligne, et j est l'indice de colonne.


Opérations de base sur les tableaux

数组插入和删除操作流程

La figure ci-dessus montre les étapes essentielles des opérations d'insertion et de suppression dans un tableau : pour l'insertion, les éléments après la position cible doivent être décalés un par un vers l'arrière pour faire de la place ; pour la suppression, les éléments après la position cible doivent être décalés un par un vers l'avant pour combler l'espace vide.

Parcours

Exemple

#include <stdio.h>

/* Parcourir et afficher tous les éléments du tableau Complexité temporelle : O(n), où n est la longueur du tableau */
"Résultat du parcours : "

void traverse(int arr[], int n) {
    printf(/* Calculer la longueur du tableau */);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {15, 28, 43, 56, 71};
    int n = sizeof(arr) / sizeof(arr[0]);  Insertion
    traverse(arr, n);
    return 0;
}

Insertion

Exemple

#include <stdio.h>

"Le tableau est plein, impossible d'insérer
"Position d'insertion invalide
/* De l'arrière vers l'avant, décaler d'une position vers l'arrière les éléments à partir de pos et au-delà */
/* Écrire les données à la nouvelle position */
/* Augmenter le nombre d'éléments de 1 */

int insert(int arr[], int n, int pos, int value, int capacity) {
    if (n >= capacity) {
        printf(/* La capacité est de 10, elle contient actuellement 4 éléments */\n");
        return -1;
    }
    if (pos < 0 || pos > n) {
        printf("Avant l'insertion : "\n");
        return -1;
    }

    /* Sortie : Avant l'insertion : 10 20 30 40 */
    for (int i = n; i > pos; i--) {
        arr[i] = arr[i - 1];
    }
    arr[pos] = value;  /* Écrire les données à la nouvelle position */
    return n + 1;      /* Augmenter le nombre d'éléments de 1 */
}

int main() {
    int arr[10] = {10, 20, 30, 40};  /* La capacité est de 10, actuellement il y a 4 éléments */
    int n = 4;

    printf(Avant l'insertion :); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");  /* Sortie : Avant l'insertion : 10 20 30 40 */

    n = insert(arr, n, 2, 25, 10);  /* Insérer 25 à l'index 2 */

    printf("Après insertion : "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");  /* Sortie : Après insertion : 10 20 25 30 40 */
    return 0;
}

Suppression

Exemple

#include <stdio.h>

/* Supprimer l'élément à une position spécifiée dans le tableau
Paramètres : arr tableau, n nombre actuel d'éléments, pos position de suppression (base 0)
Complexité temporelle : O(n), le pire cas nécessite de déplacer n éléments
Valeur de retour : le nombre d'éléments après suppression */

int delete(int arr[], int n, int pos) {
    if (n <= 0) {
        printf("Le tableau est vide, impossible de supprimer"\n");
        return 0;
    }
    if (pos < 0 || pos >= n) {
        printf("Position de suppression invalide\n");
        return n;
    }

    /* De l'avant vers l'arrière, déplacer les éléments après pos d'une position vers l'avant */
    for (int i = pos; i < n - 1; i++) {
        arr[i] = arr[i + 1];
    }
    return n - 1;  /* Diminuer le nombre d'éléments de 1 */
}

int main() {
    int arr[10] = {10, 20, 30, 40, 50};
    int n = 5;

    printf("Avant suppression : "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");  /* Sortie : Avant suppression : 10 20 30 40 50 */

    n = delete(arr, n, 2);  /* Supprimer l'élément à l'indice 2 (30) */

    printf("Après suppression : "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");  /* Sortie : Après suppression : 10 20 40 50 */
    return 0;
}

Rechercher

Pour trouver une valeur cible dans un tableau non trié, la méthode la plus directe consiste à parcourir tout le tableau et à comparer un par un, ce que l'on appelle la recherche linéaire.

Exemple

#include <stdio.h>

/* Recherche linéaire : rechercher une valeur cible dans un tableau
Complexité temporelle : O(n), le pire cas nécessite de parcourir tout le tableau
Valeur de retour : l'indice de l'élément cible, renvoie -1 s'il n'est pas trouvé */

int search(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;  /* Trouvé, retourner l'indice */
        }
    }
    return -1;  /* Non trouvé */
}

int main() {
    int arr[] = {43, 17, 89, 25, 61};
    int n = 5;

    int idx = search(arr, n, 89);
    if (idx != -1) {
        printf("Valeur cible 89 trouvée, l'indice est %d\n", idx);  /* Sortie : Valeur cible 89 trouvée, l'indice est 2 */
    } else {
        printf("Valeur cible introuvable\n");
    }
    return 0;
}

Avantages et inconvénients des tableaux

AvantagesDescription
Accès aléatoire en O(1)On peut accéder à n'importe quel élément en temps constant via l'indice, ce qui constitue le plus grand avantage des tableaux.
Mémoire contiguëLe stockage contigu favorise les succès du cache CPU (localité spatiale), ce qui améliore l'efficacité des accès
Implémentation simpleSyntaxe intuitive, prise en charge nativement dans la plupart des langages de programmation
InconvénientsDescription
Taille fixeLes tableaux statiques en C ont une taille définie à la compilation et ne peuvent pas être redimensionnés dynamiquement
Insertion/suppression lentesInsérer ou supprimer des éléments au milieu d'un tableau nécessite de déplacer de nombreux éléments, avec une complexité temporelle de O(n)
Gaspillage d'espaceSi le tableau déclaré est trop grand mais que l'utilisation réelle est faible, cela entraîne un gaspillage de mémoire

Ce sont précisément ces limitations qui donnent naissance à la structure dynamique plus flexible qui sera étudiée dans le chapitre suivant —Liste chaînée。


Résumé de la complexité des opérations

OpérationComplexité temporelleDescription
Accès par indexO(1)Calcul direct de l'adresse
Insertion à la finO(1)Pas besoin de déplacer les éléments
Insertion en tête/au milieuO(n)Besoin de déplacer les éléments suivants
Supprimer le dernier élémentO(1)Pas besoin de déplacer les éléments
Supprimer l'élément en tête/au milieuO(n)Besoin de déplacer les éléments suivants
Recherche linéaireO(n)Comparer un par un
Recherche binaire (tableau trié)O(log n)Nécessite que le tableau soit trié
Autres extensions