II. Chaînage, SDD séquentielles Piles et Files 1
Preview:
Citation preview
- Page 1
- II. Chanage, SDD squentielles Piles et Files 1
- Page 2
- Motivation 2 Pour de nombreux algorithmes et SDD squentielles
Oprations limites et contraintes Ajout et retrait seulement aux
extrmits (tte, queue) Ecrire : crer un maillon, copier llment,
ajouter le maillon Lire : retirer le maillon, copier llment,
supprimer le maillon Deux structures fondamentales Ajout et retrait
seulement en tte : pile Ajout resp. retrait en queue resp. en tte :
file
- Page 3
- Vocabulaire 3 Dsignation comportementale FIFO/LIFO First In
First Out = une file (EN : queue) Last In First Out = une pile (EN
: stack) Extrmits Ttes Pile : sommet (EN : top) File : sortie
Queues Pile : base File : entre Oprations EN : push/pop FR :
empiler/dpiler resp. enfiler/dfiler Dimensions Hauteur dune pile
vs. longueur dune file
- Page 4
- Reprsentation 4 Sommet Base Sortie Entre PUSHPOP PUSHPOP
- Page 5
- Applications types 5 De manire gnrale La pile sert mmoriser des
rsultats intermdiaires Pile dappels, analyseur syntaxique La file
sert en temporiser des flux Tampons pour la communication inter
processus En algorithmique Structures auxiliaires lmentaires les
plus courantes Algorithme gnrique de parcours itratif dun arbre
Utilisation dune pile : parcours en profondeur Utilisation dune
file : parcours en largeur
- Page 6
- 5 oprations (et pas davantage) 6 Spcification Cration et
supression Tester si la _ile est vide E__iler (push) D_iler (pop)
Implmentation Statique avec tableau Dynamique avec chanage
Lutilisation dune LSC ? Pertinent !
- Page 7
- Implmentation statique de la pile 7 Limite n lments Tableau
P[1..n] et attribut sommet Llment situ la base de la pile : P[1]
Llment situ au sommet de la pile : P[sommet] La pile est vide ssi
sommet = 0 Un empilement peut avoir lieu ssi sommet < n sommet
est alors incrment Un dpilement peut avoir lieu ssi sommet > 0
sommet est alors dcrment
- Page 8
- Implmentation statique de la pile En langage
algorithmiqueExemple de traduction en C 8 typedef struct pile { T
donne[n]; int sommet; } pile; typedef pile *pile_adr;
- Page 9
- Crer une pile 9
- Page 10
- Test de pile vide 10
- Page 11
- Empiler 11
- Page 12
- Dpiler 12
- Page 13
- Implmentation statique de la file 13 Tableau P[1..n] et
attributs entre : index de la position libre suivante sortie :
index de llment de tte Oprations sur les index : modulo n Principe
similaire ce qui a t vu pour le buffer clavier Reprage Llment situ
lentre de la file : P[entre 1] Llment situ la sortie de la file :
P[sortie] Difficult : gestion des dbordements positif et ngatif
File vide ssi entre = index Et pour la file pleine ? Pourquoi la
capacit est-elle limite n 1 ?
- Page 14
- Implmentation dynamique de la pile 14 Deux possibilits A)
Utiliser simplement une LSC B) Composer dans une structure une LSC
un champ profondeur Dans les deux cas, la tte joue le rle de
sommet
- Page 15
- Implmentation dynamique de la pile En langage
algorithmiqueExemple de traduction en C 15 typedef struct pile {
liste sommet; unsigned hauteur; // option } pile; typedef pile
*pile_adr;
- Page 16
- Crer une pile 16
- Page 17
- Test de pile vide 17
- Page 18
- Empiler 18
- Page 19
- Dpiler 19
- Page 20
- Implmentation dynamique de la file 20 Structure Une LSC Deux
adresses : La sortie de file (la tte de la LSC) Option un champ
largeur On ne prsente ci-aprs que la version sans largeur Pour
adapter vos algos cf. pile
- Page 21
- Implmentation dynamique de la file En langage
algorithmiqueExemple de traduction en C 21 typedef struct file {
liste entree; liste sortie; } file; typedef file *file_adr;
- Page 22
- Crer une file 22
- Page 23
- Test de file vide 23
- Page 24
- Enfiler 24 Algorithme 37 : Enfiler (f : file_adr, e : T)
(version dynamique Donne : ladresse de la file f Donne : llment e
enfiler dans f Variable locale : Ladresse m du maillon crer pour
stocker e dbut m rserver maillon m info e m succ nul si EstFileVide
(f) alors f sortie m sinon f entre succ m fin f entre m fin
- Page 25
- Dfiler 25 Algorithme 38 : Defiler (f : file_adr) : T (version
dynamique Donne : ladresse de la file f Variable locale : Llment e
dfil de f Variable locale : Ladresse m du maillon supprimer aprs
lextraction de e dbut si EstFileVide (f) alors erreur dbordement
ngatif sinon m f sortie f sortie m succ si f sortie = nul alors f
entre nul fin e m info librer m retourner e fin
- Page 26
- Simuler la rcursivit avec une pile 26 Soit lalgorithme rcursif
suivant : En donner la version itrative qui simule la rcursivit Tip
Utiliser une pile auxiliaire comme pile dappels
- Page 27
- Simuler la rcursivit avec une pile 27