Retour à l'index
La première façon d'utiliser les pointeurs, vue à la section précédente, nous permet de gagner un peu de place en mémoire centrale. Mais nous n'avons pas encore vraiment de structure de données dynamique (nous avons toujours un problème s'il y a plus de 500 éléments dans notre répertoire). La notion de structure auto-référente va nous permettre de construire de vraies structures de données dynamiques.
Voyons ceci sur un exemple, celui des listes chaînées.
Si nous reprenons le problème précédent de manipulation d'un répertoire en mémoire centrale, une structure de donnée plus intéressante que celle de tableau (dont la dimension est fixée une fois pour toute) est celle de liste chaînée. L'idée de base est très simple.
Une telle liste est constituée d'éléments, comme pour un tableau. Un élément contient des informations utiles à l'utilisateur, comme pour un tableau, mais aussi des informations structurelles pour construire la liste. Plus exactement on aura un pointeur désignant l'élément suivant.
Bien entendu si on fait ainsi on a une liste infinie. On a donc besoin d'une valeur spéciale de pointeur qui ne pointe sur rien (ce qui permet de terminer la liste) : c'est le pointeur nul. Le dessin ci-dessus se réécrit alors plutôt de la façon suivante, le pointeur nul étant traditionnellement représenté par une croix.
| Problème de la déclaration récursive | Essayons de déclarer le type d'une telle liste chaînée, par exemple en langage C. Nous pouvons penser à la déclaration suivante :
struct DONNEE {
char nom[30];
char tel[20];
struct DONNEE *suivant;
};
Il y a cependant un cercle vicieux (appelé plus particulièrement ici du nom technique de récursivité) car on utilise le type pointeur de DONNEE dans la déclaration de DONNEE. |
| Syntaxe | On utilise cependant quand même la dé nition récursive du genre de celle que nous venons de voir. C'est au niveau de la conception du compilateur qu'il faudra résoudre ce problème de récursivité. |
| Définition | Une structure auto-référente est une structure dans laquelle un ou plusieurs champs ont pour type un pointeur sur cette structure. |
Le programme suivant crée une liste chaînée dont les éléments sont des structures comprenant un nom, un numéro de téléphone et un pointeur permettant d'accéder à l'élément suivant. Le répertoire lui-même est un pointeur, de nom debut, permettant d'accéder au premier élément. Pour simplifier, la liste est créée en partant du dernier élément, et non pas du premier.
On affiche, dans une seconde étape, les valeurs de la liste. Celle-ci sera affichée dans l'ordre inverse de l'ordre d'entrée.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct DONNEE
{
char nom[30];
char tel[20];
struct DONNEE *suivant;
};
int main(void)
{
struct DONNEE item, *debut, *ptr;
char name[30], telephone[20];
/* Initialisation de la liste */
debut = NULL;
do
{
printf("\nNom : ");
scanf("%s",name);
if (name[0] != '#')
{
printf("Telephone : ");
scanf("%s",telephone);
ptr = (struct DONNEE *) malloc(sizeof(item));
strcpy(item.nom, name);
strcpy(item.tel,telephone);
item.suivant = debut;
*ptr = item;
debut = ptr;
}
} while (name[0] != '#');
/* Affichage de la liste */
printf("\nLa liste dans l\'ordre inverse est :\n");
while (debut != NULL)
{
printf("%s : %s\n",debut->nom, debut->tel);
debut = debut->suivant;
}
/* Liberation des pointeurs */
while (debut != NULL)
{
ptr = debut;
debut = debut->suivant;
free(ptr);
}
}
Cours, éxercices ou graphismes libre de droit. Un mail est souhaitable | Webmestre : Aublet Bastien (bastien.aublet@hotmail.fr)