Les files - Premier Entré Premier Sorti

Requis

Les types de données
Les structures
L'utilisation de typedef
Les pointeurs
Les fonctions utilisateur
Les listes simplement chaînées
Les listes doublement chaînées

I. INTRODUCTION

Cette article a pour but la compréhension des files.
L'implémentation en fonction du besoin vous appartient.
Pour expliquer l'algorithme j'ai choisi d'utiliser une liste simplement chaînée. Donc la compréhension des listes chaînées est nécessaire.

II. Définition

La file est une structure de données, qui permet de stocker les données dans l'ordre FIFO (First In First Out) - en français Premier Entré Premier Sorti).
La récupération des données sera faite dans l'ordre d'insertion.

Pour l'implémentation j'ai choisi une liste simplement chaînée.
L'insertion dans la file se fera dans l'ordre normal, le 1er élément de la file sera le premier élément saisi, donc sa position est au début de la file.

III. La construction du prototype d'un élément de la file

Pour définir un élément de la file le type struct sera utilisé.
L'élément de la file contiendra un champ donnee et un pointeur suivant.
Le pointeur suivant doit être du même type que l'élément, sinon il ne pourra pas pointer vers l'élément.
Le pointeur suivant permettra l'accès vers le prochain élément.

typedef struct ElementListe {
    char *donnee;
    struct ElementListe *suivant;
}Element;

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:

typedef struct ListeRepere{
  Element *debut;
  Element *fin;
  int taille;
} File;

IV. Opérations sur les files

A. Initialisation

Prototype de la fonction :

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 de 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ération 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;
}

VI. Voir aussi

• les listes simplement chaînées
• les listes doublement chaînées
• les listes circulaires
• les piles