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

ortho
(ortho)
Pour la suite nous utiliserons une machine 8 bits, bien que les machines PC grand public ([[w:x86|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 octectoctet est codée sur un octectoctet, ce qui nous fait 256 cases numérotées de 0 à 255, 00 à FF en [[w:hexadécimal|hexadécimal]] (qu'on utilisera pour numéroter les cases mémoires)
 
[[Image:StructDonnees_Memoires_vierge.svg]]
 
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 dude P puisse y être stockées. Les cases ainsi réservées seront représentées sur fond gris.
 
=== Exemple ===
[[Image:StructDonnees_Memoires_inversion_calcul.svg]]
 
À 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èrederriè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 auriontaurions pu omettre 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écedemmentprécédemment. 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'''.
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]].
 
Il convient cependant de distinguer les pointeurs typés des pointeurs non-typés (également appellésappelés génériquegénériques). 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).
[[Image:StructDonnees_Memoires_pointeur_new.svg]]
 
Deux choses se sont porduitesproduites :
* De la mémoire a été réservée pour stocker une donnée de type T (la case pointée est grisée).
* La variable p contient l'adresse mémoire de cet espace réservé (représenté par une flèche).
[[Image:StructDonnees_Memoires_pointeur_assignation.svg]]
 
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àcela on utilise la procédure "réciproque" de <code>new</code> :
 
delete(p)
On remarquera qu'après un <code>delete</code> la donnée stockée ainsi que le pointeur restent en mémoire : la seule chose qui change est que l'espace en mémoire dynamique n'est plus réservé. La donnée pointée peut donc être écrasée. La valeur de p^ restera en mémoire tant que le système d'exploitation n'aura pas décidé d'attribuer cet espace. Remarquez que demander au processeur de supprimer les contenus qui ont été stockés serait une perte de temps puisque si cette partie de la mémoire venait à être utilisé, les données serait écrasées de toute façon.
 
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 <code>new</code> et <code>delete</code>. Stocker la valeur de t dans la mémoire dynamique n'a aucun interêtintérêt en soi puisque la valeur est déjà dans t. L'important est de comprendre comment (par <code>new</code> et <code>delete</code>) 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écedemmentprécédemment.
 
Algorithme Exemple