Corrigé 1. Enoncé
1. Listes unidirectionnelles
Inverser une liste
On définit un maillon d'une liste chaînée par
TYPE S = STRUCTURE
Val : Typeqq {Type quelconque
}
Adr : POINTEUR(S)
FIN
L'algorithme qui suit inverse une liste L en une liste L' qui contient tous les éléments
de L dans l'ordre inverse.
Soient Q et P des variables de type POINTEUR(S).
L':= NIL
Q := L
TANTQUE Q <> NIL :
Allouer (P, S)
Aff_Val(P, Valeur(Q) )
Aff_Adr(P, L')
L' := P
Q := Suivant(Q)
FINTANTQUE
2. Listes bilatérales
Modèle sur les listes bilatérales
Un maillon d'une liste bidirectionnelle est défini comme suit:
TYPE S = STRUCTURE
Val : Typeqq
Suiv, Prec : POINTEUR(S)
FIN
Le modèle est l'ensemble des opérations suivantes: Allouer(P, S), Aff_Adrg(P, Val),
Aff_Adrd(P, Val), Suivant(P), Précédent(P) et Valeur(P).
Se référer au cours ( Partie I. Chapitre 1 ) pour une définition complète de ses
opérations.
Recherche d'un élément X donné
La fonction Recherche(L, X), qui suit, rend le pointeur de l'élément X s'il existe dans
la liste L, Sinon la valeur NIL.
Soit P une variable de type POINTEUR, Trouv une variable de type Booléen.
P := L
Trouv := FAUX
TANTQUE P <> NIL ET NON Trouv :
SI Valeur(P) = X
Trouv := VRAI
SINON P := Suivant(P) FSI
FINTANTQUE
Recherche := P
Suppression d'un élément x donné.
L 'algorithme qui suit supprime l'élément X de la liste L s'il existe.
P étant une variable de type POINTEUR.
P := Recherche(L,X)
SI P <> NIL :
SI Precedent(P) <> NIL :
Aff_Adrd (Precedent(P),
Suivant(P) )
SINON
L := Suivant(P)
FSI
SI Suivant(P) <> NIL :
Aff_Adrg( Suivant(P), Precedent(P) )
FSI
Liberer(P, S)
SINON " X n'est pas dans la liste " FSI
3. Les Piles à éléments de longueur variable
Le modèle
En définissant le type T comme suit :
TYPE T = STRUCTURE
Nbr : ENTIER
Tab: TABLEAU(1..N) DE ENTIER
FIN
on peut garder le même modèle défini sur les piles, c'est à dire avec les opérations
suivantes:
Creerpile(P), Pilevide(P), Pilepleine(P), Empiler(P, Val), Depiler(P, Val) o� Val est un
objet de type T.
Représentation mixte
Définition algorithmique de la pile :
TYPE T = STRUCTURE
Nbr : ENTIER
Tab : TABLEAU (1..N) DE ENTIER
FIN
TYPE S = STRUCTURE
Val : T
Adr : POINTEUR(S)
FIN
VAR P : POINTEUR(S) { P est une pile }
Avec cette représentation, les opérations sont exactement les mêmes que celles
définies sur les piles, sauf que la composante valeur est du type T au lieu d'un type
quelconque.
Les opérations sont traduites comme suit :
Créerpile(P)
: P := NIL
Pilevide(P)
: Pilevide := (P = NIL)
Empiler(P,
Val) : Allouer (Q, S)
Aff_Adr(Q, P)
Aff_Val(Q, Val)
P := Q
Dépiler(P, Val) :
SI NON Pilevide(P)
Val := Valeur(P)
Sauv := P
P := Suivant(P)
Liberer(Sauv)
SINON "Underflow" FSI
Une représentation chaînée possible
Définition algorithmique de la pile :
TYPE S1 = STRUCTURE
Elt : POINTEUR(S2)
Adr : POINTEUR(S1)
FIN
TYPE S2 = STRUCTURE
Val : ENTIER
Suiv: POINTEUR(S2)
FIN
Pile = POINTEUR(S1)
VAR P : Pile
Les opérations sont traduites comme suit :
Soient les deux procédures suivantes à écrire préalablement:
Créerlist(Val, L) : crée une liste linéaire chaînée L à partir de l'objet composé
Val (de type T défini ci-dessus). Val.Tab(1), Val.Tab(2), .... constituent les éléments
de la liste L.
Libererlist(L, Val) : libère tous les maillons de la liste L et range dans l'objet
composé Val le nombre de maillons et les valeurs correspondantes.
Les procédures du modèle sont alors les suivantes :
Creerpile(P)
: P := NIL
Pilevide(P) :
Pilevide := (P = NIL)
Empiler (P, Val) : Allouer (Q, S1)
Creerlist(Val, L)
Aff_Val(Q, L)
Aff_Adr(Q, P)
P := Q
Depiler(P, Val) : SI NON
Pilevide(P) :
Q := P
P := Suivant(P)
Libererlist( Valeur(Q), Val )
Liberer(Q)
SINON
" Underflow" FSI
Représentation contigu�
La pile est alors définie comme suit :
TYPE Pile = STRUCTURE
Som : ENTIER
Element : TABLEAU(1..Max) DE ENTIER
FIN
VAR P : Pile
Pilepleine(P) est remplacée par Placedisponible(P) car un empilement n'est possible que
si la place disponible dans la pile est suffisante pour stocker l'élément.
Noter aussi l'importance de la variable globale Der qui contient à tout moment le sommet
précédent de la pile. C'est gr�ce à cette variable que les dépilements sont
possibles.
Le modèle est implémenté comme suit :
Creerpile(P)
: P.Som := 0
Placedisponible(P) :
Placedisponible:=Max-(P.Som+P.Element(P.Som) )+1
Pilevide(P)
:
Pilevide := ( P.Som = 0 )
Empiler(P, Val)
: SI Val.Nbr + 2 > Placedisponible (P)
" Empilement impossible "
SINON
Der := P.Som
SI P.Som = 0 : { Premier empilement }
P.Som := 1
SINON
P.Som := P.Som + P.Element(P.Som) + 2
FSI
P.Element(P.Som) := Val.Nbr
P.Element(P.som + 1) := Der
J := 1
POUR I=P.Som + 2, Val.Nbr+P.Som +1:
P.Element(I) := Val.Tab(J)
J := J + 1
FINPOUR
FSI
Depiler (P, Val) : SI NON
Pilevide(P) :
Val.Nbr
:= P.Element(P.Som)
Der
:= P.Element(P.som + 1)
POUR
I = 1, Val.Nbr :
Val.Tab(I):= P.Element(P.Som + I + 1)
FINPOUR
P.Som
:= Der
SINON
"Pile Vide" FSI
4. Le modèle 2-Piles
Les 2 piles peuvent être définies comme suit :
TYPE Pile = STRUCTURE
Som1 : ENTIER
Som2 : ENTIER
Tab : Tab(1..N) DE Typeqq
FIN
A tout moment, on peut utiliser l'une des deux Piles. Donc, au niveau du modèle, il faut
préciser pour chaque opération sur quelle pile elle opère.
Modèle
Le modèle est donc le suivant :
Créerpile(P, Sorte), Pilevide(P, Sorte), EmPiler(P, Sorte), Depiler(P, Sorte),
Pilepleine(P). Cette dernière est la même pour les deux piles. Noter que Sorte est un
paramètre qui désigne sur quelle pile est effectuée l'opération.
Il faut ajouter au modèle, une opération d'initialisation des deux piles à vide (
P.som1 := 0 et P.som2 := N+1 )
Implémentation du modèle
Creerpile(P, Sorte ) : SI Sorte = 1 : P.Som1 :=
0
SINON
P.Som2 := N + 1 FSI
Pilevide (P, Sorte : SI Sorte = 1 :
Pilevide := (P.Som = 0)
SINON Pilevide := (P.Som2 = N+1 ) FSI
Pilepleine (P) :
Pilepleine := (P.Som2 = P.Som1 + 1)
Empiler (P, Val, Sorte) : SI NON Pilepleine (P) :
SI Sorte = 1 :
P.Som1 := P.Som1 + 1
P.Tab(P.Som1) := Val
SINON
P.Som2 := P.Som2 - 1
P.Tab(P.Som2) := Val
FSI
SINON " Overflow" FSI
Depiler (P, Val, Sorte) : SI Sorte = 1 :
SI NON Pilevide(P,1) :
Val := P.Tab(P.Som1)
P.Som1 := P.Som1 - 1
SINON " Underflow " FSI
SINON
SI NON Pilevide(P, 2)
Val := P.Tab(P.Som2)
P.Som2 := P.Som2 + 1
SINON " Underflow " FSI
FSI