Résumé
Dans cette série d'articles, nous présentons le langage C. Il ne s'agit pas de réécrire les ouvrages de référence donnés en annexe, mais de donner, au travers du C, une méthode de programmation basée sur la notion d'interface.
Au fur et à mesure de notre progression, nous nous sentons plus libres dans la conception de nos programmes. Nous commençons à aborder des programmes complexes et à passer plus de temps sur la conception que sur la programmation. C'est bon signe.
Ce mois-ci, nous continuons avec une structure de données très utilisée, à la base de toutes les structures dynamiques : la liste. Nous allons programmer une bibliothèque de listes à double chaînage permettant de stocker des objets de toute nature.
Les sources présentées ici sont disponibles à l'adresse http://www.erian-concept.com/pub/liste.tgz.
Description
La liste est une structure de donnée élémentaire. Elle est tellement importante qu'elle a servi à définir un langage, Lisp, pour LISt Programming. Un dérivé de Lisp plus accessible et épuré est le langage Scheme décrit dans ces colonnes :)
La liste est une structure de donnée permettant de rassembler des objets et de les acceder en séquence. Pour optimiser cette description, nous ajoutons le double chaînage qui permet de parcourir les éléments de la liste dans les deux sens, du premier au dernier et du dernier au premier.
La liste peut être réalisée de manière statique, en remplissant un tableau où chaque élément possède une référence vers l'objet contenu et l'index de la case précédente et de la case suivante. Par exemple :
-
Index
Elément
Précédent
Suivant
0
443
4
3
1
123
-1
4
2
3
764
0
-1
4
456
1
0
En considérant qu'une variable contient l'index du premier élément de la liste, ici 1, et que l'index -1 signifie qu'il n'y a pas de lien, nous avons la liste :
--> 123 --> 456 --> 443 --> 764
Cette manière de procéder possède l'avantage d'être simple à réaliser et efficace car il n'y pas d'allocation dynamique de mémoire. Elle pourra être utilisée dans tous les cas où le nombre maximum d'éléments de la liste est connu ``et pas trop grand''.
Cependant, la liste statique ne permet pas de s'adapter si le nombre d'éléments est tantôt très petit, tantôt très grand. Sa consommation de mémoire est fixée une fois pour toute au moment de l'écriture du programme et ne peut pas être modifiée plus tard.
Une liste qui adapte sa consommation de mémoire en fonction des besoins doit utiliser l'allocation dynamique. Nous avons vu dans un précédent article que la fonction malloc est une fonction standard du C ANSI. Elle retourne à partir d'un tas (en anglais heap) l'adresse d'une zone de mémoire de la taille voulue. Cette zone mémoire est libérée avec la fonction free appelée avec l'adresse retournée par malloc. Une fois la zone libérée, la zone de mémoire peut être réutilisée. Deux précautions doivent être prises en utilisant ces fonctions : 1°) malloc peut retourner l'adresse nulle, ce qui indique qu'il n'y pas plus de mémoire disponible dans le tas, 2°) free doit être appelée une seule fois pour une adresse valide retournée par malloc. Bien que simplement énoncées, ces contraintes sont à l'origine de bien des écrans bleus.
Avec ces deux fonctions nous allons être en mesure de définir une structure de donnée que nous appellerons cellule représentant les éléments de la liste. Cette structure contient deux pointeurs, le premier pointe vers la cellule précédente et le second pointe vers la cellule suivante. La cellule devra aussi contenir l'objet C.
Interface
Nous pouvons commencer la création de la bibliothèque en spécifiant son interface. On placera les définitions suivantes dans le fichier public liste.h :
#ifndef
___LISTE_H
#define ___LISTE_H
/* type de
données */
typedef struct s_Liste
* Liste;
typedef struct s_Cellule *
Cellule;
typedef int Element;
/*
fonctions de base */
Liste liste_cree
(void);
void liste_detruit
(Liste);
void liste_ajoute
(Liste, Element);
Element liste_enleve
(Liste);
Cellule liste_reference (Liste liste,
unsigned
index);
/* fonctions avancées */
Cellule
liste_premier (Liste);
Cellule
liste_dernier (Liste);
Cellule
liste_suivant (Cellule);
Cellule
liste_precedent (Cellule);
Element liste_element (Cellule);
#endif
/* ___LISTE_H */
Nous testons tout d'abord la macro ___LISTE_H afin d'éviter les inclusions multiples. Dans le cas où le fichier est inclus pour la première fois, nous définissons cette macro. Ensuite, nous déclarons les types de données qui seront manipulés, à savoir le type Liste et le type Element. Ce dernier est le type des éléments qui seront insérés dans la liste ; dans un premier temps, nous nous contenterons des entiers. Par la suite, nous étendrons ce type pour manipuler toutes sortes d'objets.
La première fonction crée une liste vide ; la seconde fonction détruit la liste donnée en argument, qu'elle soit vide ou non. La fonction qui suit permet d'ajouter un élément en tête de liste. Ensuite, la fonction suivante permet de supprimer l'élément en tête de liste et retourne cet élément. Enfin, la dernière fonction permet d'obtenir le nième élément de la liste.
Cette interface assez simple permet déjà d'effectuer la plupart des opérations courantes.
Utilisation
Dans cette section, nous procédons comme un utilisateur de la bibliothèque partant de l'interface qui définit les fonctionnalités publiques : la seule chose que nous connaissons de cette bibliothèque est regroupée dans ce fichier d'en-tête.
Avant de commencer à programmer un exemple simple d'utilisation des listes, nous allons examiner la manière de générer des nombres pseudo-aléatoires à l'aide de fonctions standard de la bibliothèque du langage C.
Nombres (pseudo) aléatoires
Les nombres pseudo-aléatoires peuvent être générés très facilement en C, en utilisant des fonctions standard. Ces fonctions génèrent des séquences d'entiers avec des algorithmes connus. Cette séquence est toujours la même à l'allumage de la machine. C'est pour cette raison qu'on qualifie ces nombres de pseudo-aléatoires. Pour éviter cet inconvénient, la bibliothèque standard permet d'initialiser la séquence à partir d'un certain index. En utilisant un nombre basé sur la date du jour, par exemple, on obtient des séquences de nombres différentes à chaque allumage de la machine.
Linux utilise un démon pour initialiser pour nous cette séquence ; ce démon est nommé random, et vous devriez le voir notifié au démarrage de votre système, si toutefois vous le l'avez pas désactivé.
La fonction qui permet d'obtenir un nombre aléatoire est rand(void) qui retourne un entier. Cette fonction est définie dans le fichier d'en-tête stdlib.h. La fonction qui permet d'initialiser la séquence des nombres est void srand(unsigned int). Pour utiliser un index basé sur la date du jour, on pourra utiliser la fonction time() définie dans le fichier d'en-tête time.h. Si cette fonction est appelée avec zéro comme argument, elle retourne le nombre de secondes écoulées depuis 1970. Sinon, l'argument est l'adresse d'une variable de type time_t capable de recevoir la valeur.
En regroupant toutes ces fonctions, on obtient par exemple :
/*
fichier d'en-tête */
#include <stdlib.h>
/* rand et srand */
#include <time.h> /*
time */
#include <stdio.h> /*
printf */
/* programme principal */
void
main (void) {
int i;
/*
initialisation de la séquence avec
* la
date du jour */
srand ((unsigned
int) time (0));
/* affichage des
20 premiers nombres
* pseudo-aléatoires
*/
for (i = 0; i < 20; i++)
{
int n = rand();
printf
("nombre aléatoire n°%d = %d\n",
i,
n);
}
}
Programme principal
Maintenant que nous sommes capables de gérer les nombres aléatoires, nous allons commencer notre programme de manipulations des listes à double chaînage.
Il s'agit de créer une liste dont le nombre d'éléments sera choisi de manière aléatoire. Cette liste va être remplie avec des nombres eux-mêmes aléatoires.
Le caractère dynamique du programme vient du fait que la taille de la liste est aléatoire. Nous l'avons cependant limitée à une valeur limite pour éviter les problèmes de saturation de la mémoire.
/*
fichiers d'en-tête */
#include
<liste.h>
#include <stdio.h>
#include
<stdlib.h>
#include <time.h>
/*
programme principal */
void main (void)
{
int taille, i,
element;
Liste liste;
Cellule
cellule;
/* création de la liste
*/
liste = liste_cree();
if
(! liste) abort();
/* remplissage de
la liste */
srand ((unsigned int)
time (0));
do taille = rand();
while (taille <= 0);
taille = taille %
100;
for (i = taille -1; i >= 0; i--)
{
element = rand();
printf
("élément n° %d = %d\n",
i, element);
liste_ajoute (liste,
element);
}
/* affichage de la
liste */
i = 0;
while
(1) {
cellule = liste_element (liste,
i);
if (! cellule) {
printf
("fin de liste\n");
break;
}
printf
("élément n° %d =
%d\n",
i,
liste_element
(cellule));
i++;
}
/*
destruction de la liste */
liste_detruit
(liste);
}
Ce programme est compilable dans la mesure où le fichier d'en-tête liste.h existe, mais il ne pourra pas être lié pour produire un exécutable car nous n'avons pas encore réalisé le fichier liste.c.
Réalisation
En-tête
L'en-tête du fichier commence comme d'habitude par une macro permettant d'identifier le fichier source, puis par les fichiers d'en-têtes à inclure :
#define
___LISTE_C
#include <liste.h>
#include
<stdlib.h>
En général, on ajoute les fichiers à inclure au fur et à mesure que le compilateur signale les erreurs ou les avertissements. Ici, nous aurons besoin de liste.h et de stdlib.h pour les fonctions d'allocation.
Type de donnée
Nous passons ensuite à la définition des types de données.
Nous commençons par définir la structure de donnée modélisant chaque élément de la liste, que nous appelons cellule :
/*
cellule de la liste */
typedef struct s_Cellule
{
/* nombre magique */
unsigned
magique;
# define CELLULE_MAGIQUE 434332
/*
pointeur vers la cellule suivante et
*
précédente */
Cellule prec,
suiv;
/* élément de la
cellule */
Element element;
}
_Cellule;
Une cellule est une structure contenant un nombre magique, deux pointeurs pointant vers une structure de type Cellule et d'un champ de type Element contenant l'élément de la cellule et défini dans liste.h.
Le nombre magique va servir à contrôler que la structure de donnée que l'utilisateur va passer aux fonctions des listes est bien une liste. Cette méthode n'est pas absolue, mais elle est très simple à réaliser et détecte la plupart des erreurs. C'est pour cette raison qu'elle est très souvent utilisée.
La liste est définie par :
/*
la liste */
typedef struct s_Liste {
/*
nombre magique */
unsigned magique;
#
define LISTE_MAGIQUE 1212345
/*
tete de la liste */
Cellule tete;
}
_Liste;
Une liste est simplement une structure contenant un nombre magique et pointeur vers une cellule qui jouera le rôle de la tête de la liste.
Dans le fichier d'en-tête liste.h, les types Liste et Cellule sont définis comme étant des pointeurs sur des structures de données respectivement de type s_Liste et s_Cellule, sans les avoir définis. Comme les fichiers utilisateurs ne tentent pas d'accéder directement au contenu de ces structures, le compilateur se contente de cette définition incomplète et ne provoque pas d'erreur.
Création / destruction
La fonction de création alloue une liste dynamiquement en mémoire et initialise cette zone :
/*
Crée une liste vide */
Liste liste_cree (void)
{
/* allocation de la liste */
Liste
lst = malloc (sizeof (_Liste));
if
(lst) {
/* initialisation de la
liste */
lst->tete =
0;
lst->magique =
LISTE_MAGIQUE;
}
return lst;
}
Le résultat de malloc peut être nul ce qui signifie qu'il n'y a plus de mémoire disponible. Dans ce cas, nous n'initialisons pas la structure et retournons l'adresse nulle. Le résultat de liste_cree devra donc être testé par la fonction appelante.
Dans les fonctions ayant une liste en argument, nous utiliserons une macro nommée CHECK_LISTE pour vérifier que l'argument est non nul et que son nombre magique est bien celui des listes. Cette macro est définie par :
/*
vérifie une liste */
#define
CHECK_LISTE(lst) \
if (!
(lst) || (lst)->magique != LISTE_MAGIQUE) \
abort()
Par convention, le nom des macros est écrit en majuscule. La macro teste que son argument est non nul et que son champ magique vaut bien LISTE_MAGIQUE. Ainsi, si nous passons à cette macro un pointeur sur une autre structure, l'emplacement en mémoire correspondant au champ magique ``a peu de chances'' de valoir LISTE_MAGIQUE et si on passe une liste, ce champs ``a toutes les chances'' de valoir LISTE_MAGIQUE. On remarque que la macro est trop longue pour tenir sur une seule ligne ; aussi, nous plaçons le reste du texte de la définition sur la ligne suivante et nous terminons la première ligne par un anti-slash suivi d'aucun caractère.
Le nom des paramètres de la macro doit être entouré de parenthèses. En effet, considérons la macro suivante :
#define DOUBLE(x) x * 2
Considérons :
int
a = DOUBLE(3);
int b = DOUBLE(3+4);
Ce code est traité par le préprocesseur du compilateur C et produit :
int
a = 3 * 2;
int b = 3 + 4 * 2;
Du fait de la priorité de l'opérateur de multiplication sur l'addition, la valeur de b sera 3+8=11, au lieu de 7*2=14.
On réécrit dont la macro DOUBLE de la manière suivante en entourant les paramètres de parenthèses pour obtenir :
#define PLUS2(x) (x) + 2
Considérons maintenant :
int
a = PLUS2(3);
int b = PLUS2(3+4) * 5;
Après traitement par le préprocesseur, on a :
int
a = (3) + 2;
int b = (3) + 4 * 5;
Là encore, la seconde affectation ne correspond pas à ce que nous attendions. On entourera donc le corps des macros remplacées par des expressions du langage C de parenthèses ; les macros dont le corps est remplacé par une instruction n'a pas besoin d'être entouré. Une expression du langage C ``a une valeur'', comme une opérations arithmétique alors qu'une instruction ``n'a pas de valeur'', comme un test avec if. C'est notamment le cas de la macro CHECK_LISTE.
Revenons maintenant aux listes !
Nous contrôlons de la même façon le nombre magique des cellules avec :
/*
vérifie une cellule */
#define
CHECK_CELLULE(cell) \
if (!
(cell) || (cell)->magique != CELLULE_MAGIQUE) \
abort()
La fonction de destruction d'une liste libère l'espace mémoire occupé par toutes les cellules de la liste, puis libère la liste proprement dit :
/*
détruit une liste après l'avoir vidée
*/
void liste_detruit (Liste lst) {
Cellule
cell, suiv;
/* vérification de
l'argument */
CHECK_LISTE (lst);
/*
libération des cellules */
for
(cell = lst->tete; cell; cell = suiv) {
suiv
= cell->suiv;
free
(cell);
}
/* destruction du
champs magique */
lst->magique = 0;
/*
libération de la structure de liste */
free
(lst);
}
Cette fonction est assez simple, mais elle possède quand même une finesse. En effet, lors de la libération des cellules, nous plaçons le pointeur vers la cellule suivante dans la variable suiv, puis nous libérons la cellule. La post-exécution de la boucle for se chargera avec cell=suiv de placer dans la variable cell le contenu du suiv et de recommencer.
A priori, nous aurions pu écrire plus simplement :
for
(cell = lst->tete; cell; cell = cell->suiv) {
free
(cell);
}
Dans ce cas, la cellule est libérée avec l'appel à la fonction free, puis son champs suiv est lu pour être placé dans la variable cell, ce qui provoque une erreur mémoire, puisque la cellule vient d'être libérée et donc n'existe plus. En utilisant la variable suiv comme tampon intermédiaire, on supprime cette erreur.
Ajout / suppression
La fonction suivante ajoute un élément en tête de liste. Elle est définie par :
/*
ajoute un élément en tete de liste
*/
void liste_ajoute (Liste lst, Element
elem) {
Cellule cell;
/*
vérification de l'argument */
CHECK_LISTE
(lst);
/* allocation d'une nouvelle cellule
*/
cell = malloc (sizeof
(_Cellule));
/* si la cellule est créée
correctement...*/
if (cell) {
/*
nombre magique */
cell->magique
= CELLULE_MAGIQUE;
/* placer
l'élément */
cell->element =
elem;
/* mise à jour des
liens */
cell->suiv =
lst->tete;
cell->prec = 0;
if
(cell->suiv) {
cell->suiv->prec
= cell;
}
/*
placer la cellule en tete de la liste*/
lst->tete
= cell;
}
}
Nous commençons par vérifier l'argument contenant la liste avec la macro CHECK_LISTE. Puis nous allouons une espace capable de recevoir une Cellule. Nous ignorons le cas où l'allocation échoue et ne provoquons pas d'erreur. Si l'allocation réussit, nous initialisons le nombre magique et nous plaçons l'élément dans la nouvelle cellule, puis nous mettons à jour les liens. Pour bien saisir la mise à jour des liens, l'usage d'un crayon peut souvent être utile ! Enfin, nous plaçons la nouvelle cellule en tête de la liste.
La fonction de suppression de la tête de la liste est définie comme suit :
/*
supprime la tete de liste */
Element liste_enleve
(Liste lst) {
Element element = 0;
/*
vérification de l'argument */
CHECK_LISTE
(lst);
/* si la liste n'est pas vide */
if
(lst->tete) {
/* variable
temporaire */
Cellule ancienne =
lst->tete;
/* mise à
jour des liens */
lst->tete =
lst->tete->suiv;
if
(lst->tete->suiv) {
lst->tete->suiv->prec
= 0;
}
/*
valeur de retour */
element =
ancienne->element;
/*
invalidation de la cellule */
ancienne->magique
= 0;
/* libération de la
cellule */
free
(ancienne);
}
return element;
}
La fonction commence par vérifier l'argument contenant la liste. Son traitement ne commence que si la liste n'est pas vide. Dans ce cas, la cellule en tête de liste est conservée dans une variable temporaire, puis les liens sont mis à jour. Enfin, la cellule contenue dans la variable temporaire est invalidée puis libérée. La fonction retourne la valeur de l'élément qui est supprimé ; nous verrons plus tard l'utilisé de cette valeur de retour.
Fonctions avancées
La première fonction avancée permet d'obtenir la valeur du nième élément de la liste :
/*
retourne la nième
cellule de la liste */
Cellule liste_reference (Liste
lst, unsigned n) {
Cellule
cell;
CHECK_LISTE (lst);
for
(cell = lst->tete;
cell
&& n;
n--, cell =
cell->suiv);
return n >= 0 ? cell : 0;
}
La fonction réalise une itération jusqu'à ce que le nième élément soit atteint, en partant de zéro. Si la valeur de l'index est trop grande, zéro est retourné.
La seconde fonction avancée donne la valeur de l'élément à partir d'une cellule. Nous avons :
/*
retourne l'élément de la cellule */
Element
liste_element (Cellule cell) {
CHECK_CELLULE
(cell);
return cell->element;
}
Ensuite, nous avons les fonctions de parcourt de la liste qui ne présentent pas de difficultés majeures :
/*
retourne la première cellule de la liste */
Cellule
liste_premier (Liste lst) {
CHECK_LISTE
(lst);
return lst->tete;
}
/*
retourne la dernière cellule de la liste */
Cellule
liste_dernier (Liste lst) {
Cellule
cell;
CHECK_LISTE (lst);
cell =
lst->tete;
if (cell)
while
(cell->suiv) cell = cell->suiv;
return
cell;
}
/* retourne la cellule suivante */
Cellule
liste_suivant (Cellule cell) {
CHECK_CELLULE
(cell);
return cell->suiv;
}
/*
retourne la cellule précédente */
Cellule
liste_precedent (Cellule cell) {
CHECK_CELLULE
(cell);
return cell->suiv;
}
Le double chaînage de la liste prend tout son sens avec la fonction list_precedent qui permet de parcourir la liste du dernier élément au premier. Une réalisation plus simple des listes pourrait ne pas utiliser cette possibilité ; tout le code relatif au lien vers la cellule précédente doit alors être supprimé de la réalisation.
Généralisation
La bibliothèque de liste que nous venons de définir est suffisamment puissante pour servir de base à de véritables programmes. Cependant, elle souffre d'une limitation sérieuse, tout comme la bibliothèque du mois dernier : elle ne sait manipuler que des entiers. Nous ne pouvons pas réaliser une pile d'autre chose, comme des objets complexes.
Pour pallier à cet inconvénient, sans toutefois parvenir à la souplesse des langages évolués comme Scheme, nous allons légèrement modifier l'en-tête liste.h : dans ce fichier, le type Element détermine le type des données contenues dans la liste. Nous allons rendre ce type de donnée générique.
En C, un pointeur sur un entier se déclare par :
int * pointeur;
Un pointeur est une variable capable de contenir une adresse de la mémoire. Une adresse est un mot de 32 bits sur un processeur Intel Pentium. Pour l'ordinateur, rien ne distingue une adresse sur un entier d'une adresse sur un réel, par exemple. Seul le compilateur C va tenir compte des types de données pour effectuer des vérifications de cohérences. Pour pouvoir manipuler les adresses sans les associer à un type précis, le langage C ANSI introduit le mot clef void. Nous savons déjà qu'une fonction qui retourne void est une fonction qui ne retourne rien ; de même, une fonction qui a void dans ses paramètres est une fonction sans paramètre. Pour désigner un pointeur sur tout type d'objet, nous écrivons :
void * pointeur_generique;
Attention, il n'est pas possible de déclarer une variable de type void comme dans :
void declaration_interdite;
Ainsi, nous redéfinissons le type Element comme étant le type d'un pointeur void :
typedef void * Element;
Désormais, nous pouvons donner l'adresse obtenue avec l'allocation dynamique de tout objet C à la fonction liste_ajoute. Attention cependant à ne pas donner des adresses obtenues avec l'opérateur & car ces adresses sont invalides sitôt le bloc d'instruction (entre accolades) qui l'utilise se termine.
L'utilisation des listes avec des objets est bien pratique, mais nous perdons la possibilité de manipuler des listes d'entiers simplement. Aussi, nous allons utiliser la possibilité du langage C de convertir les types.
En C, la conversion d'une valeur d'un certain type dans un autre s'appelle le cast. Cela s'écrit en plaçant le nouveau type à gauche de la valeur, entre parenthèses, comme dans :
int a = (int) 123.432;
Dans cette écriture, la valeur entière 123.432 est convertie en entier, puis affectée à la variable.
Si nous écrivons maintenant :
liste_ajoute (lst, (void *) 123);
Nous ajoutons à la liste la valeur entière 123 convertie en adresse de type void à la liste lst. Attention, cette écriture n'est possible que sur les machines ou les adresses ont une taille machine supérieure ou égale à la taille des entiers. C'est le cas sur les Pentium et sur la plupart des systèmes.
Nous avons donc maintenant une bibliothèque complète de manipulation des listes génériques à double chaînage. Cette bibliothèque pourra être enrichie de fonctions plus élaborées s'appuyant de préférence sur ces fonctions de base.
L'auteur
Guilhem de Wailly, directeur de la société Erian Concept, partenaire NetUltra et Getek.
|
|
Votre interlocuteur Linux ! Support, formations, configurations, administration, développements Linux. http://www.erian-concept.com |
Références
Langage C - norme ANSI
Ph. DRIX
Masson
Programmer en C++
S.C. DEWHURST et K.T.
STARK
Masson
Le Langage C
B.W. KERNIGHAN et D.M. RITCHIE
Masson
Kdevel
http://samuel.cs.uni-potsdam.de/~smeier/kdevelop_new/index.html