Algorithmes et programmation structure

si lon excute laction dpiler (val), le nouvel tat de la

pile est (3).

4.2. Listes linaires particulires.

4.2.1. Les piles.
La structure de pile ne sert pas garder de faon
plus ou moins dfinitive des informations. On
sintresse plutt la suite des tats de la pile et on
utilise le fait que le dernier lment ajout se trouve
au sommet de la pile, afin de pouvoir tre atteint le
premier.
On peut donner une image du fonctionnement de
cette structure avec une pile dassiettes : on peut
ajouter et enlever au sommet de la pile ; toute
insertion ou retrait dune assiette en milieu de pile
est une opration qui comporte des risques.
La stratgie de gestion dune pile est dernier arriv,
premier servi. En anglais, Last In First Out, plus
connu sous le nom FIFO.
La structure de pile est utilise pour sauvegarder
temporairement des informations en respectant leur
ordre dentre, et le rutiliser en ordre inverse.
4.2.1.1. Dfinitions.
Une pile est une liste linaire, telle que lon passe d
un tat de la pile au suivant par adjonction ou
suppression dun lment en tte.
schma 1 : Etats dune pile.
sommet
sommet
.
.
.

.
.
.

base

..

.
.
.
.

base

le dernier lment de chaque liste est appel base

de la pile ; le premier lment de chaque liste est
appel sommet de la pile. Les mises jour se font
partir du sommet.
Une liste est toujours forme dun nombre fini
dlments qui correspond la taille maximale de la
pile. Les adjonctions sarrte lorsque cette taille
maximale est atteinte ; on parle de dbordement de
la pile (ou sur-dpassement). Les suppressions
sarrtent lorsque la pile devient vide (sousdpassement)
On dfinit habituellement les deux primitives :
- empiler (val) : ajoute un nouvel lment val au
sommet de la pile.
- dpiler (val) : supprime llment sommet de la
pile et range sa valeur dans val.
Schma 2 : pile source en (1), val contient z.
En excutant empiler (val), la pile devient (2).

c
b
a
(1)

empiler (val)
val

z
c
b
a
(2)

c
dpiler (val)
b
b
val
a
a
c
(1)
(3)
On peut dfinir dautres primitives qui facilitent
lutilisation dune pile, mais qui ne modifient pas la pile
elle-mme.
- Une fonction sommetpile qui dlivre la valeur de
llment de sommet de la pile.

c
sommetpile dlivre la valeur
b
c, sans modification de pile.
a
- Deux prdicats qui permettent de tester ventuellement
les sur- et sous-dpassements de la pile : pilevide et
pilepleine. Les dbordements sont dtermins en
comparant laccs courant au premier lment de la pile
et aux deux valeurs extrmes de cet accs qui
dterminent entirement la pile (base et valeur de laccs
pour la taille maximale).
Enfin, une primitive initpilevide permet dinitialiser une
pile.
Une pile est une liste chane, elle peut donc tre
reprsente de manire contigu (4.2.1.1.) ou chane
(4.2.1.2.).
4.2.1.1. Reprsentation contigu dune pile.
Soit une pile utilisant une reprsentation contigu : un
vecteur pile dont on donne priori la taille maximale
dimpile.
Algorithme : primitives empiler, dpiler.
Programme ch421_1.c = a et b
Algorithme : sommetpile, pilevide, pilepleine et
initpilevide.
Programme ch421_2.c : a, b, c et d.
4.2.1.2. Reprsentation chane dune pile.
Une pile peut tre reprsente par une liste linaire
chane telle que les insertions ou les suppressions sont
toujours effectues en tte de liste.
pile

Algorithme : empiler, dpiler, pilevide, initpilevide et

sommetpile.
La variable pile, de type pointeur, tant globale, les
primitives deviennent :
Programme ch421_3.c : a, b, c et d
4.2.1.3. Traitement des expressions.

Rakotoasimbahoaka Cyprien Robert

anne 2008

54

Algorithmes et programmation structure

Les applications utilisant des piles sont
nombreuses : valuation de fonctions rcursives,
parcours darborescences
Nous donnons des algorithmes dvaluation et de
transformation dcriture dexpressions. Ces
algorithmes ncessitent lutilisation dune pile.

<expref>::=
(<opbin><expref><expref>)|<opun><
<expref >|<variable>.
Exemples :
+ - A B C ((A - B) + C)
< A B C (( (A < B)) C)
A-+BC nest pas une expression prfixe.

