« Structures de données/Pointeurs » : différence entre les versions

Un livre de Wikilivres.
Contenu supprimé Contenu ajouté
→‎Spécification des pointeurs génériques : pointeurs génériques, spécification, utilisation, les effets de bords
m réorganisation du plan
Ligne 35 : Ligne 35 :
Nous allons apprendre comment utiliser cette mémoire dynamique. Et ce, avec cet outil que sont les '''pointeurs'''.
Nous allons apprendre comment utiliser cette mémoire dynamique. Et ce, avec cet outil que sont les '''pointeurs'''.


== Approche ==
== Les pointeurs typés ==


Le pointeur est un nouveau [[Algorithmique impérative/Types expressions opérateurs|type]] au même titres que les entiers, les caractères, chaînes de caractères, booléens et autres abordés en [[algorithmique impérative]].
Le pointeur est un nouveau [[Algorithmique impérative/Types expressions opérateurs|type]] au même titres que les entiers, les caractères, chaînes de caractères, booléens et autres abordés en [[algorithmique impérative]].
Ligne 43 : Ligne 43 :
Un pointeur typé indique le type de la donnée qu'il pointe. Il y a donc des pointeurs vers des entiers, des pointeurs vers des caractères, etc. Il convient d'affecter à des variables de types pointeur vers T uniquement des expressions de types pointeur vers T (tout comme on doit assigner à une variable de type entier une expression entière).
Un pointeur typé indique le type de la donnée qu'il pointe. Il y a donc des pointeurs vers des entiers, des pointeurs vers des caractères, etc. Il convient d'affecter à des variables de types pointeur vers T uniquement des expressions de types pointeur vers T (tout comme on doit assigner à une variable de type entier une expression entière).


== Spécification des pointeurs typés ==
=== Spécification ===


On déclare un pointeur vers T (T : un type) comme suit :
On déclare un pointeur vers T (T : un type) comme suit :
Ligne 58 : Ligne 58 :
<code>Ecrire(identifiant_du_pointeur)</code> afficherait l'adresse mémoire ou est stockée la donné pointée (souvent en sous la forme hexadécimale) : dans notre cours ce n'est d'aucune utilité.
<code>Ecrire(identifiant_du_pointeur)</code> afficherait l'adresse mémoire ou est stockée la donné pointée (souvent en sous la forme hexadécimale) : dans notre cours ce n'est d'aucune utilité.


== Utilisation des pointeurs typés ==
=== Utilisation ===


Pour stocker des données dans notre mémoire dynamique, il faut réserver l'espace nécessaire.
Pour stocker des données dans notre mémoire dynamique, il faut réserver l'espace nécessaire.

Version du 2 décembre 2006 à 20:01

Retour sur la gestion des variables en mémoire

Pour aborder la notion de pointeur, il convient de revenir sur le notion de variable. Nous devons regarder de plus près ce qu'il se passe au niveau de la machine quand on déclare un variable ou qu'on l'assigne.

Faisons donc un retour sur l'architecture des ordinateurs. Les variables sont stockées dans une mémoire statique : on peut représenter cette mémoire par un tableau. Chaque ligne de ce tableau est une "case" mémoire c'est à dire une zone ou l'on peut stocker une donnée atomique (par exemple un entier). Dans la machine, toutes ces cases sont numérotées sur n bits (dépend de l'architecture de la machine en question). Ce numéro, attribué de façon unique à chaque case identifie la case : c'est l'adresse mémoire de la case.

Pour la suite nous utiliserons une machine 8 bits, bien que les machines PC grand public (x86) sont aujourd'hui (2006) des machines 32 bits, 64 bits pour les plus récentes.

Nous avons donc une mémoire dont l'adresse de chaque octect est codée sur un octect, ce qui nous fait 256 cases numérotées de 0 à 255, 00 à FF en hexadécimal (qu'on utilisera pour numéroter les cases mémoires)

schéma de la mémoire

Que se passe-t-il quand on exécute un programme P ? Et bien le système d'exploitation qui exécute P va allouer au programme autant de place que nécessaire dans cette mémoire statique pour que toutes les variables du lexique du P puisse y être stockées.

Exemple avec le programme suivant : il s'agit de l'algorithme inversion de deux variables étudié en algorithmique impérative) :

Algorithme inversion_calcul
Variables
  a : entier
  b : entier
...

Voici à quoi ressemble notre mémoire statique si notre machine code les entiers sur un octet (une case mémoire)

schéma de la mémoire avec deux cases a et b réservées

À chaque assignation d'une variable, on affecte le contenu de la case mémoire dont l'adresse est contenu dans la variable. L'identifiant de la variable est en fait une abstraction, derrrière l'identifiant d'une variable se cache l'adresse mémoire de son contenu.

La mémoire dynamique

En plus d'allouer à chaque programme une mémoire statique, le système d'exploitation alloue au programme P une mémoire dynamique. Dans notre exemple avec l'inversion de deux variables notre programme n'utilise que la mémoire statique. Nous avons donc omis de représenter sur nos schémas cette mémoire.

La mémoire dynamique a les même caractéristiques que le mémoire statique telle que décrite précedemment. Les cases sont numérotées (nous supposerons là encore sur 8 bits : de 00 à FF)

Nous allons apprendre comment utiliser cette mémoire dynamique. Et ce, avec cet outil que sont les pointeurs.

Les pointeurs typés

Le pointeur est un nouveau type au même titres que les entiers, les caractères, chaînes de caractères, booléens et autres abordés en algorithmique impérative.

