Aller au contenu
Encyclopédie informatique Édition 2026

Tableaux, listes et structures de données

Partie 2 sur 3

Niveau de lecture :

4La structure

Le tableau impose un seul type d’élément. Or, une fiche de personne contient un nom (du texte), un âge (un entier) et une moyenne (un nombre décimal). Les structures « permettent de remédier à cette lacune des tableaux, en regroupant des objets (des variables) au sein d’une entité repérée par un seul nom ». Chaque objet contenu est un champ (on dit aussi membre).

4.1Déclarer une structure, puis définir une variable

Il faut distinguer deux étapes, qu’il importe de bien séparer :

  • La déclaration décrit la forme de la structure : le type et le nom de chaque champ. Elle ne réserve aucune mémoire ; elle crée un nouveau type, comme on décrirait un modèle de formulaire.
  • La définition d’une variable structurée crée une variable de ce type et lui réserve de la place, comme on remplirait un exemplaire du formulaire.
struct Personne {
    char nom[12];
    int  age;
    char sexe;
    float moyenne;
};                       /* le point-virgule final est obligatoire */

struct Personne pierre, paul, jacques;   /* trois variables */
pierre.age = 18;
pierre.sexe = 'M';

Le point-virgule qui suit l’accolade fermante est une cause classique d’erreur. Pour accéder à un champ, on emploie l’opérateur de champ, un simple point, entre le nom de la variable et celui du champ : pierre.age. Le nom d’un champ n’a de sens que dans la variable où il se trouve.

4.2Ce qu’une structure peut et ne peut pas contenir

Les règles sont les suivantes : le nom d’un champ suit les règles des noms de variables, deux champs ne peuvent pas avoir le même nom, et un champ peut être de n’importe quel type sauf le type de la structure elle-même. Pourquoi cette dernière interdiction ? Parce qu’une structure qui se contiendrait elle-même serait de taille infinie : elle contiendrait une copie de soi, qui contiendrait une copie de soi, et ainsi de suite. En revanche, elle peut contenir un pointeur vers une structure du même type, car une adresse a une taille fixe. C’est la clé de la liste chaînée (partie 5).

4.3Tableaux de structures

Comme une structure a une taille fixe, on peut faire un tableau de structures :

struct Personne repertoire[8];     /* 8 personnes */
repertoire[0].age = 31;

On peut aussi passer des structures à des fonctions, ou en renvoyer. En C++, le mot struct n’est plus nécessaire après la déclaration : on écrit Personne repertoire[8]; (voir le langage C++). C’est aussi en C++ que les structures ont évolué vers les classes, qui y ajoutent des fonctions (voir la programmation orientée objet).

4.4Ce que l’on oublie souvent : l’alignement

La taille d’une structure n’est pas toujours la somme de la taille de ses champs. Les processeurs lisent la mémoire plus vite, ou parfois seulement, quand chaque valeur commence à une adresse adaptée à sa taille. Le compilateur ajoute donc des octets vides, appelés remplissage (padding), entre les champs. La figure 2 en donne un exemple avec trois champs : un caractère (1 octet), un entier (4 octets) et un autre caractère.

L’ORDRE DES CHAMPS CHANGE LA TAILLE D’UNE STRUCTURE char c; int n; char d; c 0 vide 1 vide 2 vide 3 n 4 n 5 n 6 n 7 d 8 vide 9 vide 10 vide 11 taille : 12 octets dont 6 octets de remplissage int n; char c; char d; n 0 n 1 n 2 n 3 c 4 d 5 vide 6 vide 7 taille : 8 octets dont 2 octets de remplissage Le compilateur laisse des vides pour que chaque champ commence à une adresse adaptée à sa taille. Les tailles données sont des valeurs courantes (int sur 4 octets) ; elles varient selon la machine.
Figure 2. Les mêmes champs dans un autre ordre donnent une structure plus petite : 8 octets au lieu de 12.

