Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Informatique

Structures, listes chaînées et structures de données

Structures et typedef, l'opérateur flèche, listes chaînées avec insertion et parcours, comparaison avec les tableaux, piles, files, arbres et tables de hachage.

https://www.electronics-engineering.com/fr/structures-listes-chainees-structures-de-donnees/

Pas encore de vote : soyez le premier à noter cette page.

Un tableau contient des données du même type. Mais souvent une information est faite de données différentes qui vont ensemble : un composant a un code, une valeur, une tolérance et une quantité en stock. Les structures (struct) du C regroupent des champs de types différents en un seul nouveau type. Avec les structures et les pointeurs on construit des structures de données dynamiques, dont la première est la liste chaînée. Dans cette leçon nous voyons les deux, avec leurs avantages et inconvénients par rapport aux tableaux.

Les structures

#include <stdio.h>

struct component {
    char   code[16];
    double value;         /* in ohms, farads or henries */
    double tolerance;     /* in per cent */
    int    quantity;
};

int main(void)
{
    struct component r = {"R-10K", 10e3, 1.0, 250};
    r.quantity -= 10;                                     /* fields are accessed with a dot */
    printf("%s: %.0f ohm +/- %.0f%%, %d pieces\n", r.code, r.value, r.tolerance, r.quantity);
    return 0;
}

Avec typedef le type reçoit un nom plus court : typedef struct component Component;. Les structures peuvent être copiées par affectation, passées aux fonctions et mises dans des tableaux : Component stock[500]; est une petite base de données.

Une grande structure passée par valeur est copiée en entier. On passe en général son adresse, et on accède aux champs avec l’opérateur flèche : p->value est une abréviation de (*p).value.

double minimum_value(const Component *c)
{
    return c->value * (1.0 - c->tolerance / 100.0);
}

La liste chaînée

Un tableau a deux limites : sa taille est fixe, et insérer un élément au milieu oblige à décaler tous ceux qui suivent, O(n). Une liste chaînée résout les deux : chaque élément (nœud) contient la donnée et un pointeur vers le nœud suivant ; le dernier pointe sur NULL.

typedef struct node {
    int value;
    struct node *next;
} Node;
Insertion d'un nœud dans une liste chaînée entre deux nœuds existants
Une liste de trois nœuds (3, 8, 15) à partir du pointeur de tête. Pour insérer 11 entre 8 et 15 il suffit de créer le nouveau nœud, de le faire pointer sur 15 puis de faire pointer 8 sur le nouveau nœud : deux affectations, rien n’est déplacé.

Insertion et parcours

#include <stdlib.h>

/* inserts v after node prev; returns the new node or NULL */
Node *insert_after(Node *prev, int v)
{
    Node *n = malloc(sizeof *n);
    if (n == NULL) return NULL;
    n->value = v;
    n->next = prev->next;      /* 1: the new node points to the next one */
    prev->next = n;            /* 2: the previous one points to the new node */
    return n;
}

void print(const Node *head)
{
    for (const Node *p = head; p != NULL; p = p->next) {
        printf("%d ", p->value);
    }
    printf("\n");
}

L’ordre des deux affectations compte : les faire dans l’autre sens fait perdre la référence au reste de la liste. Supprimer un nœud est tout aussi rapide : on fait pointer le précédent sur le suivant, et le nœud retiré est libéré avec free.

Tableau ou liste ?

OpérationTableauListe chaînée
accès au i-ème élémentO(1)O(n) : il faut parcourir
insérer ou supprimer au milieu (position connue)O(n) : décalageO(1)
croissancetaille fixe ou réallocationun nœud à la fois
mémoire supplémentaireaucuneun pointeur par nœud
usage du cacheexcellent, cellules contiguësmédiocre, nœuds dispersés

En pratique, sur les processeurs modernes, les tableaux sont souvent plus rapides même quand la théorie favorise les listes, justement à cause du cache. Les listes sont utiles quand les insertions et suppressions à des positions connues sont fréquentes, ou quand les éléments doivent rester à la même adresse.

Piles, files et autres structures

Les tableaux et les listes servent à construire les structures de données fondamentales :

  • pile : le dernier élément entré est le premier sorti (LIFO). C’est la pile d’appels des fonctions, et celle qu’utilise une calculatrice en notation polonaise inverse.
  • file : le premier élément entré est le premier sorti (FIFO). C’est le tampon circulaire qui reçoit les octets d’un port série : l’interruption de réception les met dans la file, le programme principal les lit à son rythme.
  • arbres : chaque nœud a plusieurs successeurs. Les arbres binaires de recherche trouvent un élément en O(\log n) pas, et les systèmes de fichiers organisent dossiers et fichiers en arbre.
  • tables de hachage : elles trouvent un élément à partir de sa clé en temps moyen O(1), en calculant directement la position avec une fonction de la clé. Ce sont les « dictionnaires » de Python et les objets de JavaScript.

Choisir la bonne structure de données, c’est la moitié du travail de conception d’un programme : comme le disait Niklaus Wirth, algorithmes plus structures de données égalent programmes.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x