Structures et listes chaînées

14 Mar

Structures et listes chaînées

a) Les Structures

Jusqu’à présent, nous manipulions exclusivement des variables typées du langage C.
Dans les langages d’aujourd’hui, on retrouve souvent la notion d’objet. Le langage C n’est pas un langage orienté objet, c’est un langage procédural.

Cependant, on retrouve quelque chose de très similaire : les structures.
Une structure est une compilation de variables typées personnalisée. On peut également retrouver des structures à l’intérieur d’une structure.

Par exemple, si on veut matérialiser une voiture en C, on peut le faire avec une structure :

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

struct Voiture {

char *marque;
char *essence;
int chevaux;
float puissance;

};

On peut mettre sans souci la déclaration de la structure en variable globale (avant le main).
On déclare une structure avec le mot-clef struct, on donne donc un nom à la structure, puis on ajoute à l’intérieur tous les champs que l’on souhaite, séparés par des points virgule.
Enfin, une structure se termine toujours par un point virgule (};).

Ensuite on crée notre variable structure en faisant struct Voiture <nom_variable>. Pour ne pas être obligé de mettre à chaque fois le mot clef struct, on va utiliser l’instruction typedef, comme ci-dessous :

typedef struct Voiture Voiture

Cela aura pour conséquence de rendre équivalent Voiture et struct Voiture. Cela peut être fait dès la déclaration.

typedef struct Voiture {

char *marque;
char *essence;
int chevaux;
float puissance;

} Voiture;

Voici maintenant le code avec le code principal et une fonction d’affichage de la structure :

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

struct Voiture {

char *marque;
char *essence;
int chevaux;
float puissance;

};

void afficherVoiture (struct Voiture);

int main (int argc, char **argv) {

struct Voiture p206;
p206.marque = « Peugeot »;
p206.essence = « Diesel »;
p206.chevaux = 180;
p206.puissance = 1.9;

afficherVoiture (p206);

}

void afficherVoiture (struct Voiture voiture) {

printf (« Marque : %s\n », voiture.marque);
printf (« Essence : %s\n », voiture.essence);
printf (« Chevaux : %i\n », voiture.chevaux);
printf (« Puissance : %f\n », voiture.puissance);

}

Comme on le voit dans le bout de code plus haut, pour accéder à un champ d’une structure, on écrit : nom_structure.champ.
Le passage de la structure à la fonction se fait par valeur/copie. On ne peut pas donc modifier le contenu de la structure sans passer l’adresse de la structure en paramètre.

Les données d’une structure sont alignées en mémoire et je vous renvoie au cours sur les pointeurs, dernière partie.
Pour des raisons de rapidité d’accès, les données en mémoire sont alignées sur des adresses multiples de la taille de leur type : un char (1 octet) est aligné sur une adresse multiple de 1 (pas trop dur), un short sur une adresse multiple de 2, un int sur une adresse multiple de 4, un double sur une adresse multiple de 8, etc. Enfin, la structure elle-même (adresse de début, et adresse de fin) est alignée sur une adresse multiple de la taille du du champ dont le type prend le plus de place en mémoire. Si ma structure contient des char, des short, et des int, la structure sera alignée sur un multiple de la taille d’un int (4 octets dans un contexte 32 bits).

Dans le cas où notre structure n’est pas alignée naturellement (comme ici), le compilateur ajoute des octets de bourrage (pour boucher) afin que le champ suivant soit aligné, ce qui crée un trou dans la structure. Les données finales sont donc bien alignées.

Regardons cet exemple :

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

typedef struct Alignement {

char lettre;
double d_nb;
char tab[9];
char tab2[3];
int i_nb;
short s_nb;

} Alignement;

int main (int argc, char **argv) {

Alignement align;
align.lettre = ‘c’;
align.s_nb = 25000;
align.i_nb = 25000000;
align.d_nb = 25000000000;
align.tab[0] = ‘a’;
align.tab[1] = ‘b’;
align.tab[2] = ‘c’;
printf (« Taille de la structure : %i\n », sizeof(align));
printf (« Adresse lettre : %p\n », &align.lettre);
printf (« Adresse double : %p\n », &align.d_nb);
printf (« Adresse tableau : %p\n », align.tab);
printf (« Adresse tableau : %p\n », align.tab2);
printf (« Adresse int : %p\n », &align.i_nb);
printf (« Adresse short : %p\n », &align.s_nb);
printf (« %c %c %c %c %c %c\n », *(align.tab), align.tab[1], align.tab[2], align.tab[3], align.tab[4], align.tab[5]);

}