a) dfinitions
- expression crite sous forme compltement parenthse
On peut dfinir lcriture compltement parenthse
par les quatre rgles suivantes :
1) Une variable est une expression compltement
parenthse.
2) si x et y sont des expressions compltement
parenthses, un oprateur binaire, alors (x y)
est une expression compltement parenthse.
3) si x est une expression compltement
parenthse, un oprateur unaire, alors (x) est
une expression compltement parenthse.
4) Il ny a pas dautres expressions compltement
parenthses que celles formes partir des rgles
prcdentes.
Nous poserons les hypothses suivantes :
Un oprateur binaire est un lment de lensemble
[+,-, *, /] pour les oprateurs arithmtiques, ou de
lensemble [<, , =, , >, , , v].pour les
oprateurs de relation et logiques.
Un oprateur unaire est soit ou pour les
oprateurs arithmtiques (ces symboles reprsentent
le + et le unaires), soit pour les oprateurs
logiques.
Une variable est une lettre majuscule.
On peut donner la grammaire BNF (Backus-Naur
Form) qui rsume les dfinitions :
<ecp>::=(<ecp><opbin><ecp>)|<opun><ecp>|<vari
able>
<opbin> ::= + | - | * | / | < | | = | | > | | | v
<opun> ::= | |
<variable> ::= A | B | C| Z
Exemples : expressions compltement parenthses.
((A + B) * C), (((A / B) = C) (E < F), (A).
Les expressions suivantes ne sont des expressions
complment parenthses : (A), ((A + B)), A B.

- Expression crite sous forme postfixe.

Lcriture postfixe dune expression est dfinie par les
quatre rgles suivantes :
1) Une variable est une expression postfixe.
2) Si x et y sont des expressions postfixes, un
oprateur binaire, alors (x y ) est une expression
prfixe.
3) si x est une expression postfixe, un oprateur
unaire, alors (x ) est une expression postfixe.
4) Il ny a pas dautres expressions postfixes que celles
formes partir des rgles prcdentes.
Dans la grammaire BNF, la premire rgle est remplace
par :
<expost>::= (<expost><expost><opbin>)|<expost> <
<opun >|<variable>.
Exemples :
Ecp : ((A - B) + C)
Expref : + - A B C
Expost : A B C +

- Expression crite sous forme prfixe.

On peut dfinir lcriture prfixe dune expression
par les quatre rgles :
1) Une variable est une expression prfixe.
2) Si x et y sont des expressions prfixes, un
oprateur binaire, alors ( x y) est une expression
prfixe.
3) si x est une expression prfixe, un oprateur
unaire, alors (x) est une expression prfixe.
4) Il ny a pas dautres expressions prfixes que
celles formes partir des rgles prcdentes.

Ecp : ( (A < B) C)
Expref : < A B C
Expost : A B < C
- Expression crite sous forme infixe.
Les expressions crites sous forme compltement
parenthse sont simples lire, mais il est souvent
fastidieux dcrire toutes les parenthses. On peut
supprimer certaines parenthses si lon admet lordre de
priorit entre les oprateurs lors de lvaluation, sinon
linterprtation dune telle expression incompltement
parenthse serait ambigu.
Une expression reprsente ainsi est dite sous forme
infixe. Cest lcriture habituellement utilise dans les
langages de programmation.
Exemples :
Ecp : ((((A / B) * C) (C / (D * E))) (F - G))
Infixe : A/B*C C/ (D * E) (F G)
Les grammaires BNF qui dfinissent les expressions
infixes. Nous donnons la BNF tendue, o les symboles
en accolades peuvent tre omis ou bien rptes un
nombre quelconque de fois.
<expinf> ::= <expsimple> { <oprel><expsimple>}
<expsimple> ::= <terme> {<opadd><terme>}
<terme> ::= <facteur> {<opmult><facteur>}
<facteur>::=<variable>|-<facteur>|<facteur>|(<expinf>)
<oprel> ::= < | | = | | > |
<opadd> ::= + | - | v
<opmult> ::= * | / |
<variable> ::= A | B | | Z

Dans la grammaire BNF, la premire rgle est

remplace par :

Rakotoasimbahoaka Cyprien Robert

anne 2008

55

Algorithmes et programmation structure

