Scribd
Importer
145 vues26 pages

Concepts de Pointeurs et Listes Chaînées

Ce document décrit les concepts de base de l'allocation dynamique de mémoire en langage C++, notamment la création, la manipulation et la suppression de variables dynamiques à l'aide de pointeurs. Il explique également les listes chaînées comme structure de données permettant de stocker des éléments de taille variable en mémoire.

Transféré par

Olyvier Nzighou
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PPTX, PDF, TXT ou lisez en ligne sur Scribd
145 vues26 pages

Concepts de Pointeurs et Listes Chaînées

Ce document décrit les concepts de base de l'allocation dynamique de mémoire en langage C++, notamment la création, la manipulation et la suppression de variables dynamiques à l'aide de pointeurs. Il explique également les listes chaînées comme structure de données permettant de stocker des éléments de taille variable en mémoire.

Transféré par

Olyvier Nzighou
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PPTX, PDF, TXT ou lisez en ligne sur Scribd

Allocation dynamique

de la mémoire
Présenté par : Olyvier NZIGHOU
Ecole Polytechnique de Libreville
Utilisation des pointeurs
1. Passage de paramètres par adresse
En algorithmique :
var x : réel, pour signifier le passage par adresse.
Procédure Rectangle(long : réel, larg : réel, var périmètre : réel )
En langage C++ :
void Rectangle(float long, float larg, float * prerimetre)
Appel de la procédure : Rectangle(x , y , &z)

2. Allocation dynamique
1. Créer
2. Manipuler
3. Supprimer les variables dynamique
A. Notion de mémoire
 La mémoire centrale est divisée en plusieurs cases numérotées à
partir de 0,1,2, etc.
 Chaque case mémoire à une taille de 1 octet soit 8 bits
 Il y a des cases vides et des cases ayant déjà un certain contenu.

B. Relation entre variable et mémoire


 chaque variable occupe les cases mémoire qui lui sont dédiées.
 1 caractère occupe 1 octet en mémoire, 1 entier 4 octets, 1 réel 4
ou 8 octets selon la précision souhaitée.
B. Relation entre variable et mémoire
Variable
x : entier x
10
Début 100

x10

 x étant une variable de type entier, elle doit occuper 4 octets, dans
un espace contigüe de la mémoire.

 Supposons que le numéro de la première case occupée par x soit


100, x occupe donc les cases n°100, 101, 102, 103. on trouve x à
partir de l’adresse 100 de la mémoire.

 Adresse ? : l’adresse est le numéro du premier octet de la variable.


B. Relation entre variable et mémoire

Variable
T : tableau[5] entier va occuper 5x4 = 20 octets dans la mémoire.

 Supposons que le tableau T commence à partir de l’octet 200, on


peut déduire que l’adresse du tableau est l’adresse du premier octet
occupé par le tableau T c’est-à-dire 200.

 Une variable possède 4 caractéristiques : son nom, son type, sa


valeur et son adresse
C. Variable statique /dynamique

 Variable statique : déclarée dans la partie « variable », le système


lui réserve l’espace mémoire au moment de la compilation et reste
dans la mémoire jusqu’à la fin du programme dans lequel elle est
déclarée

 Variable dynamique : Créée ou supprimée à l’exécution à travers


les pointeurs et les primitives d’allocation et de libération d’espace
mémoire
D. Notion de pointeur
 Un pointeur est une variable qui contient l’adresse d’une autre
variable

Exemple :

Variable
x : entier
P : pointeur entier (P va contenir l’adresse d’un entier)

Déclaration
<NomPointeur> : pointeur <TypeVariable>
<NomPointeur> : ^<TypeVariable>

En langage C++
<TypeVariable> : * <Nompointeur>
D. Notion de pointeur
Exemple 1 :
P
P : pointeur entier
100
x : entier
Début x

x  10 10
PAdr(x) 100

 On dit que P pointe vers x, ou que x est pointé par P.


P contient l’adresse de x, alors il peut aller jusqu’à x, il peut travailler
sur x.
 Lorsqu’on dit que P pointe vers x, alors x et P^ sont équivalents.
P^ est le contenu de la variable pointée par P.
P
100

x = P^
P^5
5
100
D. Notion de pointeur
 Qu’est ce qu’on a pu faire avec le pointeur P ?

On a modifié la valeur de x en utilisant le pointeur P.

 Jusqu’à maintenant, la seule manière de modifier x était par


affectation ou lecture d’une autre valeur dans x.

Exemple :

x12
Lire(x)

 Ici, on a vu qu’on peut manipuler une variable x en utilisant un


pointeur à condition que ce pointeur contienne l’adresse de x.
D. Notion de pointeur
Exemple 2 :
Créer , Manipuler, Supprimer une variable dynamique
Type pEntier = pointeur entier (définition du type pEntier)
Variable
P : pEntier // P est une variable statique
Début
//1. Création de la variable dynamique
Allouer(P) // la primitive Allouer va faire deux choses :
Créer en mémoire une variable dynamique de type entier et
sauvegarder l’adresse de l’espace mémoire dans le pointeur P.
P
100

P^

100
D. Notion de pointeur
//2. manipulation de la variable dynamique
P
P^5 100

P^
5
100

//3. Suppression de la variable dynamique


Libérer(P) P
100
?
P^
5
100

La primitive Libérer(P) va supprimer la variable dynamique P^ et P


va pointé vers une valeur indéterminée.
D. Notion de pointeur
Exemple 3 : Variable dynamique de type tableau
Type Tab = tableau[100] de réel
pTab : pointeur Tab
Variable
P : pTab P
i : entier 200 P^

