|
|
|
|
T
itre : Les listes, les Piles et les Listes Circulaires.A
uteur : Emmanuel PIERREMaintenant nous allons aborder tout ce qui touche aux pointeurs. Les pointeurs permettent l’existence de structures en mémoire que les tableaux ne permettent pas. Voyons les grands types :
1. Les listes chaînées
Suite à ma petite introduction aux pointeurs, j’ai introduit le type Liste chaînée comme suit :
Type
Liste = ^Cellule;
Cellule = Record
elt : byte;
Suiv : Liste;
End;
On définit ainsi des opérations:
liste_vide: ® liste
tête: ® element
suite: liste ® liste
est_vide: liste ® boolean
cons: element x liste ® liste
et des conditions:
tete(L) et suite(L) sont définies si et seulement si NOT est_vide(L)
et des axiomes:
pour tout e element, L liste,
suite(cons(e,L))=L
tete(cons(e,L))=L
L’accès à un élément d’une liste n’est pas direct on est obligé de passer par des fonctions. La fonction CONS permet de rajouter un élément dans une liste, et de la créer si celle-ci est vide:
function cons(e:element;L:liste);
var ptr:liste;
begin
new(ptr);
ptr^.elet:=e;
ptr^.suiv:=L;
cons:=ptr;
end;
Un schéma est très parlant:
Ici on voit bien comment procède la fonction cons, pour rajouter une valeur dans la liste. Remarquez que L et Ptr ne sont pas en eux-mêmes des listes, mais des pointeurs sur liste. Quand on rajoute le chapeau après le L, i.e. L^, là on désigne la liste physique, sans c’est la liste logique ( le pointeur qui dit où elle est ). La fonction tête renvoie la valeur de 1er element dans la liste, et suite fait pointer L sur l’élément suivant, d’où besoin de préserver l’adresse physique de début d’une liste quand on veut la parcourir. Ensuite viendra les déclarations de listes vides :
function tete(L : liste):element;
begin
tete := L^.elt;
end;
function suite(L : liste):liste;
begin
suite := L^.suiv;
end;
function est_vide(L : liste):boolean;
begin
est_vide:=(L=Nil);
end;
CONST liste_vide = NIL;
Maintenant des fonctions de bases pour calculer la longueur, obtenir le dernier élément, et rechercher un élément:
function longueur(L : liste):element;
begin
if est_vide(L) then longueur:=0
else longueur:=longueur(suite(L))+1);
end;
function dernier(L : liste):element;
begin
if est_vide(suite(L)) then dernier:=tete(L)
else dernier:=last(suite(L));
end;
function recherche(E : element;L : liste):boolean;
var ;
begin
while (L<>liste_vide) do
begin
if (L^.suiv=nil) then recherche:=true
else L:=L^.suiv;
end;
recherche := false;
end;
function insert(e : element;L : liste):liste;
begin
if est_vide(L) then insert:=cons(e,L)
else if (e<=tete(L)) then insert:=cons(e,L)
else insert:=cons(tete(L),insert(e,suite(L)));
end;
On remarque, avec une connaissance des tableaux, que l’accès aux tableaux, c’est à dire à une représentation continue de la mémoire, l’accès est plus rapide, mais la mise à jour difficile, et l’insertion impossible sans modifier la structure.
Pour une liste chaînée, pour accéder au kième élément, on parcourt les (k-1) éléments précédents, mais la mise à jour est plus facile, l’insertion aussi.
2. Les piles
Une pile est une liste où insertion et suppression se font à une seule extrémité appelée SOMMET de la pile (on appelle une pile aussi une gestion LIFO Last In First Out).
Opérations sur la pile:
-tester si la pile est vide
-accéder au sommet de la pile
-retirer l’élément qui se trouve au sommet de la pile: dépiler
-empiler
opérations:
pile_vide: ® pile
empiler: pile x element ® pile
dépiler: pile ® element
sommet: pile ® element
est_vide: pile ® booléen
conditions:
sommet et dépiler sont définis ssi NOT pile_vide.
axiomes:
sommet(empiler( P , e ))=e
depiler(empiler( P , e ))=P
1. les piles contiguës
type:
TYPE Pile = RECORD
som : integer;
elem:array[1..N] of element;
END;
procedure pile_vide(var P: pile);
begin;P.som:=0;end;
Voyons maintenant comment on empile et on dépile; empiler c’est ajouter un élément sur la pile, i.e. au sommet :
Voici comment on procède:
procedure empiler(var P : pile; e : element);
begin
if P.som=N then write(‘Pile Pleine’)
else begin
P.som:=P.som+1;
P.elem[P.som]:=e;
end;
end;
et voici le reste : dépiler, sommet et est_vide:
procedure depiler(var : pile);
begin
if P.som = 0 then write(‘pile vide’)
else P.SOM/+P.som-1;
end;
function sommet(P : pile): element;
begin
if est_vide(P) then write(‘pile vide’)
else sommet:=P.elem[P.som];
end;
function est_vide(P : pile): boolean;
begin
est_vide:=(P.som=0);
end;
2. représentation chaînée des piles
type pile = ^Cellule
cellule = RECORD
valeur : element;
suivant : pile;
END;
procedure Pile_vide(var P : pile);
begin
P:=Nil;
end;
procedure empiler(var P : pile; X : element);
begin
new(E);
E^.valeur:=X;
E^.suivant:=P;
P:=E;
end;
On remarque que pour empiler et dépiler, on utilise directement l’adressage des pointeurs.
procedure depiler(var P: pile);
var C:liste;
begin
if est_vide(P) then write(‘Pile vide’)
else begin
C:=P;
P:=P^.suivant;
dispose(C);
end;
end;
pour dépiler, on passe par variable l’adresse de la pile, car elle va être modifiée, comme on en détruit un de ses éléments.
function sommet(P : pile): element;
begin
if est_vide(P) then write(‘pile vide’)
else sommet:=P^.valeur;
end;
function est_vide(P : pile): boolean;
begin
est_vide:=(P=Nil);
end;
procedure vide_pile(var P : pile);
begin
while (P<>nil) then depiler(L);
end;
Les listes dynamiques n’ont virtuellement aucune limite, puisque il n’est pas besoin de spécifier la taille de la pile.
3. Les Files d’attente
Les files sont des listes circulaires, dont l’ajout se fait à une extrémité, et les accès/suppression à l’autre extrémité. C ’est un type FIFO ( First In First Out ). On peut se les représenter par des files d’attente à un guichet ( SNCF en tant de grève ).
Opérations à faire:
- tester si la pile est vide
- accéder au premier élément
-ajouter un élément dans la file
-retirer un élément de la file
opérations:
pile_vide: ® file
ajouter: file x element ® file
retirer: file ® file
premier: file ® element
est_vide: file ® booléen
conditions
premier et retirer sont définis ssi NOT pile_vide
axiomes
pour tout f file, e element:
est_vide(f) = vrai Þ premier(ajouter(f,e))=e
est_vide(f) = faux Þ premier(ajouter(f,e))=premier(f)
est_vide(f) = vrai Þ retirer(ajouter(f,e))=file_vide
est_vide(f) = faux Þ retirer(ajouter(f,e))=ajouter(retirer(f),e )
est_vide(file_vide) = vrai
On peut la représenter de deux façons:
c’est cette deuxième représentation que nous étudierons, puisque d’un seul pointeur on peut accéder à la queue ( queue ) et à la tête (queue^.suiv). Pour la première représentation, c’est un peu plus compliqué, mais vous y arriverez facilement à partir de ce qui suit. Une file, c’est une suite de liste chaînée :
TYPE file_circ = list;
Pour ajouter, soit la queue est vide ( = Nil ), à ce moment là on initialise la liste, sinon on insère en disant que il y a encore un élément qui s’ajoute à la queue, donc il devient lui-même la queue ( on ajoute à la fin le dernier arrivé ):
procedure ajouter(e : element; var F : file_circ);
var ptr : file_circ;
begin
if est_vide(F) then
begin
new(ptr);
F^.elem:=e;
F^.suiv:=ptr;
end else
begin
new(ptr);
ptr^.elem:=e;
ptr^.suiv:=F^.suiv;
F^.suiv:=ptr;
F:=ptr;
end;
end;
Pour supprimer, on retire la tête (F^.suiv), le premier de la file vient de passer. Si il n’y en a qu’un, on vide la file.
procedure supprime(var F : file_circ);
var ptr : file_circ;
begin
if est_vide(F) then write(‘File vide’)
else if (F^.suiv=F) then
begin
dispose(F);
F:=nil;
end
else begin
ptr:=F^.suiv; (* la tête*)
F^.suiv:=F^.suiv^.suiv;
dispose(ptr);
end;
end;
function premier(F : file_circ):element;
begin
premier:=F^.suiv^.elem;
end;
function est_vide(F : file_circ):boolean;
begin
est_vide:=(F==nil);
end;
Les files sont souvent utilisées pour les claviers, avec un nombre fixe, pour limiter le nombre d’entrées. l’avantage est que quand on arrive à la fin, on peut écraser le début et ainsi de suite.
Conclusion
Voici que s’achève cette deuxième partie de notre périple sur les pointeurs, vous voici en main avec des procédures pour réaliser vos rêves. Vous pouvez maintenant relire mes articles sur les grands nombres, cela vous semblera d’une clarté limpide.
Pour ce qui suivra, je pense traiter des arbres, ce qui s’avérera une tache ardue, puisque les arbres sont, entre autre à la base de la compression Huffman. D’ailleurs je vous détaillerais un projet entier basé sur les arbres et Huffman. Si j’ai du courage, je pourrais même vous récupérer un programme qui prend une chaîne symbolique mathématique comme 3x^2+12x+3, qui le dérive et l’intègre n-fois. Intéressant non ?
Pour aller plus loin ...
Principes fondamentaux de l’informatique, A.Aho,J.Ullman ed.DUNOD
Famous last words :
" Two roads diverged in a wood and I-
I took the one less travelled by
And that has made all the difference "
R.FROST