Leçon 44 : Structures auto-référentielles (Introduction aux listes chaînées)

Une structure auto-référentielle est une structure qui contient au moins un membre qui est un pointeur vers une autre structure du même type.

Ces structures sont les éléments de base pour construire des structures de données dynamiques comme les listes chaînées, les arbres et les graphes.

Définir la structure

La structure doit inclure un champ de données et un champ pointeur.

c struct Noeud { int donnee; // Donnée stockée dans ce noeud struct Noeud *suivant; // Pointe vers le prochain noeud de la liste };

Remarque : La structure ne peut pas contenir la structure elle-même en tant que membre (ex: struct Noeud n;) car cela nécessiterait une mémoire infinie. Ce doit être un pointeur vers le type de la structure.

Concept de liste chaînée

Une liste chaînée est une séquence de nœuds où chaque nœud est relié au suivant par un pointeur.

1. Un pointeur spécial (head ou debut) pointe vers le premier nœud.
2. Chaque nœud pointe vers le nœud suivant.
3. Le pointeur du dernier nœud est mis à NULL pour signifier la fin de la liste.

Exemple (Liaison conceptuelle)

c struct Noeud *tete, *noeud1, *noeud2;

// 1. Allouer de la mémoire pour les noeuds noeud1 = (struct Noeud *)malloc(sizeof(struct Noeud)); noeud2 = (struct Noeud *)malloc(sizeof(struct Noeud));

// 2. Définir les données noeud1->donnee = 10; noeud2->donnee = 20;

// 3. Les relier noeud1->suivant = noeud2; noeud2->suivant = NULL; // Fin de la liste

tete = noeud1; // Point de départ

Nous avons créé une liste : TETE -> [10 | adresse_2] -> [20 | NULL].