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
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
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
/* 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
"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
/* 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
/* 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
| Avantages | Description |
|---|---|
| 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 simple | Syntaxe intuitive, prise en charge nativement dans la plupart des langages de programmation |
| Inconvénients | Description |
|---|---|
| Taille fixe | Les tableaux statiques en C ont une taille définie à la compilation et ne peuvent pas être redimensionnés dynamiquement |
| Insertion/suppression lentes | Insé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'espace | Si 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ération | Complexité temporelle | Description |
|---|---|---|
| Accès par index | O(1) | Calcul direct de l'adresse |
| Insertion à la fin | O(1) | Pas besoin de déplacer les éléments |
| Insertion en tête/au milieu | O(n) | Besoin de déplacer les éléments suivants |
| Supprimer le dernier élément | O(1) | Pas besoin de déplacer les éléments |
| Supprimer l'élément en tête/au milieu | O(n) | Besoin de déplacer les éléments suivants |
| Recherche linéaire | O(n) | Comparer un par un |
| Recherche binaire (tableau trié) | O(log n) | Nécessite que le tableau soit trié |