Programme
Semestre 1
Chapitre 1: Introduction à l'Informatique
Chapitre 2: Le Langage Algorithmique
Chapitre 3: Les Tableaux
Chapitre 4: Les Actions Paramétrées
Semestre 2
Chapitre 5: Les Enregistrements
Chapitre 6: Les Pointeurs
Chapitre 7: Les Listes Chaînées
Chapitre 8:
1
Les Pointeurs
Algorithme: 1ere Année Informatique
Introduction
Un algorithme est composé de 3 phases:
1. Acquisition des données
2. Traitement
3. Affichage des résultats
Chaque étape est constituée d’opérations : instructions ou
actions
Une instruction est l’expression d’un ordre fournit à la
machine.
Les instructions manipulent des objets. On distingue deux
types:
Objets modifiables : variables
Objets non modifiables : constantes
3
Chaque objet possède un emplacement en mémoire centrale.
La déclaration d’un objet permet de réserver une zone
mémoire. La taille de cette zone varie suivant le type de
l’objet.
Forme générale d’un algorithme
Algorithme <idf_algo>;
Constante
<déclaration des constantes>
TYPE
<déclaration des types>
Variable
<déclaration des variables>
Début
Action 1;
…..
Action n;
Fin. 4
La déclaration d’une variable revient à lui donner un
identifiant et un type. Sa forme générale :
idf : type;
Un type définit la taille de l’espace nécessaire à la sauvegarde
d’un objet. C’est l’ensemble de valeurs que peut prendre un
objet ainsi que les opérations permises sur cet objet.
Var Mémoire Centrale
n, age : entier; n prix
prix : réel;
nom :chaine[5]; @300 @304
nom
age
@360
@302
5
Var
n, age : entier;
Mémoire Centrale (MC)
prix : réel;
nom :chaine[5]; n age
@300 @302
lorsqu’on exécute un programme, la
machine accède à la (MC) en utilisant prix
les adresses et non pas les noms des
variables: @304
Lorsqu’on écrit : n n+1; nom
La machine utilise :
Contenu(@300) Contenu(@300) +1;
@308
En réalité la machine prend le
contenu (@300, @301) contenu (@300, @301) + 1
6
Var Mémoire Centrale (MC)
T :tableau [5] de entier; T
@300
Comment la machine accède à l’élément T[i] pour faire
une affectation : T[i] 100;
La machine calcul l’adresse du ième élément d’un tableau par :
@T[i]= @T[1] + (i-1)* Taille_du_type
@T[4]= @T[1] + 3* 2 (Taille_entier = 2)
@T[4]= @300 + 3* 2 = @306 (exp: @T[1] = 300)
Donc:
T[4] 100; est équivalent à contenu(@306, @307) 100; 7
Question :
Puisqu’il y a une correspondance entre les variables et les
adresses, peut-on utiliser directement les adresses ?
(MC)
Oui, oui, oui ….. n
Mettre le symbole @ devant le nom de la @300
variable pour désigner l’adresse de cette
variable. prix
Var @304
n : entier; (* @n désigne l’adresse de n : @300 *)
prix : réel; (* @prix désigne l’adresse de prix: @304*)
8
Var
n : entier; (* @n désigne l’adresse de n : @300 *)
prix : réel; (* @prix désigne l’adresse de prix: @304 *)
Note: (MC)
On peut utiliser cette affectation : n
p1 @n;
p2 @prix; @300
prix
Dans p1 on sauvegarde l’adresse de n et
dans p2 on sauvegarde l’adresse de prix
@304
p1 et p2 sont donc des variables et p1 @300
elles seront déclarées dans la partie @350
< VARIABLE> p2 @304
@380
Donc ces variables ont des adresses
9
Question : Quel est le type de p1 et p2 ?
--- les pointeurs ---
Définition : un pointeur est une variable qui contient l’adresse
d’un objet de type simple ou composé.
Remarque: un pointeur sur un type d’objet donné a pour
valeur l’ensemble des adresses de ce type.
Déclaration :
<Idf_Pointeur> : ^ <TypeVar>;
10
Déclaration :
<Idf_Pointeur> : ^ <TypeVar>;
(MC)
Exemple: pe1 pe2
Type
complexe : Enregistrement @300 @310
re: entier; p pcx
im: entier;
Feng;
@318 @322
Var
x y
pe1, pe2 : ^entier;
p : ^caractère;
@400 @402
pcx:^complexe;
c d
x, y : entier;
c: caractère;
@404 @405
d :complexe; 11
Var (MC)
pe1, pe2 : ^entier; pe1 pe2
p : ^caractère; @400
pcx:^complexe; @300 @310
x, y : entier; p pcx
c: caractère; @404 @405
d :complexe; @318 @322
x y
Début
pe1 @x; @400 @402
c d
p @c;
pcx @d; @404 @405
Fin;
12
(MC)
Remarque: pe1 pe2
Du moment que le pointeur contient @400
l’adresse de la variable ⇒ accéder au @300 @310
contenu de cette variable. p pcx
On utilise la syntaxe suivante: @404 @405
Idf_Pointeur^ @318 @322
x y
Lire (x); ≡ lire (pe1^);
Ecrire (x); ≡ Ecrire (pe1^);
@400 @402
c d
Lire (c); ≡ lire(p^);
Ecrire (c); ≡ Ecrire (p^);
@404 @405
Lire (d.re, d.im); ≡ lire (pcx^.re, pcx^.im);
Ecrire (d.re, d.im); ≡ Ecrire (pcx^.re, pcx^.im);
13
Opérations sur les pointeurs :
Affectation entre les pointeurs de même type
p1, p2: ^ entier; p1p1 p2
@300
@300
x : entier; @400
@400
@200
@200
y : réel; x y
@300 @500
p1 @x;
p2 p1; (* c’est équivalent à p2 @x *)
p2 @y; (* PAS POSSIBLE! INCOMPATIBILITE DE TYPE*)
14
Opérations sur les pointeurs :
Comparaison (=, ≠) entre les pointeurs de même type
p1, p2: ^ entier; p1
@300 p2
x, y : entier; @500
@400
@200
x
y
p1 @x; 1 1
@300
p2 @y; @500
la condition ci-dessous retourne faux
si (p2 = p1) alors écrire (‘’les 2 pointeurs pointent sur la même zone ‘’);
sinon écrire (‘’les 2 pointeurs ne pointent pas sur la même zone‘’);
Fsi;
ATTENTIENT : la condition ci-dessous retourne vrai
si (p2^ = p1^) alors écrire (‘’les 2 zones ont la même valeur ‘’);
sinon écrire (‘’les 2 zones n’ont pas la même valeur‘’);
Fsi; 15
Opérations sur les pointeurs :
p
@202
@200
incrémenter un pointeur @500
p: ^entier;
t : tableau[5] de entier; t
@200
p @t;
p p+1;
Remarque:
Le contenu du pointeur s’incrémente on ajoutant la taille du
type sur lequel il pointe.
Exemple :
En utilisant l’affectation pp+1 pour le type:
caractère : le contenu de p augmente de 1
entier : le contenu de p augmente de 2 (par exemple)
date de naissance : le contenu de p augmente de de 6 16
Question : qu’est ce qu’on a gagné avec ces pointeurs ?
Jusqu’à présent rien! Mais on prépare le terrain pour la suite
Une variable manipulée dans nos programmes :
Est créée dans la partie déclaration des variables
Sa taille est fixe: ne peut être changée au cours du
programme
La place occupée par cette variable sera récupérée à la fin
du programme
c’est ce qu’on appel une variable statique
Lorsqu’on déclare un pointeur p, son contenu est indéfini.
L’objet pointé par p, peut être crée durant l’exécution du
programme.
c’est ce qu’on appel une variable dynamique 17
Une variable dynamique est toujours manipulée par
l’intermédiaire d’un pointeur.
Elle est créée dynamiquement lors de l’exécution
Peut être détruite avant la fin du programme
Création et destruction des variables dynamiques:
Soit la définition suivante d’un pointeur :
<Idf_Pointeur> : ^ <TypeVar>;
Création :
Allouer (Idf_Pointeur);
(* cette action alloue un espace mémoire selon le type du pointeur *)
(* et affecte l’adresse de cet espace au pointeur *)
Destruction:
Libérer (Idf_Pointeur);
(* cette action libère l’espace occupé par la variable dynamique *)
(* la valeur du pointeur est indéfinie *) 18
Exemple : Partie de la MC
p
p : ^caractère; @318
@310 @311 @312 @313
Allouer(p);
@314 @315 @316 @317
Libérer(p);
@318 @319 @320 @321
@322 @323 @324 @325
Remarque :
Après qu’on a libéré p, le contenu de p est toujours à : @318.
Il est recommandé de mettre à jour le pointeur à une adresse
spéciale juste après l’utilisation de : libérer (p).
L’adresse spéciale Nil joue ce rôle : le pointeur ne contient l’adresse
d’aucun élément: p Nil; 19
Exemple : Partie de la MC
p
p : ^caractère; @318
@310 @311 @312 @313
Allouer(p);
@314 @315 @316 @317
Libérer(p);
@318 @319 @320 @321
@322 @323 @324 @325
Remarque :
L’adresse spéciale Nil est utilisée pour initialiser les pointeurs :
p nil;
L’adresse spéciale Nil est utilisée pour vérifier le retour de
allouer (p ):
Si p= nil alors problème d’allocation
Si p ≠ nil alors espace mémoire accordé 20
Attention :
R P
P, R : ^entier; @400 @318
@400
@380 @313
Allouer(P);
Allouer(R);
@400 @318
P R;
Cet espace mémoire ne peut être utilisé ni par l’utilisateur ni par
la machine.
La machine le récupère à la fin du programme.
21
Attention :
R P
P, R : ^entier; @400 @318
Nil
@380 @313
Allouer(P);
Allouer(R);
@400 @318
P nil;
Cet espace mémoire ne peut être utilisé ni par l’utilisateur ni par
la machine.
La machine le récupère à la fin du programme.
22
Attention :
P
P : ^entier; @380
x : entier; @313
x
P @x;
@380
Libérer (x);
On ne peut pas libérer une variable statique
23
Exercice :
On veut écrire un algorithme qui sauvegarde dans un tableau
N chaînes, puis les afficher en utilisant les deux concepts :
allocation statique et dynamique.
24
Algoritme Allocation statique
Var tab 1 2 ………………………………………………….30
tab: tableau[30][20] de caractère; A l g o
1
ch : chaîne[20];
2 a k r a m
i, N: entier; .
. a i t a m r a n e
Début .
Répéter lire (N); jusqu’à (N≤ 0 ou N > 30); ..
Pour (i 1 à N) .
.
Faire .
.
écrire (‘’ donner la ‘’, i, ‘’ième chaîne’’); .
Lire(ch); 30
tab[i] ch;
Fait;
Pour (i 1 à N)
Faire
ch tab[i];
écrire (‘’ la ‘’, i, ‘’ième chaîne est : ’’ ch);
Fait;
Fin; 25
Algoritme Allocation dynamique
Type
Pchaine: Enregistrement tab
c: chaine[20]; 1 A l g o
Feng; 2
a k r am
Var .
.
tab: tableau[30] de ^Pchaine; . a i t amr a n e
.
b : booléen; .
i, j : entier; .
.
Début .
.
Répéter lire (N); jusqu’à (N≤ 0 ou N > 30); .
.
i 1; b vrai; 30
Tant que (i ≤ N et b = vrai)
Faire
Allouer(tab[i]);
si (tab[i] ≠ Nil) alors écrire (‘’ donner la ‘’, i, ‘’ième chaîne’’);
Lire(tab[i]^.c); i i+1;
sinon b<- faux;
écrire (‘’ Problème d’allocation’’);
Fsi; 26
…..
……
…..
(* la suite de l’algorithme *)
Pour (j 1 à i-1)
Faire
écrire (‘’ la ‘’, j, ‘’ième chaîne est : ’’ tab[j]^.c);
Fait; tab
(* Libérer l’espace mémoire *) 1 nil
Pour (j 1 à i-1) 2 nil
Faire .
. nil
Libérer(tab[j]); .
.
tab[j] Nil; .
Fait; .
.
(* l’algorithme peut continuer après …. *) .
.
……… .
.
………. 30
………
Fin;
27
Fin
28
