Obligement - L'Amiga au maximum

Vendredi 24 mai 2019 - 05:12  

Translate

En De Nl Nl
Es Pt It Nl


Rubriques

 · Accueil
 · A Propos
 · Articles
 · Galeries
 · Glossaire
 · Liens
 · Liste jeux Amiga
 · Quizz
 · Téléchargements
 · Trucs et astuces


Articles

 · Actualité (récente)
 · Actualité (archive)
 · Comparatifs
 · Dossiers
 · Entrevues
 · Matériel (tests)
 · Matériel (bidouilles)
 · Points de vue
 · En pratique
 · Programmation
 · Reportages
 · Tests de jeux
 · Tests de logiciels
 · Tests de compilations
 · Articles divers

 · Articles in english
 · Articles en d'autres langues


Twitter

Suivez-nous sur Twitter




Liens

 · Sites de téléchargements
 · Associations
 · Pages Personnelles
 · Matériel
 · Réparateurs
 · Revendeurs
 · Presse et médias
 · Programmation
 · Logiciels
 · Jeux
 · Scène démo
 · Divers


Jeux Amiga

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Trucs et astuces

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Glossaire

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Partenaires

Annuaire Amiga

Amedia Computer

Relec

Hit Parade


Contact

David Brunet

Courriel

 