Taille de la structure : 40
Adresse lettre : 0028FEE8
Adresse double : 0028FEF0
Adresse tableau : 0028FEF8
Adresse tableau : 0028FF01
Adresse int : 0028FF04
Adresse short : 0028FF08
a b c b ◄

On a un peu tous les types de champ (char, short, int, double ..).
On remarque que la taille de la structure ne fait non pas : 1+8+9+3+4+2 = 27 octets, mais 40.
La raison de cette différence se trouve dans l’alignement des données et de la structure elle-même.

Tout d’abord, l’adresse de départ est 0x0028FEE8 = 2686696 = 8 * 335837. Notre structure est donc bien alignée sur une adresse multiple de 8, qui est la taille du plus grand type contenu dans la structure, le type double. Il en est de même pour l’adresse de fin, puisque la taille de la structure est par conséquent multiple de 8 (40 = 8 * 5).

Pour ce qui est de l’alignement des données, voici l’explication :
Le premier membre de la structure (char) est bien aligné sur un multiple de 1 octet, ce qui n’est pas un exploit en soi. Le deuxième champ (double) lui n’est pas naturellement aligné, puisque 1 n’est pas un multiple de 8. On rajoute donc 7 octets de bourrage pour arriver à 8.
Le troisième membre est de type char, il ne nécessite donc pas de réajustement, puisque n’importe quel nombre entier est multiple de 1. Il en est de même pour le champ suivant. Le 5e champ est lui de type int, il doit donc être aligné sur 4 octets. Mais puisque 1 + 7 + 8 + 9 + 3 = 28 est déjà un multiple de 4, il n’y pas besoin d’ajouter du bourrage. Le dernier champ est un short, et doit donc être aligné sur deux octets, ce qui ne nécessite pas non plus de trou, puisuqe 28 + 4 = 32 est bien multiple de 2 octets. En revanche, 32 + 2 = 4 n’est pas un multiple de 8. Or la structure doit être alignée sur un multiple de 8. 6 octets de bourrage sont donc rajoutés à la fin.

La taille de la structure est donc de : 1 + 7 (trou alignement donnée) + 8 + 9 + 3 + 4 + 2 + 6 (trou alignement structure) = 40 octets.
Les trous se vérifient en regardant les adresses de chaque champ.

On notera par ailleurs qu’un tableau et un pointeur ne sont pas du tout pareil dans une structure !
Quand on déclare un pointeur, seul le pointeur est dans la structure, mais pas la donnée pointée.
Au contraire, si on déclare un tableau, le tableau entier se trouve dans la structure, ce que l’on peut remarquer ici.
On voit d’ailleurs que le tableau (comme les variables en général) n’est pas initialisé à 0 quand on le déclare, puisqu’on a des caractères « inattendus » après les trois premiers indices du tableau que nous avons initialisés.

Si l’on souhaite modifier une structure en la passant à une fonction, c’est très simple il suffit que la fonction prenne en paramètre un pointeur et reçoive l’adresse de la structure, ce qui donne par exemple ceci :

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

typedef struct Voiture {

char *marque;
char *essence;
int chevaux;
float puissance;

} Voiture;

void modifierVoiture (Voiture*);
void afficherVoiture (Voiture);

int main (int argc, char **argv) {

struct Voiture p206;
p206.marque = « Peugeot »;
p206.essence = « Diesel »;
p206.chevaux = 180;
p206.puissance = 1.9;

afficherVoiture (p206);
modifierVoiture (&p206);
afficherVoiture (p206);

}

void modifierVoiture (Voiture* voiture) {

(*voiture).marque = « Ferrari »;
(*voiture).essence = « Essence »;
voiture->chevaux = 450;
voiture->puissance = 4.2;

}
void afficherVoiture (Voiture voiture) {

printf (« Marque : %s\n », voiture.marque);
printf (« Essence : %s\n », voiture.essence);
printf (« Chevaux : %i\n », voiture.chevaux);
printf (« Puissance : %f\n », voiture.puissance);

}

