Scribd
Importer
81 vues22 pages

Gestion et Implémentation des Files et Piles

Le document décrit les files et les piles, leurs propriétés et leurs implémentations possibles à l'aide de tableaux. Il présente notamment les opérations de base sur les files et piles ainsi que leur implémentation avec des structures contenant un tableau et des indices.

Transféré par

مريم جميعي
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
81 vues22 pages

Gestion et Implémentation des Files et Piles

Le document décrit les files et les piles, leurs propriétés et leurs implémentations possibles à l'aide de tableaux. Il présente notamment les opérations de base sur les files et piles ainsi que leur implémentation avec des structures contenant un tableau et des indices.

Transféré par

مريم جميعي
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Les Files

Introduction
• Gestion FIFO (First In First Out)
– Exemples d’utilisation
• Les mémoires tampons (Buffers), les pipes…
• On a deux créateurs :
– nil :  file
– adjq : file x element  file
• On a deux fonctions d’accès :
– Lecture de l’élément de tête : hd
– Suppression de l’élément de tête : tl

hd : file element
hd(nil)= ┴
hd(adjq(nil,el))=el
hd(adjq(adjq(l,el1),el2))= hd(adjq(l,el1))
tl : file  file
tl(nil)=┴
tl(adjq(nil,el))=nil
tl(adjq(adjq(l,el1),el2))= adjq(tl(adjq(l,el1)),el2)
Implémentation des Files
à base de tableaux
• Problèmes
– Il faut mémoriser l’endroit où le prochain élément
doit être mis
– Chaque fois que l’élément de tête est
« consommé », il faut décaler tout le tableau, ce
qui peut s’avérer très long.
• Solutions :
– Le premier point implique d’utiliser une structure
comportant un tableau et un indice
– Le second problème peut être résolu grâce à
l’opérateur modulo : au lieu de décaler le tableau,
on modifie le pointeur de tête de la file sur
l’élément suivant. La taille du tableau étant
limitée, il faut arriver à la fin et recommencer à
partir du début. Il faut donc un indice pour le
premier élément courant.
#define Taille 100
#define T (Taille +1)
typedef struct fl
{ int tete;
int next;
element tab[T];
} f_file;
void Init (f_file *f)
{ ftete=0;
fnext=0;
}
int vide (f_file *f)
{ if (ftete == fnext) return 1;
else return 0;
}
element tete (f_file *f)
{ if (vide(f))
{printf(‘’erreur, la file est vide’’);
return -32000;
/*on suppose que le nombre -32000 n’est jamais
utilisé dans la file et qu’il appartient à element */
}
else return ftab[ftete];
}
void enfiler (f_file *f, element el)
{ if ((ftete – fnext == 1) || (ftete==0 &&
fnext==Taille))
printf(‘’File pleine’’);
else
{ ftab[fnext]=el;
fnext=((fnext)+1)%T;
}
}
element defiler (f_file *f)
{ element e;
if (ftete == fnext)
{printf(‘’erreur, la File est vide’’);
return -32000;
/*on suppose que le nombre -32000 n’est jamais utilisé
dans la file et qu’il appartient à element */
}
else
{e=ftab[ftete];
ftete= ((ftete) +1)%T;
return e;
}
}
Les Piles
Une pile (stack en anglais) est une liste
dans laquelle l'insertion ou la suppression
d'un élément s'effectue toujours à partir de
la même extrémité de la liste, extrémité de la
appelée début ou tête de la pile.
• L'action consistant à ajouter un nouvel
élément au début de la pile s'appelle empiler ;
• L'action consistant à retirer l'élément situé au
début de la pile s'appelle dépiler.
• Une pile permet de modéliser un système régi
par la discipline
« dernier arrivé - premier sorti »;
on dit souvent qu'il s'agit d'un un traitement
LIFO (last in, first out).
• La hauteur de la pile est son nombre
d’éléments
Exemples d'utilisation des piles
• Évaluation des expressions arithmétiques

• Gestion des appels de fonctions

• Analyseurs syntaxiques
Les fonctions souvent définies dans
l'implémentation d'une pile sont:
- Création d'une pile
- savoir est-ce que la pile est vide
- sommet, délivre l’élément en sommet de la
pile
- empiler un élément
- dépiler un élément
donner la valeur de l'élément qui se trouve au
début de la pile, sans dépiler celui-ci
Implémentation de la Pile à base
de tableaux
typedef struct stp
{ element tab[100];
int taille;
} pile;
void init (pile *p)
{ ptaille =0;
}

int estvide (pile *p)


{
if (ptaille == 0)
return 1;
else return 0;
}
element sommet (pile *p)
/* retourne l’élément en sommet de pile sans le
dépiler */
{ if (estvide(p))
{printf (‘’erreur pile vide’’); return -32000; }
/*on suppose que le nombre -32000 n’est jamais
utilisé dans la pile et qu’il appartient à element */
else
return (ptab[(ptaille)-1]);
}
void depiler (pile *p)
{
if (estvide(p))
printf (‘’erreur pile vide’’);
else
ptaille--;
}
void empiler (pile *p, element el)
{
if (ptaille == 100)
printf(‘’erreur pile pleine’’);
else
{ ptab[ptaille]=el;
ptaille++;
}
}

Vous aimerez peut-être aussi