Début 200 1 2 3 … 100

Allouer(P)
//2. Création de la variable dynamique
Pour i 1 à 100 faire P
200
P^[i] i P^

1 2 2 … 99 100
Fin pour 200 1 2 3 … 100
D. Notion de pointeur
//3. Suppression de la variable dynamique
P
200
Libérer(P) P^
? 1 2 2 … 99 100
200 1 2 3 … 100

Exemple 4 : variable dynamique de type structure ou enregistrement


Type structure = Date
J, m, a : entier
Fin
pDate : pointeur Date

Variable
P : pDate
D. Notion de pointeur
Début
//1. Création de la variable dynamique
P
Allouer(P) 150
P^
j m a

150

//2. Manipulation de la variable dynamique


Aff_j(P,24) P^.j24P
Aff_m(P,2) P^.m2 150
P^
Aff_a(P,2021) P^.a2021
j m a
En langage C++ 24 2 2021
(*P).j24 Pj = 24
(*P).m2 Pm=2
150
(*P).j2021 Pa = 2021
Aff_Nom_champs(Nom_pointeur, valeur)
D. Notion de pointeur
Début
//3. Supprimer de la variable dynamique
Libérer(P)

P
150
?
P^
j m a
24 2 2021

150
E. Les listes
T 1 7 2 0
1 2 3 … N

1 7 2 0

 Dans le tableau, il n’ y a que les valeurs, alors que dans la liste


composée de structures, il y a pour chacune d’elles la valeur et
l’adresse de l’élément suivant.
 Supposons qu’on veut veuille sauvegarder en mémoire tous les
nombres premiers inférieurs ou égaux à n avec n strictement
positif.
 Est-ce que vous connaissez tous les nombres premiers qui sont
inférieurs ou égaux à n ?
E. Les listes
 Vous ne les connaissez pas car vous ne connaissez même pas la
valeur de n, parce que la valeur de n est donnée par l’utilisateur. Il
peut donner n=10, n=100, comme il peut donner n= 1 million, tout
dépend de ce qu’il va saisir au clavier.

 On ne sait donc pas le nombre d’éléments qu’on peut sauvegarder


en mémoire.

 L’utilisation d’un tableau nécessite que la taille de ce dernier soit


connue d’avance.

 En effet à chaque fois que je trouve un nombre premier, je le


stocke en mémoire
E. Les listes
 Prenons n=10
Pour i2 à n faire
2
si(Premier(i)) alors
Allouer(P) 3 5 7
P^i
fin si
Fin pour
 A chaque fois que je vais trouver un nombre premier, je vais
réserver un espace mémoire dédiée à un entier afin d’ y stocker la
valeur du nombre premier

 Supposons que vous voulons afficher les éléments… Existe-t-il un


moyen pour le faire ?
 La solution du tableau ne convient pas !
E. Les listes chaînées
L

100 2 200 3 250 5 300 5


100 200 250 300 NUL
L

La liste est constituée de structures à 2 champs :

 Un champ de type entier ou valeur (val)


 Un champ de type pointeur suivant (suiv) car contenant l’adresse
du suivant.

 La porte d’entrée de la liste est le pointeur L, il contient l’adresse


du premier élément de la liste.
E. Les listes chaînées

Lorsqu’on travaille sur les listes on doit maîtriser deux choses


principales :

 Les structures de données (structure de données utilisée dans la


liste, ensemble de maillons chaînés entre eux).

 Le modèle

Il existe deux formes d’implémentation des listes :


a) statique (vecteurs)
b) dynamique (listes linéaires chaînées)
E. Les listes chaînées
 Structure de données (SDD)
Type Maillon = structure
Val : <Type qlq>
Suiv : pointeur Maillon
Fin

Type pListe = pointeur Maillon

Variable
L, p, q : pListe

L Val Suiv
E. Les listes chaînées
 Le modèle de la liste
Ensemble des procédures et des fonctions permettant de manipuler la
liste :
Primitive En algorithmique En langage C++
Init Init(P) P = nullptr
Allouer Allouer(P) P = new <Type>
Libérer Libérer(P) delete P
Ecrire(Val(P)) cout<<(*P).Val ou PVal
Val Si Val(P) > 0 … if(PVal > 0)

Suiv Tant que (Suiv(P) <> Nil) while(Psuiv != nullptr)


Aff_Val(P,3) PVal = 3
Aff_Val Aff_Val(P,x) PVal = x
Aff_Val(P,Val(Q)) PVal = QVal
E. Les listes chaînées
P

Nom Age Moy

Nom(P) Moy(P)
Age(P)

Pour consulter le nom du champ de n’importe quel maillon :


Nom_champ(Nom_pointeur)
E. Les listes chaînées
Primitive En algorithmique En langage C++
Aff_Suiv (P,Nil) PSuiv = nullptr
Aff_Suiv Aff_Suiv (P,Q) PSuiv = Q
Aff_Suiv (P, Suiv(Q)) PSuiv = QSuiv

 Exercice d’application
S, Q, P : pListe
Allouer(S)
Aff_val(S,2)
QS …ligne 1

Allouer(P)
Aff_val(P,val(Q)-1)
Aff_suiv(S,P) … ligne 2
E. Les listes chaînées
Q suiv(S) …ligne 3

Aff_suiv(P,S) … ligne 4

Aff_suiv(S,Nil) … ligne 5

Aff_suiv(P,suiv(S)) … ligne 6

Q suiv(P) …ligne 7
Merci de votre attention

Questions ?

Vous aimerez peut-être aussi