Comme on peut le remarquer ici, on passe donc l’adresse de la structure.
Pour modifier, on ne peut pas faire : *structure.champ, car dans ce cas, le point s’applique à structure (qui est un pointeur sur la structure) et non à *structure. Il faut donc mettre entre parenthèses (*structure), ce qui donne par exemple : (*voiture).marque = « Ferrari »;.
Une écriture équivalente a été inventée (utilisée pour les deux dernières modifications) : Au lieu de s’embêter à écrire (*structure).champ, on peut directement écrire structure->champ. Vous pouvez choisir celui que vous voulez, sachant que la première est peut-être plus formelle (pour les gens « carrés ») et que la deuxième rend le code plus doux à lire.

On remarque également une chose que je n’avais pas dit dans le chapitre sur les pointeurs & cie.

On ne peut pas faire :

char tab[5];
tab = « test »;

Car le compilateur ne le permet simplement pas. Comme je l’ai dit, lorsqu’on fait :

char *tab = « maman »;

la chaîne « maman » est transformée en tableau, et le pointeur tab prend comme valeur l’adresse du premier élément du tableau. « maman » est donc bien un char *. Cela marche seulement à la déclaration du tableau ! Ce sont les règles du compilateur …
De plus, un tableau ne peut pas être déréférencé, contrairement à un pointeur.
On peut donc modifier un char * à notre guise (s’il n’est pas constant : mot clef const). La modification des chaînes marchent très bien dans la fonction. Le pointeur est déréférencé (ne pointe plus sur « Peugeot » par exemple) et est référencé à nouveau (sur « Ferrari » cette fois).

b) Listes chaînées

Grâce aux structures, on peut aborder un point particulier : les listes chaînées.
Une liste chaînée, c’est une liste d’éléments reliés entre eux par une chaîne. Les éléments sont donc chaînés.
Chaque élément de la liste (appelé Noeud) peut contenir une ou plusieurs valeurs, et contient un pointeur sur l’élément suivant. De cette manière, on peut parcourir la liste du premier élément au dernier élément. Il existe également les listes doublement chaînées : chaque élément contient un pointeur sur l’élément suivant et un sur l’élément précédent. Cette fois, on peut parcourir la liste dans les deux sens.

Exemple d’utilisation concrète : Nous allons prendre l’exemple du système de fichiers FAT.
Sous Windows 95/98, avec le système FAT, les fichiers étaient organisés sous la forme de listes chaînées. Les données d’un fichier sont, de manière générale (toujours aujourd’hui), réparties sur des unités d’allocations (cluster) du disque dur.
Ainsi, dans Fat, on maintient une table qui représente tous les clusters du disque et le chaînage entre ceux-ci.
D’autre part, on maintient une autre table, qui pour chaque fichier, contient le numéro du cluster où il débute.
Pour recueillir toutes les données de tel fichier :
Etape 1 :
– On va dans la table « des fichiers » voir quel est le numéro du cluster où le fichier débute.
Etape 2 :
– On va chercher les données correspondantes sur le disque,
– On regarde dans la table des clusters quelle donnée correspond à ce cluster :
– Si cette donnée vaut EOF (fin de fichier), on arrête. C’était le dernier cluster.
– Sinon, on récupère ce numéro, et on recommence l’étape 2.

Un cluster pointe donc sur un autre cluster, et ainsi de suite jusqu’à arriver au cluster qui indique la fin du fichier « EOF », et ce pour chaque fichier. À un fichier correspond donc une liste chaînée de clusters.

On peut se demander quel est l’intérêt par rapport à l’utilisation d’un simple tableau (car on peut faire des tableaux de structures).
Un tableau, si une taille de départ a été déclarée, est statique : vous ne pouvez donc pas ajouter ou supprimer d’élément. Dans notre exemple, si un fichier grossit ou rétrécit, il faut pouvoir libérer un Cluster facilement (l’enlever de la chaîne d’un fichier).
Avec malloc(), on peut certes utiliser realloc() pour agrandir ou rétrécir l’espace déjà alloué. Cependant, même si c’est transparent, l’adresse du tableau pointé change souvent, afin de trouver de l’espace mémoire libre. Cela veut dire que le tableau est supprimé, puis recréé. C’est le plus gros défaut du tableau, ce traitement est lourd.

Avec une liste chaînée, on peut ajouter/retirer autant d’éléments qu’on veut, puisqu’on joue juste avec des pointeurs. On crée des éléments en mémoire, et on fait pointer tel élément dessus, etc.

