Quand un programmeur veut stocker/traiter des données de manière répétitive, il n'a souvent pas
le choix et doit utiliser un tableau ou des tableaux. Ceux-ci sont très faciles d'emploi et
permettent d'accéder à tout élément, d'une manière directe (non séquentielle). Le seul vrai
problème posé par l'usage d'un tableau est sa taille. En effet, celui-ci doit être dimensionné
dans la partie déclarative (avant compilation) et doit donc avoir une taille fixée à l'avance et
celle-ci est souvent trop grande (sinon toujours). Il y a donc un gaspillage de mémoire non
négligeable qui dans certains cas pose des problèmes.
Définition.
Une variable du type 'pointeur' est une variable appelée à contenir une adresse (et donc 4 octets)
mais l'adresse de quoi me direz-vous? Et bien, l'adresse de la donnée que nous désirons stocker.
En effet, les pointeurs sont entre autres utilisés pour contourner le problème décrit ci-dessus
à propos des tableaux. Revenons-en donc à ce que nous désirons stocker. Par exemple,
un WORD (2 octets), une chaîne, un Etudiant, ....
pointeur: p, Tete, q
permet de déclarer des variables amenées à conserver les adresses nécessaires.
q ß L
permet d'indiquer au compilateur que la variable q ne possède pas d'adresse valable. Si vous désirez
accéder à la donnée de l'adresse q, vous aurez un message d'erreur mais aucun dommage ne sera fait
à un emplacement mémoire peut-être primordial pour le bon fonctionnement de votre PC.
p <-- nouveau (WORD)
q <-- nouveau (chaîne)
Tete <-- nouveau (Etudiant)
indiquent au compilateur qu'il doit chercher et stocker dans
p une adresse où il pourra stocker un WORD
q une adresse où il pourra stocker une chaîne
Tete une adresse où il pourra stocker une entité du type Etudiant
Pour accéder à cette partie de mémoire réservée, nous utiliserons
[p] <-- 270
[q] <-- "bonjour"
Nom de [Tete] <-- "dupont"
Prenom de [Tete] <-- "andré"
En Pascal/Delphi.
pointeur: p, Tete, q
n'existe pas tel quel (sauf si on veut 'laisser' une marque dans la mémoire en vue d'une
'libération' prochaine). Il faut toujours indiquer quel type de 'donnée' sera stockée à
l'adresse mémorisée dans la variable du type pointeur. Il s'agit donc en fait d'une combinaison
de la déclarative et de l'instruction 'nouveau' du pseudo-code.
VAR p: ^WORD; ^ placé devant le type est donc la manière choisie par Pascal pour indiquer à quel type de donnée le pointeur donne accès
Tete :^STRING;
q: ^Etudiant;
q ß L
se traduit par:
q:=NIL;
Et
p <-- nouveau (WORD)
q <-- nouveau (chaîne)
Tete <-- nouveau (Etudiant)
se traduisent par:
NEW(p);
NEW(q);
NEW(Tete);
Il n'est plus nécessaire de préciser vers quoi le pointeur doit pointer puisque cela a été fait
dans la partie déclarative.
Pour accéder à cette partie de mémoire réservée, en pseudo-code, nous utilisons:
[p] <-- 270
[q] <-- "bonjour"
Nom de [Tete] <-- "dupont"
Prenom de [Tete] <-- "andré"
et en Pascal/Delphi:
Tete^.Nom:='dupont'; et le nom de la variable suivie de ^ indique donc que l'on accède à la variable stockée à l'adresse mémorisée dans le pointeur
Tete^.Prenom:='andré';
Dans le cas plus complexe de:
entité Etudiant
composantes: Nom: chaîne
Nr: entier
fent
entité EtudiantPtr
composantes: Data: Etudiant
Pr, Svt: pointeur
fent
pointeur: Tete, q, Last, Curr
...
q ß nouveau EtudiantPtr
...
on a:
TYPE Etudiant=RECORD
Nom:STRING;
Nr:WORD;
END;
PtrEtudiant=^EtudiantPtr; On utilise donc EtudiantPtr qui n'est pas encore défini!
EtudiantPtr=RECORD
Data:Etudiant;
Pr,Svt:PtrEtudiant; On définit donc EtudiantPtr à partir de PtrEtudiant qui est défini lui-même par EtudiantPtr....
END;
VAR Tete,q,Last,Curr:PtrEtudiant;
...
NEW(q);
...
Usage.
Si nous voulons par exemple stocker en mémoire le contenu d'un fichier de chaînes pour le trier
ou lui faire subir un quelconque traitement, nous devrons écrire:
lire S sur FichIn
si NOT EOF(FichIn) alors p <-- nouveau (chaîne)
[p] <-- S
lire S sur FichIn
si NOT EOF(FichIn) alors q <-- nouveau (chaîne)
[q] <-- S
....
.....
et le problème auquel nous sommes ramenés est la génération automatique de noms de variables p, q, ...
Ce problème classique est résolu par la constitution d'un tableau .... que nous voulions
justement éviter. Notons cependant que cette solution du tableau de pointeurs est une solution qui
ne doit pas être rejetée à priori parce que le gaspillage de mémoire ainsi généré est souvent
nettement moindre qu'avec un autre tableau (un tableau de pointeurs prend nettement moins
de place qu'un tableau de chaînes par exemple).
L'autre solution est le chaînage des informations stockées: chaque donnée stockée sera composée
de la donnée brute (par exemple celle lue dans un fichier) et de l'adresse de la donnée suivante
(un pointeur).
Cette manière de faire passe nécessairement par la constitution d'une entité:
entité DataPtr
composantes: Data: chaîne si la donnée à stocker est du type chaîne
Ptr: pointeur
fent
On obtient une chaîne du type suivant:
Dans ce type de chaînage, chaque maillon contient une donnée et l'adresse du maillon suivant. Il est
donc impossible de revenir au maillon précédent et il est primordial de ne pas perdre l'adresse
du premier maillon que personnellement je stocke toujours dans la variable Tete.
Pour palier au problème du déplacement limité à un sens, il faut utiliser une entité qui contient
une donnée et 2 adresses: celle du maillon précédent et celle du maillon suivant. Il devient ainsi
possible d'aller en avant et en arrière.
entité DataPtr
composantes: Data: chaîne si la donnée à stocker est du type chaîne
Prec,Svt: pointeur
fent
Il ne faut pas oublier de mettre L dans l'adresse du maillon précédent
le premier maillon. En effet il n'y en a pas. Le dessin est trompeur et laisse croire qu'il faut y mettre p.
Ce qui est faux puisque p contient l'adresse du premier maillon.
On obtient une chaîne du type suivant:
|
Liste simplement chaînée.
|
Voici une implémentation de liste simplement chaînée qui réalise la lecture d'un fichier de Etudiant
et recherche ensuite si un étudiant s'y trouve.
entité Etudiant
composantes: Nom: chaîne
Nr: entier
fent
entité EtudiantPtr
composantes: Data: Etudiant
Ptr: pointeur
fent
fichier de Etudiant: FIn
Etudiant: S
pointeur: Tete, Mémorisera l'adresse du premier maillon
q, Servira de pointeur temporaire, le temps de créer le maillon
Last Mémorisera l'adresse du dernier maillon
FIn ß "student.dat"
ouvrir FIn
lire S sur FIn
Tete ß L Comme aucune donnée n'a encore été stockée, nous n'avons pas d'adresse valable.
q ß L Idem pour q qui sera mis dans Last (adresse du dernier maillon qui n'existe pas).
tant que NOT EOF(FIn) faire
Last ß q Last prend la valeur de q (qui est l'adresse du dernier maillon créé).
q ß nouveau EtudiantPtr Nous créons un nouveau maillon qui, quand il sera attaché, deviendra le dernier comme écrit à la ligne ci-dessus. Cette ligne est FONDAMENTALE et permet de réserver la place nécessaire au stockage d'une entité EtudiantPtr
Data de [q] ß S On stocke la donnée.
Ptr de [q] ß L Il n'y a pas de suivant et donc pas d'adresse à mémoriser.
si Tete=L alors Tete ß q L'adresse du premier maillon doit être mise dans Tete. Si Tete=L, aucune adresse valable n'est stockée et par conséquent, aucun maillon n'a encore été créé.
sinon Ptr de [Last] ß q On attache le maillon créé au dernier de la chaîne.
fsi
lire S sur FIn
ftant
fermer FIn
écrire "Introduisez le nom à chercher:"
lire NomE
si Tete =L alors écrire "Liste vide!"
sinon q ß Tete
tant que NOT ((Ptr de [q]=L) ou (Nom de Data de [q]=NomE)) faire
q ß Ptr de [q]
ftant
si Nom de Data de [q]=NomE alors écrire NomE, " a le numéro ", Nr de Data de [q]
sinon écrire NomE, "n'est pas dans la liste!"
fsi
fsi
|
Liste doublement chaînée.
|
Voici une implémentation de liste doublement chaînée qui réalise la lecture d'un fichier de Etudiant et
permet ensuite la navigation dans cette liste.
entité Etudiant
composantes: Nom: chaîne
Nr: entier
fent
entité EtudiantPtr
composantes: Data: Etudiant
Pr, Svt: pointeur
fent
fichier de Etudiant: FIn
Etudiant: S
pointeur: Tete, q, Last, Curr
caractère: C
FIn ß "student.dat"
ouvrir FIn
lire S sur FIn
Tete ß L
q ß L
tant que NOT EOF(FIn) faire
Last ß q
q ß nouveau EtudiantPtr
Data de [q] ß S
Pr de [q] ß L
Svt de [q] ß L
si Tete=L alors Tete ß q
sinon Svt de [Last] ß q
Pr de [q] ß Last
fsi
lire S sur FIn
ftant
fermer FIn
écrire "'+' avance, '-' recule, 'd' = début de liste, 'f' = fin de liste et 'q' quitte"
lire C
si Tete=L alors tant que NOT (C="q") faire
écrire "Liste vide!"
lire C
ftant
sinon Last ß q
Curr ß Tete
tant que NOT (C="q") faire
selon que
C="d" faire Curr ß Tete
écrire Nom de Data de [Curr]
oq C="f" faire Curr ß Last
écrire Nom de Data de [Curr]
oq C="+" faire si Svt de [Curr]= L alors écrire "Fin de liste!"
sinon Curr ß Svt de [Curr]
écrire Nom de Data de [Curr]
fsi
oq C="-" faire si Pr de [Curr]= L alors écrire "Début de liste!"
sinon Curr ß Pr de [Curr]
écrire Nom de Data de [Curr]
fsi
fselon
lire C
ftant
fsi
Cliquez ici pour charger une archive contenant une implémentation en Delphi
d'une liste doublement chaînée.
Voici une contribution de Melle Adnane:
un programme qui inverse une liste chainée circulaire
(*exercice: ecrire le programme qui inverse une liste circulaire simplement chainée. *)
program inverse_circulair;
type element=string[20];
ptr=^node;
node=record
data:string[20];(* le champ qui contient l'information*)
link:ptr;(* le champ qui contient lèadresse du suivant*)
end;
var f:ptr;
elt,inserer:string[20];
procedure insert (var f:ptr; mot:element);
var x,y,z:ptr;
begin
new(x);
x^.data:=mot;
if (f=nil) then begin
f:=x;
x^.link:=f;
end
else begin
if f^.data>= mot then begin
x^.link:=f; y:=f;
while y^.link <>f do
y:=y^.link;
y^.link:=x;
f:=x;
end
else begin
z:=f;
y:=f^.link;
while (y<>f) and (y^.data<=mot) do
begin
z:=y;
y:=y^.link;
end;
x^.link:=y;
z^.link:=x;
end;
end;
end;
procedure lecture(var f:ptr);
var i,n:integer; x:string[20];
begin
write('donner le nombre d''elements de votre liste: ');
readln (n);
for i:=1 to n do
begin
writeln ('l''element nø',i,' est= ');
readln (x);
insert (f,x);
end;
end;
procedure affiche (var f:ptr);
var y:ptr;
begin
y:=f;
while (y^.link<>f) do
begin
writeln(' ', y^.data);
y:=y^.link;
end;
writeln(' ',y^.data);
writeln(' ****************');
end;
procedure inverse(var f:ptr);
var x,y,z:ptr;
begin
x:=f; y:=f^.link;
while y<>f do
begin
z:=y^.link;
y^.link:=x;
x:=y;
y:=z;
end;
f^.link:=x;
f:=x;
end;
begin
f:=nil;
writeln('lecture de la liste');
lecture(f);
write ('voulez vous inserer un element dans votre liste? oui ou non ---- ');
readln (inserer) ;
while inserer <>'non' do
begin
write('donner l''element a inserer: ');
readln(elt);
insert(f,elt);
write ('voulez vous inserer un autre element dans votre liste? oui ou non ---- ');
readln (inserer);
end;
if f= nil then writeln(' liste vide ')
else begin
writeln (' la liste est: ');
affiche(f);
writeln (' la liste invers‚ est: ');
inverse(f);
affiche(f);
end;
readln;
end.
Voici une autre contribution de Melle Adnane:
un programme qui propose la représentaion, sous forme d'arbre, d'une liste entrée sous la
forme: (a(b,c(f,k),m)) où b,c et m sont des frères et b est le fils de a.
program arbres;
uses crt;
const n=20;
type treepointer=^treenode;
treenode=record
data:char;
fils,frer:treepointer;
end;
pile=array[1..n] of treepointer;
mot=string[30];
var f:treepointer;
exp,fin:mot;
FUNCTION depiler (var s:pile;var top:integer):treepointer;
BEGIN
depiler:=s[top];
top:=top-1;
END;
PROCEDURE empiler (var s:pile; var top:integer; z:treepointer);
BEGIN
top:=top+1;
s[top]:= z;
END;
function creat(l:mot):treepointer;
var y,z:treepointer;
n,i,top:integer;
p:pile;
begin
i:=2; top:=0; n:=length(l);
new(y); creat:=y;
while (i<=n) do
begin
case l[i] of
'(': begin
empiler(p,top,y);
new(z);
y^.fils:=z;
y:=z;
end;
',': begin
new(z);
y^.frer:=z;
y:=z;
end;
')': y:=depiler(p,top)
else
begin
y^.data:=l[i];
y^.fils:=nil;
y^.frer:=nil;
end;
end;
i:=i+1;
end;
end;
procedure affiche(f:treepointer);
begin
write(f^.data);
if (f^.fils<>nil) then
begin
write('(');
affiche(f^.fils);
end;
if (f^.frer<>nil) then
begin
write(',');
affiche(f^.frer);
end
else write(')');
end;
begin
fin:='non';
while (fin<>'yes') do
begin
clrscr;
readln(exp);
f:=creat(exp);
writeln(' affichage apres la representation:');
write('(');
affiche(f);
writeln('voulez vous arreter? yes ou non');
readln(fin);
end;
readln;
end.