Retour à l'index
Nous avons vu la notion de structures de données et nous avons étudié les structures de données dont la manipulation est prévue en tant que telle dans la plupart des langages de programmation. Nous avons fait, en particulier, la distinction entre les structures de données statiques et les structures de données dynamiques. De plus les seules structures de données dynamiques que nous ayons rencontrées jusqu'à maintenant sont les chiers, qui concernent la mémoire de masse.
Les autres structures de données dont on peut avoir besoin sont appelées structures de données abstraites. L'adjectif fait référence au fait qu'elles ne sont pas implémentées dans le langage de programmation : il faut d'abord constituer un cahier des charges précis sur leur manipulation puis ensuite les implémenter. L'étude des structures de données abstraites les plus courantes, parmi celles qui ont été dégagées au cours de l'histoire de la programmation, fait l'objet d'un cours à part entière, de taille analogue au cours d'initiation à la programmation. Nous renvoyons donc à un tel cours pour leur étude.
L'implémentation des structures de données dynamiques est facilitée par la gestion de la mémoire. Nous avons déjà fait remarquer à plusieurs reprises que le programmeur n'a pas à entrer dans les détails du matériel mais ne doit considérer que les besoins de la programmation. Un bon compromis, en ce qui concerne la programmation, entre les structures de données dynamiques toutes faites et la gestion directe de la mémoire (dépendant, en particulier, du matériel utilisé) est l'utilisation des pointeurs. Nous allons étudier cette notion de pointeur dans ce chapitre.
En fait les pointeurs sont déjà apparus plus tôt à propos du passage par adresse des arguments des fonctions. Ce dernier point est une spécificité du langage C.
L'inconvénient avec une structure de données statique telle qu'un tableau est qu'il faut prévoir une taille maximum dès le départ. Une exécution du programme occupera la même place mémoire quelle que soit la session de travail.
Le concept d'indexation indirecte permet une première amélioration.
Comme nous venons de le rappeler nous avons déjà rencontré les pointeurs, puisque nous illustrons ce cours d'initiation à la programmation par le langage C, à propos du passage des arguments par adresse. Nous rappelons cependant ici les notions essentielles les concernant. De plus nous abordons la notion d'appel de pointeur.
| Intérêt des pointeurs | |
| Principe | Nous avons vu, en ce qui concerne la désignation des entités, la notion de référence directe grâce à une variable. Ceci correspond en gros à une boîte noire dans laquelle on peut placer certaines entités, le type de la variable indiquant la taille des entités que l'on peut y placer. L'indexation indirecte repose sur le principe suivant. On utilise une nouvelle sorte de variables, dites variables pointeur. Le contenu d'une telle variable ne sera pas une entité du type voulu mais l'adresse de cette entité (dite entité pointée). L'intérêt de cette façon de faire est que le contenu d'une telle variable pointeur a une taille xe (celle d'une adresse), quel que soit le type de l'entité pointée (qui peut être de taille très grande). |
| Types pointeurs | A tout type correspond un type pointeur. L'intérêt d'un type pointeur est le suivant. Le contenu d'une variable d'un type pointeur est de taille xe, il suffirait donc a priori, d'un seul type pointeur. Cependant lorsqu'on réservera l'emplacement pour l'entité pointée, il faudra en connaître la taille, qui est indiquée par le type du type pointeur. |
| Déclaration d'une variable de type pointeur | Une variable de type pointeur, ou plus concisément un pointeur, se déclare comme n'importe quelle variable. |
| Accès au contenu pointé | La référence à une variable pointeur donnera l'adresse de l'entité voulue et non l'entité elle-même. Il faut donc un moyen pour désigner cette entité. Celui-ci dépend du langage considéré. Dans beaucoup de langages de programmation, l'adresse n'est pas accessible directement. Le langage C est, à cet égard, un langage à part. |
| Pointeur nul | On a quelquefois besoin d'une valeur spéciale de pointeur qui ne pointe sur rien : on l'appelle le pointeur nul. Il y a a priori une valeur nulle par type de pointeurs mais, dans la plupart des langages de programmation, tous ces pointeurs nuls portent le même nom. |
| Appel et libération des pointeurs | |
| Initialisation d'un pointeur | Une variable d'un type simple s'initialise directement, soit par lecture, soit par affectation. Il est dangereux d'attribuer directement une adresse à un pointeur, car celle-ci peut avoir été choisie par le système d'exploitation et le compilateur pour une autre variable ou, pire, pour une partie du programme. Cela peut cependant se faire dans certains langages orientés programmation système, tel que le langage C (pour pouvoir accéder aux cartes son ou graphique, par exemple). En général cependant, en ce qui concerne la programmation pure, l'initialisation d'un pointeur se fait par appel de pointeur : on indique que l'on veut une initialisation du pointeur ; une recherche est effectuée automatiquement par le système d'exploitation pour déterminer une région de la mémoire vive dans laquelle un certain nombre d'octets consécutifs ne sont pas réservés pour autre chose et correspondent à la taille du type de l'entité pointée ; l'adresse du premier octet est placée dans la variable pointeur ; le nombre adéquat d'octets (connu par le type du pointeur) est réservé par le système d'exploitation (qui ne pourront donc pas être utilisés par autre chose). |
| Libération des pointeurs | Une fois qu'on n'a plus besoin d'utiliser un pointeur initialisé par appel, il faut penser à libérer la place réservée, sinon on risque d'arriver très rapidement à une saturation de la mémoire vive pour rien (et de façon inexplicable à l'utilisateur). En effet, l'utilisation des pointeurs permet d'accéder à un nombre d'emplacements mémoire dépendant de la session d'utilisation du programme. Ceci permet d'accéder à beaucoup de mémoire. Mais la mémoire n'est pas inffinie. On risque de dépasser la capacité du matériel, surtout si on ne fait pas attention. Or certains emplacements peuvent être utiles temporairement, sans qu'on en ait besoin tout au long de la session. On aimerait donc pouvoir les réserver lorsqu'on en a besoin, et les laisser libres pour d'autres activités à d'autres moments. Une instruction spécifique permet la libération de l'emplacement pointé par un pointeur donné. On obtient ainsi une véritable gestion dynamique de la mémoire. |
| Type et variable pointeurs | |
| Type pointeur | A tout type 'T' (dit alors type de base, comme 'int') est associé un nouveau type dont les éléments sont des pointeurs sur des éléments du premier type. Pour désigner ce type il suffit de faire suivre le nom du type de base du symbole '*' pour obtenir T*. |
| Exemple | Le type pointeur sur les entiers sera int*. |
| Variable pointeur | Une variable pointeur se déclare comme toute autre variable. |
| Exemple | On a par exemple :
int* ptr;pour indiquer que ptr est une variable de type pointeur sur un entier. On remarquera la désignation traditionnelle ptr de la variable, évidemment pour PoinTeuR, ou plus exactement pour PoinTeR. |
| Déplacement de l'astérisque | En fait il est traditionnel d'écrire :
int *ptr;en déplaçant le symbole '*'. Cette façon de faire permet de faire des déclarations multiples telles que : int *ptr, n;indiquant que ptr est une variable de type pointeur sur un entier et n une variable de type entier. |
| Accès au contenu pointé | Pour accéder à l'entité pointée par un pointeur, on fait précéder le nom du pointeur par le symbole '*'. |
| Exemple | L'affectation :
*ptr = 5;permet d'initialiser l'entité pointée par la variable ptr. |
| Pointeur nul | Les pointeurs nuls sont tous notés NULL en langage C, quel que soit leur type. |
| Appel de pointeur | |
| Introduction | La fonction malloc (pour l'anglais memory allocation, c'est-à-dire allocation de mémoire) permet l'appel de pointeur. La déclaration de cette fonction se trouve dans le chier en-tête stdlib.h, non utilisé jusqu'à maintenant. |
| Syntaxe | La syntaxe de cette fonction est :
ptr = malloc(entier);où entier est une expression entière (positive) et ptr un pointeur. |
| Sémantique | La signification de cette instruction est la suivante : un bloc mémoire de entier octets disponibles (consécutifs) est réservé et son adresse (un pointeur) est renvoyée à ptr. Bien entendu cela se déroule correctement s'il reste suffisamment de place disponible en mémoire, sinon le pointeur null est retourné. |
| Libération des pointeurs | |
| Introduction | La libération d'un pointeur se fait en langage C grâce à la fonction free. La déclaration de cette fonction se trouve également dans le fichier en-tête stdlib.h. |
| Syntaxe | La syntaxe de cette fonction est :
free(ptr);où ptr est un pointeur. |
| Principe | |
| Le problème | On veut disposer en mémoire centrale d'un répertoire téléphonique. Chaque composant de ce répertoire comportera un nom et un numéro de téléphone. |
| Analyse du problème | Les structures de données à lesquelles on peut penser pour ce programme sont un type structuré avec les champs nom et telephone, et un tableau repertoire dont les éléments sont de ce type structuré. Il faut décider d'une dimension maximum pour ce tableau, par exemple 500. |
| Inconvénients | Cette façon de faire réserve beaucoup de place mémoire, ce qui risque de laisser peu de place pour faire autre chose. Ceci peut, par exemple, ralentir considérablement une impression dans le cas d'une utilisation de l'ordinateur en mode multitâche. |
| Utilisation d'un tableau de pointeurs | Une autre façon de faire, permettant d'économiser la mémoire non réellement nécessaire, est d'utiliser un tableau dont le type d'un élément est, non pas une structure, mais un type pointeur sur une telle structure. On ne fera pointer de façon effective que pour les emplacements nécessaires. |
| Un programme | Ceci nous conduit au programme suivant, pour l'initialisation de ce répertoire (en s'arrêtant sur un nom commençant par '#') puis pour l'affichage des données ainsi initialisées :
#include <stdio.h>
#include <stdlib.h>
struct DONNEE {
char nom[30];
char tel[20];
};
int main(void) {
struct DONNEE *repertoire[500], individu;
inti, j;
/* initialisation */
i = -1;
do
{
printf("\nNom : ");
scanf("%s", individu.nom);
if (individu.nom[0] != '#') {
printf("Telephone : ");
scanf("%s", individu.tel);
i++;
repertoire[i] = (struct DONNEE *) malloc(50);
*(repertoire[i]) = individu;
}
} while ((individu.nom[0] != '#') && (i < 500));
/* affichage */
for (j = 0; j <= i; j++) {
printf("%s : %s\n", repertoire[j]->nom, repertoire[j]->tel);
}
|
| Introduction | L'allocation de mémoire que nous avons réservée pour un individu dans le programme ci-dessus est de 50 octets puisque l'on sait qu'un caractère occupe un octet. Mais nous ne sommes pas toujours au fait des procédés de codage employés par tel ou tel compilateur, et donc de la taille associée à un type donné. La fonction sizeof (`taille de' en anglais) permet d'obtenir la place nécessaire. |
| Syntaxe | La syntaxe de cette fonction est :
entier = sizeof(variable);où variable est une variable (et non un type comme on pourrait s'y attendre) et entier une variable entière. |
| Sémantique | La variable entier contient alors le nombre d'octets nécessaire pour coder une entité du type celui de la variable variable. |
| Exemple d'utilisation | On peut reprendre le programme ci-dessus en changeant juste la ligne faisant intervenir la fonction malloc :
repertoire[i] = (struct DONNEE *) malloc(sizeof(individu)); |
Cours, éxercices ou graphismes libre de droit. Un mail est souhaitable | Webmestre : Aublet Bastien (bastien.aublet@hotmail.fr)