8.

Les Pointeurs
Les Pointeurs

Notion de pointeur
Intérêt des pointeurs en C
 La plupart des langages de programmation offrent la
possibilité d'accéder aux données dans la mémoire de
l'ordinateur à l'aide de pointeurs, c.-à-d. à l'aide de
variables auxquelles on peut attribuer les adresses
d'autres variables.
 En C, les pointeurs jouent un rôle primordial dans la
définition de fonctions:
 Comme le passage des paramètres en C se fait
toujours par la valeur, les pointeurs sont le seul
moyen de changer le contenu de variables déclarées
dans d'autres fonctions.
 De même le traitement de tableaux et de chaînes de
caractères dans des fonctions serait impossible sans
l'utilisation de pointeurs

3
Adressage de variables

 Une variable est caractérisée par:

 son adresse: c.à.d l’adresse mémoire à partir de
laquelle l’objet est stocké.
 sa valeur, c.à.d ce qui est stocké à cette adresse.
 Deux modes d’adressage:
 Adressage direct
 Adressage indirect

4
Adressage direct
 La valeur d'une variable se trouve à un endroit spécifique
dans la mémoire interne de l'ordinateur. Le nom de la
variable nous permet alors d'accéder directement à cette
valeur.
 Adressage direct: Accès au contenu d'une variable par
le nom de la variable.
 Exemple:

5
Adressage indirect
 On peut copirer l'adresse d’une variable dans une variable
spéciale P, appelée pointeur. Ensuite, on peut retrouver
l'information de la variable A en passant par le pointeur P.
 Adressage indirect: Accès au contenu d'une variable, en
passant par un pointeur qui contient l'adresse de la variable.
 Exemple: Soit A une variable contenant la valeur 10 et P un
pointeur qui contient l'adresse de A. En mémoire, A et P
peuvent se présenter comme suit:

6
Pointeur
 Un pointeur est une variable spéciale qui peut contenir
l'adresse d'une autre variable.
 En C, chaque pointeur est limité à un type de données. Il peut
contenir l'adresse d'une variable simple de ce type ou l'adresse
d'une composante d'un tableau de ce type.
 Si un pointeur P contient l'adresse d'une variable A, on dit que
'P pointe sur A'.
 Remarque : Les pointeurs et les noms de variables ont le même
rôle: Ils donnent accès à un emplacement dans la mémoire
interne de l'ordinateur. Il faut quand même bien faire la
différence:
 Un pointeur est une variable qui peut 'pointer' sur différentes
adresses.
 Le nom d'une variable reste toujours lié à la même adresse.

7
Déclaration d'un pointeur

<Type> *<NomPointeur>
déclare un pointeur <NomPointeur> qui peut recevoir des
adresses de variables du type <Type>
 Exemple:
Signifie que
int *PNUM; *PNUM est du type int
ou
PNUM est un pointeur sur int
ou
PNUM peut contenir l'adresse d'une
variable du type int

8
Les opérateurs de base(1)

 Lors du travail avec des pointeurs, nous avons besoin:

 d'un opérateur 'adresse de': & pour obtenir l'adresse d'une
variable. &<NomVariable> fournit l'adresse de la variable
<NomVariable>

 d'un opérateur 'contenu de': * pour accéder au contenu d'une

adresse. *<NomPointeur> désigne le contenu de l'adresse
référencée par le pointeur <NomPointeur>

 d'une syntaxe de déclaration pour pouvoir déclarer un pointeur.

9
Les opérateurs de base(2)

 Exemple: Soit A une variable contenant

la valeur 10, B une variable contenant la
valeur 50 et P un pointeur non initialisé:

 Après les instructions,

P = &A;
B = *P;
*P = 20;
 P pointe sur A,
 le contenu de A (référencé par *P) est
affecté à B, et
 le contenu de A (référencé par *P) est
mis à 20.

10
Les opérateurs de base(3)
Le programme complet effectuant les transformations de l'exemple ci-dessus
peut se présenter comme suit:
main() Ou bien main()
{ {
/* déclarations */ /* déclarations */
short A = 10; short A, B, *P;
short B = 50; /* traitement */
short *P; A = 10;
/* traitement */ B = 50;
P = &A; P = &A;
B = *P; B = *P;
*P = 20; *P = 20;
return 0; return 0;
} }

11
Les opérations élémentaires sur un pointeur(1)
Priorité de * et &
 Les opérateurs * et & ont la même priorité
que les autres opérateurs unaires (la
négation !, l'incrémentation ++, la
décrémentation --). Dans une même
expression, les opérateurs unaires *, &, !,
++, -- sont évalués de droite à gauche.
 Si un pointeur P pointe sur une variable X,
alors *P peut être utilisé partout où on peut
écrire X.
12
Les opérations élémentaires sur un pointeur(2)

