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/
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,
. 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 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ération | Tableau | Liste chaînée |
|---|---|---|
| accès au i-ème élément | ||
| insérer ou supprimer au milieu (position connue) | ||
| croissance | taille fixe ou réallocation | un nœud à la fois |
| mémoire supplémentaire | aucune | un pointeur par nœud |
| usage du cache | excellent, cellules contiguës | mé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
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
, 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.






Sono l'autore di questa pagina su «Struct, liste concatenate e strutture dati». Se qualcosa non è chiaro, se vi serve un esempio in più o volete approfondire un punto, scrivetelo qui sotto nei commenti: rispondo personalmente. Se la pagina vi è stata utile, lasciate un voto con le stelle in cima all'articolo.I am the author of this page on “Structs, linked lists and data structures”. If something is unclear, if you need another example or want to go deeper into a point, write it in the comments below: I answer personally. If the page was useful, leave a star rating at the top of the article.