Structures Référentielles en C

Bonjour à tous, futurs magiciens de la programmation ! Aujourd'hui, nous allons entreprendre un voyage passionnant à travers le monde des structures auto-référentielles en C. Ne vous inquiétez pas si cela semble un peu intimidant - je promets que nous le décomposerons en morceaux mangeables, même ma grand-mère pourrait les comprendre (et croyez-moi, elle pense toujours qu'une souris n'est qu'un petit animal poilu).

Quelles sont les Structures Auto-référentielles ?

Imaginez que vous êtes à une fête et que vous voulez présenter votre ami à quelqu'un. Vous pourriez dire : "C'est mon ami Alex, et Alex est aussi développeur logiciel." Dans cette présentation, vous faites référence à Alex deux fois - une fois par son nom et une fois par sa profession. C'est similaire à la façon dont les structures auto-référentielles fonctionnent en C !

Une structure auto-référentielle est une structure qui contient un pointeur vers une structure du même type dans sa définition. C'est comme une poupée russe, mais au lieu de petites poupées à l'intérieur, c'est le même type de structure tout le long.

Définir une Structure Auto-référentielle

Voyons comment nous définissons ces structures fascinantes. Voici un exemple simple :

struct Node {
int data;
struct Node* next;
};

Dans cet exemple, nous avons défini une structure appelée Node. Elle contient deux membres :

1. Un entier data pour stocker certaines informations.
2. Un pointeur next qui pointe vers une autre structure Node.

C'est l'essence d'une structure auto-référentielle - elle se réfère à elle-même dans sa propre définition.

Exemples de Structures Auto-référentielles

Maintenant, examinons quelques exemples pratiques où nous pourrions utiliser des structures auto-référentielles.

1. Nœud de Liste Chaînée

Nous avons déjà vu celui-ci, mais analysons-le plus en détail :

struct ListNode {
int data;
struct ListNode* next;
};

Cette structure est parfaite pour créer une liste chaînée. Chaque nœud contient certaines données et un pointeur vers le nœud suivant dans la liste.

2. Nœud d'Arbre

Les arbres sont un autre cas d'utilisation commun pour les structures auto-référentielles :

struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};

Ici, chaque nœud de l'arbre peut avoir jusqu'à deux enfants (gauche et droit), ce qui nous permet de créer des arbres binaires.

3. Nœud de Graphique

Pour ceux d'entre vous qui aiment l'aventure, voici comment nous pourrions représenter un nœud dans un graphe :

struct GraphNode {
int data;
struct GraphNode** neighbors;
int neighborCount;
};

Dans ce cas, nous avons un tableau de pointeurs vers d'autres structures GraphNode, représentant les connexions dans notre graphe.

Créer une Liste Chaînée avec une Structure Auto-référentielle

Maintenant que nous comprenons les bases, créons une liste chaînée simple en utilisant notre structure auto-référentielle. Ne vous inquiétez pas si vous ne comprenez pas tout de suite - Rome ne s'est pas construite en un jour, et ni ne le fera l'expertise en codage !

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

// Fonction pour créer un nouveau nœud
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Fonction pour imprimer la liste chaînée
void printList(struct Node* head) {
struct Node* current = head;
printf("Notre liste chaînée : ");
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}

int main() {
struct Node* head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(3);

printList(head);

return 0;
}

Voici ce que cela fait :

1. Nous définissons notre structure Node comme avant.
2. Nous créons une fonction createNode qui alloue de la mémoire pour un nouveau nœud et initialise ses données.
3. Nous avons une fonction printList qui traverse la liste et imprime les données de chaque nœud.
4. Dans main, nous créons une liste chaînée avec trois nœuds et l'imprimons.

Lorsque vous exécutez ce programme, vous devriez voir :

Notre liste chaînée : 1 -> 2 -> 3 -> NULL

Créer une Liste Chaînée Double avec une Structure Auto-référentielle

Maintenant, levons le niveau et créons une liste chaînée double. C'est comme une liste chaînée régulière, mais chaque nœud a également un pointeur vers le nœud précédent. C'est comme une rue à double sens au lieu d'une rue à sens unique !

#include <stdio.h>
#include <stdlib.h>

struct DoubleNode {
int data;
struct DoubleNode* next;
struct DoubleNode* prev;
};

// Fonction pour créer un nouveau nœud
struct DoubleNode* createDoubleNode(int data) {
struct DoubleNode* newNode = (struct DoubleNode*)malloc(sizeof(struct DoubleNode));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}

// Fonction pour imprimer la liste chaînée en avant
void printForward(struct DoubleNode* head) {
struct DoubleNode* current = head;
printf("Avant : ");
while (current != NULL) {
printf("%d <-> ", current->data);
current = current->next;
}
printf("NULL\n");
}

// Fonction pour imprimer la liste chaînée en arrière
void printBackward(struct DoubleNode* tail) {
struct DoubleNode* current = tail;
printf("Arrière : ");
while (current != NULL) {
printf("%d <-> ", current->data);
current = current->prev;
}
printf("NULL\n");
}

int main() {
struct DoubleNode* head = createDoubleNode(1);
head->next = createDoubleNode(2);
head->next->prev = head;
head->next->next = createDoubleNode(3);
head->next->next->prev = head->next;

struct DoubleNode* tail = head->next->next;

printForward(head);
printBackward(tail);

return 0;
}

Dans cet exemple :

1. Notre structure DoubleNode a maintenant des pointeurs next et prev.
2. Nous créons des fonctions pour imprimer la liste en avant et en arrière.
3. Dans main, nous créons une liste chaînée double et définissons les pointeurs next et prev.

Lorsque vous exécutez ce programme, vous devriez obtenir :

Avant : 1 <-> 2 <-> 3 <-> NULL
Arrière : 3 <-> 2 <-> 1 <-> NULL

Créer un Arbre avec une Structure Auto-référentielle

Enfin, créons un arbre binaire simple en utilisant notre structure auto-référentielle. Pensez à cela comme un arbre familial, où chaque personne peut avoir jusqu'à deux enfants.

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};

// Fonction pour créer un nouveau nœud
struct TreeNode* createTreeNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// Fonction pour effectuer une traversée en ordre
void inOrderTraversal(struct TreeNode* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}

int main() {
struct TreeNode* root = createTreeNode(1);
root->left = createTreeNode(2);
root->right = createTreeNode(3);
root->left->left = createTreeNode(4);
root->left->right = createTreeNode(5);

printf("Traversée en ordre de l'arbre : ");
inOrderTraversal(root);
printf("\n");

return 0;
}

Dans cet exemple final :

1. Notre structure TreeNode a des pointeurs left et right pour les nœuds enfants.
2. Nous créons une fonction pour effectuer une traversée en ordre, qui visite d'abord le sous-arbre gauche, puis la racine, puis le sous-arbre droit.
3. Dans main, nous créons un arbre binaire simple et effectuons une traversée en ordre.

Lorsque vous exécutez ce programme, vous devriez obtenir :

Traversée en ordre de l'arbre : 4 2 5 1 3

Et voilà, amis ! Nous avons fait le voyage à travers le pays des structures auto-référentielles, des listes chaînées simples aux listes chaînées doubles et même aux arbres binaires. Souvenez-vous, la pratique rend parfait, donc n'ayez pas peur d'expérimenter avec ces structures et de créer vos propres variantes. Qui sait ? Vous pourriez être la prochaine personne à inventer une structure de données révolutionnaire !

Bonne programmation, et que les structures auto-référentielles soient avec vous !

Credits: Image by storyset