Pour économiser la mémoire sur des millions d’éléments, on range en général les champs du plus gros au plus petit. Ce détail compte aussi pour la sécurité et l’échange de données : copier une structure telle quelle dans un fichier ou sur le réseau transmet aussi le remplissage, dont le contenu est imprévisible, et dépend du compilateur. On sérialise, c’est-à-dire que l’on écrit chaque champ à son tour (voir XML et JSON).

Pour s’exercer

Exercice 4 : alignement

Avec un int de 4 octets aligné sur 4, quelle est la taille de struct { char a; double b; char c; } si le double (8 octets) est aligné sur 8 ? Comment la réduire ?

Voir la réponse

a à l’octet 0, 7 octets de remplissage, b aux octets 8 à 15, c à l’octet 16, puis 7 octets de remplissage pour que la taille totale soit un multiple de 8 : 24 octets. En rangeant b, a, c, on obtient 8 + 1 + 1 = 10 octets, complétés à 16 : 16 octets.

5La liste chaînée

Un tableau a un défaut : sa taille est fixe. Insérer un élément au milieu oblige à décaler tous les suivants. La liste chaînée résout ce problème en abandonnant la contiguïté : les éléments sont éparpillés en mémoire et reliés par des « liens logiques », c’est-à-dire des adresses. On la présente comme une structure autoréférentielle (ou récursive) : une structure dont au moins un champ est un pointeur vers une structure du même type.

5.1Le maillon

Chaque élément de la liste est un maillon (on dit aussi nœud ou lien). Il contient les données et l’adresse du maillon suivant :

struct Maillon {
    char chaine[16];
    struct Maillon *suivant;   /* adresse du maillon suivant */
};

Pour ne pas perdre la liste, il faut conserver quelque part l’adresse du premier maillon : c’est le pointeur de tête. Le dernier maillon n’a pas de suivant : son pointeur reçoit la valeur spéciale NULL, qui signifie « rien » (voir les pointeurs et la mémoire). La figure 1 montre une liste de quatre maillons. Selon le contenu des maillons, on distingue trois formes :

  • la liste simplement chaînée : données et pointeur vers le suivant ;
  • la liste doublement chaînée : données, pointeur vers le suivant et pointeur vers le précédent, ce qui permet de la parcourir dans les deux sens ;
  • l’arbre binaire : données et deux pointeurs, vers un « fils gauche » et un « fils droit ».

5.2Ajouter un maillon en tête

L’ajout se fait en trois temps : réserver la mémoire du nouveau maillon avec malloc, faire pointer son champ « suivant » vers l’ancienne tête, puis déclarer le nouveau maillon comme tête. Voici la version correcte :

#include <stdlib.h>
#include <string.h>

struct Maillon *ajouter_en_tete(struct Maillon *tete, const char *texte)
{
    struct Maillon *nouveau = malloc(sizeof *nouveau);
    if (nouveau == NULL) {
        return tete;            /* plus de mémoire : on ne change rien */
    }
    strncpy(nouveau->chaine, texte, sizeof nouveau->chaine - 1);
    nouveau->chaine[sizeof nouveau->chaine - 1] = '\0';
    nouveau->suivant = tete;    /* l'ancien premier devient le deuxième */
    return nouveau;             /* le nouveau est la nouvelle tête */
}

Des corrections utiles. On voit écrire Nouveau = (Liste*)malloc(sizeof(struct Liste)); : en C, le type de la structure est struct Liste, pas Liste, et le transtypage (la conversion explicite d’un type vers un autre, ici devant malloc) est inutile et déconseillé. Il est bon de tester la valeur renvoyée par malloc, ce que nous faisons. On oublie en revanche souvent de dire qu’il faut rendre la mémoire avec free quand on n’a plus besoin du maillon (voir 5.5). Enfin, la copie de texte avec strcpy sans contrôle de longueur est une source classique de dépassement de tampon ; on lui préfère une copie bornée.

5.3Ajouter en fin de liste

