Les Piles & Les Files

Application

Plan

1 Objectifs

2 Rappels

3 Abstraction

4 Type abstrait de donn´ees PILE

Sana HAMDI (ISSAT-M)

3/ 16

Objectifs

Rappels

Abstraction

Type abstrait de donn´ees PILE

Application

Abstraction

(cid:136) Lorsqu’on utilise une structure de donn´ees, l’important est de connaˆıtre les

op´erations que l’on peut effectuer sur les donn´ees

(cid:73) la fa¸con dont les op´erations sont programm´ees n’a pas d’int´erˆets pour

l’utilisateur

(cid:136) Un type abstrait de donn´ees est une description d’une structure de donn´ees

comprenant :

(cid:73) type de donn´ees qu’on peut mettre en m´emoire

(cid:73) description des op´erations possibles sur ces donn´ees

(cid:73) conditions d’erreurs associ´ees aux op´erations

Sana HAMDI (ISSAT-M)

4/ 16

Objectifs

Rappels

Abstraction

Type abstrait de donn´ees PILE

Application

Plan

1 Objectifs

2 Rappels

3 Abstraction

4 Type abstrait de donn´ees PILE

Sana HAMDI (ISSAT-M)

4/ 16

Objectifs

Rappels

Abstraction

Type abstrait de donn´ees PILE

Application

Les Piles

(cid:136) Garde en m´emoire des objets arbitraires

(cid:136) Les insertions et suppressions se font dans l’ordre ”dernier arriv´e, premier

servi”

(cid:136) Principales op´erations :

(cid:73) empiler(objet) ins`ere un objet sur la pile

(cid:73) d´epiler():objet retire et retourne l’objet en haut de la pile

Sana HAMDI (ISSAT-M)

5/ 16

Objectifs

Rappels

Abstraction

Type abstrait de donn´ees PILE

Application

Les Piles

(cid:136) Garde en m´emoire des objets arbitraires

(cid:136) Les insertions et suppressions se font dans l’ordre ”dernier arriv´e, premier

servi”

(cid:136) Principales op´erations :

(cid:73) empiler(objet) ins`ere un objet sur la pile

(cid:73) d´epiler():objet retire et retourne l’objet en haut de la pile

(cid:136) op´erations auxiliaires :

(cid:73) sommet():objet retourne l’objet en haut de la pile sans le retirer

(cid:73) taille():entier retourne le nombre d’objets de la pile

(cid:73) pileVide():bool´een indique si la pile est vide ou non

(cid:73) pilePleine():bool´een indique si la pile est pleine ou non (cas contigu¨e)

(cid:136) 2 impl´ementations

(cid:73) Repr´esentation contigu¨e

(cid:73) Repr´esentation chaˆın´ee

Sana HAMDI (ISSAT-M)

6/ 16

Objectifs

Rappels

Abstraction

Type abstrait de donn´ees PILE

Application

Piles en repr´esentation contigu¨e : tableaux

Type ´El´ement = . . . //d´epend du probl`eme

