require("../global.php"); entete(); ?>
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-PiedDePage(); ?>
I took the one less travelled by
And that has made all the difference "
R.FROST