Pour ajouter à la fin, on utilise un pointeur courant, qui parcourt la liste jusqu’au dernier maillon, celui dont le suivant vaut NULL. L’idée est juste, mais le code que l’on voit souvent ne gère pas le cas d’une liste vide, où la tête vaut NULL et où le pointeur courant n’a rien à parcourir. Version complète :

struct Maillon *ajouter_en_fin(struct Maillon *tete, const char *texte)
{
    struct Maillon *nouveau = malloc(sizeof *nouveau);
    if (nouveau == NULL) return tete;
    strncpy(nouveau->chaine, texte, sizeof nouveau->chaine - 1);
    nouveau->chaine[sizeof nouveau->chaine - 1] = '\0';
    nouveau->suivant = NULL;       /* le dernier n'a pas de suivant */

    if (tete == NULL) return nouveau;   /* liste vide : c'est la tête */

    struct Maillon *courant = tete;
    while (courant->suivant != NULL) {
        courant = courant->suivant;
    }
    courant->suivant = nouveau;
    return tete;
}

Le coût est visible : il faut parcourir toute la liste pour y arriver. Si l’on ajoute souvent en fin, on conserve un second pointeur vers le dernier maillon pour y aller directement.

5.4Parcourir, chercher, supprimer

Parcourir une liste se fait avec une boucle qui avance de maillon en maillon jusqu’à NULL :

for (struct Maillon *m = tete; m != NULL; m = m->suivant) {
    printf("%s\n", m->chaine);
}

Supprimer un maillon demande de faire « sauter » le lien : le maillon précédent doit pointer vers le suivant du maillon supprimé, après quoi on rend la mémoire du maillon retiré. Si le maillon à supprimer est la tête, c’est la tête elle-même qui change. Rien de tout cela ne coûte de décalage, contrairement au tableau : c’est l’avantage de la liste.

5.5Rendre la mémoire

Chaque maillon créé avec malloc doit être rendu avec free. Pour libérer toute une liste, il faut lire le suivant avant de libérer le maillon courant, sinon on lirait une mémoire déjà rendue :

while (tete != NULL) {
    struct Maillon *suivant = tete->suivant;
    free(tete);
    tete = suivant;
}

Oublier cette boucle provoque une fuite de mémoire, et la faire dans le mauvais ordre une utilisation de mémoire libérée, deux erreurs étudiées dans l’article sur les pointeurs et la mémoire.

5.6Liste doublement chaînée et arbre binaire

Dans une liste doublement chaînée, chaque maillon contient aussi l’adresse du précédent. On peut alors supprimer un maillon sans retrouver son prédécesseur par parcours, et circuler dans les deux sens. Le prix est un pointeur de plus par maillon et plus de liens à maintenir à jour à chaque modification. (Erreur fréquente : omettre le point-virgule après pPrecedent dans la déclaration de la structure double.)

Un arbre binaire généralise l’idée : chaque nœud a deux fils. Si l’on range les valeurs de façon que tout ce qui est à gauche d’un nœud soit plus petit et tout ce qui est à droite plus grand, on obtient un arbre binaire de recherche : pour trouver une valeur, on ne descend que d’une branche à chaque étape, ce qui divise le travail par deux à chaque pas, tant que l’arbre est équilibré. C’est la base de beaucoup d’index de bases de données (voir les algorithmes).

Pour s’exercer

Exercice 5 : suivre une liste

Une liste contient, de la tête vers la fin, les valeurs 5, 8, 2. On ajoute 9 en tête, puis on supprime le maillon contenant 8. Quelle est la liste finale ? Quels liens ont changé ?

Voir la réponse

Après l’ajout : 9, 5, 8, 2 (le suivant de 9 est l’ancienne tête, 5 ; la tête vaut maintenant 9). Après la suppression de 8 : 9, 5, 2. Le suivant du maillon 5, qui pointait vers 8, pointe maintenant vers 2 ; le maillon 8 est ensuite rendu avec free.