En langage C, les oprateurs et v ont une priorit
infrieure aux oprateurs de relation, ce qui conduit
ne pas parenthser des expressions telle que :
A=B C>D. En effet on a les quivalences :
Infix A=B C>D
Compltement parenthse ((A=B) (C>D)).
Postfix AB = C D >
Infix A=(B C) >D
Compltement parenthse ((A= (B C))>D)
Postfix A B C = D >
Les traitements dune expression partir dune
reprsentation linaire font lobjet dalgorithmes en
gnral plus simples qu partir dune reprsentation arborescente. On peut assimiler la
reprsentation linaire un vecteur parcouru
squentiellement. Le schma des algorithmes sont
toujours le mme : on numre chacun des lments
du vecteur, on cherche quelle classe appartient
llment (variable, oprateur unaire ou binaire,
parenthse ventuellement), puis on applique le
traitement appropri la classe de llment.
b) Evaluation dune expression.
Si lcriture compltement parenthse semble
naturelle, les critures postfixes et prfixes ne
trouvent une justification que dans la simplicit des
algorithmes dvaluation de lexpression. Nous
allons examiner successivement les algorithmes
dvaluation dune expression postfixe et dune
expression compltement parenthse.
Soit une expression S (1,.., p, a1,.., an) o les i
sont les oprateurs et les ai sont les variables.
Lvaluation se dfinit indpendamment de la
reprsentation choisie pour cette expression. Si on
associe chaque ai une valeur vi, la suite E = (v1,..,
vn) de ces valeurs est appel environnement de
lexpression. Evaluer lexpression pour un
environnement donn consiste calculer la valeur
de lexpression pour les valeurs associes chaque
variable. Avant dvaluer une expression ou une sousexpression, on doit disposer de son environnement.
Pour effectuer cette valuation, on procde par
rductions successives en partant des sousexpressions dont les oprandes sont des variables
que lon peut calculer par une simple composition
de valeurs ; puis, de proche en proche, on est
toujours ramen valuer des expressions dont les
oprandes sont soit des variables soit de sousexpressions.
On peut schmatiser formellement lvaluation
dune sous-expression S forme dun oprateur
et de deux oprandes op1 et op2 :

variable(a) est un prdicat qui dlivre vrai si et

seulement si a est une variable,
opration(, v1, v2) est une fonction valuant
lopration binaire dont est loprateur et v1 et v2 les
valeurs des oprandes.
Exemple : valuer (A+(C*D)) avec A=3, B=4, C=5.
Evaluation ((A+(C*D)))=
= opration(+, 3, valuation ( (C*D))),
= opration(+, 3, opration (*, 4, 5)),
= opration(+, 3, 20),
= 23.
- Evaluation dune expression postfixe.
Lors du parcours de gauche droite dune expression
posfixe, on rencontre les oprandes avant les oprateurs.
Si lon sest arrang pour se souvenir de la valeur de
chaque oprande lorsque lon rencontre un oprateur, on
peut composer, laide de cet oprateur, le ou les
oprandes dont on a gard les valeurs. Le rsultat de
cette composition est une valeur qui est soit le rsultat
final, soit la valeur dun oprande dont il faut se souvenir
pour la suite de lvaluation.
La structure de pile est bien adapte pour sauvegarder
temporairement ces valeurs et constituer en sommet de
pile chaque instant lenvironnement de la sousexpression que lon va valuer.
On notera que la pile doit pouvoir contenir
indiffremment des valeurs de tous les types envisags
pour les expressions : numriques (entiers ou rels) ou
logiques.
En effet, lvaluation dune expression telle que :
AB+CD-> ; ncessite lvaluation de deux sousexpressions arithmtiques, alors que le rsultat est
boolen. Nous crerons tind, le type indiffrenci
correspondant dans la suite du chapitre. Il pourrait tre
ralis en codant les boolens vrai et faux par des
nombres tels que 0 et 1. Il suffit alors dassocier chaque
valeur un indicateur de type : B pour un boolen, N pour
une valeur numrique. Ainsi, faux serait cod (B, 1) alors
que le nombre 1 serait cod (N,1). La dclaration de tind
en C est :
typedef struture tind
{ typeval : (B, N) ;
valeur : real ;
};
Exemple dvaluation dune expression postfixe laide
dune pile. Soit lexpression : AB*CD+/, avec
lenvironnement A=20, B=4, C=9, D=7.
Nous parcourons lexpression de gauche droite et pour
chaque symbole lu nous modifions ltat de la pile :

