< < E-NEF > >

Création de sites | Moniteurs | Chercher | Voyager | Cartes

()

Titre : Les listes, les Piles et les Listes Circulaires. 

Auteur : Emmanuel PIERRE 

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 :

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

 

counter
&copy; Copyright 1998-1999 Emmanuel PIERRE. Libre reproduction sous Licence LLDDv1.
Pour tout commentaire, webmaster@e-nef.com
Dernière MaJ

Valid XHTML 1.0!

No Patents/