Type Tab = tableau [1 `a MAX] de ´El´ement

Type

Structure Pile

corps : Tab

taille : Entier //nombre d’´el´ement

finStructure Pile

proc´edure cr´eerPile (var p : Pile)

p.taille ← 0

Fin Proc´edure

Sana HAMDI (ISSAT-M)

7/ 16

Objectifs

Rappels

Abstraction

Type abstrait de donn´ees PILE

Application

Piles en repr´esentation contigu¨e : tableaux

Fonction pileVide (p : Pile) : Bool´een

pileVide ← (p.taille = 0)

Fin Fonction

Fonction pilePleine (p : Pile) : Bool´een

pilePleine ← (p.taille = Max)

Fin Fonction

Fonction sommet (p : Pile) : ´El´ement

Si pileVide (p) Alors

Erreur

Sinon

retourner p.corps[p.taille]

Fin Si

Fin Fonction

Sana HAMDI (ISSAT-M)

8/ 16

Objectifs

Rappels

Abstraction

Type abstrait de donn´ees PILE

Application

Piles en repr´esentation contigu¨e : tableaux

Proc´edure empiler (e : ´El´ement, var p:Pile)

Si (p.taille < MAX) Alors

p.taille ← p.taille + 1

p.corps[p.taille] ← e

Sinon

Erreur //possibilit´e de r´e-allocation du tableau

Fin Si

Fin Proc´edure

Fonction d´epiler (var p :Pile): Element

Si pileVide (p) Alors Erreur

Sinon

p.taille ← p.taille - 1

d´epiler ← p.corps[p.taille]

Fin Si

Fin Proc´edure

Sana HAMDI (ISSAT-M)

9/ 16

Objectifs

Rappels

Abstraction

Type abstrait de donn´ees PILE

Application

Piles en repr´esentation chaˆın´ee : listes chaˆın´ees

Type ´El´ement = . . . //d´epend du probl`eme

Type PtrM = Maillon *

Type

Structure Maillon

valeur : ´El´ement

next : PtrM

finStructure Maillon

proc´edure cr´eerPile (var Pile : PtrM)

Pile ← Nil

Fin Proc´edure

Fonction pileVide (Pile : PtrM) : Bool´een

pileVide ← (Pile = Nil)

Fin Fonction

Sana HAMDI (ISSAT-M)

10/ 16

Objectifs

Rappels

Abstraction

Type abstrait de donn´ees PILE

Application

Piles en repr´esentation chaˆın´ee : listes chaˆın´ees

Fonction taille (Pile : PtrM) : entier

Variables

p : PtrM

n : entier

D´ebut

p ← Pile

n ← 0

Si pileVide(Pile) = Faux Alors

n ← 1

Tant que *p.next (cid:54)= Nil Faire

n ← n + 1

p ← *p.next

Fin Tant que

Fin Si

taille ← (n)

Fin Fonction

Sana HAMDI (ISSAT-M)

11/ 16

Objectifs

Rappels

Abstraction

Type abstrait de donn´ees PILE

Application

Piles en repr´esentation chaˆın´ee : listes chaˆın´ees

Fonction Recherche (Pile : PtrM, pos : entier) : PtrM

Variables

p : PtrM, n : entier

D´ebut

p ← Pile ; pred ← Nil ;n ← 0

Si pileVide (p) Alors Recherche ← Nil

Sinon

Tant que *p.next (cid:54)= Nil et n (cid:54)= pos Faire

n ← n + 1

pred ← p

p ← *p.next

Fin Tant que

Si p = Nil Alors Recherche ← Nil

Sinon Recherche ← Pred

Fin Si

Fin Si

Fin Fonction

Sana HAMDI (ISSAT-M)

12/ 16

Objectifs

Rappels

Abstraction

Type abstrait de donn´ees PILE

Application

Piles en repr´esentation chaˆın´ee : listes chaˆın´ees

Fonction ValSommet (Pile : PtrM) : ´El´ement

Variables

p : PtrM

D´ebut

Si pileVide(Pile) Alors

Erreur

Sinon

p ← Recherche (Pile, taille(Pile))

ValSommet ← *p.valeur

Fin Si

Fin Fonction

Sana HAMDI (ISSAT-M)

13/ 16

Objectifs

Rappels

Abstraction

Type abstrait de donn´ees PILE

Application

Piles en repr´esentation chaˆın´ee : listes chaˆın´ees

Proc´edure Empiler (var Pile : PtrM, x : ´El´ement)

Variables

pt : PtrM

D´ebut

p ← r´eserver(tailleDe(Maillon))

*p.valeur ← x

*p.next ← Nil

Si Pile = Nil Alors

Pile ← p

Sinon

pt ← Recherche (Pile, taille(Pile))

*pt.next ← p

Fin Si

Fin Proc´edure

Sana HAMDI (ISSAT-M)

14/ 16

Objectifs

Rappels

Abstraction

Type abstrait de donn´ees PILE

Application

Piles en repr´esentation chaˆın´ee : listes chaˆın´ees

Proc´edure D´epiler (var Pile : PtrM)

Variables

p, pred : PtrM

D´ebut

Si pileVide(Pile) Alors Erreur

Sinon

pred ← Recherche (Pile, taille(Pile)-1)

Si pred = Nil Alors

p ← Pile

Pile ← Nil

Sinon

p ← *pred.next

*pred.next ← Nil

Fin Si

Lib´erer(p)

Fin Si

Fin Proc´edure

Sana HAMDI (ISSAT-M)

15/ 16

Objectifs

Rappels

Abstraction

Type abstrait de donn´ees PILE

Application

Remplissage d’une zone d’une image

Une image en informatique peut ˆetre repr´esent´ee par une matrice de points

”Image” ayant M colonnes et N lignes. Un ´el´ement Image[x, y] de la matrice

repr´esente la couleur du point p de coordonn´ees (x, y). On propose d’´ecrire ici une

fonction qui, `a partir d’un point p, ´etale une couleur c autour de ce point. La

progression de la couleur ´etal´ee s’arrˆete quand elle rencontre une couleur autre que

celle du point p. La figure suivante illustre cet exemple, en consid´erant p = (3, 4).

Pour effectuer le remplissage, on doit aller dans toutes les directions `a partir du

point p. Ceci ressemble au parcours d’un arbre avec les noeuds de quatre fils. La

proc´edure suivante permet de r´esoudre le probl`eme en utilisant une pile.

Sana HAMDI (ISSAT-M)

16/ 16

Merci pour votre attention !

Sana Hamdi

Assistante en Informatique `a ISSAT Mateur

Membre du Laboratoire LIPAH (FST-Tunisie) et

du Laboratoire SAMOVAR (T´el´ecom SudParis-France)

Sana HAMDI (ISSAT-M)

16/ 16