Il convient cependant de distinguer les pointeurs typés des pointeurs non-typés (également appellés générique). Nous allons d'abord nous pencher sur les premiers et réserver les seconds pour plus tard.

Un pointeur typé indique le type de la donnée qu'il pointe. Il y a donc des pointeurs vers des entiers, des pointeurs vers des caractères, etc. Il convient d'affecter à des variables de types pointeur vers T uniquement des expressions de types pointeur vers T (tout comme on doit assigner à une variable de type entier une expression entière).

Spécification

On déclare un pointeur vers T (T : un type) comme suit :

Lexique
  identifiant_du_pointeur : ^T

On accède à la valeur pointée comme suit :

 identifiant_du_pointeur^

Cette expression est donc du type pointé : T

Ecrire(identifiant_du_pointeur) afficherait l'adresse mémoire ou est stockée la donné pointée (souvent en sous la forme hexadécimale) : dans notre cours ce n'est d'aucune utilité.

Utilisation

Pour stocker des données dans notre mémoire dynamique, il faut réserver l'espace nécessaire.

p est une variable de type pointeur (vers T, un type quelconque : entier...) :

Lexique
  t : T   (* une variable d'un type quelconque que l'on va stocker en mémoire dynamique *)
  p : ^T  (* un pointeur vers des données du type de t *)

On réserve l'espace nécessaire pour stocker une variable de type T en faisait appel à l'instruction :

new(p)

p contient alors l'adresse de l'espace qui nous pourront utilisé : on peut donc stocker le contenu de t en mémoire dynamique.

p^:=t

On peut libérer l'espace : c'est à dire indiquer au système d'exploitation que cette partie de la mémoire dynamique n'est plus utilisée et qu'il peut désormais en faire ce qu'il veut. Pour celà on utilise la procédure "réciproque" de new :

delete(p)

On remarquera qu'après un delete la donnée stockée reste en mémoire : seul le pointeur change de valeur (il se retrouve avec la valeur "pointeur vers vide"). La valeur de t restera en mémoire tant que le système d'exploitation n'aura pas décidé d'attribuer cet espace : cette valeur est néanmoins perdue, il n'y est plus possible d'y accéder puisque son adresse est perdue.

Remarque : l'utilité de ce qui est expliqué dans cette partie "utilisation" peut échappée au lecteur. En effet, cette partie sert seulement à donner les procédures new et delete. Stocker la valeur de t dans la mémoire dynamique n'a aucun interêt en soi puisque la valeur est déjà dans t. L'important est de comprendre comment (par new et delete) on peut stocker et lire des informations en mémoire dynamique.

Exemple avec des entiers

Remarque : encore une fois ce programme n'est d'aucune utilité. On pourrait en faire un équivalent sans utiliser de pointeurs. Le but est d'expliquer les mécanismes décrits précedemment.

Algorithme Exemple
Lexique
  a : entier
  b : entier
  p1 : ^entier
  p2 : ^entier
Début
  a:=1
  new(p1) (* on réserve de l'espace pour stocker un entier *)
  p1^:=a (* stocke 1 dans la zone mémoire pointée par p1 *)
  ecrire(p1^) (* affiche 1 *)
  a:=2
  ecrire(p1^) (* affiche 1 *)
  p2:=p1 (* p2 va pointer la zone mémoire pointée par p1 *)
  ecrire(p2^) (* affiche 1 *)
  p2^:=3 (* on place 2 dans la zone mémoire pointée par p2 *)
  ecrire(p1^) (* affiche 3 *)
  delete(p1) (* on libère la zone pointée par p1 et donc la zone pointée par p2 *)
  
  (* a se stade : plus aucune zone mémoire n'est réservée dans la mémoire dynamique *)
  
  new(p1)
  new(p2)
  p1^:=4
  p2^:=p1^+1
  ecrire(p2^) (* affiche 5 *)
  
  (* il est d'usage de libérer au maximum la mémoire dynamique : *)
  delete(p1)
  delete(p2)
Fin

Les pointeurs génériques

Un pointeur générique est un type de pointeur particulier puisqu'il ne donne pas d'information sur ce qu'il pointe. C'est simplement une adresse vers une zone mémoire.

Spécification des pointeurs génériques

Il suffit de déclarer un pointeur comme suit

Lexique
  identifiant_du_pointeur : pointeur

Utilisation des pointeurs génériques

Les pointeurs typés sont également des adresses mémoires donc on peut assigner les uns aux autres.

Lexique
  p : pointeur
  p_T : ^T

Ces opérations sont possibles :

p:=p_T
p_T:=t_T

Cependant, on ne peut utiliser les procédures new() et delete() en leur passant un pointeur générique en paramètre. En effet, le type de la donnée pointée étant inconnu le système d'exploitation de peut savoir combien d'espace réservé.

Exemple avec des entiers

Algorithme exemple
Lexique
  p : pointeur
  p_entier : ^entier
début
  new(p_entier)
  p_entier^:=1
  p:=p_entier
  p_entier:=p
  ecrire(p_entier^) (* affiche 1 *)
fin

Les effets de bord

Que se passe-t-il ?

Algorithme bogue
Lexique
  p : pointeur
  p_entier : ^entier
  p_carac : ^caractere
début
  new(p_entier)
  p_entier^:=2645
  p:=p_entier
  p_caractere:=p
  ecrire(p_carac^) (* ???? *)
fin