Evaluation (S) = opration (,

Si (variable(op1))valeur(op1)sinon valuation(op1),
Si (variable(op2))valeur(op2)sinon valuation(op2),

tat initial
pile vide

20
empiler
valeur de A

4
20
empiler
valeur de B

80
valuer le *

O
valeur(a) est une fonction qui dlivre la valeur v
qui est associe la variable a,

AB*CD+/# AB*CD+/#

AB*CD+/#

AB*CD+/#

Rakotoasimbahoaka Cyprien Robert

anne 2008

56

Algorithmes et programmation structure

9
80

7
9
80

empiler
empiler
valeur de C valeur de D

16
80
valuer le +

5
valuer le /

lement de la sous-expression qui suit, lvaluation de la

sous-expression la plus rcemment empile. La pile,
comme prcdemment, permet de sauvegarder
temporairement des informations pendant le
parcours, avant que lon puisse dcider de leur
utilisation.
Exemple : soit valuer lexpression (A*(B+C)) avec
lenvironnement A=2, B=3, C=1. Les tapes de
lvaluation sont :

AB+CD+/# AB+CD+/# AB+CD+/# AB+CD+/#

On peut dduire intuitivement, partir de cet

exemple, les rgles concernant les actions
prendre. Soit expost un vecteur de caractres,
contenant une expression post-fixe cadre
gauche, et termine par le signe #.
Raisonnement par rcurrence : supposons que lon
ait dj parcouru les i-1 premiers caractres, et que
lon ait empil les valeurs des sous-expressions
contenues dans expost[1..i-1].

expost[i] = #
parcours termin, le rsultat final est
la valeur au sommet de la pile. *
expost[i] #
>> expost[i] est une variable.
il faut empiler sa valeur.
i++ ; H
on dpile son oprande (ou ses 2 oprandes),
puis on empile le rsultat de lopration.
i++ ; H
Itration : tantque(expost[i] #)
Initialisation : i = 1 ; H //en C, indice du 1er lment
//dun vecteur est gal 0.
Algorithme : valuation dune expression postfixe.
Programme ch421_5.c
- Evaluation dune expression compltement
parenthse.
Nous donnons ici, un algorithme qui utilise un
parcours squentiel de gauche droite de
lexpression compltement parenthse et des
rductions successives des sous-expressions rencontres, mais les informations sauvegardes dans
la pile seront diffrentes.
Le principe est de sauvegarder dans la pile
dvaluation non des valeurs doprandes, mais des
sous-expressions compltes (oprandes et valeurs
doprandes) sans les dlimiteurs.
On supposera cette fois que la pile peut contenir,
par des codages appropris, soit des valeurs
numriques ou logiques, soit des oprateurs (caractres).
Une sous-expression tant dlimite par une
parenthse gauche et une parenthse droite, leur
rencontre dans le parcours squentiel de
lexpression va provoquer respectivement lemp-

*
2

*
2

3
*
2

(A*(B+C))# (A*(B+C))# (A*(B+C))# (A+(B+C))#

+
3
*
2

1
+
3
*
2

4
*
2

(A*(B+C))# (A*(B+C))# (A*(B+C))# (A*(B+C))#

On voit que les actions entreprendre sont :

* si le symbole lu est un oprateur, on lempile,
* si cest une variable, on empile sa valeur,
* si cest une parenthse droite, on dpile une sousexpression et on empile le rsultat de son valuation.
La parenthse gauche ne correspond aucune action.
Dans la lecture de gauche droite dune expression
compltement parenthse, les parenthses gauches sont
inutiles.
Algorithme : expression compltement parenthse.
Programme ch421_6.c
On constate que lvaluation dexpression compltement
parenthse, est plus coteuse que lvaluation
dexpressions postfixes. La pile contient non seulement
des valeurs doprandes, mais aussi des oprateurs.
c) Passage dune expression une autre.
- Passage de la reprsentation compltement parenthse la reprsentation postfixe.
Lvaluation dune expression est plus simple partir
dune expression postfixe, cependant une expression
compltement parenthse est plus lisible.
Nous nous trouvons devant un aspect trs simplifi du
processus de compilation dun langage de programmation qui ne serait forme que dexpressions compltement parenthse : le programme source fourni par
lutilisateur doit tre transform en une chane postfixe
quivalente (programme objet) directement interprtable
pour tre valu. On peut tre amen dans certaines

Rakotoasimbahoaka Cyprien Robert

anne 2008

57

Algorithmes et programmation structure

applications effectuer la transformation inverse :
postfixe=>compltement parenths.
Soit transformer une expression compltement
parenthse EXCP en une expression postfixe
EXPOST, en nutilisant si possible, quun seul
parcours squentiel de EXCP. Un suppose que
EXCP est syntaxiquement correcte : la sous
expression correspondante de EXPOST sera
termine par loprateur. Les oprandes figurent
dans le mme ordre dans les deux expressions. Il
semble donc naturel de ne ranger, lors du parcours
de EXCP, que les oprandes dans EXPOST, et de
se souvenir de loprateur associ la sousexpression courante. Lorsque le parcours de la
sous-expression dans EXCP est termin (rencontre
dune parenthse droite) on rangera loprateur
correspondant dans EXPOST.
Exemple : on suppose que les oprandes sont des
variables :
EXCP : (A+B)
EXPOST : A

EXPOST : A

EXCP : (A + B ) +

EXPOST :AB

EXCP : (A + B) +

EXPOST : ...AB+

EXCP : (A + B)

Lordre des variables nest pas modifi dans le

passage de EXCP EXPOST. Par contre, on
rencontre un oprateur binaire dans une sousexpression avant loprande droit associ. Cet
oprande droit peut lui-mme une sous-expression,
par exemple : (A * (B + C))
On est alors amen mmoriser deux oprateurs
quil ne faut pas intervertir. La structure de pile
permet de mmoriser les oprateurs et de les
restituer dans lordre voulu. Loprateur qui est en
sommet de pile est toujours loprateur de la sousexpression dont le niveau dimbrication relatif est le
plus grand ; ses oprandes sont les derniers qui ont
t rangs dans EXPOST ; Il est normal que la
transformation de cette sous-expression ait lieu en
premier.
On peut associer chaque classe dlment de
EXPC une action avec les rgles :
* oprateur : on lempile,
* variable : on la range dans EXPOST,
* parenthse droite : on dpile un oprateur que
lon range dans EXPOST,
* parenthse gauche : aucune action.
Ces rgles permettent intuitivement de construire
un algorithme cohrent. Si lexpression EXCP est

syntaxiquement correcte, en fin dalgorithme la pile est

vide.
Algorithme : passage dune EXCP en EXPOST.
Programme ch421_7.c
On peut amliorer cet algorithme afin quil dtecte des
erreurs de syntaxe dans lexpression compltement
parenthse. En supposant toujours que la fin de EXCP
est note par #, il suffit dajouter deux tests : lun sur
les caractres possibles en entre, lautre sur la pile qui
doit tre vide la fin. On notera que si la pile est vide
avant la fin (cas o il y aurait trop de parenthses
droites), cest lappel de la fonction dpiler qui dtectera
lerreur et fera arrter le droulement de lalgorithme.
Algorithme : passage dune EXCP en EXPOST avec
dtection derreurs dans EXCP.
Programme ch421_8.c
- passage de la reprsentation infixe la reprsentation
postfixe
Les rgles de transformation dune expression infixe
EXPINF en une expression postfixe EXPOST, sont
donnes en-dessous. On parcourt EXPINF de gauche
droite en effectuant des actions diffrentes selon la classe
des lments de EXPINF :
* Les variables sont ranges directement dans EXPOST.
* Les oprateurs sont empils ; toutefois, il faut tenir
compte de leur priorit. Les sous-expressions dont les
oprateurs sont de forte priorit sont values avant les
sous-expressions dont les oprateurs sont de faible
priorit ; elles doivent donc se trouver avant ces
dernires dans EXPOST. Par suite, chaque fois que lon
rencontre un oprateur, il faut dpiler tous les
oprateurs de priorit suprieure, et les ranger dans
EXPOST. Ils appartiennent des sous-expressions qui
sont elles-mmes oprandes ou sous-oprandes de la
sous-expression dont on traite loprateur. Ceci fait, on
peut empiler loprateur.
N.B. On doit galement dpiler les oprateurs de
priorit gale afin dvaluer, priorit gale, la sousexpression de gauche en premier (cette sous-expression,
vu le balayage de gauche droite de EXPINF, a dj son
oprateur rang dans la pile).
* La parenthse gauche sert de dlimiteur dune sousexpression ; il faut lempiler pour pouvoir dpiler les
oprateurs de cette sous-expression. La parenthse
gauche permet alors de dlimiter la sous-pile
correspondant la sous-expression courante. Il reste en
effet sur la pile, la fin du balayage dune sousexpression parenthse, tous les oprateurs de plus faible
priorit.
Comme ce dlimiteur est rang dans la pile des
oprateurs, il doit avoir une priorit, afin de ne pas
perturber le mcanisme de dpilement. Il est ncessaire
daffecter la parenthse gauche une priorit plus
faible que celle de tous les oprateurs.
* la parenthse droite marque la fin dune sousexpression, on dpile alors tous les oprateurs restants
jusqu la parenthse gauche, et on les range dans
EXPOST pour terminer lcriture postfixe de la sous-

Rakotoasimbahoaka Cyprien Robert

anne 2008

58

Algorithmes et programmation structure

expression. Ces oprateurs ont dailleurs tous la
mme priorit (priorit minimale pour la sousexpression considre). On procde de mme
lorsque lon rencontre la fin de EXPINF.
Exemple : soit transformer en reprsentation
postfixe lexpression : A*B+C/(D*E).
Les tats successifs de la pile et de lexpression
obtenue :

La taille de lenvironnement dpendant du nombre de

paramtres de la fonction, on ne peut plus le connatre priori
comme pour les oprateurs unaires et binaires. Pour dpiler
lenvironnement courant, aprs lvaluation de la fonction du
sommet de pile, et passer lenvironnement prcdent dans
lequel est rang le rsultat, il faut tablir un chanage entre
chaque environnement. Chaque valuation conduit donc
empiler les informations suivantes (tableau 2):

Tableau 2 : informations de chaque environnement

Argument n

A*B+C/(D*E A*B+C/(D*E)# A*B+C/(D*E)# A*B+C/(D*E)#

EXPOST : A

AB

AB*

(
/
+

/
+

(
/
+

A*B+C/(D*E# A*B+C/(D*E)# A*B+C/(D*E)# A*B+C/(D*E)#

EXPOST : AB*C

*
(
/
+

AB*C

AB*C

*
(
/
+

AB*CD

/
+

.
.
.
Argument 1

environnement

code de lopration

environnement prcdent

Exemple : considrons la fonction factorielle.

entier fact (entier n)
//spcification(n0)(fact = n !)
{ si (n1)retour 1 ;
sinon retour (n*fact(n-1)) ; }
Pour n=5, lvaluation de fatc(5) conduit la
construction dune pile dont certaines des tapes sont
figures ci-dessous :

2
mult

3
mult

4
mult

5
mult

A*B+C/(D*E A*B+C/(D*E)# A*B+C/(D*E)# A*B+C/(D*E)#

EXPOST : AB*CD AB*CDE

AB*CDE*

AB*CD*/+

Pour crire lalgorithme, on supposera quune

fonction priorit associe un entier chaque oprateur. Pour les expressions C, les valeurs sont :
Tableau 1 : priorit des oprateurs.
OPERATEUR
PRIORITE
(
0
||
1
&&
2
== !=
3
4
< >
5
+ 6
* / %
7
! ++ -Algorithme : transformation EXINF en EXPOST.
Programme ch21_9.c
4.2.1.4. Evaluation des fonctions rcursives.
Lvaluation dune fonction rcursive avec le principe
simplifi du mcanisme dvaluation dune fonction
(interprtation dun appel dune fonction dans un
programme). Un principe analogue est utilis par le
compilateur.
On retrouve la notion denvironnement. Lopration
dcrite par une fonction ntant plus standard et bien
connu comme dans le cas des oprateurs, il est ncessaire
de garder un accs au code qui permet dinterprter cette
opration. Cette information est empile comme
lenvironnement.

...

5
mult

4
mult

5
mult

fact(4)

fact(3)
fact(4)

fact(5)
fact(5)=5*fact(4) fact(4)=4*fact(3)
1
2
mult

3
mult

4
mult

5
mult

fact(1)

fact(2)=2*fact(1)

fact(1)

2
3
mult

4
mult

5
mult

fact(2)

..

24
5
mult

fact(4)

120
valuation

valuation
de fact(1) de fact(2)

Rakotoasimbahoaka Cyprien Robert

valuation
de fact(4)

anne 2008

fact(5)

rsultat
final

59

Algorithmes et programmation structure

Dans lvaluation dune telle fonction rcursive,
cest un mcanisme interne au compilateur qui est
charg de la gestion de la pile.
Il ne faut pas oublier que la forme itrative permet
une excution plus rapide et utilise moins de place
en mmoire, puisquelle vite les appels et retours
de sous-programmes, avec empilements des
environnements. Il faut donc les prfrer quand le
temps dexcution et lencombrement de la
mmoire posent des problmes.
Nous venons de donner deux utilisations de la
structure de pile. Elle peut tre utilise dans
dautres applications, et peut servir, lors dun
parcours non linaire, garder des informations
associes aux lments de la liste.
4.2.1.5. Allocation despace pour une pile.
Lespace mmoire quil est ncessaire dallouer
pour la pile est mesure par la hauteur maximale de
la pile. On essaie de la connatre priori ou de la
fixer empiriquement pour viter davoir allouer un
nouvel espace en cours dexcution dun algorithme
utilisant la pile. Une pile tant situe en mmoire
centrale, le cot dutilisation des primitives empiler
et dpiler sont ngligeables.
Plusieurs cas peuvent se prsenter pour allouer un
espace mmoire suffisant une pile :
- Si la taille de la pile (hauteur maximale) est
connue pour les donnes possibles de lalgorithme,
et que celle-ci est infrieure la taille mmoire
disponible, tout se passe bien.
- Si la taille mmoire nest pas connue, il faut tester
les dbordements ventuels pour chaque appel de
empiler.
Certains algorithmes demandent lutilisation de
deux piles. Avec une reprsentation contigu, on
alloue les piles partir des deux extrmits de la
mmoire disponible. On a alors le schma :
mmoire
pile1

pile2

Si la taille des deux piles nest pas connue, ou que

la somme des deux tailles dpasse la capacit de la
mmoire disponible, on peut quand mme utiliser
les deux piles. Le test de dbordement consiste
dtecter la collision des sommets de deux piles.
Si lon doit allouer plus de deux piles pour un
algorithme donn, on doit fixer pour chacune
delles une taille (soit par calcul, soit empiriquement), et allouer pour chaque pile une zone fixe d
espace mmoire. Il faut alors tester les dbordements ventuels.
mmoire

pile1

pile2

pile3

Une autre technique consiste, lorsque cest possible,

imbriquer plusieurs piles et chaner les divers lments
de chaque pile entre eux.
sommet pile1
base pile1
chanages pile1

pile3
chanage pile2
sommet pile3
base pile3
sommet pile2
base pile2

4.2.2. Les files dattente.

Ces listes correspondent au comportement dune file
dattente devant un guichet o la gestion est : premier
arriv, premier servi. En anglais on dira : First In First
Out ou plus simplement FIFO.
Ces files sont dun usage trs rpandu dans la programmation systme.
Dfinition : une file dattente est une liste linaire telle
que, les insertions sont effectues en fin de liste et les
suppressions sont toujours effectues en tte de liste.
4.2.2.1. Reprsentation contigu.
On peut songer reprsenter une file dattente dans un
vecteur simplement en ajoutant les nouveaux lments
droite (queue de la file), et en dplaant le pointeur de
tte de la file vers la droite chaque fois que lon supprime
un lment.
Exemple :
File avant modification : 0
n-1
ABCD
tte

queue

aprs insertion de E, F, G et suppression de A et B.

0
n-1
ABCDEFG
tte queue
En supposant que le vecteur FILE[0..n-1], ainsi que les
entiers tte et queue, sont des variables globales, les
primitives de gestion de la file seraient les suivantes :
Algorithme : primitives de gestion de la file.
Programme ch422_1.c
On voit que tte et queue augmentent toujours, et donc
que le vecteur devra tre trs grand, mme sil ne
contient que peu dlments chaque instant. Pour viter
cet inconvnient, on peut envisager deux solutions :
a) Dcaler les lments de la file vers la gauche chaque
suppression. Tous les lments avancent dune place
lorsque le premier est servi. Le pointeur de tte devient
alors inutile, puisquil est toujours gal 0.
File avant modification :
0
n-1
ABCD
tte queue
aprs insertion de E, F, G et suppression de A et B.

Rakotoasimbahoaka Cyprien Robert

anne 2008

60

Algorithmes et programmation structure

0
CDEFG
tte

n-1

liste

queue

les primitives modifies sont :

Algorithme : primitives modifies de gestion de file.
Programme ch422_2.c
La taille du vecteur doit correspondre au nombre
maximum dlments qui peuvent tre simultanment prsents dans la file dattente.
b) grer le vecteur de manire circulaire.
Cest la meilleure solution, elle minimise la place
ncessaire dans le vecteur, tout en vitant les
oprations de dcalage.
Exemple :
On suppose n = 6
File avant modification : 0
5
ABCD- tte queue
aprs insertion de E, F, G et supression de A et B :
0
5
G-CDEF
queue tte
Lorsque tte devient gal (queue+1) mod n, la file
est soit vide, soit pleine. On est donc amen
distinguer les deux possibilits en utilisant deux
indicateurs boolens filevide et filepleine. Les
primitives deviennent :
Algorithme : gestion de file, grer le vecteur de
faon circulaire.
Programme ch422_3.c
4.2.2.2. Reprsentation chane
Cest une reprsentation de liste chaine, dans
laquelle on utilise un pointeur supplmentaire : le
pointeur sur la dernire cellule, ce qui permet
dacclrer lalgorithme dinsertion qui a toujours
lieu en fin de liste.
tte
queue

Ces listes sont trs utilises dans les systmes de gestion

de base de donnes et en programmation systme. Une
liste circulaire permet de chaner entre eux un lment
possdant une mme proprit
Il suffit alors de connatre un lment possdant cette
proprit pour obtenir, par un parcours de la liste
circulaire tous les autres.
Algorithme : parcours dune liste circulaire.
Programme ch423_1.c
O traiter est une fonction quelconque de traitement
dune cellule dadresse donne.

4.2.4. Les listes bidirectionnelles.

Dans le cas dune reprsentation contigu dune liste
linaire (vecteur), on peut effectuer un parcours du
vecteur dans les deux sens (gauche-droite et droitegauche) alors que dans la cas de la reprsentation
chane, on ne peut effectuer quun parcours de gauche
droite. On peut qualifier cette liste chane de monodirectionnelle. Si on veut pouvoir effectuer un parcours
de droite gauche, il faut ajouter un pointeur permet
laccs la cellule prcdente. On qualifie alors la liste
de bidirectionnelle. Compte tenu de la place
supplmentaire occupe, on nutilise cette possibilit que
dans des cas o on a trs souvent besoin deffectuer un
retour en arrire, vers la tte de liste. Citons par exemple
les diteurs de texte structurs par lignes, o la partie
information de chaque cellule est constitue par un
pointeur vers le texte dune ligne.
On dispose alors du type pointeurb suivant :
structure cellule {
structure cellule *pointeurb ;
info : t ;
structure cellule *pointeurb ;
};
type structure cellule *ponteurb ;
Exemple :
liste

Les algorithmes dinsertion et de suppression sont

les suivantes (tte et queue sont globales) :
Algorithme : gestion de file, reprsentation chane.
Programme ch422_4.c

4.2.4. Listes circulaires ou anneaux.

Ce sont des listes linaires dans lesquelles le dernier
lment pointe sur le premier. Il ny a donc ni
premier ni dernier lment. Il suffit de connantre
ladresse dun lment pour parcourir tous les
lments de la liste.

Nous donnons deux exemples dalgorithmes de mise

jour dune liste chane bidirectionnelle. On suppose que
lon dispose de la fonction pointv (liste, val) daccs la
cellule contenant la premire occurrence de val dans
liste+.
4.2.4.1. Algorithme dinsertion dun lment avant
une valeur.
Il sagit sinsrer un lment elem avant la premire
occurrence de la valeur val. On utilise une variable
rsultat possible qui permettra de savoir si cette insertion

Rakotoasimbahoaka Cyprien Robert

anne 2008

61

Algorithmes et programmation structure

a pu tre ralise ou non, cest--dire si val
appartient la liste.
Supposons que la variable ptval contienne ladresse
de la cellule qui contient la premire occurrence de
la valeur val et la variable p ladresse de la cellule
insrer.
ptval

On peut effectuer les liaisons (1), (2) dans nimporte quel

ordre.
Dans le cas de la suppression en tte, on a deux cas :
- Le premier lment est aussi le dernier :
liste

ptval

4
2

Il suffit deffectuer laction : liste = liste->suivant ;

- Le premier lment nest pas le dernier.
Liste
1

2
Il faut effectuer les modifications des pointeurs (1),
(2), (3), (4) et faire surtout attention effectuer (3),
(4) dans cet ordre.
Dans le cas de linsertion en tte, on obtient :

liste

ptval

ptval
Il suffit deffectuer (1), (2).
Si llment supprimer est le dernier, on a galement
deux :
- le dernier est aussi le premier : il suffit de se reporter au
cas prcdent.
- le dernier nest pas le premier :
ptval

P
1
1
2
Il faut effectuer les modifications (1), (2), (3), (4).
Lalgorithme : insertion dun lment avant une
valeur.
Programme ch424_1.c
4.2.4.2. Algorithme de suppression dune valeur.
On veut supprimer la premire occurrence de la
valeur val dans une liste chane bidirectionnelle.
On a trois cas : suppression du premier lment,
suppression du dernier lment et le cas gnral.
Supposons que ptval contienne ladresse de la
cellule supprimer.

Il suffit deffectuer la liaison (1).

Algorithme : suppression du dernier lment.
Programme ch424_2.c
On peut avoir des listes bidirectionnelles organises en
anneaux ou utilises comme une pile ou une file
dattente.

Dans le cas gnral, on a :

ptval

Rakotoasimbahoaka Cyprien Robert

anne 2008

62