Exemple
Après l'instruction P = &X; les expressions suivantes, sont
équivalentes:

Y = *P+1 Y = X+1
*P = *P+10 X = X+10
*P += 2 X += 2
++*P ++X
(*P)++ X++

les parenthèses sont nécessaires

13
Les opérations élémentaires sur un pointeur(3)

Le pointeur NUL
 Seule exception: La valeur numérique 0 (zéro) est utilisée pour
indiquer qu'un pointeur ne pointe 'nulle part'.

int *P;
P = 0;
 Finalement, les pointeurs sont aussi des variables et peuvent être
utilisés comme telles. Soit P1 et P2 deux pointeurs sur int, alors
l'affectation
P1 = P2;
copie le contenu de P2 vers P1. P1 pointe alors sur le même objet
que P2.

14
Les opérations élémentaires sur un pointeur(4)

Résumé:
 Après les instructions:
int A;
int *P;
P = &A;
A désigne le contenu de A et &A désigne l'adresse de A
P désigne l'adresse de A et *P désigne le contenu de A

 En outre:
&P désigne l'adresse du pointeur P
*A est illégal (puisque A n'est pas un pointeur)

15
Les Pointeurs

Pointeurs et tableaux
Adressage des composantes d'un tableau(1)

 Le nom d'un tableau représente l'adresse de son

premier élément. En d'autre termes:
&tableau[0] et tableau
sont une seule et même adresse.
 En simplifiant, nous pouvons retenir que le nom d'un
tableau est un pointeur constant sur le premier
élément du tableau.
 Exemple: En déclarant un tableau A de type int et un
pointeur P sur int, int A[10];
int *P;
l'instruction: P = A; est équivalente à P = &A[0];

17
Adressage des composantes d'un tableau(2)

 Si P pointe sur une composante quelconque d'un tableau, alors

P+1 pointe sur la composante suivante et:
P+i pointe sur la i-ième composante derrière P et
P-i pointe sur la i-ième composante devant P.

 Ainsi, après l'instruction, P = A; le pointeur P pointe sur A[0], et

*(P+1) désigne le contenu de A[1]
*(P+2) désigne le contenu de A[2]
...
...
*(P+i) désigne le contenu de A[i]

18
Adressage des composantes d'un tableau(3)

 Exemple
Soit A un tableau contenant des éléments de type
float et P un pointeur sur float:
float A[20], X;
float *P;
Après les instructions,
P = A;
X = *(P+9);
X contient la valeur du 10-ième élément de A, (c.-à-d.
celle de A[9]). Une donnée du type float ayant besoin
de 4 octets, le compilateur obtient l'adresse P+9 en
ajoutant 9 * 4 = 36 octets à l'adresse dans P.

19
Adressage des composantes d'un tableau(4)

Différence essentielle entre un pointeur et le nom d'un tableau:

 Un pointeur est une variable,
donc des opérations comme P = A ou P++ sont permises.
Le nom d'un tableau est une constante,
donc des opérations comme A = P ou A++ sont impossibles.

 Lors de la première phase de la compilation, toutes les expressions de la

forme A[i] sont traduites en *(A+i). En multipliant l'indice i par la grandeur
d'une composante, on obtient un indice en octets:
<indice en octets> = <indice élément> * <grandeur élément>
Cet indice est ajouté à l'adresse du premier élément du tableau pour obtenir
l'adresse de la composante i du tableau. Pour le calcul d'une adresse
donnée par une adresse plus un indice en octets, on utilise un mode
d'adressage spécial connu sous le nom 'adressage indexé':
<adresse indexée> = <adresse> + <indice en octets>

20
Adressage des composantes d'un tableau(5)

Formalisme tableau et formalisme pointeur

• Exemple: Les deux programmes suivants copient les éléments positifs d'un
tableau T dans un deuxième tableau POS.
Formalisme tableau Formalisme pointeur
main() main()
{ {
int T[10] = {-3, 4, 0, -7, 3, 8, 0, -1, 4, -9}; int T[10] = {-3, 4, 0, -7, 3, 8, 0, -1, 4, -9};
int POS[10]; int POS[10];
int I,J; int I,J;
for (J=0,I=0 ; I<10 ; I++) for (J=0,I=0 ; I<10 ; I++)
if (T[I]>0) { if (*(T+I)>0) {
POS[J] = T[I]; *(POS+J) = *(T+I);
J++; J++;
} }
return 0; return 0;
} }

21
Résumons
 Les variables et leur utilisation int A; déclare une variable
simple du type int
A désigne le contenu de A
&A désigne l'adresse de A

int B[]; déclare un tableau d'éléments de type int

B désigne l'adresse de la première composante de B.
(Cette adresse est toujours constante)

B[i] désigne le contenu de la composante i du tableau

&B[i] désigne l'adresse de la composante i du tableau
en utilisant le formalisme pointeur:

B+i désigne l'adresse de la composante i du tableau

*(B+i) désigne le contenu de la composante i du tableau

22
Résumons

int *P;
déclare un pointeur sur des éléments du type int.
P peut pointer sur des variables simples du type int ou sur les
composantes d'un tableau du type int.
P désigne l'adresse contenue dans P
(Cette adresse est variable)

*P désigne le contenu de l'adresse dans P

Si P pointe dans un tableau, alors

P désigne l'adresse de la première composante

P+i désigne l'adresse de la i-ième composante derrière P
*(P+i) désigne le contenu de la i-ième composante derrière P

23
Les Pointeurs

Arithmétique des pointeurs

Arithmétique des pointeurs(1)

 Affectation par un pointeur sur le même type

Soient P1 et P2 deux pointeurs sur le même type de
données, alors l'instruction
P1 = P2;
fait pointer P1 sur le même objet que P2

 Addition et soustraction d'un nombre entier

Si P pointe sur l'élément A[i] d'un tableau, alors
P+n pointe sur A[i+n]
P-n pointe sur A[i-n]

25
Arithmétique des pointeurs(2)

 Incrémentation et décrémentation d'un pointeur

Si P pointe sur l'élément A[i] d'un tableau, alors après
l'instruction

P++; P pointe sur A[i+1]

P+=n; P pointe sur A[i+n]
P--; P pointe sur A[i-1]
P-=n; P pointe sur A[i-n]

26
Arithmétique des pointeurs(3)

 Domaine des opérations

 L'addition, la soustraction, l'incrémentation et la décrémentation sur les
pointeurs sont seulement définies à l'intérieur d'un tableau. Si l'adresse
formée par le pointeur et l'indice sort du domaine du tableau, alors le résultat
n'est pas défini.
 Seule exception: Il est permis de 'pointer' sur le premier octet derrière un tableau
(à condition que cet octet se trouve dans le même segment de mémoire que le
tableau). Cette règle, introduite avec le standard ANSI-C, légalise la définition de
boucles qui incrémentent le pointeur avant l'évaluation de la condition d'arrêt.
 Exemples:
int A[10];
int *P;
P = A+9; /* dernier élément -> légal */
P = A+10; /* dernier élément + 1 -> légal */
P = A+11; /* dernier élément + 2 -> illégal */
P = A-1; /* premier élément - 1 -> illégal */

27
Arithmétique des pointeurs(4)

 Soustraction de deux pointeurs

Soient P1 et P2 deux pointeurs qui pointent dans le même tableau:
P1-P2
fournit le nombre de composantes comprises entre P1 et P2.
Le résultat de la soustraction P1-P2 est

- négatif, si P1 précède P2
- zéro, si P1 = P2
- positif, si P2 precède P1
- indéfini, si P1 et P2 ne pointent pas dans le même tableau

Plus généralement, la soustraction de deux pointeurs qui pointent

dans le même tableau est équivalente à la soustraction des
indices correspondants.

28
Arithmétique des pointeurs(5)

 Comparaison de deux pointeurs

On peut comparer deux pointeurs par
<, >, <=, >=, ==, !=.
La comparaison de deux pointeurs qui pointent dans le
même tableau est équivalente à la comparaison des
indices correspondants. (Si les pointeurs ne pointent pas
dans le même tableau, alors le résultat est donné par
leurs positions relatives dans la mémoire).

29
Les Pointeurs

Pointeurs et chaînes de caractères

Pointeurs sur char et chaînes de caractères constantes(1)

De la même façon qu'un pointeur sur int peut contenir l'adresse d'un nombre isolé ou
d'une composante d'un tableau, un pointeur sur char peut pointer sur un caractère
isolé ou sur les éléments d'un tableau de caractères. Un pointeur sur char peut en
plus contenir l'adresse d'une chaîne de caractères constante et il peut même être
initialisé avec une telle adresse.
 Affectation
On peut attribuer l'adresse d'une chaîne de caractères constante à un pointeur sur
char:
Exemple
char *C;
C = "Ceci est une chaîne de caractères constante";

 Nous pouvons lire cette chaîne constante (p.ex: pour l'afficher), mais il n'est pas
recommandé de la modifier, parce que le résultat d'un programme qui essaie de
modifier une chaîne de caractères constante n'est pas prévisible en ANSI-C.

31
Pointeurs sur char et chaînes de caractères constantes(2)

 Initialisation
Un pointeur sur char peut être initialisé lors de la déclaration si on lui affecte l'adresse
d'une chaîne de caractères constante:
char *B = "Bonjour !";
Remarque:
 Il existe une différence importante entre les deux déclarations:
char A[] = "Bonjour !"; /* un tableau */
char *B = "Bonjour !"; /* un pointeur */
 A est un tableau qui a exactement la grandeur pour contenir la chaîne de
caractères et la terminaison '\0'. Les caractères de la chaîne peuvent être
changés, mais le nom A va toujours pointer sur la même adresse en
mémoire.
 B est un pointeur qui est initialisé de façon à ce qu'il pointe sur une chaîne
de caractères constante stockée quelque part en mémoire. Le pointeur peut
être modifié et pointer sur autre chose. La chaîne constante peut être lue,
copiée ou affichée, mais pas modifiée

32
Pointeurs sur char et chaînes de caractères constantes(3)

 Modification
Si nous affectons une nouvelle valeur à un pointeur sur une chaîne
de caractères constante, nous risquons de perdre la chaîne
constante. D'autre part, un pointeur sur char a l'avantage de pouvoir
pointer sur des chaînes de n'importe quelle longueur:
Exemple
char *A = "Petite chaîne";
char *B = "Deuxième chaîne un peu plus longue";
A = B;
Maintenant A et B pointent sur la même chaîne; la "Petite chaîne" est
perdue:

33
Pointeurs sur char et chaînes de caractères constantes(4)

 Remarque:
Les affectations discutées ci-dessus ne peuvent pas être effectuées avec des tableaux de
caractères:
Exemple
char A[45] = "Petite chaîne";
char B[45] = "Deuxième chaîne un peu plus longue";
char C[30];
A = B; /* IMPOSSIBLE -> ERREUR !!! */
C = "Bonjour !"; /* IMPOSSIBLE -> ERREUR !!! */

 Dans cet exemple, nous essayons de copier l'adresse de B dans A, respectivement l'adresse de la
chaîne constante dans C. Ces opérations sont impossibles et illégales parce que l'adresse
représentée par le nom d'un tableau reste toujours constante.
 Pour changer le contenu d'un tableau, nous devons changer les composantes du tableau l'une
après l'autre (p.ex. dans une boucle) ou déléguer cette charge à une fonction de <stdio> ou
<string>.

34
Pointeurs sur char et chaînes de caractères constantes(5)

 Conclusions:
 Utilisons des tableaux de caractères pour déclarer
les chaînes de caractères que nous voulons
modifier.
 Utilisons des pointeurs sur char pour manipuler
des chaînes de caractères constantes (dont le
contenu ne change pas).
 Utilisons de préférence des pointeurs pour
effectuer les manipulations à l'intérieur des
tableaux de caractères.

35
Les Pointeurs
Pointeurs et tableaux à
deux dimensions
Pointeurs et tableaux à deux dimensions(1)

 L'arithmétique des pointeurs se laisse élargir avec toutes ses

conséquences sur les tableaux à deux dimensions.
 Exemple
Le tableau M à deux dimensions est défini comme suit:
int M[4][10] = {{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
{10,11,12,13,14,15,16,17,18,19},
{20,21,22,23,24,25,26,27,28,29},
{30,31,32,33,34,35,36,37,38,39}};
Le nom du tableau M représente l'adresse du premier élément du
tableau et pointe sur le tableau M[0] qui a la valeur:
{0,1,2,3,4,5,6,7,8,9}.
L'expression (M+1) est l'adresse du deuxième élément du tableau
et pointe sur M[1] qui a la valeur: {10,11,12,13,14,15,16,17,18,19}.

37
Pointeurs et tableaux à deux dimensions(2)

 Problème
Comment pouvons-nous accéder à l'aide de pointeurs aux éléments de
chaque composante du tableau, c.à-d.: aux éléments M[0][0], M[0][1], ... ,
M[3][9] ?
 Discussion
Une solution consiste à convertir la valeur de M (qui est un pointeur sur un
tableau du type int) en un pointeur sur int. Par exemple:
int M[4][10] = {{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
{10,11,12,13,14,15,16,17,18,19},
{20,21,22,23,24,25,26,27,28,29},
{30,31,32,33,34,35,36,37,38,39}};
int *P;
P = M; /* conversion automatique */
Cette dernière affectation entraîne une conversion automatique de l'adresse
&M[0] dans l'adresse &M[0][0]. (Remarquez bien que l'adresse transmise reste
la même, seule la nature du pointeur a changé).

38
Pointeurs et tableaux à deux dimensions(3)

 Cette solution n'est pas satisfaisante à cent pour-cent: Généralement, on

gagne en lisibilité en explicitant la conversion mise en oeuvre par
l'opérateur de conversion forcée ("cast"), qui évite en plus des messages
d'avertissement de la part du compilateur.
 Solution
Voici finalement la version que nous utiliserons:
int M[4][10] = {{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
{10,11,12,13,14,15,16,17,18,19},
{20,21,22,23,24,25,26,27,28,29},
{30,31,32,33,34,35,36,37,38,39}};
int *P;
P = (int *)M; /* conversion forcée */

Dû à la mémorisation ligne par ligne des tableaux à deux dimensions, il

nous est maintenant possible traiter M à l'aide du pointeur P comme un
tableau unidimensionnel de dimension 4*10.

39
Pointeurs et tableaux à deux dimensions(4)

 Exemple
Les instructions suivantes calculent la somme de tous les éléments du tableau M:
int M[4][10] = {{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
{10,11,12,13,14,15,16,17,18,19},
{20,21,22,23,24,25,26,27,28,29},
{30,31,32,33,34,35,36,37,38,39}};
int *P;
int I, SOM;
P = (int*)M;
SOM = 0;
for (I=0; I<40; I++)
SOM += *(P+I);

 Remarque:
Lors de l'interprétation d'un tableau à deux dimensions comme tableau
unidimensionnel il faut calculer avec le nombre de colonnes indiqué dans la
déclaration du tableau.

40
Les Pointeurs

Tableaux de pointeurs
Tableaux de pointeurs(1)
 Si nous avons besoin d'un ensemble de pointeurs du même type, nous pouvons les
réunir dans un tableau de pointeurs.
 Déclaration d'un tableau de pointeurs
<Type> *<NomTableau>[<N>]
déclare un tableau <NomTableau> de <N> pointeurs sur des données du type
<Type>.
Exemple
double *A[10];
déclare un tableau de 10 pointeurs sur des rationnels du type double dont les
adresses et les valeurs ne sont pas encore définies.
 Remarque
Le plus souvent, les tableaux de pointeurs sont utilisés pour mémoriser de façon
économique des chaînes de caractères de différentes longueurs. Dans la suite, nous
allons surtout considérer les tableaux de pointeurs sur des chaînes de caractères.
 Initialisation
Nous pouvons initialiser les pointeurs d'un tableau sur char par les adresses de
chaînes de caractères constantes.

42
Tableaux de pointeurs(2)
 Exemple
char *JOUR[] = {"dimanche", "lundi", "mardi", "mercredi", "jeudi",
"vendredi", "samedi"};
déclare un tableau JOUR[] de 7 pointeurs sur char. Chacun des pointeurs
est initialisé avec l'adresse de l'une des 7 chaînes de caractères.

43
Tableaux de pointeurs(3)
 On peut afficher les 7 chaînes de caractères en fournissant les adresses
contenues dans le tableau JOUR à printf :
int I;
for (I=0; I<7; I++)
printf("%s\n", JOUR[I]);

Comme JOUR[I] est un pointeur sur char, on peut afficher les premières
lettres des jours de la semaine en utilisant l'opérateur 'contenu de' :
int I;
for (I=0; I<7; I++)
printf("%c\n", *JOUR[I]);

L'expression JOUR[I]+J désigne la J-ième lettre de la I-ième chaîne. On peut

afficher la troisième lettre de chaque jour de la semaine par:
int I;
for (I=0; i<7; I++)
printf("%c\n",*(JOUR[I]+2));

44
Tableaux de pointeurs(4)
int *D[]; déclare un tableau de pointeurs sur des éléments du type int

D[i] peut pointer sur des variables simples ou

sur les composantes d'un tableau.

D[i] désigne l'adresse contenue dans l'élément i de D

(Les adresses dans D[i] sont variables)

*D[i] désigne le contenu de l'adresse dans D[i]

Si D[i] pointe dans un tableau,

D[i] désigne l'adresse de la première composante
D[i]+j désigne l'adresse de la j-ième composante
*(D[i]+j) désigne le contenu de la j-ième composante

45
Les Pointeurs
Allocation dynamique
de mémoire
Déclaration statique de données(1)

 Chaque variable dans un programme a besoin d'un certain nombre

d'octets en mémoautomatiquement ire. Jusqu'ici, la réservation de la
mémoire s'est déroulée par l'emploi des déclarations des données.
Dans tous ces cas, le nombre d'octets à réserver était déjà connu
pendant la compilation. Nous parlons alors de la déclaration
statique des variables.
 Exemples
float A, B, C; /* réservation de 12 octets */
short D[10][20]; /* réservation de 400 octets */
char E[] = {"Bonjour !"}; /* réservation de 10 octets */
char F[][10] = {"un", "deux", "trois", "quatre"}; /* réservation de
40 octets */

47
Déclaration statique de données(2)

 Pointeurs
Le nombre d'octets à réserver pour un pointeur dépend
de la machine et du 'modèle' de mémoire choisi, mais il
est déjà connu lors de la compilation. Un pointeur est
donc aussi déclaré statiquement. Supposons dans la
suite qu'un pointeur ait besoin de p octets en mémoire.
(En DOS: p =2 ou p = 4)
 Exemples
double *G; /* réservation de p octets */
char *H; /* réservation de p octets */
float *I[10]; /* réservation de 10*p octets */

48
Allocation dynamique

 Problème
Souvent, nous devons travailler avec des données dont nous ne pouvons pas prévoir
le nombre et la grandeur lors de la programmation. Ce serait alors un gaspillage de
réserver toujours l'espace maximal prévisible. Il nous faut donc un moyen de gérer la
mémoire lors de l'exécution du programme.
 Exemple
Nous voulons lire 10 phrases au clavier et mémoriser les phrases en utilisant un
tableau de pointeurs sur char. Nous déclarons ce tableau de pointeurs par:
char *TEXTE[10];
Pour les 10 pointeurs, nous avons besoin de 10*p octets. Ce nombre est connu dès le
départ et les octets sont réservés automatiquement. Il nous est cependant impossible
de prévoir à l'avance le nombre d'octets à réserver pour les phrases elles-mêmes qui
seront introduites lors de l'exécution du programme ...
 Allocation dynamique
La réservation de la mémoire pour les 10 phrases peut donc seulement se faire
pendant l'exécution du programme. Nous parlons dans ce cas de l'allocation
dynamique de la mémoire.

49
La fonction malloc

 La fonction malloc de la bibliothèque <stdlib> nous aide à localiser et à réserver de la

mémoire au cours d'un programme.
 syntaxe
malloc( <N> )
fournit l'adresse d'un bloc en mémoire de <N> octets libres ou la valeur zéro s'il
n'y a pas assez de mémoire.
 Remarque:
Sur notre système, le paramètre <N> est du type unsigned int. A l'aide de malloc,
nous ne pouvons donc pas réserver plus de 65535 octets à la fois!
 Exemple: Supposons que nous avons besoin d'un bloc en mémoire pour un texte de
4000 caractères. Nous disposons d'un pointeur T sur char (char *T). Alors
l'instruction:
T = malloc(4000);
fournit l'adresse d'un bloc de 4000 octets libres et l'affecte à T.
S'il n'y a plus assez de mémoire, T obtient la valeur zéro.
 Si nous voulons réserver de la mémoire pour des données d'un type dont la grandeur
varie d'une machine à l'autre, nous avons besoin de la grandeur effective d'une
donnée de ce type. L'opérateur sizeof nous aide alors à préserver la portabilité du
programme.

50
L'opérateur unaire sizeof(1)

sizeof <var> fournit la grandeur de la variable <var>

sizeof <const> fournit la grandeur de la constante <const>
sizeof (<type>) fournit la grandeur pour un objet du type <type>
 Exemple
Après la déclaration,
short A[10];
char B[5][10];
nous obtenons les résultats suivants sur un IBM-PC (ou compatible):

sizeof A s'évalue à 20
sizeof B s'évalue à 50
sizeof 4.25 s'évalue à 8
sizeof "Bonjour !" s'évalue à 10
sizeof(float) s'évalue à 4
sizeof(double) s'évalue à 8

51
L'opérateur unaire sizeof(2)

 Exemple
Nous voulons réserver de la mémoire pour X valeurs du type int; la
valeur de X est lue au clavier:
int X;
int *PNum;
printf("Introduire le nombre de valeurs :");
scanf("%d", &X);
PNum = malloc(X*sizeof(int));

 exit
S'il n'y a pas assez de mémoire pour effectuer une action avec
succès, il est conseillé d'interrompre l'exécution du programme à
l'aide de la commande exit (de <stdlib>) et de renvoyer une valeur
différente de zéro comme code d'erreur du programme.

52
Exemple(1)
 Le programme suivant lit 10 phrases au clavier, recherche des blocs
de mémoire libres assez grands pour la mémorisation et passe les
adresses aux composantes du tableau TEXTE[]. S'il n'y a pas assez
de mémoire pour une chaîne, le programme affiche un message
d'erreur et interrompt le programme avec le code d'erreur -1.
 Nous devons utiliser une variable d'aide INTRO comme zone
intermédiaire (non dynamique). Pour cette raison, la longueur
maximale d'une phrase est fixée à 500 caractères.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
main() {
/* Déclarations */
char INTRO[500];
char *TEXTE[10];
int I;

53
Exemple(2)

/* Traitement */
for (I=0; I<10; I++) {
gets(INTRO);
/* Réservation de la mémoire */
TEXTE[I] = malloc(strlen(INTRO)+1);
/* S'il y a assez de mémoire, ... */
if (TEXTE[I]) /* copier la phrase à l'adresse fournie par malloc, ... */
strcpy(TEXTE[I], INTRO);
else { /* sinon quitter le programme après un message d'erreur. */
printf("ERREUR: Pas assez de mémoire \n");
exit(-1);
}
}
return 0; }

54
Remarques(1)

 Dans le programme :
#include <stdio.h>
main()
{
int i ;
int *p ;
p=&i ;
}
i et *p sont identiques et on n’a pas besoin d’allocation
dynamique puisque l’espace mémoire à l’adresse &i est
déjà réservé pour un entier.

55
Remarques(2)

 La fonction calloc de la librairie stdlib.h a le même rôle que la

fonction malloc mais elle initialise en plus l’objet pointé *p à 0. Sa
syntaxe est la suivante :
calloc( nb_objets, taille_objet_octets)
 Exemple :
Int n=10;
Int *p ;
p= (int*) calloc (n, sizeof(int)); /* tableau de n entiers*/
 Est équivalent à:
Int n=10;
Int *p ;
p= (int*) malloc (n * sizeof(int)); /* tableau de n entiers*/
For (i=0; i<n; i++)
*(p+i)=0;

56
La fonction free

 Si nous n'avons plus besoin d'un bloc de mémoire que nous avons
réservé à l'aide de malloc, alors nous pouvons le libérer à l'aide de
la fonction free de la bibliothèque <stdlib>.
free( <Pointeur> )
libère le bloc de mémoire désigné par le <Pointeur>; n'a pas d'effet si
le pointeur a la valeur zéro.
 Remarque:
 La fonction free peut aboutir à un désastre si on essaie de libérer de la
mémoire qui n'a pas été allouée par malloc.
 La fonction free ne change pas le contenu du pointeur; il est conseillé
d'affecter la valeur zéro au pointeur immédiatement après avoir libéré le
bloc de mémoire qui y était attaché.
 Si nous ne libérons pas explicitement la mémoire à l'aide de free, alors
elle est libérée automatiquement à la fin du programme.

57
Les Pointeurs

Pointeurs et structures
Pointeur et structures
 Pointeur et structures:
Supposons que l'on ait défini la struct personne à l'aide de la déclaration :
struct personne
{
char nom[20] ;
unsigned int age ;
};
On déclare une variable de type pointeur vers une telle structure de la manière
suivante :
struct personne *p ;
On peut alors affecter à p des adresses de struct personne. Exemple :
struct personne pers; /* pers est une variable de type struct personne */
struct personne *p; /* p est un pointeur vers une struct personne */
p = &pers;
(*p).age=20 ; /* parenthèses obligatoires OU */
p -> age=22 ; /* -> opérateur d’accès */

59
Listes chaînées
Une des utilisations fréquentes des structures, est de créer des
listes de structures chaînées. Pour cela, il faut que chaque
structure contienne un membre qui soit de type pointeur vers une
structure du même type. Cela se fait de la façon suivante :
struct personne
{
char nom[20] ;
unsigned int age ;
struct personne *suivant ;
};
Le membre de nom suivant est déclaré comme étant du type
pointeur vers une struct personne. La dernière structure de la liste
devra avoir un membre suivant dont la valeur sera le pointeur
NULL.

60
Allocation et libération d'espace pour les structures

 Allocation et libération d'espace pour les structures

Quand on crée une liste chaînée, c'est parce qu'on ne sait pas à la
compilation combien elle comportera d'éléments à l'exécution (sinon
on utiliserait un tableau). Pour pouvoir créer des listes, il est donc
nécessaire de pouvoir allouer de l'espace dynamiquement. On
dispose pour cela de deux fonctions malloc et calloc.
 La fonction malloc admet un paramètre qui est la taille en octets de
l'élément désiré et elle rend un pointeur vers l'espace alloué.
Utilisation typique :
struct personne *p ;
p = malloc(sizeof(struct personne));

61
Exemple

 Exemple de liste simplement //Ajout d’un nouvel element

chaînée : void AjoutTete (List **L, int n) {
List *c = nouv(n) ;
#include <stdio.h> c->suiv = *L;
#include <stdlib.h> *L = c ;
typedef struct List { c=NULL;
int val; }
struct List *suiv; void main () {
} List; List *lst = NULL;
//Construction d’un nouvel élément int i;
List *nouv(int n){ for(i=1;i<=5;i++){
List *c = (List *)malloc(sizeof(List)); AjoutTete (&lst, i*i);
c->val = n; if (lst==NULL)
c->suiv = NULL; printf("liste vide");
return c; else
} printf("%d\n",lst->val);
}
}

62
 9. Application

Piles et Files
Les piles

64
Pile(1)

 Ex : pile d'assiettes, pile de dossiers à traiter, …

 Une pile est une structure linéaire permettant de stocker et
de restaurer des données en n’autorisant que 4 opérations:
1. consulter le dernier élément de la pile (le sommet de la
pile)
2. tester si la pile es vide
3. empiler un élément, le mettre au sommet de la pile
==> PUSH
4. dépiler un élément (enlever l’élément au sommet)
==> POP

65
Pile(2)

 Toutes les opérations sont effectuées sur la

même extrémité; on parle de structure en
LIFO (Last In First Out)).

66
 Exemple de Pile
Empiler B
Empiler A
Empiler E Dépiler D
Empiler C
Empiler D

67
Implémentation de la structure Pile à l’aide
d’une liste chaînée(1)
// Définition du type Pile
typedef int Element; /* les éléments sont des int */
typedef struct cellule {
Element valeur;
struct cellule *suivant;
} Cellule;
typedef Cellule *Pile;
// Déclaration des fonctions gérant la pile
Pile pile_vide ();
Pile empiler ( Pile p, Element e );
Pile depiler ( Pile p );
Element sommet ( Pile p );
int est_vide ( Pile p );

68
 Implémentation de la structure Pile à l’aide
d’une liste chaînée(2)Pile empiler(Pile p, Element e) {
Pile pile_vide(void) { Cellule * pc;
return NULL;
} pc=(Cellule*)malloc(sizeof
(Cellule));
int est_vide(Pile p) { pc->valeur=e;
return (p == NULL); pc->suivant=p;
} return pc;
Element sommet(Pile p) { }
/* pré-condition: pile non Pile depiler(Pile p) {
vide ! */ Cellule * pc = p;
if (est_vide(p)) { if (est_vide(p)) {
printf("Erreur: pile vide
!\n"); printf("Erreur: pile vide!\n");
exit(-1); exit(-1);
} }
return p->valeur; p=p->suivant;
}
free(pc);
return p;
}
69
Implémentation de la structure Pile à l’aide
d’une liste chaînée(3)
//Exemple d’utilisation
int main () {
Pile p = pile_vide();

p = empiler(p,50);
p = empiler(p,5);
p = empiler(p,20);
p = empiler(p,10);
printf("%d au sommet après empilement de 50, 5, 20 et 10\n", sommet(p));
p = depiler(p);
p = depiler(p);
printf("%d au sommet après dépilement de 10 et 20\n", sommet(p));
return 0;
}

70
Les files

71
File(1)

 Ex: File d'attente à un guichet, file de documents à imprimer, …

 Une file est une structure de données dynamique dans laquelle
on insère des nouveaux éléments à la fin (queue) et où on enlève
des éléments au début (tête de file).
 L’application la plus classique est la file d’attente, et elle sert
beaucoup en simulation. Elle est aussi très utilisée aussi bien
dans la vie courante que dans les systèmes informatiques. Par
exemple, elle modélise la file d’attente des clients devant un
guichet, les travaux en attente d’exécution dans un système de
traitement par lots, ou encore les messages en attente dans un
commutateur de réseau téléphonique.

72
File(2)

 On retrouve également les files d’attente dans les

programmes de traitement de transactions telle que les
réservations de sièges d’avion ou de billets de théâtre.
 Dans une file, le premier élément inséré est aussi le
premier retiré. On parle de mode d’accès FIFO (First In
Fist Out).

 La file est modifiée à ses deux bouts.

73
File(3)

 Quatre opérations de base:

1. consulter le premier élément de la file
2. tester si la file est vide
3. enfiler un nouvel élément: le mettre en dernier
4. défiler un élément, le premier (le supprimer)

74
Implémentation de la structure File à l’aide
d’une liste chaînée(1)
// Définition du type File
typedef int Element; /* les éléments sont des int */

typedef struct cellule {

Element valeur;
struct cellule *suivant;
} Cellule;

typedef struct {
struct cellule *tete;
struct cellule *queue;
} File;

// Déclaration des fonctions gérant la file

File file_vide ();
File enfiler ( File f, Element e );
File defiler ( File f );
Element tete ( File f );
int est_vide ( File f );

75
Implémentation de la structure File à l’aide
d’une liste chaînée(2) File enfiler(File f, Element e) {
Cellule * pc;
File file_vide() { pc=(Cellule *)malloc(sizeof(Cellule));
File f; pc->valeur=e;
f.tete=f.queue=NULL; pc->suivant=NULL;
return f; if (est_vide(f)
} f.tete=f.queue=pc;
else f.queue=(f.queue)->suivant=pc;
int est_vide(File f) { return f;
return }
(f.tete==NULL)&&(f.queue==NULL);
}
File defiler(File f) {
Element tete(File f) { Cellule * pc;
/* pré-condition: file non vide ! */ if (est_vide(f)) {
if (est_vide(f)) { printf("Erreur: file vide !\n");
printf("Erreur: file vide !\n"); exit(-1);
exit(-1); }
} pc=f.tete;
return (f.tete)->valeur; f.tete=(f.tete)->suivant;
} free(pc);
if (f.tete==NULL) f.queue=NULL;
return f;
}

76