Nous allons prendre un exemple simple d’implémentation du chaînage de fichiers FAT. On va considérer que EOF sera représenté par la valeur NULL.

Il nous faut créer notre unité de base : le cluster. On considère pour simplifier qu’un cluster a un contenu de 4 octets (int), même si c’est plutôt 1024 fois plus (4 ko).

Je propose cette structure :

typedef struct Cluster {
int numero;
int contenu;
struct Cluster *suivant;
} Cluster;

La table représente un cluster par son contenu, un numéro (table des clusters) et par le cluster qui le suit (pour tel fichier).

Maintenant, on va matérialiser une structure Fichier, qui va contenir un pointeur vers le cluster où il démarre :

typedef struct Fichier {
char *nom;
struct Cluster *debut;
} Fichier;

Bien. Maintenant, il nous reste à créer quelques fichiers et leur ajouter des clusters.
On va considérer qu’on a 4 fichiers alloués sur des secteurs non contiguës.
Par exemple, on va dire que le fichier 1 est réparti sur le Cluster 2,7,9,12 et 18.

int main () {

Fichier fichier_1 = {« HijackThis.exe », NULL};
Fichier fichier_2 = {« Super.txt », NULL};
Fichier fichier_3 = {« Combofix.exe », NULL};
Fichier fichier_4 = {« mapage.html », NULL};

}

Ici, on a créé quatre fichiers en mettant le cluster du début à NULL. Maintenant, il nous reste juste à ajouter des secteurs au fichier.

Pour cela, on peut créer la fonction suivante :

void ajouterCluster (Fichier* fichier, int numero, int contenu) {

Cluster *nouveauCluster = NULL;
nouveauCluster = malloc (sizeof(*nouveauCluster));

if (nouveauCluster == NULL)

return;

nouveauCluster->numero = numero;
nouveauCluster->contenu = contenu;
nouveauCluster->suivant = NULL;

if (fichier->debut == NULL) {

fichier->debut = nouveauCluster;

} else {

Cluster *courant = fichier->debut;

while (courant->suivant != NULL)
courant = courant->suivant;
courant->suivant = nouveauCluster;

}

}

On envoie à notre fonction l’adresse du fichier, ainsi que le couple numéro/contenu du cluster qu’on veut lui ajouter.
À l’intérieur de la fonction, on crée le cluster avec les propriétés renseignées grâce à malloc(), pour que celui-ci ne soit pas perdu après la fin de la fonction (zone du tas).

Puis on l’ajoute au fichier :

– Si le début du fichier est null, on va donc le mettre ici,
– Si le début n’est pas null, on parcourt la chaîne jusqu’au dernier noeud (champ suivant à NULL), dans lequel on fait pointer le champ suivant sur le cluster venant d’être créé.
Une fois qu’on a fait ça, on s’amuse dans le main à ajouter plusieurs secteurs au fichier, et après cela, on va pouvoir afficher l’ensemble des secteurs du fichier, grâce au parcours du chaînage :

void afficherSecteurs (Fichier fichier) {

if (fichier.debut == NULL) {

printf (« Le fichier est nul\n »);

} else {

Cluster *courant = fichier.debut;
int i = 0;

printf (« Nom fichier : %s\n », fichier.nom);

while (courant->suivant != NULL) {

printf (« Secteur %i du fichier :\n\tNumero : %i\n\tContenu : %i\n », i, courant->numero, courant->contenu);
courant = courant->suivant;
i++;

}

printf (« Secteur %i du fichier :\n\tNumero : %i\n\tContenu : %i\n », i, courant->numero, courant->contenu);

}

}

Ce qui peut donner par exemple :

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

typedef struct Cluster {

int numero;
int contenu;
struct Cluster *suivant;

} Cluster;

typedef struct Fichier {

char *nom;
struct Cluster *debut;

} Fichier;

void afficherSecteurs (Fichier);
void ajouterCluster (Fichier*, int, int);