En pratique : Algorithmes et structures de données - Les files
(Article écrit par Lucien Turski-Marcon et Bruno Bailluet et extrait d'Amiga News Tech - mars 1992)


Petite définition : une file est une structure de données représentée par un vecteur, où tout ajout d'élément se fait en queue de file et tout retrait, en tête de file.

Nous avons donc affaire à une structure de données de type FIFO (First In, First Out), contrairement à la pile qui, comme nous l'avons vu précédemment, est de type LIFO. La file peut être représentée soit par un tableau, soit par une liste chaînée. Sa gestion n'est pas aussi simple que celle de la pile, pour la bonne et simple raison qu'il existe plusieurs méthodes d'implantation : la gestion contiguë, la gestion contiguë avec décalage et la gestion circulaire.

Nous allons donc étudier successivement ces trois méthodes, en décrivant pour chacune d'elles ses primitives : initialisation de la file, ajout d'un élément (enfiler), retrait d'un élément (défiler), ainsi que les grandes classiques booléennes que nous ne présentons plus : file_vide et file_pleine. Toutes les primitives sont données pour les tableaux, afin que nous puissions effectuer des comparaisons valables entre les différentes méthodes.

Commençons par la plus simple : la gestion contiguë de la file. Partant d'une file vide nous devons déterminer une valeur pour chacune de nos bornes (TETE et QUEUE). Ces valeurs ne peuvent pas être choisies au hasard, puisqu'elles doivent vérifier le test file_vide. Il est hors de question de les initialiser n'importe comment et d'utiliser une variable booléenne qui nous indiquerait l'état de la file. Dans ce premier cas, TETE vaut 1 et QUEUE vaut 0 : la file est vide si TETE = QUEUE + 1, ou plus simplement si TETE>QUEUE.

Algorithmes

Si nous exécutons manuellement les différentes procédures et fonctions, nous constatons que les deux bornes sont constamment incrémentées. Et je vous assure qu'il n'y a pas d'erreur : en effet, lorsque l'on enfile un nouvel élément, il est tout à fait légitime de voir la QUEUE s'éloigner de la TETE. Il en est de même lorsque l'on défile un élément : la TETE doit pointer sur la case suivant l'élément défilé. En fait, ce phénomène est tout à fait normal. Lorsque nous posons un livre sur une pile, il ne bouge pas. Maintenant, si nous retirons celui qui se trouve tout en dessous, les autres ne vont pas rester en suspension, ils vont descendre.

Le problème ne vient pas de la file mais du tableau. De ce fait, si nous n'opérons pas le décalage nous-mêmes, nous risquons d'atteindre très rapidement les limites que nous nous étions fixées pour le tableau. Cette méthode a le seul mérite d'être pédagogique, car elle permet d'aborder les files de manière simple et naturelle, et de soulever quelques problèmes d'implantation. En pratique, elle est à proscrire !

Algorithme Recherche_Occurence ;
(* version pour les tableaux *)
Constante
   Tete        <- 1 ;
   Max_Tableau <- 3 ;

Declaration
   mafile        : Tableau [1..3] De Caractere ; 
   motif         : Chaine [3] ;
   Trouve        : Booleen ;
   Phrase        : Tableau [1..100] De Caractere ;
   Sert_A_Rien   : Caractere ;
   Queue, Indice, Defil_NbFois, Defil_Cpt, Position : Entier ;

Fonction Cherche : Booleen
Debut
   Si (mafile = motif) Alors
      Cherche <- Vrai ;
   Sinon
      Cherche <- Faux ;
   Fsi ;
Fin ; 

Fonction File_Pleine : Booleen 
Debut
   Si (Queue = Max_Tableau) Alors
      File_Pleine <- Vrai ;
   Sinon
      File_Pleine <- Faux ;
   Fsi ;
Fin ;

Fonction File_Vide : Booleen
Debut
   Si (Tete = (Queue + 1)) Alors
      File_Vide <- Vrai ;
   Sinon
      File_Vide <- Faux ;
   Fsi ;
Fin ;

Procedure Enfiler (lettre : Caractere)
Debut
   Si non (File_Pleine) Alors
      Queue <- Queue + 1 ;
      mafile [Queue] <- lettre ;
   Sinon
      Afficher ("File Pleine") ;
      Quitter () ;
   Fsi ;
Fin ;

Fonction Defiler : Caractere 
Declaration
   compteur : Entier ;

Debut
   Si non (File_Vide) Alors

      Defiler <- mafile [Queue] ;
      compteur <- 1 ;

      Tant Que (compteur < Queue) Faire
         mafile [compteur] <- mafile[compteur + 1] ;
         compteur <- compteur + 1 ;
      Ftq ;

      Queue <- Queue - 1 ;

   Sinon
      Afficher ("File Vide") ;
      Quitter () ;
   Fsi ;
Fin ;

Debut
(* nous aurions pu aussi saisir cette phrase ainsi que *)
(* le motif a rechercher. Encore un bon petit exercice *)
   Phrase = "Only AMIGA makes it possible !!!" ;
   motif  = "le " ;

(* ces 2 lignes font office de Procedure Init *)
   Queue  = 0 ;
   Indice = 1 ;

   Tant Que non(File_Pleine) Faire
      Enfiler (Phrase [Indice]) ;
      Indice <- Indice + 1 ;
   Ftq ;

   Trouve <- Cherche() ;

   Tant Que non(Trouve) Et (Indice < Longueur(Phrase)) Faire
(* Cette fonction Emplacement a pour but de renvoyer *)
(* la position de motif[1] dans la file en ignorant  *)
(* le premier element de celle-ci. Si cet element    *)
(* n'est pas trouve la fonction renvoie 0.           *)
      Position <- Emplacement (mafile + 1, motif[1]);

      Si (Position = 0) Alors
         Defil_NbFois  <- Max_Tableau ;
      Sinon
         Defile_NbFois <- Position - 1 ;
      Fsi ;

(* pour une fois nous n'utilisons pas les elements que     *)
(* nous retourne la fonction defile car nous n'avons nul   *)
(* besoin des caracteres qui n'appartiennent pas au motif. *) 
      Defil_Cpt <- 0 ;
      Tant  Que (Defil_Cpt < Defil_NbFois) Faire
         Sert_A_Rien <- Defiler () ;
         Defile_Cpt  <- Defile_Cpt + 1 ;
      Ftq ;

(* et l'on recommence en enfilant de nouveau autant de *)
(* caracteres qu'il en a ete precedemment defiles *)
      Tant Que non(File_Pleine) Faire
         Enfiler (Phrase [Indice]) ;
         Indice <- Indice + 1 ;
      Ftq ;

      Trouve <- Cherche() ;
   Ftq ;

   Si (Trouve = Vrai) Alors
      Afficher ("Trouve\n") ;
   Sinon
      Afficher ("Non trouve\n") ;
   Fsi ;
Fin ;

Listing 2 : l'implémentation en C

/* Compile avec LC -L -O */
/* Quelques mots sur le programme qui suit. */
/* Le but est de rechercher une sous-chaine dans une chaine
   plus grande. Ici, la longueur de la sous-chaine est 3
   et elle contient "le ".
   Vous pouvez modifier la sous-chaine a travers la variable
   motif (N'OUBLIEZ PAS DE MODIFIER LA CONSTANTE MAX QUI DOIT
   ETRE EGALE A LA LONGUEUR DE motif).
*/
/* Je vais maintenant vous exposer l'algorithme retenu pour
   effectuer cette recherche.
   L'algorithme est extremement simple comme vous allez pouvoir
   le constater et ceci pour deux raisons :
      1. Le but de l'article n'etant pas axe sur l'apparition
         de motif mais sur la file, il fallait que l'exemple
         soit a la portee de chacun (tout en n'etant pas 
         totalement inutile)

      2. La seconde raison est que cet algorithme sort tout 
         droit de nos cerveaux embrumes.

   Pour nous simplifier la tache nous avons pris une file de meme 
   taille que notre motif.
   Algo :
    On commence par remplir la file puis tant que la sous-chaine 
    n'est pas trouvee on regarde dans la file si on trouve la 
    premiere lettre de la sous-chaine recherchee.
    Si cette lettre n'est pas dans la file, on n'a aucune chance 
    de trouver notre sous-chaine donc on vide la file et on la 
    remplit de nouveau puis on recommence au debut.
    Si cette lettre existe dans notre file, elle est susceptible 
    d'etre suivie par les autres lettres de notre motif. Pour le 
    savoir, il suffit de defiler jusqu'a ce que cette lettre se 
    trouve en premiere position dans notre file et de remplir la 
    file.
    Apres cela, il nous reste a tester si la file contient la 
    sous-chaine.
    Si c'est le cas, c'est GAGNE !!!.
    Sinon on recommence au debut.
*/
/* Bon assez parle, voila qui devrait regaler votre compilateur
   prefere. Si vous avez des questions, n'hesitez pas nous ferons
   de notre mieux pour vous repondre.
*/
#include <stdio.h>
#include <string.h>

#define TETE 0
/* L'indice TETE est une constante initialisee a 0 
   car en C les tableaux commencent a l'indice 0 
*/

#define MAX 3 /* On indique ici la taille de notre file */

int cherche (void);
void enfiler (char);
char defiler (void);
int file_pleine (void);
int file_vide (void);

char *mafile = NULL, *motif = "le ";
/* La variable motif contient la sous-chaine a rechercher
   Le pointeur mafile contient l'adresse de base de notre file 
*/

int trouve, queue; /* Declaration d'une sentinelle (trouve) nous
                      indiquant si la sous-chaine a ete trouvee
                      ou pas, et de la variable queue nous 
                      permettant de savoir ou se trouve la fin 
                      de notre file dans notre tableau 
                   */

void main()
{
    char *chaine = "Only AMIGA makes it possible !!!", *courant;
    /* Le pointeur chaine contient l'adresse de base de la chaine
       dans laquelle doit s'effectuer la recherche 
    */

    char *adr_a;
    int j, compteur;

    courant = chaine;
    queue = -1; /* Initialisation de notre queue de file */

    /* Allocation de MAX elements pour notre file */
    mafile = (char *) malloc (MAX);
    if (mafile == NULL)
    {
        puts ("Probleme d'allocation memoire !!!");
        exit (5);
    }

    /* Remplissage de notre file */
    while (file_pleine() == 0)
    {
        enfiler (*courant);
        courant++;
    }

    trouve = cherche(); /* Test si le contenu de notre file est
                           le meme que celui de la sous-chaine
                           recherchee 
                        */

    /* Tant que la sous-chaine n'est pas trouvee et que l'on n'a
       pas atteint la fin de la chaine 
    */
    while ((trouve == 0) && ((courant-chaine) < strlen(chaine)))
    {

        /* Recherche dans la file (en ignorant le premier element
           sinon si l'occurrence existe bien en premiere position
           dans notre file mais que la sous-chaine n'est pas 
           trouvee ON BOUCLE)
           si une occurrence du premier caractere de notre 
           sous-chaine existe et si c'est le cas, on stocke son 
           adresse dans adr_a 
        */
        adr_a = strchr (mafile+1,*motif);
        if (adr_a == NULL)
            /* Si adr_a = NULL alors notre file ne contient pas 
               le premier caractere de notre sous-chaine.
               Par consequent, nous pouvons vider la file 
               completement
            */
            compteur = MAX;
        else
           /* Si, au contraire, le premier caractere de notre
              sous-chaine est trouve dans notre file, il faut 
              defiler jusqu'a ce caractere
           */
            compteur = adr_a - mafile;

        for (j = 0; j < compteur; j++)
            defiler();

        /* Remplissage de la file afin de pouvoir tester a 
           nouveau si la sous-chaine a ete trouvee
        */
        while (file_pleine() == 0)
        {
            enfiler (*courant);
            courant++;
        }

        trouve = cherche();
    }

    /* Ce test parle de lui-meme */
    if (trouve == 1)
        printf ("Trouve\n");
    else
        printf ("Non trouve\n");

    free (mafile); /* Soyons fair-play, liberons la memoire */
}

int cherche (void)
{
    /* Si la file contient la sous-chaine recherchee
       renvoie 1
       Sinon
       renvoie 0
    */
    if (strncmp (mafile,motif,MAX) == 0)
        return (1);
    else
        return (0);
}

int file_pleine (void)
{
    /* Le test doit porter sur MAX - 1
       puisque les tableaux commencent en 0
    */
    if (queue == (MAX - 1))
        return (1);
    else
        return (0);
}

/* Si vous desirez plus de details quant aux fonctions ci-dessous
   referez vous aux primitives donnees plus haut
*/
int file_vide (void)
{
    if (TETE == (queue + 1))
        return (1);
    else
        return (0);
}

void enfiler (char carac)
{
    if (file_pleine() == 0)
    {
        queue++;
        mafile[queue] = carac;
    }
    else
        puts ("File PLEINE");
}

char defiler (void)
{
    char val = '\0';
    int i;

    if (file_vide() == 0)
    {
        val = mafile[queue];
        i = 0;
        while (i < queue)
        {
            mafile[i] = mafile[i + 1];
            i++;
        }
        queue--;
    }
    else
        puts ("File VIDE");

    return (val);
}

Pour remédier au problème posé par la gestion contigüe des files, une alternative nous est offerte, la gestion contigüe de la file avec décalage : nous devons nous-mêmes effectuer l'opération de décalage. Pour cela, nous devons imposer certaines règles : la tête devient une constante et seule la queue varie au fur et à mesure des appels aux procédures d'enfilement et de défilement. Voyons ensemble l'unique procédure à modifier.

Algorithmes

Comme nous le constatons, peu de modifications sont à apporter. En contrepartie, nous remarquons que notre file est mieux gérée puisque seule une des deux bornes bouge. De ce fait, nous occupons réellement chacune des cases du tableau (la file ne sera pleine que lorsque toutes les cases du tableau seront utilisées). Cependant, il reste tout de même un inconvénient, qui est le temps de permutation de chaque case. Sur une file de grande taille, le temps consacré à la permutation peut s'avérer excessivement long. Ceci nous amène à considérer une troisième méthode appelée gestion circulaire de la file.

Les files circulaires

La file circulaire se propose de remédier à ces inconvénients (merci la file circulaire) en faisant varier ses deux pointeurs (tête et queue) sans que la notion de borne du tableau n'intervienne. Éclaircissons un peu les choses par un exemple graphique :

Algorithmes

Nous avons rempli notre file avec les 8 premières lettres de l'alphabet. A l'étape (1) nous décidons de défiler un élément, en l'occurrence, le "A". Le pointeur "Tete" est donc incrémenté et pointe maintenant sur la seconde case du tableau. A l'étape (2), nous enfilons la lettre "I". Comme la "Queue" pointe sur la dernière case du tableau, nous la ramenons en première position (la place de la case 1 étant maintenant libre).

Le schéma (2) est le résultat de ces deux opérations.

Notre exemple n'a pas été choisi au hasard. Nous avons vu plus haut que le test filevide() était vérifié si Tete>Queue. Or, dans le second schéma, la "Tete" est bien supérieure à la "Queue", mais notre file est pleine... Déjà, nous sentons arriver les prémices des premières ambiguïtés. En effet, les deux pointeurs sont désormais gérés de la même manière et la notion de tête et de queue apparaît différemment. La "Tete" peut ne pas être inférieure à la "Queue" (comme dans l'exemple). Voyons sans plus tarder les primitives.

Algorithmes

Nous ne saurons trop vous conseiller de tester le déroulement de ces primitives sur un petit exemple de votre choix. La difficulté réside dans les tests d'évaluation de l'état de la file...

#include <exec/types.h>

#define MAX 3

int tete, queue ;
BOOL filevide, filepleine ;

VOID enfile    (char) ;
VOID batimotif (VOID) ;
VOID defile    (VOID) ;
BOOL cherche   (VOID) ;

/* File d'origine qui subira toutes les primitives et a partir
   de laquelle nous construirons buildmotif. La file etant 
   geree de maniere circulaire, nous ne pouvons pas la tester 
   comme un motif a rechercher. Car bien que toutes les lettres 
   y soient presentes, ces dernieres sont en desordres */ 
char file[MAX+1] = {'*', '*', '*', '\0'} ;

/* chaine a parcourir */
char *chaine = "Only AMIGA makes it possible !!!" ;

/* motif que l'on souhaite retrouver, et pointeur de parcours
   sur la chaine de depart */
char *motif = "!! ", *courant = NULL ;

/* le motif qui sera construit a partir de la file et qui 
    servira pour tous les tests */
char buildmotif[sizeof(motif)] =  {'*', '*', '*', '\0'} ;

main (char **argv, int argc)
{
   BOOL trouve = FALSE ;
   int  cptdefile = 0 ;

   tete = 0 ;
   queue = -1 ;

/* ces 2 booleens nous permettent de connaitre les differents 
   etats de notre file. Ils sont combines dans les tests afin 
   d'eviter que notre queue (ou la votre, mais cela ne nous   
   regarde pas !!) ne morde la tete */
   filevide = TRUE ;
   filepleine = FALSE ;

/* cette ligne permet de voir le cheminement des lettres dans
   la file ainsi que les differents etats de cette derniere. 
   Elle est facultative mais peut aider a comprender le
   mecanisme. */
   printf ("file : %s \t tete : %d \t queue : %d \t filevide :
            %d \t filepleine : %d \n", file, tete, queue, 
            filevide, filepleine) ; 

   courant = chaine ;

/* remplissage initial de la file a partir de la chaine */
   while (!filepleine)
   {
      enfile (*courant) ;
      courant++ ;   
   }

/* remettre les lettres dans le bon ordre afin d'effectuer 
   un test coherent avec le motif a rechercher. La file etant   
   etant geree de maniere circulaire, les lettres ne sont pas
   redecalees a partir de la tete mais enfilees les unes a la 
   suite des autres. */

   batimotif () ;

   trouve = cherche () ;

   while ((!trouve) && ((courant - chaine) < strlen (chaine)))
   {

/* puisque cherche n'a pas trouve notre motif nous pouvons 
   defiler le premier caractere sans risque. Mais pas les
   suivants car il se peut que le motif debute un peu plus 
   loin. Exple : motif = "mad" et buildmotif = "mma".
   cherche () nous dit que les deux chaines sont differentes.
   Or il se peut qu'apres "mma" il y ait un 'd'. Donc dans tous
   les cas nous defilons le premier caracteres et autant qu'il
   y en a de differents apres. Dans notre exemple nous ne defi
   lerons que le premier 'm'. Si la premiere lettre avait ete
   conservee nous aurions boucle a l'infinie. En effet n'ayant 
   rien defile nous nous retrouvons avec la chaine de depart
   "mma". Nous ne pourrions plu enfiler et par la meme occasion
   avance dans la chaine a parcourir */

      defile () ;
      cptdefile = 1 ;
      while ((buildmotif[cptdefile] != motif[0]) && 
            (cptdefile != MAX))
      {
         cptdefile ++ ;
         defile () ;
      }

      while (!filepleine)
      {
         enfile (*courant) ;
         courant ++ ; 
      }

      batimotif () ;

      trouve = cherche () ;
   }

   if (trouve)
      printf ("le motif [%s] est present dans :\n%s\n\n", 
               motif, chaine);
   else
      printf ("le motif [%s] n'existe pas.\n", motif);

   exit (0) ;
}

VOID enfile (char symbol)
{
   if (!filepleine)
   {
      if (queue == MAX - 1)
         queue = 0 ;
      else
         queue++ ;
      
      file [queue] = symbol ;
      filevide = FALSE ;
      if ( ((tete == 0) && (queue == MAX - 1)) || 
           ((queue < MAX - 1) && (tete == queue + 1)) )
         filepleine = TRUE ;
   }
   else 
      printf ("file pleine \n") ;

/* encore une ligne d'aide a la comprehension */
   printf ("file : %s \t tete : %d \t queue : %d \t filevide :
            %d \t filepleine : %d \n", file, tete, queue, 
            filevide, filepleine) ; 
}      

VOID defile (VOID)
{
   if (!filevide)
   {
      file [tete] = '*' ;
      if (tete == MAX - 1)
         tete = 0 ;
      else
         tete++ ;
      
      filepleine = FALSE ;

      if ( ((tete == 0) && (queue == MAX - 1)) || 
           ((queue < MAX - 1) && (tete == queue + 1)) )
         filevide = TRUE ;
   }
   else 
      printf ("file vide \n") ;

/* toujours elle */
   printf ("file : %s \t tete : %d \t queue : %d \t filevide :
            %d \t filepleine : %d \n", file, tete, queue, 
            filevide, filepleine) ; 
}

BOOL cherche (VOID)
{
   if (strncmp (buildmotif,motif,MAX) == 0)
      return (TRUE);
   else
      return (FALSE);
}

VOID batimotif (VOID)
{
   int cptfile, cptbuild ;
   
   cptbuild = 0 ;

/* nous recuperons d'abord toutes les lettres de la tete */
/* a la fin de la file. */
   for (cptfile = tete ; cptfile < MAX ; cptfile ++, cptbuild ++)
      buildmotif[cptbuild] = file[cptfile] ;

/* puis de la queue jusqu'a la tete */
   for (cptfile = 0 ; cptfile < tete ; cptfile ++, cptbuild ++)
      buildmotif[cptbuild] = file[cptfile] ;
}


[Retour en haut] / [Retour aux articles] [Article précédent] / [Article suivant]