Pour avoir le contrôle de la file, il est préférable de sauvegarder certains éléments : le premier élément, le dernier élément, le nombre d'éléments. Pour réaliser cela, une autre structure sera utilisée (ce n'est pas obligatoire, des variables peuvent être utilisées). Voici sa composition:
IV. Opérations sur les files
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||
| void initialisation (File * suite); |
Cette opération doit être faite avant toute autre opération sur la file.
Elle initialise le pointeur debut et le pointeur fin avec le pointeur NULL, et la taille avec la valeur 0.
La fonction
|
void initialisation (File * suite){ suite->debut = NULL; suite->fin = NULL; suite->taille = 0; } |
B. Insertion d'un élément dans la file 
Voici l'algorithme d'insertion et de sauvegarde des éléments :
- déclaration d'élément(s) à insérer
- allocation de la mémoire pour le nouvel élément
- remplir le contenu du champ de données
- mettre à jour le pointeur debut vers le 1er élément (le début de file)
- mettre à jour le pointeur fin (ça nous servira pour l'insertion vers la fin de la file)
- mettre à jour la taille de la file
Prototype de la fonction :
| int enfiler (File * suite, Element * courant, char *donnee); |
La 1ère image affiche le début de l'insertion, donc la liste a la taille 1 après l'insertion.
Dans la file, l'élément à récupérer c'est le 1er entré. Pour cela, l'insertion se fera toujours à la fin de la file. Il s'agit de l'ordre normal de l'insertion (1er, 2ème, 3ème ...... etc. ).
La fonction
|
int enfiler (File * suite, Element * courant, char *donnee){ Element *nouveau_element; if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL) return -1; if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char))) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); if(courant == NULL){ if(suite->taille == 0) suite->fin = nouveau_element; nouveau_element->suivant = suite->debut; suite->debut = nouveau_element; }else { if(courant->suivant == NULL) suite->fin = nouveau_element; nouveau_element->suivant = courant->suivant; courant->suivant = nouveau_element; } suite->taille++; return 0; } |
C. Oter un élément de la file
Pour supprimer (ôter) l'élément de la file, il faut tout simplement supprimer l'élément vers lequel pointe le pointeur debut.Cette opération ne permet pas de récupérer la donnée au début de la file (la première donnée), mais seulement la supprimer.
Prototype de la fonction :
| int de_filer (File * suite); |
La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.
étapes :
- le pointeur supp_elem contiendra l'adresse du 1er élément
- le pointeur debut pointera vers le 2ème élément (après la suppression du 1er élément, le 2ème sera au début de la file)
- la taille de la file sera décrémentée d'un élément
La fonction
|
int de_filer (File * suite){ Element *supp_element; if (suite->taille == 0) return -1; supp_element = suite->debut; suite->debut = suite->debut->suivant; free (supp_element->donnee); free (supp_element); suite->taille--; return 0; } |
D. Affichage de la file
Pour afficher la file entière, il faut se positionner au début de la file (le pointeur debut le permettra).
Ensuite en utilisant le pointeur suivant de chaque élément, la file est parcourue du 1er vers le dernier élément.
La condition d'arrêt est donnée par la taille de la file.
La fonction
|
void affiche(File *suite){ Element *courant; int i; courant = suite->debut; for(i=0;i<suite->taille;++i){ printf(" %s ", courant->donnee); courant = courant->suivant; } } |
E. Récupératon de la donnée au début de la file
Pour
récupérer la donnée au début de la file sans la supprimer, j'ai utilisé une macro. La macro lit les données au début de la file en utilisant le pointeur debut.| #define file_donnee(suite) suite->debut->donnee |
V. Exemple complet
file.h
| /*********************\ * file.h * \*********************/ typedef struct ElementListe{ char *donnee; struct ElementListe *suivant; } Element; typedef struct ListeRepere{ Element *debut; Element *fin; int taille; } File; /* initialisation */ void initialisation (File * suite); /* ENFILER*/ int enfiler (File * suite, Element * courant, char *donnee); /* DE_FILER*/ int de_filer (File * suite); /* FirstInFirstOut */ #define file_donnee(suite) suite->debut->donnee /* Affiche la file */ void affiche(File *suite); |
file_function.h
| /***********************\ * file_function.h * \***********************/ void initialisation (File * suite){ suite->debut = NULL; suite->fin = NULL; suite->taille = 0; } /* enfiler (ajouter) un élément dans la file */ int enfiler (File * suite, Element * courant, char *donnee){ Element *nouveau_element; if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL) return -1; if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char))) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); if(courant == NULL){ if(suite->taille == 0) suite->fin = nouveau_element; nouveau_element->suivant = suite->debut; suite->debut = nouveau_element; }else { if(courant->suivant == NULL) suite->fin = nouveau_element; nouveau_element->suivant = courant->suivant; courant->suivant = nouveau_element; } suite->taille++; return 0; } /* de_filer (supprimer) un élément de la file */ int de_filer (File * suite){ Element *supp_element; if (suite->taille == 0) return -1; supp_element = suite->debut; suite->debut = suite->debut->suivant; free (supp_element->donnee); free (supp_element); suite->taille--; return 0; } /* affichage de la file */ void affiche(File *suite){ Element *courant; int i; courant = suite->debut; for(i=0;i<suite->taille;++i){ printf(" %s ", courant->donnee); courant = courant->suivant; } } |
file.c
| /*********************\ * file.c * \*********************/ #include<stdio.h> #include<stdlib.h> #include<string.h> #include "file.h" #include "file_function.h" int main () { File *suite; char *nom; if ((suite = (File *) malloc (sizeof (File))) == NULL) return -1; if ((nom = (char *) malloc (50 * sizeof (char))) == NULL) return -1; initialisation (suite); printf ("Entrez un mot : "); scanf ("%s", nom); enfiler (suite, suite->fin, nom); printf ("La file (%d éléments)\n",suite->taille); printf("\nDébut de la FILE [ "); affiche (suite); /*le premier entré sera affiché */ printf(" ] Fin de la FILE\n\n"); printf ("Entrez un mot : "); scanf ("%s", nom); enfiler (suite, suite->fin, nom); printf ("La file (%d éléments)\n",suite->taille); printf("\nDébut de la FILE [ "); affiche (suite); /*le premier entré sera affiché */ printf(" ] Fin de la FILE\n\n"); printf ("Entrez un mot : "); scanf ("%s", nom); enfiler (suite, suite->fin, nom); printf ("La file (%d éléments)\n",suite->taille); printf("\nDébut de la FILE [ "); affiche (suite); /*le premier entré sera affiché */ printf(" ] Fin de la FILE\n\n"); printf ("\nLe premier entré (FirstInFirstOut) [ %s ] sera supprimé", file_donnee(suite)); printf ("\nLe premier entré est supprime\n"); de_filer (suite); /* suppression de premier element entre */ printf ("La file (%d éléments): \n",suite->taille); printf("\nDébut de la FILE [ "); affiche (suite); printf(" ] Fin de la FILE\n\n"); return 0; } |