int main () {

Fichier fichier_1 = {« HijackThis.exe », NULL};
Fichier fichier_2 = {« Super.txt », NULL};
Fichier fichier_3 = {« Combofix.exe », NULL};
Fichier fichier_4 = {« mapage.html », NULL};

ajouterCluster (&fichier_1, 2, 25401);
ajouterCluster (&fichier_1, 7, 441);
ajouterCluster (&fichier_1, 9, 110);
ajouterCluster (&fichier_1, 12, 42542);
ajouterCluster (&fichier_1, 18, 501);

ajouterCluster (&fichier_2, 0, 13262);
ajouterCluster (&fichier_2, 5, 01);
ajouterCluster (&fichier_2, 6, 500);
ajouterCluster (&fichier_2, 4, 120);
ajouterCluster (&fichier_2, 0, 13262);

ajouterCluster (&fichier_3, 15, 12);
ajouterCluster (&fichier_3, 17, 100);
ajouterCluster (&fichier_3, 3, 61123);
ajouterCluster (&fichier_3, 10, 2500);
ajouterCluster (&fichier_3, 14, 415);

ajouterCluster (&fichier_4, 8, 7771);
ajouterCluster (&fichier_4, 11, 8);
ajouterCluster (&fichier_4, 13, 342);
ajouterCluster (&fichier_4, 16, 422);
ajouterCluster (&fichier_4, 19, 999);

afficherSecteurs (fichier_2);

}

void afficherSecteurs (Fichier fichier) {

if (fichier.debut == NULL) {

printf (« Le fichier est nul\n »);

} else {

Cluster *courant = fichier.debut;
int i = 0;

printf (« Nom fichier : %s\n », fichier.nom);

while (courant->suivant != NULL) {

printf (« Secteur %i du fichier :\n\tNumero : %i\n\tContenu : %i\n », i, courant->numero, courant->contenu);
courant = courant->suivant;
i++;

}
printf (« Secteur %i du fichier :\n\tNumero : %i\n\tContenu : %i\n », i, courant->numero, courant->contenu);

}

}

void ajouterCluster (Fichier* fichier, int numero, int contenu) {

Cluster *nouveauCluster = NULL;
nouveauCluster = malloc (sizeof(*nouveauCluster));

if (nouveauCluster == NULL)

return;

nouveauCluster->numero = numero;
nouveauCluster->contenu = contenu;
nouveauCluster->suivant = NULL;

if (fichier->debut == NULL) {

fichier->debut = nouveauCluster;

} else {

Cluster *courant = fichier->debut;

while (courant->suivant != NULL)

courant = courant->suivant;
courant->suivant = nouveauCluster;

}

}

Ce code affiche :

Nom fichier : Super.txt
Secteur 0 du fichier :
Numero : 0
Contenu : 13262
Secteur 1 du fichier :
Numero : 5
Contenu : 1
Secteur 2 du fichier :
Numero : 6
Contenu : 500
Secteur 3 du fichier :
Numero : 4
Contenu : 120
Secteur 4 du fichier :
Numero : 0
Contenu : 13262

Nous avons jusqu’à présent vu comment ajouter un élément à la fin de la chaîne, mais on peut faire d’autres choses :

– Supprimer le dernier secteur,
– Supprimer un secteur par son numéro,
– Ajouter un secteur entre deux autres secteurs,
– Ajouter un secteur au début du fichier……

Nous allons juste voir comment ajouter un secteur en début de fichier. Pour le reste, à vous d’expérimenter et de réfléchir !

Ce n’est pas beaucoup plus dur qu’ajouter à la fin ! Il suffit juste de sauvegarder le pointeur qui était dans le début du fichier, de placer le nouveau secteur au début du fichier, et de le faire pointer sur le secteur sauvegardé :

void ajouterClusterDebut (Fichier* fichier, int numero, int contenu) {

Cluster *nouveauCluster = NULL;
nouveauCluster = malloc (sizeof(*nouveauCluster));

if (nouveauCluster == NULL)

return;

nouveauCluster->numero = numero;
nouveauCluster->contenu = contenu;
nouveauCluster->suivant = NULL;

if (fichier->debut != NULL) {

Cluster *copieDebut = fichier->debut;
nouveauCluster->suivant = copieDebut;

}

fichier->debut = nouveauCluster;

}

Pour supprimer un élément, il suffit de faire un free() dessus et de corriger les références des pointeurs.

Si vous êtes courageux, je vous donne comme exercice de créer une pile (sans regarder sur le net bien-sûr) en vous servant des listes chaînées.

Vous pouvez également expérimenter les listes doublement chaînées : chaque noeud possède un pointeur sur le noeud suivant et un autre sur l’élément précédent.
Je vous ai donné les bases de réflexion, à vous de faire travailler vos méninges maintenant !

Publicités

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s

%d blogueurs aiment cette page :