Maintenant 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 :
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 :{LISTE1}
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 tete renvoie la valeur de 1° élement 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 k° élément, on parcourt les (k-1) éléments précédents, mais la mise à jour est plus facile, l'insertion aussi.
Opérations sur la pile:
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 depiler sont définis si NOT pile_vide.
Axiomes :
sommet(empiler( P , e ))=e
depiler(empiler( P , e ))=P
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 :
+----------------------+
| |
+-+--------------------+
|
| Empile
V
+ - - - - - - - - - - -+
som + 1
+ - - - - - - - - - - -+
| sommet | som
+----------------------+
| |
+----------------------+
| |
+----------------------+
| |
+----------------------+
| | 1
+----------------------+
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;
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.
Opérations à faire:
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:
par 2 pointeurs tete et queue :
+----+----+ +----+----+ +----+----+ +----+----+
tête -->| | --+-->| | --+-->| | --+-->| | |<--- Queue
+----+----+ +----+----+ +----+----+ +----+----+
par liste circulaire :
+----+----+ +----+----+ +----+----+ +----+----+
+->| | --+-->| | --+-->| | --+-->| | |<--- Queue
| +----+----+ +----+----+ +----+----+ +----+----+
+----------------------------------------------------+
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ées :
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
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.
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